Rogers semilattices of families of two embedded sets in the Ershov hierarchy
No Thumbnail Available
Date
2012
Authors
Badaev, Serikzhan A.
Mustafa, M.
Journal Title
Journal ISSN
Volume Title
Publisher
Abstract
Let a be a Kleene's ordinal notation of a nonzero computable ordinal. We give a su cient condition on a, so that for every 1 a {computable family of two embedded sets, i.e. two sets A;B, with A properly contined in B, the Rogers semilattice of the family is in nite. This condition is satis ed by every notation of !; moreover every nonzero computable ordinal that is not sum of any two smaller ordinals has a notation that satis es this condition. On the other hand, we also give a su cient condition on a,
that yields that there is a 1 a {computable family of two embedded sets,
whose Rogers semilattice consists of exactly one element; this condition is
satis ed 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 satis es this condition.
We also show that for every nonzero n 2 !, or n = !, and every notation
of a nonzero ordinal there exists a 1 a {computable family of cardinality
n, whose Rogers semilattice consists of exactly one element.
Description
Keywords
Research Subject Categories::MATHEMATICS, Ershov hierarchy
Citation
Badaev Serikzhan A., Mustafa M.; 2012; Rogers semilattices of families of two embedded sets in the Ershov hierarchy