首页 | 本学科首页   官方微博 | 高级检索  
     检索      


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 等数据库收录!
设为首页 | 免责声明 | 关于勤云 | 加入收藏

Copyright©北京勤云科技发展有限公司  京ICP备09084417号