On the jump of an $\alpha$-recursively enumerable set
HTML articles powered by AMS MathViewer
- by Richard A. Shore PDF
- Trans. Amer. Math. Soc. 217 (1976), 351-363 Request permission
Abstract:
We discuss the proper definition of the jump operator in $\alpha$-recursion theory and prove a sample theorem: There is an incomplete $\alpha$-r.e. set with jump $0''$ unless there is precisely one nonhyperregular $\alpha$-r.e. degree. Thus we have a theorem in the first order language of Turing degrees with the jump which fails to generalize to all admissible $\alpha$.References
- R. Björn Jensen, The fine structure of the constructible hierarchy, Ann. Math. Logic 4 (1972), 229–308; erratum, ibid. 4 (1972), 443. With a section by Jack Silver. MR 309729, DOI 10.1016/0003-4843(72)90001-0 R. Jhu, Contributions to axiomatic recursion theory and related aspects of $\alpha$-recursion theory, Ph. D. Thesis, University of Toronto, 1973.
- G. E. Sacks, Metarecursion theory, Sets, Models and Recursion Theory (Proc. Summer School Math. Logic and Tenth Logic Colloq., Leicester, 1965) North-Holland, Amsterdam, 1967, pp. 243–263. MR 0253896
- Gerald E. Sacks, Post’s problem, admissible ordinals, and regularity, Trans. Amer. Math. Soc. 124 (1966), 1–23. MR 201299, DOI 10.1090/S0002-9947-1966-0201299-1
- Gerald E. Sacks, Higher recursion theory, Perspectives in Mathematical Logic, Springer-Verlag, Berlin, 1990. MR 1080970, DOI 10.1007/BFb0086109
- Joseph R. Shoenfield, Degrees of unsolvability, North-Holland Mathematics Studies, No. 2, North-Holland Publishing Co., Amsterdam-London; American Elsevier Publishing Co., Inc., New York, 1971. Dedicated to S. C. Kleene. MR 0340011
- Richard A. Shore, Splitting an $\alpha$-recursively enumerable set, Trans. Amer. Math. Soc. 204 (1975), 65–77. MR 379154, DOI 10.1090/S0002-9947-1975-0379154-1 —, The recursively enumerable $\alpha$-degrees are dense, Ann. Math. Logic (to appear). —, The irregular and non-hyperregular $\alpha$-r.e. degrees, Israel J. Math. (to appear). S. G. Simpson, Admissible ordinals and recursion theory, Ph. D. Thesis, M.I.T., 1971.
- Stephen G. Simpson, Degree theory on admissible ordinals, Generalized recursion theory (Proc. Sympos., Univ. Oslo, Oslo, 1972) Studies in Logic and the Foundations of Math., Vol. 79, North-Holland, Amsterdam, 1974, pp. 165–193. MR 0537203
Additional Information
- © Copyright 1976 American Mathematical Society
- Journal: Trans. Amer. Math. Soc. 217 (1976), 351-363
- MSC: Primary 02F27
- DOI: https://doi.org/10.1090/S0002-9947-1976-0424544-2
- MathSciNet review: 0424544