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

Definable Relations on the Computably Enumerable Degrees

  • Chapter
Computability and Models

Part of the book series: The University Series in Mathematics ((USMA))

  • 438 Accesses

Abstract

We review recent developments in the study of definable relations on the computably enumerable (c.e.) degrees, including the following aspects:

  1. (1)

    Structure and hierarchies

  2. (2)

    Definable relations

  3. (3)

    Continuity in the c.e. degrees

  4. (4)

    Automorphisms

  5. (5)

    Defining ε in εn

The author was partially supported by an EPSRC Research Grant, “Turing Definability”, No. GR/M 91419 (UK) and by NSF Grant No. 69973048 and NSF Major Grant No. 19931020 (P. R. CHINA). I am grateful to Barry Cooper for help, encouragement and suggestions during the preparation of this paper. Thanks to Yue Yang for helpful comments on the preliminary draft of the paper.

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

Access this chapter

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

Chapter
GBP 19.95
Price includes VAT (United Kingdom)
  • Available as PDF
  • Read on any device
  • Instant download
  • Own it forever
eBook
GBP 71.50
Price includes VAT (United Kingdom)
  • Available as PDF
  • Read on any device
  • Instant download
  • Own it forever
Softcover Book
GBP 89.99
Price includes VAT (United Kingdom)
  • Compact, lightweight edition
  • Dispatched in 3 to 5 business days
  • Free shipping worldwide - see info
Hardcover Book
GBP 89.99
Price includes VAT (United Kingdom)
  • Durable hardcover edition
  • Dispatched in 3 to 5 business days
  • Free shipping worldwide - see info

Tax calculation will be finalised at checkout

Purchases are for personal use only

Institutional subscriptions

Preview

Unable to display preview. Download preview PDF.

Unable to display preview. Download preview PDF.

Similar content being viewed by others

