Weak König's lemma

1. By Friedman and absoluteness: a tree in the model is infinite in the model if and only if it is infinite, and a set of the model is a path in the model if and only if it is a path.
2. ($\Rightarrow$) Given $X \in \mathcal I$, the $X$-computable tree whose paths are the $\{0, 1\}$-valued functions DNC relative to $X$ belongs to $\mathcal I$ and is infinite, so it has a path $Y \in \mathcal I$, which is PA relative to $X$. ($\Leftarrow$) Let $T \in \mathcal I$ be an infinite binary tree, and $Y \in \mathcal I$ PA relative to $T$. By the relativization of Theorem 4.2 of “PA degrees”, $Y$ computes a path of $T$, which belongs to $\mathcal I$.

Define sets $Z_0 = \emptyset$ and $Z_{n+1} = Z_n \oplus P_n$, where $P_n$ is PA relative to $Z_n$ and satisfies $(Z_n \oplus P_n)' \leq_T Z_n'$. Such a $P_n$ exists by the low basis theorem (Low basis theorem) relativized to $Z_n$, applied to the non-empty $\Pi^0_1(Z_n)$ class of $\{0,1\}$-valued functions DNC relative to $Z_n$. By induction, $Z_n' \leq_T \emptyset'$ for every $n$.

Let $\mathcal I = \{ X : \exists n\ X \leq_T Z_n \}$. It is a Turing ideal, since the sequence $Z_n$ is increasing. It is a Scott ideal: if $X \leq_T Z_n$, then $P_n \leq_T Z_{n+1}$ is in $\mathcal I$ and PA relative to $Z_n$, hence relative to $X$, and Proposition 2.3 (2) applies. Every $X \in \mathcal I$ satisfies $X' \leq_T Z_n' \leq_T \emptyset'$, so $X$ is low. In particular $\emptyset' \notin \mathcal I$, and $\mathcal I$ is not a jump ideal: it is an ω-model of $\mathsf{WKL}_0$ in which $\mathsf{ACA}_0$ fails.

($\Rightarrow$) Write $\varphi(n) \equiv \exists k\, \theta(n, k)$ and $\psi(n) \equiv \exists k\, \eta(n, k)$, with $\theta, \eta$ bounded. Let $T$ be the set of strings $\sigma$ such that for all $n, k < |\sigma|$, $\theta(n, k) \rightarrow \sigma(n) = 1$ and $\eta(n, k) \rightarrow \sigma(n) = 0$. It exists by $\Delta^0_1$ comprehension and is a tree. It is infinite: for each $m$, the string $\sigma$ of length $m$ with $\sigma(n) = 1$ if and only if $\theta(n, k)$ for some $k < m$ belongs to $T$, since no $n$ has witnesses for both formulas. A path $X$ separates: if $\varphi(n)$ with witness $k$, then $X(n) = 1$, by considering a prefix of length larger than $n$ and $k$; similarly for $\psi$.

($\Leftarrow$) Let $T$ be an infinite binary tree. For a string $\sigma$, say that $\sigma$ is extendible to length $n$ if some $\tau \succeq \sigma$ of length $n$ belongs to $T$, a bounded property. Let

and $\psi(\sigma)$ the same with $0$ and $1$ exchanged, the lengths $n$ being larger than $|\sigma|$. They are disjoint: if $\varphi(\sigma)$ with $n$ and $\psi(\sigma)$ with $n'$, say $n \leq n'$, then $\sigma 0$ is extendible to length $n'$, hence to length $n$, a contradiction; the case $n' \leq n$ is symmetric. Let $S$ separate them, with $\varphi(\sigma) \rightarrow \sigma \in S$ and $\psi(\sigma) \rightarrow \sigma \notin S$. Define $P$ by $P \uh (k+1) = (P \uh k)\, i$ with $i = 1$ if $P \uh k \in S$ and $i = 0$ otherwise; it exists by $\Delta^0_1$ comprehension.

