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

1. M. M. Arslanov, Structural properties of the degrees below0’, Dokl. Akad. Nauk. SSSR, (new series) 283 (2) (1985), 270-273.

S. B. Cooper, The strong anticupping property for recursively enumerable degrees, J. Symbolic Logic 54 (1989), no. 2, 527–539. MR 997886, DOI https://doi.org/10.2307/2274867
S. B. Cooper, A jump class of noncappable degrees, J. Symbolic Logic 54 (1989), no. 2, 324–353. MR 997870, DOI https://doi.org/10.2307/2274851
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 https://doi.org/10.1016/0168-0072%2887%2990039-X
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, DOI 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).

Richard L. Epstein, Degrees of unsolvability: structure and theory, Lecture Notes in Mathematics, vol. 759, Springer, Berlin, 1979. MR 551620
L. Feiner, The strong homogeneity conjecture, J. Symbolic Logic 35 (1970), 375–377. MR 286655, DOI https://doi.org/10.2307/2270693
Leo Harrington and Richard A. Shore, Definable degrees and automorphisms of ${\cal D}$, Bull. Amer. Math. Soc. (N.S.) 4 (1981), no. 1, 97–100. MR 590819, DOI https://doi.org/10.1090/S0273-0979-1981-14871-0
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, DOI https://doi.org/10.1090/S0002-9947-1983-0682720-1
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 https://doi.org/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 https://doi.org/10.1016/0003-4843%2876%2990023-1
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, DOI https://doi.org/10.1007/BF03007659
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 https://doi.org/10.2307/1969708
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, DOI https://doi.org/10.1016/0003-4843%2876%2990016-4
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, DOI https://doi.org/10.2307/2272227
Manuel Lerman, Initial segments of the degrees of unsolvability, Ann. of Math. (2) 93 (1971), 365–389. MR 307893, DOI https://doi.org/10.2307/1970779
Manuel Lerman, Degrees of unsolvability, Perspectives in Mathematical Logic, Springer-Verlag, Berlin, 1983. Local and global theory. MR 708718
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
Anil Nerode and Richard A. Shore, Reducibility orderings: theories, definability and automorphisms, Ann. Math. Logic 18 (1980), no. 1, 61–89. MR 568916, DOI https://doi.org/10.1016/0003-4843%2880%2990004-2
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
David B. Posner and Robert W. Robinson, Degrees joining to ${\bf 0}^{\prime } $, J. Symbolic Logic 46 (1981), no. 4, 714–722. MR 641485, DOI https://doi.org/10.2307/2273221
Emil L. Post, Recursively enumerable sets of positive integers and their decision problems, Bull. Amer. Math. Soc. 50 (1944), 284–316. MR 10514, DOI https://doi.org/10.1090/S0002-9904-1944-08111-1
Linda Jean Richter, On automorphisms of the degrees that preserve jumps, Israel J. Math. 32 (1979), no. 1, 27–31. MR 531597, DOI https://doi.org/10.1007/BF02761181
Hartley Rogers Jr., Theory of recursive functions and effective computability, McGraw-Hill Book Co., New York-Toronto, Ont.-London, 1967. MR 0224462
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 https://doi.org/10.2307/2273376
Richard A. Shore, A noninversion theorem for the jump operator, Ann. Pure Appl. Logic 40 (1988), no. 3, 277–303. MR 973483, DOI https://doi.org/10.1016/0168-0072%2888%2990034-6
Richard A. Shore, Defining jump classes in the degrees below ${\bf 0}’$, Proc. Amer. Math. Soc. 104 (1988), no. 1, 287–292. MR 958085, DOI https://doi.org/10.1090/S0002-9939-1988-0958085-4
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 https://doi.org/10.2307/1971028

30. T. A. Slaman and R. A. Shore, Working below a low2 recursively enumerable degree (to appear).

31. T. A. Slaman and R. A. Shore, 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 https://doi.org/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
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
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