Remote Access Proceedings of the American Mathematical Society
Green Open Access

Proceedings of the American Mathematical Society

ISSN 1088-6826(online) ISSN 0002-9939(print)

 
 

 

Defining jump classes in the degrees below $ {\bf0}'$


Author: Richard A. Shore
Journal: Proc. Amer. Math. Soc. 104 (1988), 287-292
MSC: Primary 03D30; Secondary 03D20
DOI: https://doi.org/10.1090/S0002-9939-1988-0958085-4
MathSciNet review: 958085
Full-text PDF

Abstract | References | Similar Articles | Additional Information

Abstract: We prove that, for each degree $ {\mathbf{c}}$ r.e. in and above $ {{\mathbf{0}}^{(3)}}$, the class of degrees $ {\mathbf{x}} \leq {\mathbf{0}}'$ with $ {{\mathbf{x}}^{(3)}} = {\mathbf{c}}$ is definable without parameters in $ \mathcal{D}( \leq 0')$, the degrees below $ {\mathbf{0'}}$. Indeed the same definitions work below any r.e. degree $ {\mathbf{r}}$ in place of $ {\mathbf{0'}}$. Thus for each r.e. degree $ {\mathbf{r}}$, $ \operatorname{Th} (\mathcal{D}( \leq {\mathbf{r}}))$ uniquely determines $ {{\mathbf{r}}^{(3)}}$.


References [Enhancements On Off] (What's this?)

  • 1. Cooper, S. B. [1988] The strong anticupping property for recursively enumerable degrees, J. Symbolic Logic (to appear) MR 997886 (91b:03071)
  • 2. Cooper, S. B. and R. L. Epstein [1987] Complementing below recursively enumerable degrees, Ann. Pure Appl. Logic 34, 15-32. MR 887552 (89f:03035)
  • 3. Enderton, H. B. and H. Putnam [1970] A note on the hyperarithmetical hierarchy, J. Symbolic Logic 35, 429-430. MR 0290971 (45:65)
  • 4. Harrington L. and T. A. Slaman [1989] The theory of the recursively enumerable degrees (in preparation).
  • 5. Jockusch, C. G. Jr. [1980] Degrees of generic sets, Recursion Theory: Its Generalizations and Application, Proceedings of Logic Colloquium '79, Leeds, August 1979, (F. R. Drake and S. S. Wainer eds), London Mathematical Society Lecture Notes Series 45, Cambridge Univ. Press, Cambridge, England, pp 110-139. MR 598304 (83i:03070)
  • 6. Jockusch, C. G. Jr. and D. Posner [1978] Double jumps of minimal degrees, J. Symbolic Logic 43, 715-724. MR 518677 (80d:03042)
  • 7. Jockusch, C. G. Jr. and R. A. Shore [1984] Pseudo-jump operators II: transfinite iterations, hierarchies and minimal covers, J. Symbolic Logic 49, 1205-1236. MR 771789 (86g:03072)
  • 8. Jockusch, C. G. Jr. and S. G. Simpson [1976] A degree theoretic definition of the ramified analytic hierarchy, Ann. of Math. Logic 10, 1-32. MR 0491098 (58:10370)
  • 9. Kleene, S. C. and E. L. Post [1954] The upper semi-lattice of degrees of recursive unsolvability, Ann. of Math. (2) 59 379-407. MR 0061078 (15:772a)
  • 10. Lerman M. [1983] Degrees of unsolvability, Springer-Verlag, Berlin. MR 708718 (85h:03044)
  • 11. Nerode, A. and R. A. Shore [1979] Second order logic and first order theories of reducibility orderings, The Kleene Symposium (J. Barwise et. al., eds.), North-Holland, Amsterdam. MR 591882 (82g:03078)
  • 12. -, [1980] Reducibility orderings: theories, definability and automorphisms, Ann. of Math. Logic 18, 61-89. MR 568916 (81k:03040)
  • 13. Robinson, R. W. [1971] Jump restricted interpolation in the recursively enumerable degrees, Ann. of Math. (2) 93, 586-96. MR 0313037 (47:1592)
  • 14. Sacks, G. E. [1971] Forcing with perfect closed sets, Axiomatic Set Theory I, (D. S. Scott, ed.) Proc. Sympos. Pure Math., vol 13, Amer. Math. Soc., Providence, R. I., pp. 331-355. MR 0276079 (43:1827)
  • 15. Shore, R. A. [1981] The theory of the degrees below $ {\mathbf{0'}}$, J. London Math. Soc. (2) 24, 1-14. MR 623666 (83m:03051)
  • 16. -, [1982] On homogeneity and definability in the first order theory of the Turing degrees, J. Symbolic Logic 47, 8-16. MR 644748 (84a:03046)
  • 17. Simpson, S. G. [1977] First order theory of the degrees of unsolvability, Ann. of Math. (2) 105, 121-39. MR 0432435 (55:5423)
  • 18. Slaman, T. A. [1989] A recursively enumerable degree which is not the top of a diamond (in preparation).
  • 19. Slaman, T. A. and R. A. Shore [1988] Working below a low$ _{2}$ recursively enumerable degree (in preparation).
  • 20. -, [1989] Working below a high recursively enumerable degree (in preparation).
  • 21. Slaman, T. A. and J. Steel [1988] Complementation in the Turing degrees, J. Symbolic Logic (to appear). MR 987329 (90c:03034)
  • 22. Slaman, T. A. and W. H. Woodin [1986] Definability in the Turing degrees, Illinois J. Math. 30, 320-34. MR 840131 (87m:03061)

Similar Articles

Retrieve articles in Proceedings of the American Mathematical Society with MSC: 03D30, 03D20

Retrieve articles in all journals with MSC: 03D30, 03D20


Additional Information

DOI: https://doi.org/10.1090/S0002-9939-1988-0958085-4
Keywords: Degrees below $ {\mathbf{0'}}$, jump classes, definability
Article copyright: © Copyright 1988 American Mathematical Society

American Mathematical Society