|
This article is cited in 9 scientific papers (total in 9 papers)
Positive undecidable numberings in the Ershov hierarchy
M. Manata, A. Sorbib a Al-Farabi Kazakh National University, Almaty, Kazakhstan
b Dip. Sci. Matem. Inform. "Roberto Magari", Siena, Italy
Abstract:
A sufficient condition is given under which an infinite computable family of $\Sigma_a^{-1}$-sets has computable positive but undecidable numberings, where $a$ is a notation for a nonzero computable ordinal. This extends a theorem proved by Talasbaeva in [Algebra and Logic, 42, No. 6 (2003), 737–746] for finite levels of the Ershov hierarchy. As a consequence, it is stated that the family of all $\Sigma_a^{-1}$-sets has a computable positive undecidable numbering. In addition, for every ordinal notation $a>1$, an infinite family of $\Sigma_a^{-1}$-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:
Ershov hierarchy, positive undecidable numbering.
Received: 22.03.2011
Citation:
M. Manat, A. Sorbi, “Positive undecidable numberings in the Ershov hierarchy”, Algebra Logika, 50:6 (2011), 759–780; Algebra and Logic, 50:6 (2012), 512–525
Linking options:
https://www.mathnet.ru/eng/al515 https://www.mathnet.ru/eng/al/v50/i6/p759
|
|