If a c.e. set $X$ is such that every $\Sigma^0_2$ set is c.e. in $X$, then $X \equiv 0'$

78 Views Asked by At

Is it true that if a c.e. set $X$ (of naturals) is such that every $\Sigma^0_2$ set $Y$ is c.e. in $X$, then $X \equiv 0'$?

An obvious and naive trial to prove this would be to take $Y := 0''$. However, this fails because of the existence of incomplete c.e. high set.

How can one prove or disprove the proposition above?

2

There are 2 best solutions below

0
On BEST ANSWER

If every $\Sigma^0_2$ set is c.e. in $X$, then every $\Delta^0_2$ set is computable relative to $X$. But the $\Delta^0_2$ sets are exactly those computable from $0'$, so $X\ge_T 0'$. But $0'$ is the largest c.e. degree, so if $X$ is c.e. then $X\equiv_T 0'$.

0
On

Your condition on $X$ is equivalent to $X\equiv_T\emptyset'$. Since this is weaker than $X\equiv_1 \emptyset'$, the claim as stated is not correct (I interpret $\equiv$ as recursively isomorphic).

To see this, recall that $Y$ is r.e. in $X$ precisely if $Y\le_1 X'$. This must hold in particular for all $Y=Z'$ with $Z\in\Sigma_1$, and $Z'\le_1 X'\iff Z\le_T X$, so $X\equiv_T \emptyset'$, as claimed. Conversely, if this holds, then $X'\equiv_1 \emptyset''$ is of course $\Sigma_2$ complete.