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

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?)

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