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

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