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 -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 -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 -computable family of cardinality n, whose Rogers semilattice consists of exactly one element.
| Original language | English |
|---|---|
| Pages (from-to) | 366-376 |
| Number of pages | 11 |
| Journal | Mathematical Logic Quarterly |
| Volume | 58 |
| Issue number | 4-5 |
| DOIs | |
| Publication status | Published - Aug 2012 |
| Externally published | Yes |
Fingerprint
Keywords
- Computable numbering
- Computable ordinal
- Ershov's hierarchy
- Ordinal notation
- Rogers semilattice
ASJC Scopus subject areas
- Logic
Cite this
Rogers semilattices of families of two embedded sets in the Ershov hierarchy. / Badaev, Serikzhan A.; Manat, Mustafa; Sorbi, Andrea.
In: Mathematical Logic Quarterly, Vol. 58, No. 4-5, 08.2012, p. 366-376.Research output: Contribution to journal › Article
}
TY - JOUR
T1 - Rogers semilattices of families of two embedded sets in the Ershov hierarchy
AU - Badaev, Serikzhan A.
AU - Manat, Mustafa
AU - Sorbi, Andrea
PY - 2012/8
Y1 - 2012/8
N2 - Let a be a Kleene's ordinal notation of a nonzero computable ordinal. We give a sufficient condition on a, so that for every -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 -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 -computable family of cardinality n, whose Rogers semilattice consists of exactly one element.
AB - Let a be a Kleene's ordinal notation of a nonzero computable ordinal. We give a sufficient condition on a, so that for every -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 -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 -computable family of cardinality n, whose Rogers semilattice consists of exactly one element.
KW - Computable numbering
KW - Computable ordinal
KW - Ershov's hierarchy
KW - Ordinal notation
KW - Rogers semilattice
UR - http://www.scopus.com/inward/record.url?scp=84864767814&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=84864767814&partnerID=8YFLogxK
U2 - 10.1002/malq.201100114
DO - 10.1002/malq.201100114
M3 - Article
AN - SCOPUS:84864767814
VL - 58
SP - 366
EP - 376
JO - Mathematical Logic Quarterly
JF - Mathematical Logic Quarterly
SN - 0942-5616
IS - 4-5
ER -