Remote Access Transactions of the American Mathematical Society
Green Open Access

Transactions of the American Mathematical Society

ISSN 1088-6850(online) ISSN 0002-9947(print)

 
 

 

Pseudojump operators. I. The r.e. case


Authors: Carl G. Jockusch and Richard A. Shore
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
Full-text PDF

Abstract | References | Similar Articles | Additional Information

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}}^{\prime}$ 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}}^{\prime}$. 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}}^{\prime}$ does not split over all lower r.e. degrees.


References [Enhancements On Off] (What's this?)

  • [1] S. B. Cooper, Sets recursively enumerable in high degrees, Abstract 72T-E4, Notices Amer. Math. Soc. 19 (1972), A-20.
  • [2] -, Initial segments of the degrees containing nonrecursive recursively enumerable degrees, preprint.
  • [3] -, On a theorem of C. E. M. Yates, handwritten notes.
  • [4] R. M. Friedberg, A criterion for completeness of degrees of unsolvability, J. Symbolic Logic 22 (1957), 159-160. MR 0098025 (20:4488)
  • [5] L. Harrington and A. Kechris, A basis result for $ \Sigma _3^0$ sets of reals with an application to minimal covers, Proc. Amer. Math. Soc. 53 (1975), 445-448. MR 0398832 (53:2683)
  • [6] L. Harrington, On Cooper's proof of a theorem of Yates. I and II, handwritten notes, 1976.
  • [7] -, Understanding Lachlan's monster paper, handwritten notes, 1980.
  • [8] C. Jockusch and R. A. Shore, Pseudo jump operators. II: Transfinite iterations and minimal covers (in preparation).
  • [9] C. Jockusch and R. I. Soare, Minimal covers and arithmetical sets, Proc. Amer. Math. Soc. 25 (1970), 856-859. MR 0265154 (42:67)
  • [10] A. H. Lachlan, On a problem of G. E. Sacks, Proc. Amer. Math. Soc. 16 (1965), 972-979. MR 0182560 (32:43)
  • [11] -, Lower bounds for pairs of r.e. degrees, Proc. London Math. Soc. 16 (1966), 537-569. MR 0204282 (34:4126)
  • [12] -, On the lattice of recursively enumerable sets, Trans. Amer. Math. Soc. 130 (1968), 1-37. MR 0227009 (37:2594)
  • [13] -, A recursively enumerable degree which will not split over all lesser ones, Ann. Math. Logic 9 (1975), 307-365. MR 0409150 (53:12912)
  • [14] -, Decomposition of pairs of recursively enumerable degrees, Proc. Amer. Math. Soc. 79 (1980), 629-634. MR 572317 (81i:03065)
  • [15] J. MacIntyre, Transfinite extensions of Friedberg's completeness criterion, J. Symbolic Logic 42 (1977), 1-10. MR 0491099 (58:10371)
  • [16] D. A. Martin, On a question of G. E. Sacks, J. Symbolic Logic 31 (1966), 66-69. MR 0204283 (34:4127)
  • [17] D. Miller, High recursively enumerable degrees and the anti-cupping property, in Logic Year 1979-80, The University of Connecticut (M. Lerman, J. H. Schmerl and R. I. Soare, eds.), Lecture Notes in Math., vol. 859, Springer-Verlag, Berlin, Heidelberg and New York, 1981, pp. 230-245. MR 619872 (82j:03048)
  • [18] R. W. Robinson, Interpolation and embedding in the recursively enumerable degrees, Ann. of Math. (2) 93 (1971), 285-314. MR 0274286 (43:51)
  • [19] G. E. Sacks, A minimal degree less than $ 0^{\prime}$, Bull. Amer. Math. Soc. 67 (1961), 416-419. MR 0126380 (23:A3676)
  • [20] -, Degrees of unsolvability, Ann. of Math. Studies, No. 55, Princeton Univ. Press, Princeton, N.J., 1966.
  • [21] -, On a theorem of Lachlan and Martin, Proc. Amer. Math. Soc. 18 (1967), 140-141. MR 0207558 (34:7373)
  • [22] J. R. Shoenfield, On degrees of unsolvability, Ann. of Math. (2) 69 (1959), 644-653. MR 0105355 (21:4097)
  • [23] -, Degrees of unsolvability, North-Holland, Amsterdam, 1971.
  • [24] R. A. Shore, On homogeneity and definability in the first order theory of the Turing degrees, J. Symbolic Logic 47 (1982), 8-16. MR 644748 (84a:03046)
  • [25] R. Soare, The infinite injury method, J. Symbolic Logic 41 (1976), 513-530. MR 0429521 (55:2534)
  • [26] R. I. Soare and M. Stob, Relative recursive enumerability, Proc. Colloq. Int. de Logique, Marseille, 1981 (to appear). MR 757037 (86b:03050)

Similar Articles

Retrieve articles in Transactions of the American Mathematical Society with MSC: 03D25, 03D30

Retrieve articles in all journals with MSC: 03D25, 03D30


Additional Information

DOI: https://doi.org/10.1090/S0002-9947-1983-0682720-1
Article copyright: © Copyright 1983 American Mathematical Society

American Mathematical Society