Pseudojump operators. I. The r.e. case
HTML articles powered by AMS MathViewer
 by Carl G. Jockusch and Richard A. Shore PDF
 Trans. Amer. Math. Soc. 275 (1983), 599609 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 wellknown 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 72TE4, Notices Amer. Math. Soc. 19 (1972), A20.
—, 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/S00029939197503988327 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/S0002993919700265154X
 A. H. Lachlan, On a problem of G. E. Sacks, Proc. Amer. Math. Soc. 16 (1965), 972–979. MR 182560, DOI 10.1090/S00029939196501825600
 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/s316.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/S00029947196802270091
 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/00034843(76)900164
 A. H. Lachlan, Decomposition of recursively enumerable degrees, Proc. Amer. Math. Soc. 79 (1980), no. 4, 629–634. MR 572317, DOI 10.1090/S00029939198005723179
 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/S000299041961106526 —, 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/S00029939196702075587
 J. R. Shoenfield, On degrees of unsolvability, Ann. of Math. (2) 69 (1959), 644–653. MR 105355, DOI 10.2307/1970028 —, Degrees of unsolvability, NorthHolland, Amsterdam, 1971.
 Richard A. Shore, On homogeneity and definability in the firstorder 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, NorthHolland, Amsterdam, 1982, pp. 299–324. MR 757037, DOI 10.1016/S0049237X(08)718925
Additional Information
 © Copyright 1983 American Mathematical Society
 Journal: Trans. Amer. Math. Soc. 275 (1983), 599609
 MSC: Primary 03D25; Secondary 03D30
 DOI: https://doi.org/10.1090/S00029947198306827201
 MathSciNet review: 682720