Minimal degrees

Case 1: some node $T(\nu)$ has no two extensions $T(\rho), T(\rho')$, with $\rho, \rho' \succeq \nu$, that form an $e$-split. Let $S$ be the full subtree above $T(\nu)$. It avoids $e$-splits.

Case 2: for every $\nu$, there are $\rho, \rho' \succeq \nu$ such that $T(\rho)$ and $T(\rho')$ form an $e$-split. Define $S(\mu) = T(\nu_\mu)$ by induction. Let $\nu_\varepsilon = \varepsilon$. Given $\nu_\mu$, search for the first pair $\rho, \rho' \succeq \nu_\mu$ such that $T(\rho)$ and $T(\rho')$ form an $e$-split, and let $\nu_{\mu 0} = \rho$ and $\nu_{\mu 1} = \rho'$. The search terminates by the hypothesis of Case 2, so $S$ is computable. The nodes $T(\rho)$ and $T(\rho')$ are incomparable, so $\rho$ and $\rho'$ are incomparable, and both strictly extend $\nu_\mu$. Hence $\mu \mapsto \nu_\mu$ preserves the prefix relation and incomparability, $S$ is an f-tree, a subtree of $T$, and it is $e$-splitting by construction.

1. To compute $\Phi^X_e(x)$, search for a node $\sigma$ of $T$ with $\Phi^\sigma_e(x)\converge$ and output its value. A long enough prefix of $X$ that is a node of $T$ has a convergent computation, so the search terminates. Two nodes of $T$ do not form an $e$-split, so the value found is the value given by the prefixes of $X$, which is $\Phi^X_e(x)$.
2. Let $Y = \Phi^X_e$. We compute, with oracle $Y$, strings $\mu_0 \prec \mu_1 \prec \cdots$ with $|\mu_n| = n$ and $T(\mu_n) \prec X$. Let $\mu_0 = \varepsilon$. Given $\mu_n$, the nodes $T(\mu_n 0)$ and $T(\mu_n 1)$ form an $e$-split; find, by a search, an $x$ with $\Phi^{T(\mu_n 0)}_e(x)\converge \neq \Phi^{T(\mu_n 1)}_e(x)\converge$. One of the two nodes is a prefix of $X$: since $X$ is a path, some node $T(\rho) \prec X$ is longer than $T(\mu_n)$; then $T(\mu_n) \prec T(\rho)$, so $\mu_n \prec \rho$, and $\rho \succeq \mu_n i$ for some $i$, which gives $T(\mu_n i) \preceq T(\rho) \prec X$. The computation of this node gives $Y(x)$, by the use principle; so exactly one of the two values equals $Y(x)$, and we let $\mu_{n+1} = \mu_n i$ for the corresponding $i$. Then $T(\mu_{n+1}) \prec X$. The nodes $T(\mu_n)$ have increasing lengths, so $X$ is computed from $Y$.

Build computable f-trees $T_0, T_1, \dots$, each a subtree of the previous one, as follows. Let $T_0$ be the identity. Given $T_{2e}$, let $T_{2e+1}$ be given by Lemma 2.2 of “Computably dominated degrees” for $T_{2e}$ and $e$. Given $T_{2e+1}$, let $S$ be given by Lemma 3.3 for $T_{2e+1}$ and $e$, and let $T_{2e+2}$ be the full subtree of $S$ above $S(0)$. Each step passes to a subtree whose root strictly extends the previous root: this holds at the odd steps, where full subtrees above $T(0)$ or $T(1)$ are taken, and at the even steps by the passage to $S(0)$. A full subtree of an $e$-splitting tree is $e$-splitting, and a subtree of a tree avoiding $e$-splits avoids them.

Let $X$ be the union of the roots $T_k(\varepsilon)$. As in the proof of Martin–Miller, $X \in [T_k]$ for every $k$.

$X$ is not computable, since $X \in [T_{2e+1}]$ gives $X \neq \Phi_e$ for every $e$.

$X$ has minimal degree. Let $Y \leq_T X$, say $Y = \Phi^X_e$. Since $X \in [T_{2e+2}]$, by Lemma 3.4, $Y$ is computable if $T_{2e+2}$ avoids $e$-splits, and $X \leq_T Y$ if it is $e$-splitting.

$X \leq_T \emptyset''$. Indices of the trees can be computed with $\emptyset''$. At the odd steps, one must decide whether $\Phi_e(i)\converge = T(0)(i)$, a $\Sigma^0_1$ question. At the even steps, one must decide which case of Lemma 3.3 holds and find $\nu$ in Case 1. The relation ”$T(\rho)$ and $T(\rho')$ form an $e$-split” is $\Sigma^0_1$, uniformly in an index of the computable tree $T$, so “no two extensions above $T(\nu)$ form an $e$-split” is $\Pi^0_1$, and the existence of such a $\nu$ is $\Sigma^0_2$; $\emptyset''$ decides it and finds the least $\nu$. The roots, hence $X$, are computable from the sequence of indices.

Relativize the construction to $A$, with $A$-computable f-trees, and start from the tree $T_0(\rho) = \rho \oplus (A \uh |\rho|)$, which interleaves the bits of $\rho$ with those of $A$; every path of every subtree computes $A$ from its odd bits. The relativized lemmas give $X \in [T_0]$ such that $X \neq \Phi^A_e$ for every $e$, and such that every $Y = \Phi^X_e$ satisfies $Y \leq_T A$ or $X \leq_T Y \oplus A$; in the splitting case, the decoding procedure needs the $A$-computable tree.

Let $B = X$. Then $A \leq_T B$, and $B \not\leq_T A$. If $A \leq_T C \leq_T B$ with $C = \Phi^B_e$, then $C \leq_T A$, or $B \leq_T C \oplus A \equiv_T C$. So there is no $C$ strictly between.