Positive undecidable numberings in the Ershov hierarchy
Loading...
Date
2012
Authors
Mustafa, M.
Sorbi, Andrea
Journal Title
Journal ISSN
Volume Title
Publisher
Abstract
We give a su cient condition for an in nite computable family of 1
a sets, to have computable positive but undecidable numberings, where a
is a notation for a nonzero computable ordinal. This extends a theorem
proved by Talasbaeva for the nite levels of the Ershov hierarchy. In par-
ticular the family of all 1 a sets has positive undecidable numberings: this
veri es for all levels of the Ershov hierarchy a conjecture due to Badaev
and Goncharov. We point out also that for every ordinal notation a of a
nonzero ordinal, there are families of 1 a sets having positive numberings,
but no Friedberg numberings: this answers for all levels (whether nite
or in nite) of the Ershov hierarchy, a question originally raised, only for
the nite levels over level 1, by Badaev and Goncharov.
Description
Keywords
Research Subject Categories::MATHEMATICS, numbering
Citation
Mustafa Manat, Sorbi Andrea; 2012; Positive undecidable numberings in the Ershov hierarchy