Abstract
A sufficient condition is given under which an infinite computable family of Σ -1 a -sets has computable positive but undecidable numberings, where a is a notation for a nonzero computable ordinal. This extends a theorem proved for finite levels of the Ershov hierarchy in [1]. As a consequence, it is stated that the family of all Σ -1 a -sets has a computable positive undecidable numbering. In addition, for every ordinal notation a > 1, an infinite family of Σ -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.
| Original language | English |
|---|---|
| Pages (from-to) | 512-525 |
| Number of pages | 14 |
| Journal | Algebra and Logic |
| Volume | 50 |
| Issue number | 6 |
| DOIs | |
| Publication status | Published - Jan 2012 |
| Externally published | Yes |
Fingerprint
Keywords
- Ershov hierarchy
- positive undecidable numbering
ASJC Scopus subject areas
- Analysis
- Logic
Cite this
Positive undecidable numberings in the Ershov hierarchy. / Manat, M.; Sorbi, A.
In: Algebra and Logic, Vol. 50, No. 6, 01.2012, p. 512-525.Research output: Contribution to journal › Article
}
TY - JOUR
T1 - Positive undecidable numberings in the Ershov hierarchy
AU - Manat, M.
AU - Sorbi, A.
PY - 2012/1
Y1 - 2012/1
N2 - A sufficient condition is given under which an infinite computable family of Σ -1 a -sets has computable positive but undecidable numberings, where a is a notation for a nonzero computable ordinal. This extends a theorem proved for finite levels of the Ershov hierarchy in [1]. As a consequence, it is stated that the family of all Σ -1 a -sets has a computable positive undecidable numbering. In addition, for every ordinal notation a > 1, an infinite family of Σ -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.
AB - A sufficient condition is given under which an infinite computable family of Σ -1 a -sets has computable positive but undecidable numberings, where a is a notation for a nonzero computable ordinal. This extends a theorem proved for finite levels of the Ershov hierarchy in [1]. As a consequence, it is stated that the family of all Σ -1 a -sets has a computable positive undecidable numbering. In addition, for every ordinal notation a > 1, an infinite family of Σ -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.
KW - Ershov hierarchy
KW - positive undecidable numbering
UR - http://www.scopus.com/inward/record.url?scp=84858746672&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=84858746672&partnerID=8YFLogxK
U2 - 10.1007/s10469-012-9162-0
DO - 10.1007/s10469-012-9162-0
M3 - Article
AN - SCOPUS:84858746672
VL - 50
SP - 512
EP - 525
JO - Algebra and Logic
JF - Algebra and Logic
SN - 0002-5232
IS - 6
ER -