The jump is definable in the structure of the degrees of unsolvability

Cooper, S. Barry

doi:10.1090/S0273-0979-1990-15923-3

Author: S. Barry Cooper
Journal: Bull. Amer. Math. Soc. 23 (1990), 151-158
MSC (1985): Primary 03D30
DOI: https://doi.org/10.1090/S0273-0979-1990-15923-3
MathSciNet review: 1027898
Full-text PDF Free Access

References | Similar Articles | Additional Information

1. M. M. Arslanov, Structural properties of the degrees below0’, Dokl. Akad. Nauk. SSSR, (new series) 283 (2) (1985), 270-273.
2. S. B. Cooper, The strong anticupping property for recursively enumerable degrees, J. Symbolic Logic 54 (1989), no. 2, 527–539. MR 997886, https://doi.org/10.2307/2274867
3. S. B. Cooper, A jump class of noncappable degrees, J. Symbolic Logic 54 (1989), no. 2, 324–353. MR 997870, https://doi.org/10.2307/2274851
4. S. Barry Cooper and Richard L. Epstein, Complementing below recursively enumerable degrees, Ann. Pure Appl. Logic 34 (1987), no. 1, 15–32. MR 887552, https://doi.org/10.1016/0168-0072(87)90039-X
5. S. Barry Cooper, Steffen Lempp, and Philip Watson, Weak density and cupping in the d-r.e. degrees, Israel J. Math. 67 (1989), no. 2, 137–152. MR 1026559, https://doi.org/10.1007/BF02937291
6. S. B. Cooper, L. Harrington, A. H. Lachlan, S. Lempp, and R. I. Soare, The d-r.e. degrees are not dense (in preparation).
7. Richard L. Epstein, Degrees of unsolvability: structure and theory, Lecture Notes in Mathematics, vol. 759, Springer, Berlin, 1979. MR 551620
8. L. Feiner, The strong homogeneity conjecture, J. Symbolic Logic 35 (1970), 375–377. MR 286655, https://doi.org/10.2307/2270693
9. Leo Harrington and Richard A. Shore, Definable degrees and automorphisms of \cal𝐷, Bull. Amer. Math. Soc. (N.S.) 4 (1981), no. 1, 97–100. MR 590819, https://doi.org/10.1090/S0273-0979-1981-14871-0
10. Carl G. Jockusch Jr. and Richard A. Shore, Pseudojump operators. I. The r.e. case, Trans. Amer. Math. Soc. 275 (1983), no. 2, 599–609. MR 682720, https://doi.org/10.1090/S0002-9947-1983-0682720-1
11. 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, https://doi.org/10.2307/2274273
12. 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, https://doi.org/10.1016/0003-4843(76)90023-1
13. Carl G. Jockusch Jr. and Robert M. Solovay, Fixed points of jump preserving automorphisms of degrees, Israel J. Math. 26 (1977), no. 1, 91–94. MR 432434, https://doi.org/10.1007/BF03007659
14. 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, https://doi.org/10.2307/1969708
15. Alistair H. Lachlan, A recursively enumerable degree which will not split over all lesser ones, Ann. Math. Logic 9 (1976), no. 4, 307–365. MR 409150, https://doi.org/10.1016/0003-4843(76)90016-4
16. A. H. Lachlan and R. Lebeuf, Countable initial segments of the degrees of unsolvability, J. Symbolic Logic 41 (1976), no. 2, 289–300. MR 403937, https://doi.org/10.2307/2272227
17. Manuel Lerman, Initial segments of the degrees of unsolvability, Ann. of Math. (2) 93 (1971), 365–389. MR 307893, https://doi.org/10.2307/1970779
18. Manuel Lerman, Degrees of unsolvability, Perspectives in Mathematical Logic, Springer-Verlag, Berlin, 1983. Local and global theory. MR 708718
19. 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), Stud. Logic Foundations Math., vol. 101, North-Holland, Amsterdam-New York, 1980, pp. 181–200. MR 591882
20. Anil Nerode and Richard A. Shore, Reducibility orderings: theories, definability and automorphisms, Ann. Math. Logic 18 (1980), no. 1, 61–89. MR 568916, https://doi.org/10.1016/0003-4843(80)90004-2
21. Piergiorgio Odifreddi, Classical recursion theory, Studies in Logic and the Foundations of Mathematics, vol. 125, North-Holland Publishing Co., Amsterdam, 1989. The theory of functions and sets of natural numbers; With a foreword by G. E. Sacks. MR 982269
22. David B. Posner and Robert W. Robinson, Degrees joining to 0′, J. Symbolic Logic 46 (1981), no. 4, 714–722. MR 641485, https://doi.org/10.2307/2273221
23. Emil L. Post, Recursively enumerable sets of positive integers and their decision problems, Bull. Amer. Math. Soc. 50 (1944), 284–316. MR 10514, https://doi.org/10.1090/S0002-9904-1944-08111-1
24. Linda Jean Richter, On automorphisms of the degrees that preserve jumps, Israel J. Math. 32 (1979), no. 1, 27–31. MR 531597, https://doi.org/10.1007/BF02761181
25. Hartley Rogers Jr., Theory of recursive functions and effective computability, McGraw-Hill Book Co., New York-Toronto, Ont.-London, 1967. MR 0224462
26. 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, https://doi.org/10.2307/2273376
27. Richard A. Shore, A noninversion theorem for the jump operator, Ann. Pure Appl. Logic 40 (1988), no. 3, 277–303. MR 973483, https://doi.org/10.1016/0168-0072(88)90034-6
28. Richard A. Shore, Defining jump classes in the degrees below 0’, Proc. Amer. Math. Soc. 104 (1988), no. 1, 287–292. MR 958085, https://doi.org/10.1090/S0002-9939-1988-0958085-4
29. Stephen G. Simpson, First-order theory of the degrees of recursive unsolvability, Ann. of Math. (2) 105 (1977), no. 1, 121–139. MR 432435, https://doi.org/10.2307/1971028
30. T. A. Slaman and R. A. Shore, Working below a low₂ recursively enumerable degree (to appear).
31. T. A. Slaman and R. A. Shore, Working below a high recursively enumerable degree (in preparation).
32. Theodore A. Slaman and John R. Steel, Complementation in the Turing degrees, J. Symbolic Logic 54 (1989), no. 1, 160–176. MR 987329, https://doi.org/10.2307/2275022
33. Theodore A. Slaman and W. Hugh Woodin, Definability in the Turing degrees, Illinois J. Math. 30 (1986), no. 2, 320–334. MR 840131
34. Robert I. Soare, Recursively enumerable sets and degrees, Perspectives in Mathematical Logic, Springer-Verlag, Berlin, 1987. A study of computable functions and computably generated sets. MR 882921
35. C. E. M. Yates, Initial segments and implications for the structure of degrees, Conference in Mathematical Logic—London ’70 (Proc. Conf., Bedford Coll., London, 1970) Springer, Berlin, 1972, pp. 305–335. Lecture Notes in Math., Vol. 255. MR 0357095