Defining jump classes in the degrees below $\textbf {0}’$
HTML articles powered by AMS MathViewer
- by Richard A. Shore PDF
- Proc. Amer. Math. Soc. 104 (1988), 287-292 Request permission
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
- S. B. Cooper, The strong anticupping property for recursively enumerable degrees, J. Symbolic Logic 54 (1989), no. 2, 527–539. MR 997886, DOI 10.2307/2274867
- S. Barry Cooper and Richard L. Epstein, Complementing below recursively enumerable degrees, Ann. Pure Appl. Logic 34 (1987), no. 1, 15–32. MR 887552, DOI 10.1016/0168-0072(87)90039-X
- H. B. Enderton and Hilary Putnam, A note on the hyperarithmetical hierarchy, J. Symbolic Logic 35 (1970), 429–430. MR 290971, DOI 10.2307/2270699 Harrington L. and T. A. Slaman [1989] The theory of the recursively enumerable degrees (in preparation).
- Carl G. Jockusch Jr., Degrees of generic sets, Recursion theory: its generalisation and applications (Proc. Logic Colloq., Univ. Leeds, Leeds, 1979) London Math. Soc. Lecture Note Ser., vol. 45, Cambridge Univ. Press, Cambridge-New York, 1980, pp. 110–139. MR 598304
- Carl G. Jockusch Jr. and David B. Posner, Double jumps of minimal degrees, J. Symbolic Logic 43 (1978), no. 4, 715–724. MR 518677, DOI 10.2307/2273510
- Carl G. Jockusch Jr. and Richard A. Shore, Pseudojump operators. II. Transfinite iterations, hierarchies and minimal covers, J. Symbolic Logic 49 (1984), no. 4, 1205–1236. MR 771789, DOI 10.2307/2274273
- Carl G. Jockusch Jr. and Stephen G. Simpson, A degree-theoretic definition of the ramified analytical hierarchy, Ann. Math. Logic 10 (1976), no. 1, 1–32. MR 491098, DOI 10.1016/0003-4843(76)90023-1
- S. C. Kleene and Emil L. Post, The upper semi-lattice of degrees of recursive unsolvability, Ann. of Math. (2) 59 (1954), 379–407. MR 61078, DOI 10.2307/1969708
- Manuel Lerman, Degrees of unsolvability, Perspectives in Mathematical Logic, Springer-Verlag, Berlin, 1983. Local and global theory. MR 708718, DOI 10.1007/978-3-662-21755-9
- Anil Nerode and Richard A. Shore, Second order logic and first order theories of reducibility orderings, The Kleene Symposium (Proc. Sympos., Univ. Wisconsin, Madison, Wis., 1978), Studies in Logic and the Foundations of Mathematics, vol. 101, North-Holland, Amsterdam-New York, 1980, pp. 181–200. MR 591882
- Anil Nerode and Richard A. Shore, Reducibility orderings: theories, definability and automorphisms, Ann. Math. Logic 18 (1980), no. 1, 61–89. MR 568916, DOI 10.1016/0003-4843(80)90004-2
- Robert W. Robinson, Jump restricted interpolation in the recursively enumerable degrees, Ann. of Math. (2) 93 (1971), 586–596. MR 313037, DOI 10.2307/1970889
- Gerald E. Sacks, Forcing with perfect closed sets, Axiomatic Set Theory (Proc. Sympos. Pure Math., Vol. XIII, Part I, Univ. California, Los Angeles, Calif., 1967) Amer. Math. Soc., Providence, R.I., 1971, pp. 331–355. MR 0276079
- Richard A. Shore, The theory of the degrees below ${\bf 0}^{\prime }$, J. London Math. Soc. (2) 24 (1981), no. 1, 1–14. MR 623666, DOI 10.1112/jlms/s2-24.1.1
- Richard A. Shore, On homogeneity and definability in the first-order theory of the Turing degrees, J. Symbolic Logic 47 (1982), no. 1, 8–16. MR 644748, DOI 10.2307/2273376
- Stephen G. Simpson, First-order theory of the degrees of recursive unsolvability, Ann. of Math. (2) 105 (1977), no. 1, 121–139. MR 432435, DOI 10.2307/1971028 Slaman, T. A. [1989] A recursively enumerable degree which is not the top of a diamond (in preparation). Slaman, T. A. and R. A. Shore [1988] Working below a low$_{2}$ recursively enumerable degree (in preparation). —, [1989] Working below a high recursively enumerable degree (in preparation).
- Theodore A. Slaman and John R. Steel, Complementation in the Turing degrees, J. Symbolic Logic 54 (1989), no. 1, 160–176. MR 987329, DOI 10.2307/2275022
- Theodore A. Slaman and W. Hugh Woodin, Definability in the Turing degrees, Illinois J. Math. 30 (1986), no. 2, 320–334. MR 840131
Additional Information
- © Copyright 1988 American Mathematical Society
- 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