Low and high sets

1. If $A$ is computable, $A' \equiv_T \emptyset'$ by monotonicity of the jump. If $A$ is low, $A \leq_T A' \leq_T \emptyset'$.
2. $B' \leq_T A' \leq_T \emptyset'$.
3. If $\emptyset' \leq_T A$, then $\emptyset'' \leq_T A'$, and lowness would give $\emptyset'' \leq_T \emptyset'$, contradicting Theorem 3.2.
4. An $A$-c.e. set is one-one reducible to $A'$ (Theorem 3.2), which is computable in $\emptyset'$.

For each $e$, let $V_e = \{ \sigma : \Phi^\sigma_e(e)\converge \}$, a c.e. set of strings, uniformly in $e$. Consider the following procedure with oracle $G \oplus \emptyset'$. On input $e$, for $n = 0, 1, 2, \dots$, let $\sigma = G \uh n$, and

• ask $\emptyset'$ whether $\sigma \in V_e$; if so, answer $e \in G'$;
• ask $\emptyset'$ whether some extension of $\sigma$ belongs to $V_e$; if not, answer $e \notin G'$.

Both questions are c.e., uniformly in $e$ and $\sigma$, so $\emptyset'$ answers them. Since $G$ is 1-generic, some prefix of $G$ is in $V_e$ or has no extension in $V_e$, so the procedure terminates. The answers are correct: if $G \uh n \in V_e$, then $\Phi^G_e(e)\converge$ by Proposition 1.5; if $G \uh n$ has no extension in $V_e$, then $\Phi^G_e(e)\diverge$, since otherwise $\Phi^{G \uh k}_e(e)\converge$ for some $k \geq n$, and $G \uh k$ is an extension of $G \uh n$ in $V_e$.

Let $G \leq_T \emptyset'$ be 1-generic (Proposition 5.7). It is not computable, and $G' \leq_T G \oplus \emptyset' \equiv_T \emptyset'$.

Conditions. A condition is a pair $(\sigma, m)$ of a string and an integer. It represents the sets

beyond $\sigma$, the columns $x < m$ are fixed to their limit value. A condition $(\tau, n)$ extends $(\sigma, m)$ if $n \geq m$ and $[\tau, n] \subseteq [\sigma, m]$; for $n = m$, this means that $\sigma \preceq \tau$ and $\tau(\langle x, y \rangle) = \emptyset''(x)$ for every position $\langle x, y \rangle$ with $|\sigma| \leq \langle x, y \rangle < |\tau|$ and $x < m$. Every set $[\sigma, m]$ is non-empty. For a fixed $m$, the relation ”$(\tau, m)$ extends $(\sigma, m)$” is computable: it only involves the finite string $\emptyset'' \uh m$, which can be written into the algorithm.

Requirements. For each $e$, $\mathcal S_e : \Phi^A_e \neq C$.

Construction. Start with $(\sigma_0, m_0) = (\varepsilon, 0)$. At step $e$, given $(\sigma_e, m_e)$, find an extension $(\tau, m_e)$ forcing $\mathcal S_e$, that is, such that every $X \in [\tau, m_e]$ satisfies $\Phi^X_e \neq C$, as shown below. Then let $m_{e+1} = m_e + 1$ and let $\sigma_{e+1}$ extend $\tau$ by one bit, chosen so that $(\sigma_{e+1}, m_{e+1})$ extends $(\tau, m_e)$. Let $A$ be the unique set extending all $\sigma_e$.

Forcing $\mathcal S_e$. Write $(\sigma, m) = (\sigma_e, m_e)$. Three cases are possible.

1. There are $x$ and an extension $(\tau, m)$ of $(\sigma, m)$ with $\Phi^\tau_e(x)\converge \neq C(x)$. Then every $X \in [\tau, m]$ satisfies $\Phi^X_e(x)\converge \neq C(x)$, by the use principle.
2. There is $x$ such that no extension $(\tau, m)$ of $(\sigma, m)$ has $\Phi^\tau_e(x)\converge$. Then every $X \in [\sigma, m]$ satisfies $\Phi^X_e(x)\diverge$: otherwise $\Phi^{X \uh k}_e(x)\converge$ for some $k \geq |\sigma|$, and $(X \uh k, m)$ is an extension of $(\sigma, m)$, since $X \in [\sigma, m]$. Take $\tau = \sigma$.
3. Neither case holds. Then $C$ is computable: to compute $C(x)$, search for $\tau$ such that $(\tau, m)$ extends $(\sigma, m)$ and $\Phi^\tau_e(x)\converge$, and output the value. The search terminates since case 2 fails, and the value is $C(x)$ since case 1 fails. The search is computable, since the extension relation with second component $m$ is. This contradicts the hypothesis on $C$.

Verification. Each condition of the construction extends the previous ones, and $A$ belongs to every $[\sigma_e, m_e]$: a position $\langle x, y \rangle \geq |\sigma_e|$ with $x < m_e$ lies below $|\sigma_k|$ for some $k > e$, and the bit placed there respects the column constraint of every condition in force, all of which fix column $x$ to $\emptyset''(x)$. So $A \in [\tau, m_e]$ for the condition $(\tau, m_e)$ chosen at step $e$, every $\mathcal S_e$ is satisfied, and $C \not\leq_T A$. Fix $x$. For $e > x$, we have $m_e > x$, and every position $\langle x, y \rangle \geq |\sigma_{x+1}|$ is assigned the value $\emptyset''(x)$ by the construction. Hence $A(\langle x, y \rangle) = \emptyset''(x)$ for all but finitely many $y$. The sets $A_y = \{ x : A(\langle x, y \rangle) = 1 \}$ form an $A$-computable $\Delta^0_2$ approximation of $\emptyset''$, so $\emptyset'' \leq_T A'$ by Theorem 4.2 relativized to $A$.

Apply Theorem 6.6 with $C = \emptyset'$.