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
MathSciNet review: 682720
Full-text PDF Free Access

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}}’$ 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 [Enhancements On Off] (What's this?)

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

Article copyright: © Copyright 1983 American Mathematical Society