Skip to main content
SpringerLink
Log in

Decomposability of low 2-computably enumerable degrees and turing jumps in the Ershov hierarchy

  • Published:
Russian Mathematics Aims and scope Submit manuscript

Abstract

In this paper we prove the following theorem: For every notation of a constructive ordinal there exists a low 2-computably enumerable degree that is not splittable into two lower 2-computably enumerable degrees whose jumps belong to the corresponding Δ-level of the Ershov hierarchy.

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. Yu. L. Ershov, “A Hierarchy of Sets. I”, Algebra i Logika 7(1), 47–74 (1968).

    MATH  MathSciNet  Google Scholar 

  2. Yu. L. Ershov, “A Hierarchy of Sets. II”, Algebra i Logika 7(4), 15–47 (1968).

    MATH  MathSciNet  Google Scholar 

  3. Yu. L. Ershov, “A Hierarchy of Sets. III”, Algebra i Logika 9(1), 34–51 (1970).

    MathSciNet  Google Scholar 

  4. M. M. Arslanov, The Ershov Hierarchy (Kazansk. Gos. Univ., Kazan, 2007) [in Russian].

    Google Scholar 

  5. M. M. Arslanov, “Structural Properties of the Degrees below 0′,” Izv. Vyssh. Uchebn. Zaved. Mat., No. 7, 27–33 (1988) [Soviet Mathmatics (Izv. VUZ) 32 (7), 25–31 (1988).

  6. R. G. Downey, “D. R. E. Degrees and the Nondiamond Theorem,” Bull. Lond. Math. Soc. 21, 43–50 (1989).

    Article  MATH  MathSciNet  Google Scholar 

  7. A. H. Lachlan, “Lower Bounds for Pairs of Recursively Enumerable Degrees,” Proc. Lond. Math. Soc., III Ser. 16, 537–569 (1966).

    Article  MATH  MathSciNet  Google Scholar 

  8. S. B. Cooper, L. Harrington, A. H. Lachlan, S. Lempp, and R. I. Soare, “The D. R. E. Degrees Are Not Dense,” Ann. Pure Appl. Logic 55(2), 125–151 (1991).

    Article  MATH  MathSciNet  Google Scholar 

  9. G. E. Sacks, “The Recursively Enumerable Degrees Are Dense,” Ann. Math. 80(2), 300–312 (1964).

    Article  MathSciNet  Google Scholar 

  10. M. Arslanov, S. B. Cooper, and A. Li, “There Is No Low Maximal D. C. E. Degree,” Math. Log. Q. 46(3), 409–416 (2000); corrigendum ibid. 50 (6), 628–636 (2004).

    Article  MATH  MathSciNet  Google Scholar 

  11. L. Welch, “A Hierarchy of Families of Recursively Enumerable Degrees and a Theorem of Founding Minimal Pairs,” Ph. D. Thesis (University of Illinois, Urbana, 1980).

    Google Scholar 

Download references

Author information

Authors and Affiliations

  1. Kazan State University, 18 Kremlevskaya str, Kazan, 420008, Russia

    M. Kh. Faizrakhmanov

Authors
  1. M. Kh. Faizrakhmanov
    View author publications

    You can also search for this author in PubMed Google Scholar

Corresponding author

Correspondence to M. Kh. Faizrakhmanov.

Additional information

Original Russian Text © M.Kh. Faizrakhmanov, 2010, published in Izvestiya Vysshikh Uchebnykh Zavedenii. Matematika, 2010, No. 12, pp. 58–66.

About this article

Cite this article

Faizrakhmanov, M.K. Decomposability of low 2-computably enumerable degrees and turing jumps in the Ershov hierarchy. Russ Math. 54, 51–58 (2010). https://doi.org/10.3103/S1066369X10120066

Download citation

  • Received:

  • Published:

  • Issue Date:

  • DOI: https://doi.org/10.3103/S1066369X10120066

Key words and phrases

Search

Navigation