Ramsey's theorem in the arithmetic hierarchy

1. For $f : \nat \to k$, the sets $C_i = \{ x : f(x) = i \}$ exist. If all were finite, bounded by $b_i$, then $\max_i b_i$ would bound $\nat$. So some $C_i$ is infinite, and it is homogeneous.
2. Let $p$ enumerate $X$ in increasing order; it exists in $\mathsf{RCA}_0$ when $X$ is infinite. Apply $\mathsf{RT}^n_2$ to $g(\{ x_1, \dots, x_n \}) = f(\{ p(x_1), \dots, p(x_n) \})$, and take the image of a homogeneous set under $p$.
3. By induction on $k$ in the metatheory. Given $f : [\nat]^n \to k + 1$, merge the colors $k - 1$ and $k$, and apply $\mathsf{RT}^n_k$ to obtain an infinite $H$. If its color is less than $k - 1$, $H$ is homogeneous for $f$; otherwise $f$ takes only the values $k - 1$ and $k$ on $[H]^n$, and (2) gives a homogeneous subset.

We build $T$ by inserting the numbers $0, 1, 2, \dots$ one at a time. The first $n$ numbers form a single branch $\langle 0, 1, \dots, n - 1 \rangle$. To insert $s \geq n$, start at this branch and descend: at a node $\sigma$, call pattern of a number $a$ over $\sigma$ the tuple of colors $f(\{ \sigma(m_1), \dots, \sigma(m_n), a \})$ for $m_1 < \cdots < m_n < |\sigma|$. If $\sigma$ has an immediate successor $\sigma\, a$ in the current tree such that $a$ and $s$ have the same pattern over $\sigma$, move to $\sigma\, a$; otherwise add $\sigma\, s$ to the tree and stop.

$T$ is $f$-computable and infinite. To decide whether a sequence $\sigma\, s$ belongs to $T$, simulate the insertion of $0, \dots, s$. Every number is inserted, so $T$ is infinite.

$T$ is finitely branching. Two immediate successors $\sigma a$ and $\sigma b$ of a node, with $a < b$, have different patterns over $\sigma$: otherwise $b$ would have moved to $\sigma a$ instead of creating $\sigma b$. So $\sigma$ has at most $k^{\binom{|\sigma|}{n}}$ successors.

