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.
Submission guide