Positive undecidable numberings in the Ershov hierarchy |
| |
Authors: | M Manat A Sorbi |
| |
Institution: | 1. Al-Farabi Kazakh National University, Al-Farabi ave. 71, Alma-Ata, 050038, Kazakhstan 2. Dipartimento di Scienze Matematiche ed Informatiche ‘Roberto Magari’, Pian del Mantellini 44, 53100, Siena, Italy
|
| |
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. |
| |
Keywords: | |
本文献已被 SpringerLink 等数据库收录! |
|