Skip to main content
SpringerLink
Log in

Automorphism bases for degrees of unsolvability

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

Abstract

A set of degrees of unsolvability is said togenerate the degrees if every degree is in the closure of the set under the lattice operations on degrees. (Of course the inf operation is only partially defined.) It is shown that every set of degrees which is comeager or of measure one generates the degrees and that the set of minimal degrees generates the degrees. (Thus any automorphism of degrees is determined by its action on, for example, the minimal degrees). Also the degrees below0′ which have the same jump as any given degree below0′ and those which cup any given nonzero degree ≤0′ to0′ are shown to generate the degrees below0′.

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
¥17,985 /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 (Japan)

Instant access to the full article PDF.

Institutional subscriptions

Similar content being viewed by others

References

  1. L. Harrington and R. Shore,Definable degrees and automorphisms of D, Bull. Amer. Math. Soc.4 (n.s.) (1981), 97–100.

    MATH  MathSciNet  Google Scholar 

  2. C. Jockusch,The degrees of bi-immune sets. Z. Math. Logik Grundlagen Math.15 (1969), 135–140.

    Article  MATH  MathSciNet  Google Scholar 

  3. C. Jockusch,Degrees in which the recursive sets are uniformly recursive, Canad. J. Math.24 (1972), 1092–1099.

    MATH  MathSciNet  Google Scholar 

  4. C. Jockusch,Simple proofs of some theorems on high degrees, Canad. J. Math.29 (1977), 1072–1080.

    MATH  MathSciNet  Google Scholar 

  5. C. Jockusch,Degrees of generic sets, inRecursion Theory: Its Generalisations and Applications (F. R. Drake and S. S. Wainer, eds.), Cambridge University Press, Cambridge, 1980.

    Google Scholar 

  6. C. Jockusch and D. Posner,Double jumps of minimal degrees, J. Symbolic Logic43 (1978), 715–724.

    Article  MATH  MathSciNet  Google Scholar 

  7. A. H. Lachlan,Solution to a problem of Spector, Canad. J. Math.23 (1971), 247–256.

    MATH  MathSciNet  Google Scholar 

  8. M. Lerman,Automorphism bases for the semilattice of recursively enumerable degrees, Abstract #77-E10, Notices Amer. Math. Soc.24 (1977), A-251.

    Google Scholar 

  9. M. Lerman,The Degrees of Unsolvability, Springer Verlag, to appear.

  10. A. Nerode and R. Shore,Second order logic and first order theories of reducibility orderings, inProceedings of the Kleene Symposium (J. Barwise, J. Keisler and K. Kunen, eds.), North-Holland, Amsterdam, 1980.

    Google Scholar 

  11. A. Nerode and R. Shore,Reducibility orderings: theories, definability and automorphisms, Ann. Math. Logic18 (1980), 61–89.

    Article  MATH  MathSciNet  Google Scholar 

  12. J. C. Oxtoby,Measure and Category, Springer Verlag, Berlin, 1971.

    MATH  Google Scholar 

  13. J. Paris,Measure and minimal degrees, Ann. Math. Logic11 (1977), 203–216.

    Article  MATH  MathSciNet  Google Scholar 

  14. D. Posner and R. Robinson,Degrees joining to 0′, J. Symbolic Logic, to appear.

  15. L. J. Richter,On automorphisms of the degrees that preserve jumps, Israel J. Math.32 (1979), 27–31.

    Article  MATH  MathSciNet  Google Scholar 

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

    MATH  Google Scholar 

  17. J. R. Shoenfield,Degrees of Unsolvability, North-Holland, Amsterdam, 1971.

    MATH  Google Scholar 

  18. R. Shore,Determining automorphisms of the recursively enumerable sets, Proc. Amer. Math. Soc.65 (1977), 318–325.

    Article  MATH  MathSciNet  Google Scholar 

  19. C. Spector,On degrees of recursive unsolvability, Ann. of Math.64 (1956), 151–163.

    Article  MathSciNet  Google Scholar 

  20. J. Stillwell,Decidability of the “almost all” theory of degrees, J. Symbolic Logic37 (1972). 501–506.

    Article  MATH  MathSciNet  Google Scholar 

  21. C. E. M. Yates,Banach-Mazur games, comeager sets, and degrees of unsolvability, Math. Proc. Camb. Phil. Soc.79 (1976), 195–220.

    Article  MATH  MathSciNet  Google Scholar 

Download references

Author information

Authors and Affiliations

  1. Department of Mathematics, University of Illinois, 61801, Urbana, IL, USA

    Carl G. Jockusch & David B. Posner

  2. Department of Mathematics, San Jose State University, 95114, San Jose, CA, USA

    Carl G. Jockusch & David B. Posner

Authors
  1. Carl G. Jockusch
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. David B. Posner
    View author publications

    You can also search for this author in PubMed Google Scholar

Additional information

The second author's research was performed while he was a Dickson instructor at the University of Chicago. The authors' research was supported by Nationals Science Foundation grants MCS 77-03452 and MCS 76-07033.

Rights and permissions

Reprints and permissions

About this article

Cite this article

Jockusch, C.G., Posner, D.B. Automorphism bases for degrees of unsolvability. Israel J. Math. 40, 150–164 (1981). https://doi.org/10.1007/BF02761906

Download citation

  • Received:

  • Revised:

  • Issue Date:

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

Keywords

Search

Navigation