A sufficient condition is given under which an infinite computable family of $\Sigma^{-1}_a$ sets has computable positive but undecidable numberings, where $a$ is a notation for a nonzero computable ordinal. This extends a theorem previously proved for finite levels of the Ershov hierarchy by Talasbaeva. As a consequence, it is stated that the family of all $\Sigma^{-1}_a$-sets has a computable positive undecidable numbering. In addition, for every ordinal notation $a > 1$, an infinite family of $\Sigma^{-1}_a$-sets is constructed which possesses a computable positive numbering but has no computable Friedberg numberings. This answers the question of whether such families exist at any —finite or infinite— level of the Ershov hierarchy, which was originally raised by Badaev and Goncharov only for the finite levels bigger than $1$.
Manat, M., Sorbi, A. (2012). Positive undecidable numberings in the Ershov hierarchy. ALGEBRA AND LOGIC, 50(6), 512-525 [10.1007/s10469-012-9162-0].
Positive undecidable numberings in the Ershov hierarchy
SORBI, ANDREA
2012-01-01
Abstract
A sufficient condition is given under which an infinite computable family of $\Sigma^{-1}_a$ sets has computable positive but undecidable numberings, where $a$ is a notation for a nonzero computable ordinal. This extends a theorem previously proved for finite levels of the Ershov hierarchy by Talasbaeva. As a consequence, it is stated that the family of all $\Sigma^{-1}_a$-sets has a computable positive undecidable numbering. In addition, for every ordinal notation $a > 1$, an infinite family of $\Sigma^{-1}_a$-sets is constructed which possesses a computable positive numbering but has no computable Friedberg numberings. This answers the question of whether such families exist at any —finite or infinite— level of the Ershov hierarchy, which was originally raised by Badaev and Goncharov only for the finite levels bigger than $1$.File | Dimensione | Formato | |
---|---|---|---|
positive-Ershov.pdf
non disponibili
Descrizione: Articolo unico
Tipologia:
PDF editoriale
Licenza:
NON PUBBLICO - Accesso privato/ristretto
Dimensione
818.2 kB
Formato
Adobe PDF
|
818.2 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/35931