[go: up one dir, main page]
More Web Proxy on the site http://driver.im/ Skip to main content
Springer Nature Link
Log in

There exists a maximal 3-C.E. enumeration degree

  • Published:
Israel Journal of Mathematics Aims and scope Submit manuscript

    We’re sorry, something doesn't seem to be working properly.

    Please try refreshing the page. If that doesn't work, please contact support so we can address the problem.

Abstract

We construct an incomplete 3-c.e. enumeration degree which is maximal among then-c.e. enumeration degrees for everyn with 3≤n≤ω. Consequently then-c.e. enumeration degrees are not dense for any suchn. We show also that no lown-c.e. e-degree can be maximal among then-c.e. e-degrees, for 2≤n≤ω.

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

Access this article

Log in via an institution

Subscribe and save

Springer+ Basic
£29.99 /Month
  • Get 10 units per month
  • Download Article/Chapter or eBook
  • 1 Unit = 1 Article or 1 Chapter
  • Cancel anytime
Subscribe now

Buy Now

Price includes VAT (United Kingdom)

Instant access to the full article PDF.

Institutional subscriptions

Similar content being viewed by others

References

  1. M. M. Arslanov,Open questions about the n-c.e. degrees, inComputability Theory and Its Applications: Current Trends and Open Problems (M. Lerman P. Cholak, S. Lempp and R. A. Shore, eds.), Contemporary Mathematics257 (2000), 15–22.

  2. M. M. Arslanov, I. Kalimullin and A. Sorbi,Density results in the Δ2/0e-degrees, Archive for Mathematical Logic40 (2001), 597–614.

    Article  MATH  MathSciNet  Google Scholar 

  3. W. C. Calhoun and T. A. Slaman,The Π2/0enumeration degrees are not dense, Journal of Symbolic Logic61 (1996), 1364–1379.

    Article  MATH  MathSciNet  Google Scholar 

  4. S. B. Cooper,Partial degrees and the density problem, Journal of Symbolic Logic47 (1982), 854–859.

    Article  MATH  MathSciNet  Google Scholar 

  5. S. B. Cooper,Partial degrees and the density problem. II. The enumeration degrees of the Σ2 sets are dense, Journal of Symbolic Logic49 (1984), 503–513.

    Article  MATH  MathSciNet  Google Scholar 

  6. S. B. Cooper,Enumeration reducibility, nondeterministic computations and relative computability of partial functions, inRecursion Theory Week, Oberwolfach 1989 (K. Ambos-Spies, G. Müller and Gerald E. Sacks, eds.), Lecture Notes in Mathematics1432, Springer-Verlag, Heidelberg, 1990, pp. 57–110.

    Chapter  Google Scholar 

  7. S. B. Cooper, L. Harrington, A. H. Lachlan, S. Lempp and R. I. Soare,The d.r.e. degrees are not dense, Annals of Pure and Applied Logic55 (1991), 125–151.

    Article  MATH  MathSciNet  Google Scholar 

  8. R. L. Epstein, R. Haas and R. L. Kramer,Hierarchies of sets and degrees below 0′, inLogic Year 1979–80, Lecture Notes in Mathematics859, Springer-Verlag, Heidelberg, 1981, pp. 32–48.

    Chapter  Google Scholar 

  9. Yu. L. Ershov,A hierarchy of sets, I, Algebra i Logika7 (1968), 47–74; English Translation: Consultants Bureau, New York, pp. 25–43.

    MATH  MathSciNet  Google Scholar 

  10. Yu. L. Ershov,A hierarchy of sets, II, Algebra i Logika7 (1968.), 15–47; English Translation, Consultants Bureau, New York, pp. 212–232.

    MATH  MathSciNet  Google Scholar 

  11. Yu. L. Ershov,A hierarchy of sets, III, Algebra i Logika9(1) (1970), 34–51; English Translation: Consultants Bureau, New York, pp. 20–31.

    MathSciNet  Google Scholar 

  12. R. M. Friedberg and H. Rogers, Jr,Reducibility and completeness for sets of integers, Zeitschrift fur Mathematische Logik und Grundlagen der Mathematik5 (1959), 117–125.

    Article  MATH  MathSciNet  Google Scholar 

  13. L. Gutteridge,Some Results on Enumeration Reducibility, PhD thesis, Simon Fraser University, 1971.

  14. I. Kalimullin,Splitting properties of n-c. e. enumeration degrees, Journal of Symbolic Logic67 (2002), 537–546.

    Article  MATH  MathSciNet  Google Scholar 

  15. A. H. Lachlan and R. A. Shore,The n-rea enumeration degrees are dense, Archive for Mathematical Logic31 (1992), 277–285.

    Article  MATH  MathSciNet  Google Scholar 

  16. K. McEvoy and S. B. Cooper,On minimal pairs of enumeration degrees, Journal of Symbolic Logic50 (1985), 983–1001.

    Article  MATH  MathSciNet  Google Scholar 

  17. J. Myhill,A note on degrees of partial functions, Proceedings of the American Mathematical Society12 (1961), 519–521.

    Article  MATH  MathSciNet  Google Scholar 

  18. H. Putnam,Trial and error predicates and the solution to a problem of Mostowski, Journal of Symbolic Logic30 (1965), 49–57.

    Article  MATH  MathSciNet  Google Scholar 

  19. H. Rogers, Jr,Computing degrees of unsolvability, Mathematische Annalen138 (1959), 125–140.

    Article  MathSciNet  Google Scholar 

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

    MATH  Google Scholar 

  21. G. E. Sacks,A minimal degree below 0′, Bulletin of the American Mathematical Society67 (1961), 416–419.

    Article  MATH  MathSciNet  Google Scholar 

  22. G. E. Sacks,The recursively enumerable degrees are dense, Annals of Mathematics80 (1964), 300–312.

    Article  MathSciNet  Google Scholar 

  23. C. Spector,On the degrees of recursive unsolvability, Annals of Mathematics64 (1956), 581–592.

    Article  MathSciNet  Google Scholar 

