1
$\begingroup$

The hop $H_e$ is defined by $H_e(X) = X \oplus W_e^{X}$. A 2-REA operator (or double hop) $J_{\langle e,i\rangle}$ is defined by $J_{\langle e,i\rangle}(X) = H_e(H_i(X))$

By a famous result from Pseudo Jump Operators. I: The R. E. Case by Jockusch and Shore it's known that for any hop $H_e$ there is an r.e. set $A$ such that $H_e(A) \equiv_T 0'$. Or, as this holds uniformly, there is a computable function $f$ such that for any $e$ $H_e(H_{f(e)}(\emptyset)) \equiv_T 0'$.

I'm wondering if this extends to 2-REA operators. In other words, given $J$ a 2-REA operator does there always exist a 2-REA set (i.e. $H_e(H_i(\emptyset))$ for some $e$, $i$) $A$ such that $J(A) \equiv_T 0''$?

I'm guessing no. I bet there's a slick proof of this but it's not coming to me.

(Note that the claim holds if you allow $A$ to be an arbitrary set.)

$\endgroup$

1 Answer 1

2
$\begingroup$

Ohh, I think I was being dumb. There is a 2-REA operator $J$ such that $J(X) <_T X'$ isn't of degree r.e. in $X$. Since $0''$ is of r.e. degree in every $X < 0''$ with $X' \geq_T 0''$.

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .