### 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

*Algebra and Logic*,

*50*(6), 512-525. https://doi.org/10.1007/s10469-012-9162-0

**Positive undecidable numberings in the Ershov hierarchy.** / Manat, M.; Sorbi, A.

Research output: Contribution to journal › Article

*Algebra and Logic*, vol. 50, no. 6, pp. 512-525. https://doi.org/10.1007/s10469-012-9162-0

}

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 -