Pseudojump operators. I. The r.e. case

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.