Pseudojump operators. I. The r.e. case
HTML articles powered by AMS MathViewer
- by Carl G. Jockusch and Richard A. Shore
- Trans. Amer. Math. Soc. 275 (1983), 599-609
- DOI: https://doi.org/10.1090/S0002-9947-1983-0682720-1
- PDF | Request permission
Abstract:
Call an operator $J$ on the power set of $\omega$ a pseudo jump operator if $J(A)$ is uniformly recursively enumerable in $A$ and $A$ is recursive in $J(A)$ for all subsets $A$ of $\omega$. Thus the (Turing) jump operator is a pseudo jump operator, and any existence proof in the theory of r.e. degrees yields, when relativized, one or more pseudo jump operators. Extending well-known results about the jump, we show that for any pseudo jump operator $J$, every degree $\geqslant {\mathbf {0}}’$ has a representative in the range of $J$, and that there is a nonrecursive r.e. set $A$ with $J(A)$ of degree ${\mathbf {0}}’$. The latter result yields a finite injury proof in two steps that there is an incomplete high r.e. degree, and by iteration analogous results for other levels of the ${H_n}$, ${L_n}$ hierarchy of r.e. degrees. We also establish a result on pairs of pseudo jump operators. This is combined with Lachlan’s result on the impossibility of combining splitting and density for r.e. degrees to yield a new proof of Harrington’s result that ${\mathbf {0}}’$ does not split over all lower r.e. degrees.References
- S. B. Cooper, Sets recursively enumerable in high degrees, Abstract 72T-E4, Notices Amer. Math. Soc. 19 (1972), A-20.
—, Initial segments of the degrees containing nonrecursive recursively enumerable degrees, preprint.
—, On a theorem of C. E. M. Yates, handwritten notes.
- Richard Friedberg, A criterion for completeness of degrees of unsolvability, J. Symbolic Logic 22 (1957), 159–160. MR 98025, DOI 10.2307/2964177
- Leo A. Harrington and Alexander S. Kechris, A basis result for $\Sigma ^{0}_{3}$ sets of reals with an application to minimal covers, Proc. Amer. Math. Soc. 53 (1975), no. 2, 445–448. MR 398832, DOI 10.1090/S0002-9939-1975-0398832-7 L. Harrington, On Cooper’s proof of a theorem of Yates. I and II, handwritten notes, 1976. —, Understanding Lachlan’s monster paper, handwritten notes, 1980. C. Jockusch and R. A. Shore, Pseudo jump operators. II: Transfinite iterations and minimal covers (in preparation).
- Carl G. Jockusch Jr. and Robert I. Soare, Minimal covers and arithmetical sets, Proc. Amer. Math. Soc. 25 (1970), 856–859. MR 265154, DOI 10.1090/S0002-9939-1970-0265154-X
- A. H. Lachlan, On a problem of G. E. Sacks, Proc. Amer. Math. Soc. 16 (1965), 972–979. MR 182560, DOI 10.1090/S0002-9939-1965-0182560-0
- A. H. Lachlan, Lower bounds for pairs of recursively enumerable degrees, Proc. London Math. Soc. (3) 16 (1966), 537–569. MR 204282, DOI 10.1112/plms/s3-16.1.537
- A. H. Lachlan, On the lattice of recursively enumerable sets, Trans. Amer. Math. Soc. 130 (1968), 1–37. MR 227009, DOI 10.1090/S0002-9947-1968-0227009-1
- 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 10.1016/0003-4843(76)90016-4
- A. H. Lachlan, Decomposition of recursively enumerable degrees, Proc. Amer. Math. Soc. 79 (1980), no. 4, 629–634. MR 572317, DOI 10.1090/S0002-9939-1980-0572317-9
- John M. Macintyre, Transfinite extensions of Friedberg’s completeness criterion, J. Symbolic Logic 42 (1977), no. 1, 1–10. MR 491099, DOI 10.2307/2272313
- Donald A. Martin, On a question of G. E. Sacks, J. Symbolic Logic 31 (1966), 66–69. MR 204283, DOI 10.2307/2270620
- David P. Miller, High recursively enumerable degrees and the anticupping property, Logic Year 1979–80 (Proc. Seminars and Conf. Math. Logic, Univ. Connecticut, Storrs, Conn., 1979/80) Lecture Notes in Math., vol. 859, Springer, Berlin, 1981, pp. 230–245. MR 619872
- Robert W. Robinson, Interpolation and embedding in the recursively enumerable degrees, Ann. of Math. (2) 93 (1971), 285–314. MR 274286, DOI 10.2307/1970776
- Gerald E. Sacks, A minimal degree less than $0’$, Bull. Amer. Math. Soc. 67 (1961), 416–419. MR 126380, DOI 10.1090/S0002-9904-1961-10652-6 —, Degrees of unsolvability, Ann. of Math. Studies, No. 55, Princeton Univ. Press, Princeton, N.J., 1966.
- Gerald E. Sacks, On a theorem of Lachlan and Martin, Proc. Amer. Math. Soc. 18 (1967), 140–141. MR 207558, DOI 10.1090/S0002-9939-1967-0207558-7
- J. R. Shoenfield, On degrees of unsolvability, Ann. of Math. (2) 69 (1959), 644–653. MR 105355, DOI 10.2307/1970028 —, Degrees of unsolvability, North-Holland, Amsterdam, 1971.
- 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
- Robert I. Soare, The infinite injury priority method, J. Symbolic Logic 41 (1976), no. 2, 513–530. MR 429521, DOI 10.2307/2272252
- Robert I. Soare and Michael Stob, Relative recursive enumerability, Proceedings of the Herbrand symposium (Marseilles, 1981) Stud. Logic Found. Math., vol. 107, North-Holland, Amsterdam, 1982, pp. 299–324. MR 757037, DOI 10.1016/S0049-237X(08)71892-5
Bibliographic Information
- © Copyright 1983 American Mathematical Society
- Journal: Trans. Amer. Math. Soc. 275 (1983), 599-609
- MSC: Primary 03D25; Secondary 03D30
- DOI: https://doi.org/10.1090/S0002-9947-1983-0682720-1
- MathSciNet review: 682720