Paths are pre-homogeneous. Let $P$ be an infinite path, $j < j'$, $a = P(j)$ and $b = P(j')$. When $b$ was inserted, it descended along $P \uh j'$, hence moved from $P \uh j$ to $P \uh (j + 1) = (P \uh j)\, a$, so $a$ and $b$ have the same pattern over $P \uh j$. For $x_1 < \cdots < x_n$ in the range of $P$, at positions $m_1 < \cdots < m_n$, and $y = P(j)$, $y' = P(j')$ with $m_n < j < j'$, this gives $f(\{ x_1, \dots, x_n, y \}) = f(\{ x_1, \dots, x_n, y' \})$.

Computing a path. The number of successors of each node is bounded, but their values are not: whether $\sigma$ has a successor above a given number is a $\Sigma^0_1(f)$ question. With $f'$, one computes, for each node, the finite list of its successors. Coding each successor by its rank in this list, the paths of $T$ correspond, computably in $f'$, to the paths of an $f'$-computable tree in $\prod_\sigma k^{\binom{|\sigma|}{n}}$, a $\Pi^0_1(f')$ class after coding into Cantor space. It is non-empty by König’s lemma. A set PA relative to $f'$ computes a member of it (Theorem 4.2 of “PA degrees”, relativized), and it computes $f'$ itself (second exercise of PA degrees, relativized to $f'$), so it computes a path of $T$.

By induction on $n$, for all colorings $f$ simultaneously. For $n = 1$, $f$ itself computes a homogeneous set, and a set PA relative to $f$ computes $f$.

For $n = 2$, let $P$ be PA relative to $f'$. By Proposition 1.4, $P$ computes an infinite pre-homogeneous set $X$, the induced coloring $g$ of $[X]^1$ is computable in $P$, and so is a homogeneous set for $g$, which is homogeneous for $f$.

For $n + 1$ with $n \geq 2$, let $P_1$ be PA relative to $f^{(n)}$. By the low basis theorem relativized to $f'$, there is $P_0$ PA relative to $f'$ with $P_0' \leq_T f''$; then $P_0^{(n-1)} \leq_T f^{(n)}$, since $n - 1 \geq 1$. $P_0$ computes an infinite pre-homogeneous set $X$ and the induced coloring $g$ of $[X]^n$, so $g^{(n-1)} \leq_T P_0^{(n-1)} \leq_T f^{(n)}$, and $P_1$ is PA relative to $g^{(n-1)}$. By the induction hypothesis, applied to $g$ transported to $[\nat]^n$ through the enumeration of $X$, $P_1$ computes an infinite homogeneous set for the transported coloring; its image under the enumeration of $X$ is computable in $P_1$, since $X \leq_T P_0 \leq_T f'' \leq_T P_1$, and it is homogeneous for $g$, hence for $f$.

For the last statement, $\emptyset^{(n)}$ is PA relative to $\emptyset^{(n-1)}$: it computes a $\{0, 1\}$-valued function DNC relative to $\emptyset^{(n-1)}$.

For each $e$ and $s$, let $A_{e,s} = \{ x < s : \Phi^{\emptyset'_s}_e(x)[s]\converge = 1 \}$, where $\emptyset'_s$ is the stage $s$ approximation of $\emptyset'$. If $\Phi^{\emptyset'}_e$ is the characteristic function of a set $A$, then for every $x$, $x \in A_{e,s}$ for all large $s$ if $x \in A$, and $x \notin A_{e,s}$ for all large $s$ otherwise. Every $\Delta^0_2$ set is of this form, by the limit lemma.

Define $f(\{ x, s \})$ for $x < s$ at stage $s$: for $e = 0, 1, \dots, s - 1$ in turn, if $A_{e,s}$ has at least $2e + 2$ elements, choose the two least elements $a < b$ of $A_{e,s}$ for which $f(\{ a, s \})$ and $f(\{ b, s \})$ are not yet defined, and set $f(\{ a, s \}) = 0$ and $f(\{ b, s \}) = 1$. Before $e$ acts, at most $2e$ values $f(\{ x, s \})$ have been defined, so the two elements exist. All remaining values $f(\{ x, s \})$ are set to $0$. The coloring is computable.

Let $A = \Phi^{\emptyset'}_e$ be an infinite $\Delta^0_2$ set, and $n$ such that $A \cap \{0, \dots, n-1\}$ has exactly $2e + 2$ elements. For large enough $s \in A$, $A_{e,s} \cap \{0, \dots, n-1\} = A \cap \{0, \dots, n-1\}$. At stage $s$, the $2e + 2$ least elements of $A_{e,s}$ are those of $A$ below $n$, and $e$ chooses two of them, $a$ and $b$, with $f(\{ a, s \}) \neq f(\{ b, s \})$. Since $a, b, s \in A$, $A$ is not homogeneous.

Finally, every infinite $\Sigma^0_2$ set $B = \{ x : \exists y\, \forall z\, R(x, y, z) \}$, with $R$ computable, has an infinite $\Delta^0_2$ subset: with $\emptyset'$, search for pairs $(x, y)$ with $\forall z\, R(x, y, z)$, and keep an increasing sequence of the first coordinates found. A subset of a homogeneous set is homogeneous.

By the limit lemma, $h(\{ x_1, \dots, x_n \}) = \lim_t f(\{ x_1, \dots, x_n, t \})$ for a computable function $f$ defined for $x_1 < \cdots < x_n < t$; replacing the values outside $k$ by $0$, which does not change the limit, $f$ is a coloring $[\nat]^{n+1} \to k$. Let $H$ be infinite and homogeneous for $f$ with color $i$. For $x_1 < \cdots < x_n$ in $H$, take $t \in H$ large enough that $f(\{ x_1, \dots, x_n, t \}) = h(\{ x_1, \dots, x_n \})$; this value is $i$.

Let $m(x)$ be the least $s$ with $\emptyset'_s \cap \{0, \dots, x - 1\} = \emptyset' \cap \{0, \dots, x - 1\}$, a $\emptyset'$-computable function. Let $h(\{ x, y \}) = 1$ if $m(x) < y$ and $0$ otherwise, for $x < y$. An infinite homogeneous set $H$ for $h$ has color $1$: color $0$ would give $m(x) \geq y$ for all $y > x$ in $H$. So for consecutive elements $x < y$ of $H$, $\emptyset' \cap \{0, \dots, x-1\} = \emptyset'_y \cap \{0, \dots, x-1\}$, and $H$ computes $\emptyset'$. Apply Lemma 1.7.

$\mathsf{ACA}_0$ proves $\mathsf{RT}^n_k$, by induction on $n$ in the metatheory. The case $n = 1$ is Proposition 1.2. Given $f : [\nat]^{n+1} \to k$, the Erdős–Radó tree exists by $\Delta^0_1$ comprehension, and $\mathsf{RCA}_0$ proves that it is infinite and finitely branching. By König’s lemma (Theorem 1.6 of “Arithmetic comprehension”), it has a path, which is pre-homogeneous. The induction hypothesis, with Proposition 1.2 (2), whose proof applies to any number of colors, gives a homogeneous set for the induced coloring.

$\mathsf{RT}^3_2$ implies $\mathsf{ACA}_0$. We prove that $X'$ exists, using Theorem 1.2 of “Arithmetic comprehension”. Define $f(\{ x, s, t \}) = 1$ for $x < s < t$ if every $e < x$ satisfies $\Phi^X_e(e)[s]\converge \leftrightarrow \Phi^X_e(e)[t]\converge$, and $0$ otherwise. Let $H$ be infinite and homogeneous. Its color is $1$: for $x \in H$, among $2^x + 1$ elements of $H$ above $x$, two have the same pattern of convergence for the indices $e < x$, by the finite pigeonhole principle, provable in $\mathsf{RCA}_0$. For each $e$, let $x_e$ be the least element of $H$ above $e$ and $s_e$ the least element of $H$ above $x_e$. If $\Phi^X_e(e)[t_0]\converge$ for some $t_0$, take $t \in H$ above $s_e$ and $t_0$, so that $\Phi^X_e(e)[t]\converge$; then $f(\{ x_e, s_e, t \}) = 1$ gives $\Phi^X_e(e)[s_e]\converge$. So $X' = \{ e : \Phi^X_e(e)[s_e]\converge \}$, which exists by $\Delta^0_1$ comprehension relative to $X \oplus H$.

For $n \geq 3$, $\mathsf{RT}^n_2$ implies $\mathsf{RT}^3_2$: a coloring $f$ of triples induces the coloring $\{ x_1, \dots, x_n \} \mapsto f(\{ x_1, x_2, x_3 \})$ of $n$-tuples, with the same infinite homogeneous sets.

By Theorem 2.4 of “Weak König's lemma”, there is an ω-model of $\mathsf{WKL}_0$ consisting of low sets, hence of $\Delta^0_2$ sets. The computable coloring of Theorem 1.6 belongs to it and has no homogeneous set in it.