The jump is definable in the structure of the degrees of unsolvability
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.
- 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
Retrieve articles in Bulletin of the American Mathematical Society with MSC (1985): 03D30
Retrieve articles in all journals with MSC (1985): 03D30