Let $a$ be a Kleene's ordinal notation of a nonzero computable ordinal. We give a sufficient condition on $a$, so that for every $\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 $\omega$; 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 $\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 $\omega + \omega$; 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\in\omega$, or $n=\omega$, and every notation of a nonzero ordinal there exists a $\Sigma^{-1}_a$--computable family of cardinality $n$, whose Rogers semilattice consists of exactly one element.
Badaev, S.A., Manat, M., Sorbi, A. (2012). Rogers semilattices of families of two embedded sets in the Ershov hierarchy. MATHEMATICAL LOGIC QUARTERLY, 58(4-5), 366-376 [10.1002/malq.201100114].
Rogers semilattices of families of two embedded sets in the Ershov hierarchy
SORBI, ANDREA
2012-01-01
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 $\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 $\omega$; 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 $\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 $\omega + \omega$; 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\in\omega$, or $n=\omega$, and every notation of a nonzero ordinal there exists a $\Sigma^{-1}_a$--computable family of cardinality $n$, whose Rogers semilattice consists of exactly one element.File | Dimensione | Formato | |
---|---|---|---|
malq201100114.pdf
non disponibili
Tipologia:
Post-print
Licenza:
NON PUBBLICO - Accesso privato/ristretto
Dimensione
855.83 kB
Formato
Adobe PDF
|
855.83 kB | Adobe PDF | Visualizza/Apri Richiedi una copia |
I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.
https://hdl.handle.net/11365/38538
Attenzione
Attenzione! I dati visualizzati non sono stati sottoposti a validazione da parte dell'ateneo