Computable members

Let $\mathcal P = [T]$ with $T$ computable. By Proposition 1.9, the set of extendible nodes of $T$ is co-c.e., hence computable in $\emptyset'$. Define $X$ by induction: $X(n) = 0$ if $(X \uh n)\, 0$ is extendible, and $X(n) = 1$ otherwise. Since $X \uh n$ is extendible, one of its two successors is, so every $X \uh n$ is extendible, and $X \in [T]$. The construction asks finitely many questions to $\emptyset'$ at each step. The sequence $X$ is the leftmost path of $T$, that is, the least member of $\mathcal P$ in the lexicographic order.

Let $\mathcal P = [T]$ with $T$ computable, and $\sigma \prec X$ with $[\sigma] \cap \mathcal P = \{ X \}$. We compute $X(n)$ for $n \geq |\sigma|$ by induction, the bits below $|\sigma|$ being given by $\sigma$. Suppose $\tau = X \uh n$ is known, with $n \geq |\sigma|$. The two strings $\tau 0$ and $\tau 1$ extend $\sigma$; the one that is a prefix of $X$ is extendible, and the other one is not, since a path through it would be a second member of $[\sigma] \cap \mathcal P$. Non-extendibility is a $\Sigma^0_1$ property (Proposition 1.9), so a search eventually finds which of $\tau 0$ and $\tau 1$ is not extendible, and never wrongly reports the other one. Set $X(n)$ to the other bit.

Let $\mathcal P = [T]$, with $T$ the tree of prefixes of members of $\mathcal P$, so that every node of $T$ is extendible. We define strings $\sigma_\rho \in T$, for $\rho \in \bstr$, such that $\sigma_{\rho 0}$ and $\sigma_{\rho 1}$ are incompatible extensions of $\sigma_\rho$. Let $\sigma_\varepsilon = \varepsilon$. Given $\sigma_\rho \in T$, let $X$ be a member of $\mathcal P$ through $\sigma_\rho$. Since $X$ is not isolated, $[\sigma_\rho] \cap \mathcal P$ contains a member $Y \neq X$. If $n$ is the first position where they differ, the strings $X \uh (n+1)$ and $Y \uh (n+1)$ are incompatible extensions of $\sigma_\rho$ in $T$. Let $\sigma_{\rho 0}, \sigma_{\rho 1}$ be the first pair of incompatible extensions of $\sigma_\rho$ in $T$, in a fixed enumeration of pairs of strings; this avoids any arbitrary choice.

For $Z \in \cs$, the classes $[\sigma_{Z \uh k}] \cap \mathcal P$ form a decreasing sequence of non-empty closed classes, so their intersection is non-empty (Proposition 1.5), and it contains a single sequence $X_Z$, since the lengths of the strings $\sigma_{Z \uh k}$ increase. If $Z \neq Z'$ first differ at position $k$, then $X_Z$ and $X_{Z'}$ extend the incompatible strings $\sigma_{(Z \uh k) 0}$ and $\sigma_{(Z \uh k) 1}$, so they are different.

1. A countable non-empty closed class is not perfect, by Theorem 2.4, so it has an isolated member, which is computable by Proposition 2.3. In a finite class, every member is isolated.
2. If the class had an isolated member, this member would be computable. So the class is perfect, and Theorem 2.4 applies.

A set $X$ satisfies $X(e) \neq \Phi_e(e)$ for all $e$ with $\Phi_e(e)\converge$ if and only if $X(e) = 1$ for $e \in A$ and $X(e) = 0$ for $e \in B$, since $X(e)$ can only equal $0$ or $1$; so $\mathrm{DNC}_2$ is the class of separating sets $\mathcal S(A, B)$, which is $\Pi^0_1$ by Example 1.8. It is non-empty: $A$ itself separates $A$ from $B$.

Suppose $X \in \mathrm{DNC}_2$ is computable, and let $c$ be an index of its characteristic function, so that $\Phi_c$ is total with values in $\{0, 1\}$. Then $\Phi_c(c)\converge = X(c)$, contradicting $X(c) \neq \Phi_c(c)$.