Rogers semilattices of families of two embedded sets in the Ershov hierarchy
- 12 July 2012
- journal article
- research article
- Published by Wiley in Mathematical Logic Quarterly
- Vol. 58 (4-5) , 366-376
Abstract
Let a be a Kleene's ordinal notation of a nonzero computable ordinal. We give a sufficient condition on a, so that for every \documentclass{article}\usepackage{amssymb}\pagestyle{empty}$\Sigma ^{-1}_a$ ‐computable family of two embedded sets, i.e., two sets A, B, with A properly contained in B, the Rogers semilattice of the family is infinite. This condition is satisfied by every notation of ω; moreover every nonzero computable ordinal that is not sum of any two smaller ordinals has a notation that satisfies this condition. On the other hand, we also give a sufficient condition on a, that yields that there is a \documentclass{article}\usepackage{amssymb}\pagestyle{empty}$\Sigma ^{-1}_a$ ‐computable family of two embedded sets, whose Rogers semilattice consists of exactly one element; this condition is satisfied by all notations of every successor ordinal bigger than 1, and by all notations of the ordinal ω + ω; moreover every computable ordinal that is sum of two smaller ordinals has a notation that satisfies this condition. We also show that for every nonzero n ∈ ω, or n = ω, and every notation a of a nonzero ordinal there exists a \documentclass{article}\usepackage{amssymb}\pagestyle{empty}$\Sigma ^{-1}_a$ ‐computable family of cardinality n, whose Rogers semilattice consists of exactly one element.Keywords
This publication has 5 references indexed in Scilit:
- The Ershov Hierarchy2011
- COMPUTABLE NUMBERINGS IN THE HIERARCHY OF ERSHOV2006
- Generalized computable numerations and nontrivial rogers semilatticesAlgebra and Logic, 1997
- On a hierarchy of sets, IIAlgebra and Logic, 1968
- A hierarchy of sets. IAlgebra and Logic, 1968