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
N1 - Copyright:
Copyright 2012 Elsevier B.V., All rights reserved.
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 -