A Friedberg numbering of the family of all sets for any given level of the Ershov hierarchy is constructed, and we also consider different consequences of this result.
Article PDF
Similar content being viewed by others
Avoid common mistakes on your manuscript.
References
R. F. Friedberg, “Three theorems on recursive enumeration. I. Decomposition. II. Maximal set. III. Enumeration without duplication,” J. Symb. Log., 23, No. 3, 309-316 (1958).
S. S. Goncharov, S. Lempp, and D. R. Solomon, “Friedberg numberings of families of n-computably enumerable sets,” Algebra and Logic, 41, No. 2, 81-86 (2002).
Yu. L. Ershov, “On a hierarchy of sets III,” Algebra and Logic, 9, No. 1, 20-31 (1970).
C. J. Ash and J. F. Knight, Computable Structures and the Hyperarithmetical Hierarchy, Stud. Logic Found. Math., 144, Elsevier, Amsterdam (2000).
S. S. Goncharov and A. Sorbi, “Generalized computable numerations and nontrivial Rogers semilattices,” Algebra and Logic, 36, No. 6, 359-369 (1997).
S. S. Ospichev, “Infinite family of Σ − 1 a -sets with only one computable numbering,” Vestnik NGU, Mat., Mekh., Inf., 11, No. 2, 89-92 (2011).
S. S. Ospichev, “Some properties of numberings in various levels in Ershov’s hierarchy,” Vestnik NGU, Mat., Mekh., Inf., 10, No. 4, 125-132 (2010).
V. L. Selivanov, “Hierarchy of limiting computations,” Sib. Math. J., 25, No. 5, 798-806 (1984).
Zh. T. Talasbaeva, “Positive numberings of families of sets in the Ershov hierarchy,” Algebra and Logic, 42, No. 6, 413-418 (2003).
S. A. Badaev, “Positive enumerations,” Sib. Math. J., 18, No. 3, 343-352 (1977).
M. Manat and A. Sorbi, “Positive undecidable numberings in the Ershov hierarchy,” Algebra and Logic, 50, No. 6, 512-525 (2011).
M. Kummer, “Numberings of ℛ1 ∪ ℱ,” in Lect. Notes Comput. Sci., 385, Springer-Verlag, Berlin (1989), pp. 166-186.
M. B. Pour-El and W. A. Howard, “A structural criterion for recursive numeration without repetition,” Z. Math. Logik Grundlagen Math., 10, No. 2, 105-114 (1964).
Author information
Authors and Affiliations
Corresponding author
Additional information
∗Supported by RFBR (project No. 14-01-00376) and by the Grants Council (under RF President) for State Aid of Leading Scientific Schools, grant NSh-860.2014.1.
Translated from Algebra i Logika, Vol. 54, No. 4, pp. 444-462, July-August, 2015.
Rights and permissions
About this article
Cite this article
Ospichev, S.S. Friedberg Numberings in the Ershov Hierarchy. Algebra Logic 54, 283–295 (2015). https://doi.org/10.1007/s10469-015-9349-2
Received:
Revised:
Published:
Issue Date:
DOI: https://doi.org/10.1007/s10469-015-9349-2