Download references

Author information

Authors and Affiliations

  1. Department of Pure Mathematics, School of Mathematics, University of Leeds, LS2 9JT, Leeds, U.K.

    S. Barry Cooper

  2. Institute of Software, Academia Sinica, 100080, Beijing, China

    Angsheng Li

  3. Dipartimento di Scienze Matematiche ed Informatiche “Roberto Magari”, Via del Capitano 15, 53100, Siena, Italy

    Andrea Sorbi

  4. Department of Mathematics, Faculty of Science, National University of Singapore, Lower Kent Ridge Road, 119260, Singapore

    Yue Yang

Authors
  1. S. Barry Cooper
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Angsheng Li
    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

  4. Yue Yang
    View author publications

    You can also search for this author in PubMed Google Scholar

Additional information

The first two authors were partially supported by EPSRC Research Grant “Turing Definability” No. GR/M 91419 (UK), and the second author by NSF grant No. 69973048 and by NSF major grant No. 19931020 (P. R. China), and by an INDAM visiting professorship at the University of Siena. The fourth author was partially supported as a visiting scholar by the University of Siena. The first three authors were funded by the INTAS-RFBR joint projectComputability and Models, no. 972-139. The fourth authors would like to thank Marat Arslanov for useful discussions.

Rights and permissions

Reprints and permissions

About this article

Cite this article

Cooper, S.B., Li, A., Sorbi, A. et al. There exists a maximal 3-C.E. enumeration degree. Isr. J. Math. 137, 285–320 (2003). https://doi.org/10.1007/BF02785966

Download citation

  • Received:

  • Issue Date:

  • DOI: https://doi.org/10.1007/BF02785966

Keywords

Search

Navigation