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.
2012
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].
File in questo prodotto:
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.

Utilizza questo identificativo per citare o creare un link a questo documento: https://hdl.handle.net/11365/38538
 Attenzione

Attenzione! I dati visualizzati non sono stati sottoposti a validazione da parte dell'ateneo