Let $E(\sigma)$ be the $\Pi^0_1$ property ”$\sigma$ is extendible to every length”. We show $E(P \uh k)$ for every $k$ by $\Pi^0_1$ induction (Proposition 2.2 of “The base theory RCA₀”). $E(\varepsilon)$ holds since $T$ is infinite. Suppose $E(\sigma)$ with $\sigma = P \uh k$. If neither $\sigma 0$ nor $\sigma 1$ had $E$, there would be lengths beyond which neither is extendible, and $\sigma$ would not be extendible beyond their maximum. If only $\sigma 1$ has $E$, then $\varphi(\sigma)$ holds, so $\sigma \in S$ and $P$ chooses $\sigma 1$; if only $\sigma 0$ has $E$, then $\psi(\sigma)$, $\sigma \notin S$, and $P$ chooses $\sigma 0$. If both have $E$, either choice works. So $E(P \uh (k+1))$. In particular every $P \uh k$ belongs to $T$, and $P$ is a path.

For a binary string $\sigma$, let $I_\sigma$ be the closed dyadic interval $[0.\sigma, 0.\sigma + 2^{-|\sigma|}]$.

($\Rightarrow$) Let $(a_i, b_i)$ cover $[0, 1]$, and suppose that no finite subfamily does. Let $T$ be the set of strings $\sigma$ such that $I_\sigma \not\subseteq \bigcup_{i < |\sigma|} (a_i, b_i)$, a decidable condition on rational intervals. $T$ is a tree, since $I_\tau \supseteq I_\sigma$ and fewer intervals are used for a prefix $\tau$ of $\sigma$. It is infinite: for each $n$, the finite union $\bigcup_{i < n} (a_i, b_i)$ misses some point of $[0, 1]$, which can be taken rational, as an endpoint of the uncovered set, and this point lies in some $I_\sigma$ with $|\sigma| = n$, so $\sigma \in T$. By $\mathsf{WKL}$, $T$ has a path $X$. The real $x = \sum_i X(i) 2^{-i-1}$ lies in every $I_{X \uh n}$. It is covered by some $(a_i, b_i)$, so $(x - \delta, x + \delta) \subseteq (a_i, b_i)$ for some $\delta > 0$. For $n > i$ with $2^{-n} < \delta$, $I_{X \uh n} \subseteq (a_i, b_i)$, contradicting $X \uh n \in T$.

($\Leftarrow$) Let $T$ be an infinite binary tree, and suppose that it has no path. We use the Cantor middle-thirds set: for a string $\sigma$, let $C_\sigma$ be the closed interval of length $3^{-|\sigma|}$ with left endpoint $\sum_{i < |\sigma|} 2\sigma(i) 3^{-i-1}$. Consider the following intervals:

• for each string $\sigma \notin T$, the open interval $U_\sigma$ obtained by enlarging $C_\sigma$ by $3^{-|\sigma|-1}$ on each side;
• the open middle thirds removed in the construction of the Cantor set, at every level.

The sequence of these intervals exists by $\Delta^0_1$ comprehension. It covers $[0, 1]$: a real $x$ outside the removed middle thirds lies in $\bigcap_n C_{X \uh n}$ for some $X$, which can be found by deciding at each level whether $x$ is in the left or the right third; since $X$ is not a path of $T$, some $X \uh n \notin T$, and $x \in C_{X \uh n} \subseteq U_{X \uh n}$. By Heine–Borel, finitely many intervals cover $[0, 1]$; let $n$ exceed the lengths of the strings $\sigma$ whose intervals $U_\sigma$ are used. For a string $\tau$ of length $n$, the left endpoint $c$ of $C_\tau$ is a point of the Cantor set, so it lies in none of the middle thirds, and it is covered by some $U_\sigma$ in the finite family. The interval $U_\sigma$ meets the Cantor set only in $C_\sigma$, because the neighboring intervals of level $|\sigma|$ are at distance at least $3^{-|\sigma|}$. So $c \in C_\sigma$, which means that $\sigma$ is a prefix of $\tau 0 0 \cdots$; since $|\sigma| < n$, $\sigma \preceq \tau$. As $\sigma \notin T$ and $T$ is a tree, $\tau \notin T$. So $T$ has no string of length $n$, contradicting its infiniteness.