The Sacks splitting theorem

By induction on $k$. Suppose the three statements hold for all codes smaller than $k$, and let $R$ bound the restraints of all requirements of higher priority, at all stages.

Item 1. Suppose $\mathcal R_{e,i}$ is injured at stage $s + 1$, with $s \geq k$ (there are finitely many earlier stages). Then $a_s \leq r(e, i, s)$ and $k \leq s$, so the pair of smallest code at most $s$ whose restraint is at least $a_s$ has code at most $k$; since $a_s$ goes into $A_i$, this pair is some $\langle e', 1 - i \rangle$, of code smaller than $k$. So $a_s \leq r(e', 1 - i, s) \leq R$. Since the enumeration is injective, this happens for finitely many $s$. Let $s_0$ be a stage after the last injury, and after the last enumeration of a number at most $R$.

Preservation. For $s \geq s_0$, no number at most $r(e, i, s)$ enters $A_i$ at stage $s + 1$. So every computation $\Phi^{A_{i,s}}_e(x)[s]$ with $x \leq l(e, i, s)$ that converges also converges at stage $s + 1$, with the same value and use.

Item 2. Suppose, towards a contradiction, that $\Phi^{A_i}_e = B$. Then $l(e, i, s) \to \infty$: for each $y$, once $A_i$ has settled below the uses of the computations $\Phi^{A_i}_e(x)$ for $x < y$, and $B$ has settled below $y$, these computations converge with the correct values at all large stages. We show that $B$ is computable, by the following procedure: to compute $B(p)$, find a stage $s \geq s_0$ with $l(e, i, s) > p$, and output $B_s(p)$.

Suppose the output is wrong for some $p$. Since $B$ is c.e., $B_s(p) = 0$ and $p$ enters $B$ after stage $s$. Let $q \leq p$ be the least number that enters $B$ after stage $s$. We claim that for all $t \geq s$, the computations $\Phi^{A_{i,t}}_e(x)[t]$ for $x \leq q$ are the ones found at stage $s$, and $l(e, i, t) \geq q$. This holds at $t = s$. If it holds at $t$, then $q \leq l(e, i, t)$, so the restraint $r(e, i, t)$ covers the uses of these computations, which are preserved at stage $t + 1$. Their values at $x < q$ equal $B_s(x) = B_{t+1}(x)$, since no $x < q$ enters $B$ after stage $s$, so $l(e, i, t + 1) \geq q$. Hence $\Phi^{A_i}_e(q) = \Phi^{A_{i,s}}_e(q)[s] = B_s(q) = 0$, while $q \in B$: this contradicts $\Phi^{A_i}_e = B$. So the procedure computes $B$, contradicting the hypothesis on $B$.

Item 3. By item 2, let $p$ be the least number with $\Phi^{A_i}_e(p) \neq B(p)$, either because $\Phi^{A_i}_e(p)$ diverges or because it converges to another value. For $x < p$, the computation $\Phi^{A_i}_e(x)$ converges to $B(x)$; once $A_i$ has settled below its use and $B$ has settled below $p + 1$, the computation found at each large stage is this one, with a fixed use. So $l(e, i, s) \geq p$ for all large $s$.

We show that $l(e, i, s) \leq p$ for all large $s$. If $\Phi^{A_i}_e(p)$ converges to a value different from $B(p)$, then at large stages the computation at $p$ is the true one and disagrees with $B_s(p) = B(p)$. If $\Phi^{A_i}_e(p)$ diverges, suppose $l(e, i, s) > p$ for some $s \geq s_0$ at which $B$ has settled below $p + 1$. Then the computations at $x \leq p$ converge at stage $s$; by preservation and since $B$ no longer changes below $p + 1$, they converge at every later stage with $l(e, i, t) > p$, so $\Phi^{A_i}_e(p)$ converges, a contradiction.

So $l(e, i, s) = p$ for all large $s$. The restraint is then the maximum of the uses of the computations at $x < p$, which are eventually fixed, and of the use of the computation at $p$, if it converges. In the first case, the latter is eventually the true computation, with a fixed use. In the second case, a computation at $p$ converging at a stage $s \geq s_0$ with $l(e, i, s) = p$ would be preserved forever, so that $\Phi^{A_i}_e(p)$ would converge; hence the computation at $p$ eventually diverges at every stage. In both cases $r(e, i, s)$ is eventually constant.

The sets $A_0$ and $A_1$ are c.e., disjoint, with union $A$, and computable in $A$. By Lemma 4.3, $\Phi^{A_i}_e \neq B$ for every $e$ and $i$, so neither $A_0$ nor $A_1$ computes $B$.

We prove item 2 first. Apply Theorem 4.1 with $B = A$. Then $A_i \leq_T A$ and $A \not\leq_T A_i$. Since $x \in A$ if and only if $x \in A_0$ or $x \in A_1$, we have $A \leq_T A_0 \oplus A_1$. If $A_0 \leq_T A_1$, then $A \leq_T A_0 \oplus A_1 \leq_T A_1$, a contradiction; so $A_0 \not\leq_T A_1$, symmetrically $A_1 \not\leq_T A_0$, and in particular neither $A_i$ is computable.

Item 1 is item 2 with $A = \emptyset'$.

Let $A \in \abf$ be c.e., and $A_0, A_1$ as in Corollary 4.4. Then $\deg_T(A_0)$ is strictly between $\obf$ and $\abf$. Moreover $A_0 \oplus A_1 \equiv_T A$: one direction was shown above, and $A_0, A_1 \leq_T A$ gives the other.