Degree structure of $1$-Generic Set

Question

We can construct a $1$-generic set $A\leq_{T}\emptyset'$, using an $\emptyset'$-oracle and finite extension construction as in the Kleene-Post theorem to meet all jump requirements. How can I show there is a $1$-generic set $A\leq_{T}\emptyset'$ which does not have c.e. degree?

Answer 1

Every 1-generic set does not have c.e. degree.

The claim is: If $A$ is 1-generic, then there are no incomputable c.e. sets $Z$ such that $Z \leq_T A$.

To prove this, recall that the definition of $A$ being $1$-generic is that given any c.e. subset $W \subseteq 2^{<\omega}$,

$(\exists \sigma \prec A)( \sigma \in W \vee (\forall \tau \succeq \sigma)(\tau \notin W))$

This is equivalent to forcing the jump. Now suppose that $Z$ is an incomputable c.e. set such that $Z \leq_T A$. Hence there is some $e$ such that $\Phi_e^A = Z$. Define

$W = \{\sigma : (\exists x)(\Phi_e^\sigma(x) = 0 \wedge x \in Z)\}$

Since $Z$ is c.e., it is clear that $W$ is a c.e. subset of $2^{<\omega}$. Since $A$ is 1-generic, $A$ forces $W$. That is, there exists some $\sigma \prec A$ such that exactly one of the two holds

(1) $\sigma \in W$

(2) $(\forall \tau \succeq \sigma)(\tau \notin W)$.

Case (1) can not hold: If $\Phi_e^\sigma(x) = 0$ and $x \in Z$, then $\Phi_e^A(x) = 0$ and $x \in Z$. $\Phi_e^A$ can not be the characteristic function $Z$.

Hence (2) must hold. Now the claim is that

$\omega - Z = \{x : (\exists \tau \succeq \sigma)(\Phi_e^\tau(x) = 0)\}$.

To show this, if $x \in \omega - Z$, then certainly such a $\tau$ exists since $\Phi_e^A = Z$. Now suppose $x$ is in the set above. Since case (2) holds, $x \notin Z$. So $x \in \omega - Z$. Hence the claim has been shown.

The claim implies that $\omega - Z$ is $\Sigma_1^0$ definable and hence c.e. Therefore, $Z$ and $\omega - Z$ are c.e. Thus $Z$ is computable. Contradiction since it was assumed that $Z$ was incomputable c.e. at the beginning.

So it has been shown that there are no incomputable c.e. set below a 1-generic. Of course, you can show that $\mathbf{0}$ is not a 1-generic degree. Hence any 1-generic set does not have c.e. degree. As you mentioned, you can construct 1-generic set $A$ such that $A \leq_T \emptyset'$. So any 1-generic set (in particular one below $\emptyset'$) does not have c.e. degree.

Note that this proves that the degree belows $\emptyset'$ and the c.e. degrees below $\emptyset'$ are not the same.