Finitely branching trees

Call a node large if infinitely many nodes of $T$ extend it. The root is large. If $\sigma$ is large, then since the nodes extending $\sigma$, other than $\sigma$, extend one of its finitely many successors, one successor is large. Define $P(n)$ as the least $v$ such that $(P \uh n)\, v$ is large. By induction every prefix of $P$ is large, hence in $T$.

$S$ is closed under prefixes by definition. A binary string $\rho$ decomposes uniquely as $c(\tau)\, 1^k$, with $\tau$ the sequence of complete blocks and $k \geq 0$. Then $\rho \in S$ if and only if $\tau \in T$ and, in case $k > 0$, some $v \geq k$ has $\tau v \in T$. This is a c.e. condition, and it is decidable when $T$ is computably bounded by $g$, since then only the values $k \leq v < g(|\tau|)$ need to be tested.

If $P \in [T]$, every prefix of $c(P)$ is a prefix of some $c(P \uh n)$, so $c(P) \in [S]$. Conversely, let $Y \in [S]$. If $Y$ had only finitely many zeros, it would end with $1^\infty$ after some $c(\tau)$, and $\tau$ would have successors $\tau v \in T$ with arbitrarily large $v$, contradicting finite branching. So $Y = c(P)$ for some $P$, and every prefix $c(P \uh n)$ of $Y$ is in $S$, which by the decomposition means $P \uh n \in T$. So $P \in [T]$.

$c([T])$ is a non-empty $\Pi^0_1$ class by Proposition 5.2 and Lemma 5.1. A PA set computes a member $c(P)$ of it (Theorem 4.2), hence the path $P$. Similarly, the basis theorems give a member $c(P)$ that is low, or computably dominated, and $P \equiv_T c(P)$.

Let $\emptyset'_s = \{ e : \Phi_e(e)[s]\converge \}$, and for $n \in \emptyset'$ let $s_n$ be the least $s$ with $n \in \emptyset'_s$. Let $T$ be the set of sequences $\sigma$ such that for every $n < |\sigma|$, either $\sigma(n) = \langle 1, s \rangle$ where $s$ is the least stage with $n \in \emptyset'_s$, or $\sigma(n) = \langle 0, 0 \rangle$ and $n \notin \emptyset'_{|\sigma|}$.

$T$ is computable: each condition is decidable. It is closed under prefixes, since $n \notin \emptyset'_{|\sigma|}$ implies $n \notin \emptyset'_{|\tau|}$ for $\tau \preceq \sigma$. Each node has at most two successors, since at position $n$ only the values $\langle 0, 0 \rangle$ and $\langle 1, s_n \rangle$ are possible.

The sequence $P$ with $P(n) = \langle 1, s_n \rangle$ for $n \in \emptyset'$ and $P(n) = \langle 0, 0 \rangle$ for $n \notin \emptyset'$ is a path: every prefix satisfies the conditions. Conversely, let $Q$ be a path. If $Q(n) = \langle 1, s \rangle$, then $n \in \emptyset'$. If $Q(n) = \langle 0, 0 \rangle$, then $n \notin \emptyset'_\ell$ for every $\ell > n$, so $n \notin \emptyset'$. Hence $Q = P$, and $\emptyset'(n)$ is the first component of $P(n)$.

A low set does not compute $\emptyset'$ (Proposition 6.2 of “Low and high sets”). Take a low PA set (Corollary 4.3) and the tree of Theorem 5.4.

($\Leftarrow$) Let $T$ be an infinite computable finitely branching tree. The binary tree $S$ of Proposition 5.2 is c.e., hence computable in $\emptyset'$, and $[S] = c([T])$ is non-empty. So $[S]$ is a non-empty $\Pi^0_1(\emptyset')$ class, and $X$, being PA relative to $\emptyset'$, computes a member $c(P)$, by Theorem 4.2 relativized to $\emptyset'$. Then $X$ computes $P$.

($\Rightarrow$) By the same characterization relativized, it suffices to show that $X$ computes a member of every non-empty $\Pi^0_1(\emptyset')$ class $[U]$, with $U$ a binary tree computable in $\emptyset'$. By the limit lemma (Shoenfield's limit lemma), $U$ has a $\Delta^0_2$ approximation $(U_s)$; replacing $U_s$ by the set of strings of length at most $s$ all of whose prefixes are in $U_s$, we may assume that each $U_s$ is a tree contained in $2^{\leq s}$, and it is still an approximation of $U$. Let $V = \bigcup_s U_s$.

$[V] = [U]$. Since $U \subseteq V$, $[U] \subseteq [V]$. Let $Y \in [V]$ and $m \in \nat$. For each $t \geq m$, $Y \uh t$ belongs to some $U_s$, with $s \geq t$ since $U_s \subseteq 2^{\leq s}$, and then $Y \uh m \in U_s$. So $Y \uh m \in U_s$ for infinitely many $s$, hence $Y \uh m \in U$, as $(U_s)$ converges.

A finitely branching tree. For $\sigma \in V$, let $f(\sigma)$ be the least $s$ with $\sigma \in U_s$. Let $T$ be the set of sequences $\langle \sigma(0), m_0 \rangle \cdots \langle \sigma(n-1), m_{n-1} \rangle$ such that, for every $i < n$, $m_i = f(\sigma \uh (i+1))$. $T$ is computable, since $m_i = f(\sigma \uh (i+1))$ is decided by testing $\sigma \uh (i+1) \in U_{m_i}$ and $\sigma \uh (i+1) \notin U_s$ for $s < m_i$. It is a tree, and each node has at most two successors, one for each bit. Its paths are the sequences $\langle Y(0), f(Y \uh 1) \rangle \langle Y(1), f(Y \uh 2) \rangle \cdots$ for $Y \in [V]$, and each such path computes $Y$ by reading the first components. It is infinite since $[V] = [U] \neq \emptyset$.

So $X$ computes a path through $T$, hence a member of $[U]$.