Skip to main content
SpringerLink
Log in

Friedberg numberings in the Ershov hierarchy

  • Published:
Archive for Mathematical Logic Aims and scope Submit manuscript

Abstract

We show that for every ordinal notation \({\xi}\) of a nonzero computable ordinal, there exists a \({\Sigma^{-1}_\xi}\)—computable family which up to equivalence has exactly one Friedberg numbering, which does not induce the least element in the corresponding Rogers semilattice.

This is a preview of subscription content, log in via an institution to check access.

Access this article

Log in via an institution

Price excludes VAT (USA)
Tax calculation will be finalised during checkout.

Instant access to the full article PDF.

Institutional subscriptions

Similar content being viewed by others

References

  1. Ash, C.J., Knight, J.: Computable Structures and the Hyperarithmetical Hierarchy, volume 144 of Studies in Logic and the Foundations of Mathematics. North-Holland Publishing Co., Amsterdam (2000)

  2. Badaev, S.A., Goncharov, S.S.: On computable minimal enumerations. In: Yu, L. Ershov, E.I. Khukhro, V.M. Levchuk, Podufalov, N.D. (eds.) Algebra. Proceedings of the Third International Conference on Algebra Held in Krasnoyarsk, August 23–28, 1993, De Gruyter Proceedings in Mathematics, pp. 21–32. Walter de Gruyter, Berlin (1996)

  3. Ershov Y.L.: Enumerations of families of general recursive functions. Sib. Math. J. 8(5), 771–778 (1967)

    Article  Google Scholar 

  4. Ershov, Y.L.: A hierarchy of sets, I. Algebra Logic, 7(1), 25–43 (1968) Russian

  5. Ershov Y.L.: A hierarchy of sets, II. Algebra Log. 7(4), 212–232 (1968)

    Article  Google Scholar 

  6. Ershov Y.L.: A hierarchy of sets, III. Algebra Log. 9(1), 20–31 (1970)

    Article  Google Scholar 

  7. Ershov, Y.L.: Theory of Numberings. Nauka, Moscow (1977) Russian

  8. Ershov, Y.L.: Theory of numberings. In: Griffor, E.R. (ed.) Handbook of Computability Theory, volume 140 of Studies in Logic and the Foundations of Mathematics, pp. 473–506. Elsevier Science, Amsterdam (1999)

  9. Ershov Y.L., Goncharov S.S.: Constructive Models. Siberian School of Algebra and Logic. Springer, Berlin (2000)

    Book  Google Scholar 

  10. Friedberg R.M.: Three theorems on recursive enumeration. I. Decomposition. II. Maximal set. III. Enumeration without duplication. J. Symb. Log. 23, 309–316 (1958)

    Article  MathSciNet  Google Scholar 

  11. Goncharov S.S., Sorbi A.: Generalized computable numerations and non-trivial Rogers semilattices. Algebra Log. 36(6), 359–369 (1997)

    Article  MathSciNet  Google Scholar 

  12. Goncharov S.S.: Computable single-valued numerations. Algebra Log. 19(5), 325–356 (1980)

    Article  MathSciNet  Google Scholar 

  13. Goncharov S.S.: Problem of the number of non-self-equivalent constructivizations. Algebra Log. 19(6), 401–414 (1980)

    Article  MathSciNet  Google Scholar 

  14. Goncharov, S.S.: The family with unique univalent but not the smallest enumeration. In: Trudy Inst. Matem. SO AN SSSR, Nauka, Novosibirsk, vol. 8, pp. 42–48 (1988) Russian

  15. Goncharov S.S., Lempp S., Solomon D.R.: Friedberg numberings of families of n-computably enumerable sets. Algebra Log. 41(2), 81–86 (2002)

    Article  MathSciNet  Google Scholar 

  16. Kummer M.: Some applications of computable one-one numberings. Arch. Math. Log. 30(4), 219–230 (1990)

    Article  MATH  MathSciNet  Google Scholar 

  17. Kummer M.: A learning-theoretic characterization of classes of recursive functions. Inf. Process. Lett. 54, 205–211 (1995)

    Article  MATH  MathSciNet  Google Scholar 

  18. Manat M., Sorbi A.: Positive undecidable numberings in the Ershov hierarchy. Algebra Log. 50(6), 512–525 (2012)

    Article  MATH  MathSciNet  Google Scholar 

  19. Ospichev, S.: Computable family of \({\Sigma^{-1}_a}\)-sets without Friedberg numberings. In: Ferreira, F., Guerra, H., Mayordomo, E., Rasga, J. (eds.) 6th Conference on Computability in Europe, CiE 2010, Ponta Delgada, Azores, Portugal, June/July 2010. Abstract and Handout Booklet, pp. 311–315. Centre for Applied Mathematics and Information Technology, Department of Mathematics, University of Azores (2010)

  20. Rogers H. Jr.: Theory of Recursive Functions and Effective Computability. McGraw-Hill, New York (1967)

    MATH  Google Scholar 

  21. Talasbaeva Z.T.: Positive numberings of families of sets in the Ershov hierarchy. Algebra Log. 42(6), 413–418 (2003)

    Article  MathSciNet  Google Scholar 

Download references

Author information

Author notes

  1. Mustafa Manat

    Present address: School of Physical and Mathematical Sciences, Nanyang Technological University, Singapore, 637371, Singapore

  2. Andrea Sorbi

    Present address: Department of Information Engineering and Mathematics, University of Siena, 53100, Siena, Italy

Authors and Affiliations

  1. Al-Farabi Kazakh National University, Almaty, 050038, Kazakhstan

    Serikzhan A. Badaev & Mustafa Manat

  2. Department of Mathematics and Computer Science “Roberto Magari”, University of Siena, 53100, Siena, Italy

    Andrea Sorbi

Authors
  1. Serikzhan A. Badaev
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Mustafa Manat
    View author publications

    You can also search for this author in PubMed Google Scholar

  3. Andrea Sorbi
    View author publications

    You can also search for this author in PubMed Google Scholar

Corresponding author

Correspondence to Andrea Sorbi.

Additional information

Part of the research contained in this paper was carried out while Badaev was INDAM-GNSAGA Visiting Professor at the Department of Mathematics and Computer Science “Roberto Magari” of the University of Siena, Italy, July 2011. Badaev wishes to thank INDAM-GNSAGA for supporting the visiting professorship. Manat is currently supported by research Grant MOE2011-T2-1-071 from Ministry of Education of Singapore. Part of the research contained in this paper was carried out while Manat was visiting the Department of Mathematics and Computer Science “Roberto Magari” of the University of Siena, Italy. Manat wishes to thank the Al-Farabi University for supporting the visit, and the Department of Mathematics and Computer Science “Roberto Magari” for its hospitality. Sorbi is a member of INDAM-GNSAGA.

Rights and permissions

Reprints and permissions

About this article

Check for updates. Verify currency and authenticity via CrossMark

Cite this article

Badaev, S.A., Manat, M. & Sorbi, A. Friedberg numberings in the Ershov hierarchy. Arch. Math. Logic 54, 59–73 (2015). https://doi.org/10.1007/s00153-014-0402-y

Download citation

  • Received:

  • Accepted:

  • Published:

  • Issue Date:

  • DOI: https://doi.org/10.1007/s00153-014-0402-y

Keywords

Mathematics Subject Classification

Search

Navigation