The finite extension method

Let $h$ be any function with $h(n, \sigma) \succeq \sigma$ and $h(n, \sigma) \in D_n$ for all $n$ and $\sigma$; for the first statement, take $h(n, \sigma)$ to be the first extension of $\sigma$ in $D_n$, in a fixed computable enumeration of $\bstr$. Define $\sigma_0 = \varepsilon$ and $\sigma_{n+1} = h(n, \sigma_n)\, 0$. The strings $\sigma_0 \prec \sigma_1 \prec \cdots$ have strictly increasing lengths, and determine a unique $X$ with $\sigma_n \prec X$ for every $n$. Since $h(n, \sigma_n) \prec X$ belongs to $D_n$, $X$ meets $D_n$. If $h$ is $Z$-computable, so is the sequence $(\sigma_n)$, and $X(k)$ is the bit at position $k$ of $\sigma_{k+1}$, whose length exceeds $k$; so $X \leq_T Z$.

We build $A$ and $B$ together, by finite extensions of a pair of strings. The requirements are, for every $e$:

If all are satisfied, then $A \not\leq_T B$ and $B \not\leq_T A$. Here $\Phi^A_e \neq B$ means that for some $x$, either $\Phi^A_e(x)\diverge$ or $\Phi^A_e(x)\converge \neq B(x)$.

We define pairs of strings $(\sigma_n, \tau_n)$ with $\sigma_n \preceq \sigma_{n+1}$ and $\tau_n \preceq \tau_{n+1}$, starting from $(\varepsilon, \varepsilon)$, and let $A$ and $B$ be the limits. At step $n = 2e$ we satisfy $\mathcal R_e$, at step $n = 2e + 1$ we satisfy $\mathcal S_e$, and at the end of each step we append the bit $0$ to both strings, so that the lengths tend to infinity.

Satisfying $\mathcal R_e$. Let $x = |\tau_n|$, the first position at which $B$ is not yet determined.

• If there is a string $\sigma \succeq \sigma_n$ with $\Phi^\sigma_e(x)\converge$, take the string $\sigma$ of the first pair $(\sigma, s)$, in a fixed computable enumeration of pairs, such that $\sigma \succeq \sigma_n$ and $\Phi^\sigma_e(x)[s]\converge$; let $i = \Phi^\sigma_e(x)$, and set $\sigma_{n+1} = \sigma$ and $\tau_{n+1} = \tau_n\, j$ with $j = 1 - i$ if $i \in \{0, 1\}$ and $j = 0$ otherwise. For every $A \succ \sigma$, the use principle gives $\Phi^A_e(x) = i \neq B(x)$.
• Otherwise, set $\sigma_{n+1} = \sigma_n$ and $\tau_{n+1} = \tau_n$. For every $A \succ \sigma_n$, $\Phi^A_e(x)\diverge$: a convergent computation would converge already with a prefix of $A$ extending $\sigma_n$ (Proposition 1.5).

In both cases, $\mathcal R_e$ holds for every pair of sets extending $(\sigma_{n+1}, \tau_{n+1})$, and therefore for $(A, B)$. The requirements $\mathcal S_e$ are satisfied symmetrically.

Effectivity. The only non-computable step is the case distinction, the question “is there $\sigma \succeq \sigma_n$ with $\Phi^\sigma_e(x)\converge$?”. It is a c.e. question about $(e, x, \sigma_n)$, so $\emptyset'$ answers it; and in the first case, the string $\sigma$ is then found by a computable search. So the whole sequence of pairs is computable in $\emptyset'$, and so are $A$ and $B$.

The first statement is the theorem. For the second, take $\abf = \deg_T(A)$. If $A$ were computable, then $A \leq_T B$. If $A \equiv_T \emptyset'$, then $B \leq_T \emptyset' \leq_T A$. Both are excluded, so $\obf < \abf < \obf'$.

Every $X$ meeting $D_e$ satisfies $\Phi^X_e \neq C$: in the first case, $\Phi^X_e(x)\converge \neq C(x)$ by the use principle; in the second, $\Phi^X_e(x)\diverge$ by Proposition 1.5.

Let $\sigma$ be a string, and suppose that no extension of $\sigma$ belongs to $D_e$. Then for every $x$ there is $\rho \succeq \sigma$ with $\Phi^\rho_e(x)\converge$, since otherwise $\sigma$ itself would be in the second part of $D_e$; and for every such $\rho$, $\Phi^\rho_e(x) = C(x)$, since otherwise $\rho$ would be in the first part. Then $C$ is computable: to compute $C(x)$, search for a string $\rho \succeq \sigma$ and a stage $s$ with $\Phi^\rho_e(x)[s]\converge$, and output its value. This contradicts the hypothesis on $C$. So $D_e$ is dense.

By Lemma 5.2, some $B$ meets every $D_e$, and then $C \not\leq_T B$. To ensure also $B \not\leq_T A$, add the dense sets $E_e = \{ \tau : \exists x < |\tau|\ \ \Phi^A_e(x)\converge \neq \tau(x) \} \cup \{ \tau : \exists x < |\tau|\ \ \Phi^A_e(x)\diverge \}$: given $\sigma$, let $x = |\sigma|$; if $\Phi^A_e(x)\converge = i$, the string $\sigma\, (1 - i)$ belongs to $E_e$ (with $1 - i$ replaced by $0$ if $i \notin \{0, 1\}$), and otherwise $\sigma 0$ does. A set meeting every $E_e$ is not computable in $A$.

1. Fix a computable enumeration $(W'_n)$ of the c.e. sets of strings, say $W'_n = \{ \tau : \text{the code of } \tau \text{ is in } W_n \}$. The sets $D_n = W'_n \cup \{ \sigma : \forall \tau \succeq \sigma\ \tau \notin W'_n \}$ are dense: a string either has an extension in $W'_n$, or belongs to the second part. The function $h(n, \sigma)$ which asks $\emptyset'$ whether some $\tau \succeq \sigma$ belongs to $W'_n$ — a c.e. question — and returns the first such $\tau$ found by enumerating $W'_n$ if so, and $\sigma$ otherwise, is computable in $\emptyset'$. Apply Lemma 5.2.
2. Let $G$ be 1-generic. First, $G$ is infinite: for each $m$, every string has an extension in the c.e. set $V_m = \{ \sigma : \exists x \geq m\ \sigma(x) = 1 \}$, so $G$ cannot have a prefix without extension in $V_m$, and therefore meets $V_m$; that is, $G$ has an element $x \geq m$. Symmetrically, $\nat \setminus G$ is infinite. Now suppose $G$ is c.e. The set $W = \{ \sigma : \exists x < |\sigma|\ (\sigma(x) = 0 \wedge x \in G) \}$ is c.e., and no prefix of $G$ belongs to it, since a prefix of $G$ has the bit $1$ at every element of $G$. So some $\sigma \prec G$ has no extension in $W$. But if $x \geq |\sigma|$ belongs to $G$, the string obtained by extending $\sigma$ with $0$s up to position $x$ included is in $W$. Hence $G$ has no element $x \geq |\sigma|$, contradicting its infiniteness. If $\nat \setminus G$ is c.e., the same argument applies to $W = \{ \sigma : \exists x < |\sigma|\ (\sigma(x) = 1 \wedge x \notin G) \}$, and shows that $\nat \setminus G$ is finite. In particular $G$ is not computable.