References

  1. K. Ambos-Spies [1984a], On pairs of recursively enumerable degrees, Trans. Amer. Math. Soc. 283 (1984), 507–537.

    Article  MathSciNet  MATH  Google Scholar 

  2. K. Ambos-Spies [1984b], An extension of the non-diamond theorem in classical and α-recursion theory, J. Symbolic Logic 49, 586–607.

    Article  MathSciNet  MATH  Google Scholar 

  3. K. Ambos-Spies [1993], Automorphism bases for the recursively enumerable degrees, preprint.

    Google Scholar 

  4. K. Ambos-Spies, C. G. Jockusch, Jr., R. A. Shore and R. I. Soare [1984], An algebraic decomposition of the recursively enumerable degrees and the coincidence of several degree classes with the promptly simple degrees, Trans. Amer. Math. Soc. 281 (1984), 109–128.

    Article  MathSciNet  MATH  Google Scholar 

  5. K. Ambos-Spies, A. H. Lachlan and R. I. Soare [1993], The continuity of cupping to 0′, Annals of Pure and Applied Logic 64 (1993) 195–209.

    Article  MathSciNet  MATH  Google Scholar 

  6. M. M. Arslanov [1985], Structural properties of the degrees below 0′, Dokl. Akad. Nauk. SSSR 283, 270–273.

    MathSciNet  Google Scholar 

  7. M. M. Arslanov, S. B. Cooper and A. Li [2000], There is no low maximal d.c.e. degree, Math. Log. Quart. 46 (2000) 3, 409–416.

    Article  MathSciNet  MATH  Google Scholar 

  8. M. M. Arslanov, G. L. LaForte and T. A. Slaman [1998], Relative enumerability in the difference hierarchy, J. Symb. Logic 63, 411–420.

    Article  MathSciNet  MATH  Google Scholar 

  9. M. Bickford and C. F. Mills, Lowness properties, to appear.

    Google Scholar 

  10. P. Cholak, R. Downey and S. Walk [ta], Maximal contiguous degrees, to appear in J. Symbolic Logic.

    Google Scholar 

  11. P. Cholak, M. Groszek and T. A. Slaman [2001], An almost deep degree, J. Symbolic Logic, 66 (2001), No. 2, 881–901.

    Article  MathSciNet  MATH  Google Scholar 

  12. S. B. Cooper [1972], Jump equivalence of the \( \Delta_2^0 \) hyperhyperimmune sets, J. Symbolic Logic 37(1972) 598–600.

    Article  MathSciNet  MATH  Google Scholar 

  13. S. B. Cooper [1974a], Minimal pairs and high recursively enumerable degrees, J. Symbolic Logic 39 (1974), 655–660.

    Article  MathSciNet  Google Scholar 

  14. S. B. Cooper [1974b], On a theorem of C.E.M. Yates, handwritten notes, 1974.

    Google Scholar 

  15. S. B. Cooper [1991], The density of the Low2 n-r.e. degrees, Archive for Math. Logic 31, 19–24.

    Article  MATH  Google Scholar 

  16. S. B. Cooper [1992], A splitting theorem for the n-r.e. degrees, Proc. Amer. Math. Soc. 115 (2), 461–471.

    MathSciNet  MATH  Google Scholar 

  17. S. B. Cooper [1997], Beyond Gödel’s theorem- the failure to capture information content, in Complexity, Logic and Recursion Theory (ed. A. Sorbi), Lecture Notes in Pure and Applied Mathematics, Vol. 187, Marcel Dekker, New York, 1997, pp. 93–122.

    Google Scholar 

  18. S. B. Cooper [1999], Local degree theory, in Handbook of Computability Theory (ed. Edward R. Griffor), Studies in Logic, Vol. 140, Amsterdam, Laussanne, New York, Oxford, Shannon, Singapore, Tokyo, 1999.

    Google Scholar 

  19. S. B. Cooper, L. Harrington, A. H. Lachlan, S. Lempp and R. I. Soare [1991], The d-r.e. degrees are not dense, Ann. Pure and Appl. Log. 55 (2), 125–151.

    Article  MathSciNet  MATH  Google Scholar 

  20. S. B. Cooper, S. Lempp and P. Watson [1989], Week density and cupping in the d-r.e. degrees, Israel J. Math. 67, (1989), 137–152.

    MathSciNet  MATH  Google Scholar 

  21. S. B. Cooper and A. Li [tal], Splitting and Nonsplitting, I: A low3 Harrington Nonsplitting Base, to appear.

    Google Scholar 

  22. S. B. Cooper and A. Li [ta2], Splitting and Nonsplitting, II: A Low2 c.e. degree above which 0′ is not splittable, to appear.

    Google Scholar 

  23. S. B. Cooper and A. Li [ta3], On Lachlan’s Major Subdegree Problem, to appear.

    Google Scholar 

  24. S. B. Cooper and A. Li [ta4], Non-uniformity and generalised Sacks splitting, to appear in Acta Mathematica Sinica.

    Google Scholar 

  25. S. B. Cooper and A. Li [ta5], Turing definability in the Ershov hierarchy, Journal of London Mathematical Society, to appear.

    Google Scholar 

  26. S. B. Cooper and A. Li [ta6], Splitting and cone avoidance in the d.c.e. degrees, to appear.

    Google Scholar 

  27. S. B. Cooper, A. Li and X. Yi [ta], On the distribution of Lachlan nonsplitting bases, Archive for Mathematical Logic, To appear.

    Google Scholar 

  28. S. B. Cooper and T. A. Slaman [1988], Major subdegrees and cup classes, Recursive Function Theory Newsletter, Item 371, Issue No. 37, February 1988.

    Google Scholar 

  29. S. B. Cooper and X. Yi, Isolated d.r.e. degrees, unpublished.

    Google Scholar 

  30. D. Ding, H. Lu and L. Qian [2000], A splitting with infimum in the d.c.e. degrees, Math. Log. Quart. 46 (2000) 1, 53–76.

    Article  MathSciNet  MATH  Google Scholar 

  31. D. Ding and L. Yu [ta], To appear.

    Google Scholar 

  32. R. Downey [1989], D.r.e. degrees and the nondiamond theorem, Bull. London Math. Soc. 21, 43–50.

    Article  MathSciNet  MATH  Google Scholar 

  33. R. G. Downey, S. Lempp and R. A. Shore [1993], Highness and bounding minimal pairs, Math. Logic Quarterly, Vol. 39, pp 475–491.

    Article  MathSciNet  MATH  Google Scholar 

  34. R. M. Friedberg, Two recursively enumerable sets of incomparable degrees of unsolvability, Proc. Natl. Acad. Sci. SUA 43 (1957), 236–238.

    Article  MathSciNet  MATH  Google Scholar 

  35. M. B. Giorgi [2001], Continuity properties of degree structures, PhD dissertation, University of Leeds, 2001.

    Google Scholar 

  36. L. Harrington [1976], On Cooper’s proof of a theorem of Yates, Part I, (handwritten notes), 1976.

    Google Scholar 

  37. L. Harrington [1978], Plus cupping in the recursively enumerable degrees (handwritten notes).

    Google Scholar 

  38. L. Harrington [1980], Understanding Lachlan’s monster paper (handwritten notes), 1980.

    Google Scholar 

  39. L. Harrington and R. I. Soare [1989], Games in recursion theory and continuity properties of capping degrees, in Proceedings of the workshop on set theory and the continuum, Oct. 16–20, 1989, Mathematical Sciences Research Institute, Berkeley.

    Google Scholar 

  40. S. Ishmukhametov [1996], Splitting above r.e. degrees, Fundamental Mathematics and Mechanics, 1996, Ulynovsk University Press, Vol. 1, 139–143.

    Google Scholar 

  41. Z. Jiang [1993], Diamond lattice embedded into d.r.e. degrees, Science in China (Series A) 36, 803–811.

    MATH  Google Scholar 

  42. C. G. Jockusch, Jr., A. Li and Y. Yang [ta], A join theorem for the computably enumerable degrees, to appear.

    Google Scholar 

  43. C. G. Jockusch and R. A. Shore [1983], Pseudo jump operators I: The R.E. case, Trans. Amer. Math. Soc. 275 (1983), 599–609.

    MathSciNet  MATH  Google Scholar 

  44. A. H. Lachlan [1966], Lower bounds for pairs of recursively enumerable degrees, Proc. London Math. Soc. 16 (1966), 537–569.

    MathSciNet  MATH  Google Scholar 

  45. A. H. Lachlan [1968], On the lattice of recursively enumerable sets, Trans. Amer. Math. Soc. 130 (1968), 1–37.

    Article  MathSciNet  MATH  Google Scholar 

  46. A. H. Lachlan [1975], A recursively enumerable degree which will not split over all lesser ones, Ann. Math. Logic 9 (1975), 307–365.

    Article  MathSciNet  MATH  Google Scholar 

  47. A. H. Lachlan [1979], Bounding minimal pairs, J. Symbolic Logic 44 (1979), 626–642.

    Article  MathSciNet  MATH  Google Scholar 

  48. S. Lempp [1988], A high strongly noncappable degree, J. Symbolic Logic.

    Google Scholar 

  49. S. Lempp, A. Nies and T. A. Slaman [1998], The II3-theory of the enumerable Turing degrees is undecidable, Trans. Amer. Math. Soc. 350, 2719–2736.

    Article  MathSciNet  MATH  Google Scholar 

  50. S. Lempp and T. A. Slaman [1989], A limit on relative genericity in the recursively enumerable sets, J. Symbolic Logic, 54 (1989), No. 2 376–395.

    Article  MathSciNet  MATH  Google Scholar 

  51. A. Li [2000a], On a Conjecture of Lempp, Archive for Mathematical Logic (2000) 39: 281–309.

    Article  MathSciNet  MATH  Google Scholar 

  52. A. Li [2000b], Bounding cappable degrees, Archive of Mathematical Logic (2000) 39: 311–352.

    Article  MATH  Google Scholar 

  53. A. Li [tal], Elementary differences among jump hierarchies, to appear.

    Google Scholar 

  54. A. Li [ta2], A hierarchy characterisation of cuppable degrees, to appear.

    Google Scholar 

  55. A. Li, T. A. Slaman and Y. Yang [ta], A nonlow2 c.e. degree which bounds no diamond bases, to appear.

    Google Scholar 

  56. A. Li, G. Wu and Z. Zhang [2000], A hierarchy for the cuppable degrees, Illinois Journal of Mathematics, Vol. 44, No. 3, Winter 2000, 619–632.

    MathSciNet  Google Scholar 

  57. A. Li and D. Yang [2000], A high diamond theorem, ISSN 1000–9825 Journal of Software, 2000, 11(1): 23–39.

    Google Scholar 

  58. A. Li and X. Yi [1999], Cupping the recursively enumerable degrees by d.r.e. degrees, Proc. London Math. Soc. 78 (3) (1999), 1–21.

    Article  MathSciNet  Google Scholar 

  59. D. Miller [1981], High recursively enumerable degrees and the anti-cupping property, in M. Lerman, J. H. Schmerl and R. I. Soare (editors), Logic Year 1979–80: University of Connecticut, Lecture Notes in Mathematics No. 859, Springer-Verlag, Berlin, Heidelberg, Tokyo, New York, 1981, 230–245.

    Chapter  Google Scholar 

  60. A. A. Muchnik [1956], On the unsolvability of the problem of reducibility in the theory of algorithms, Dokl. Akad. Nauk SSSR, N.S. 108 (1956), 194–197 (Russian).

    MathSciNet  MATH  Google Scholar 

  61. A. Nies [ta], Model theoretic properties of structures from computability theory, to appear.

    Google Scholar 

  62. A. Nies, R. A. Shore and T. A. Slaman [1998], Interpretability and definability in the recursively enumerable degrees, Proc. London Math. Soc. (3), 77, 241–249.

    MathSciNet  Google Scholar 

  63. E. L. Post [1944], Recursively enumerable sets of positive integers and their decision problems, Bull. Amer. Math. Soc. 50 284–316.

    Article  MathSciNet  MATH  Google Scholar 

  64. P. Odifreddi [1989], Classical Recursion Theory, North-Holland, Amsterdam, New York, Oxford.

    MATH  Google Scholar 

  65. R. W. Robinson [1971a], Interpolation and embedding in the recursively enumerable degrees, Ann. of Math. (2) 93 (1971), 285–314.

    Article  MathSciNet  MATH  Google Scholar 

  66. R. W. Robinson [1971b], Jump restricted interpolation in the recursively enumerable degrees, Ann. of Math. (2) 93 (1971), 586–596.

    Article  MathSciNet  MATH  Google Scholar 

  67. G. E. Sacks [1963], On the degrees less than 0′, Ann. of Math. (2) 77 (1963), 211–231.

    Article  MathSciNet  MATH  Google Scholar 

  68. G. E. Sacks [1964], The recursively enumerable degrees are dense, Ann. of Math. (2) 80 (1964), 300–312.

    Article  MathSciNet  MATH  Google Scholar 

  69. D. Seetapun [1991], Contributions to Recursion Theory, Ph.D. thesis, Trinity College, Cambridge, 1991.

    Google Scholar 

  70. D. Seetapun [1992], Defeating Red, (handwritten notes), 1992.

    Google Scholar 

  71. J. R. Shoenfleld [1965], Application of model theory to degrees of unsolvability, in J. W. Addison, L. Henkin and A. Tarski, Symposium on the theory of models (editors), North-Holland, Amsterdam, 1965.

    Google Scholar 

  72. R. A. Shore [1999], The recursively enumerable degrees, in Handbook of Computability Theory (ed. E. R. Griffor), Amsterdam, Lausanne, New York, Oxford, Shannon, Singapore, Tokyo, 1999, 169–197.

    Google Scholar 

  73. R. A. Shore [2000], Natural definability in degree structures, in M. Lerman, R Cholak, S. Lempp and R. A. Shore, eds., Computability Theory and Its Applications, Contemporary Mathematics Vol. 257, Providence RI, 2000, AMS, 255–271.

    Google Scholar 

  74. R. A. Shore and T. A. Slaman [1990], Working below Low2 recursively enumerable degrees, Archive for Math. Logic, 29 (1990), 201–211.

    Article  MathSciNet  MATH  Google Scholar 

  75. R. A. Shore and T. A. Slaman [1993], Working below high recursively enumerable degrees, 58, J. Symbolic Logic, 824–859.

    Article  MathSciNet  MATH  Google Scholar 

  76. T. A. Slaman and R. I. Soare [1995], Algebraic aspects of the recursively enumerable degrees, Proc. Nat. Acad. Sci. USA, 92, (1995), 617–621.

    Article  MathSciNet  MATH  Google Scholar 

  77. T. A. Slaman and R. I. Soare [2001], Extension of embeddings in the recursively enumerable degrees, Annals of Math., 153: 1–43, 2001.

    Article  MathSciNet  Google Scholar 

  78. R. I. Soare [1974], Automorphisms of the lattice of recursively enumerable sets, Bull. Amer. Math. Soc. 80 (1974), 53–58.

    Article  MathSciNet  MATH  Google Scholar 

  79. R. I. Soare [1987], Recursively Enumerable Sets and Degrees, A study of computable function and computably generated sets, Springer-Verlag Berlin Heidelberg New York London Pairs Tokyo, 1987.

    Google Scholar 

  80. D. Wang [2000], Saturation properties in the computably enumerable degrees, Ph. D. Dissertation, University of Wisconsin, 2000.

    Google Scholar 

  81. C. E. M. Yates [1966], A minimal pair of recursively enumerable degrees, J. Symbolic Logic 31 (1966), 159–168.

    Article  MathSciNet  MATH  Google Scholar 

Download references

Author information

Authors and Affiliations

  1. Institute of Software, Chinese Academy of Sciences, P.O. Box, 8718, Beijing, P. R. of CHINA

    Angsheng Li

Authors
  1. Angsheng Li
    View author publications

    You can also search for this author in PubMed Google Scholar

Rights and permissions

Reprints and permissions

Copyright information

© 2003 Springer Science+Business Media New York

About this chapter

Cite this chapter

Li, A. (2003). Definable Relations on the Computably Enumerable Degrees. In: Computability and Models. The University Series in Mathematics. Springer, Boston, MA. https://doi.org/10.1007/978-1-4615-0755-0_12

Download citation

  • DOI: https://doi.org/10.1007/978-1-4615-0755-0_12

  • Publisher Name: Springer, Boston, MA

  • Print ISBN: 978-1-4613-5225-9

  • Online ISBN: 978-1-4615-0755-0

  • eBook Packages: Springer Book Archive

Publish with us

Policies and ethics

Search

Navigation