Deriving Konig's Lemma directly from Infinite Ramsey's Theorem for triples

Question

Let KL denote König's Lemma (for trees over $\mathbb{N}$), and RT(3) denote the Infinite Ramsey Theorem for triples over $\mathbb{N}$ (notation as in Simpson's book Subsystems of second order arithmetic, 2ed, 2009, see definitions below).

Question: Is there a simple direct derivation of KL from RT(3)?

KL, RT(3), and ACA$_0$ are equivalent over RCA$_0$, and Simpson's book has proofs (in RCA$_0$) of the following implications: ACA$_0$ $\implies$ KL $\implies$ RT(3) $\implies$ ACA$_0$.

I am looking for a direct "simple" proof of RT(3) $\implies$ KL (formalizable in RCA$_0$ and without having to go through an intermediate ACA$_0$).

Definitions

1. Here KL (König's Lemma) is the statement "Every finitely branching infinite tree over $\mathbb{N}$ has an infinite branch", where (a) $T$ is a tree over $\mathbb{N}$ if $T$ is a set of finite sequences from $\mathbb{N}$ such that any initial segment of any sequence in $T$ is in $T$, (b) $T$ is finitely branching if for any sequence $u \in T$ there are at most finitely many sequences in $T$ of length $\operatorname{length}(u)+1$ which extend $u$, and (c) a branch of a tree is a maximal linearly ordered subset of it (under the relation $u \preceq v$ iff $u$ is an initial segment of $v$).

2. RT(3) (Infinite Ramsey Theorem for triples) is the statement "If $F$ is a finite set and $f \colon [\mathbf{N}]^3 \to F$, then there is an infinite subset $H$ of $\mathbb{N}$ such that $f$ is constant on $[H]^3$", where $[X]^n$ denotes the set of all $n$-element subsets of $X$ (for any set $X$).

Answer 1

Here is an attempt...

The function $\Delta:[\mathbb{N}^{< \omega}]^2 \rightarrow \mathbb{N}$ is given by $\Delta(a,b)$ is the largest natural number $i$ such that $\langle a(0), a(1) \ldots a(i-1)\rangle = \langle b(0), b(1) \ldots b(i-1)\rangle$. If $a =b$ then this is the length of $a$, and if $a$ is an initial segment of $b$ then this is again the length of $a$. The point is that $\Delta(a,b)$ is the length at which $a$ and $b$ `branch'.

Now, let $T \subseteq \mathbb{N}^{< \omega}$ be a finitely branching infinite tree. Define the function $f: [T]^{3} \rightarrow 3$ by $f(a,b,c) = 0$ if $|\{ \Delta(a,b) , \Delta(a,c), \Delta(c,b)\}| = 1$, that is, if all three of them branch off at the same point. Otherwise, $f(a,b,c) = 1$ if $a< b < c$ (in the lexicographic order on $\mathbb{N}^{< \omega}$) and $\Delta(a,b) > \Delta(b,c)$. If not, let $f(a,b,c) = 2$. If $H$ is an infinite homogenous set for $f$, as $T$ is finitely branching, $f[H]$ cannot be $\{0\}$. Hence, it must be either $\{1\}$ or $\{2\}$. We observe that in either case, if $\{a,b,c\}$ is a subset of $H$, then if $a < b < c$ is their order lexicographically, then it is not possible that $\Delta(a,b) = \Delta(b,c)$, as this implies that $\Delta(a,b) = \Delta(b,c) = \Delta(c,a)$.

Now, suppose $f[H] = \{1\}$. Let $a < b < c < d$ be in $H$ then $\Delta(a,b) > \Delta(b,c) > \Delta(c,d)$. It follows that $H$ cannot contain an infinite lexicographically increasing sequence. Assuming that we can get an actual decreasing sequence $\langle a_i\rangle$ in $H$, we can choose a branch through $T$ by taking the union of all those elements of $T$ which are initial segments of cofinitely many of the $a_i$. This is a computable procedure because the first $n$ digits are fixed $a_{n+1}$ onwards.

So to pick this infinite decreasing sequence, do this naively, namely, if you have made the choices upto $i$, let $a_{i+1}$ be any element in $H$ which is lexicographically below $a_i$. To find such an an element you only need to look at more elements than the length of $a_i$ (here again we use the fact that if $a,b,c$ are distinct elements of $H$ then $|\{ \Delta(a,b) , \Delta(a,c), \Delta(c,b)\}| = 2$, so if you look at more elements than the length of $a_i$, you must find two elements which branch off from $a_i$ at the same point. If neither of them is smaller than $a_i$, then we have a situation like this: $a_i < b < c$ and $\Delta(a_i, b) = \Delta(a_i, c) < \Delta(b,c)$, which is not possible by the homogeniety of $H$ with respect to $f$).

The proof for the case of $f[H] = \{2\}$ is similar.

Answer 2

Here is a simple direct derivation of $\mathsf{WKL}$ from $\mathsf{RT}^3_3$; a similar idea ought to work for the more general principle $\mathsf{KL}$ but I haven't worked that out.

Given a (downward closed) tree $T \subseteq 2^{\lt\infty}$ define the coloring $c:[T]^3\to\lbrace-1,0,+1\rbrace$ as follows. If $t,u,v$ are not mutually incomparable, set $c(t,u,v) = 0$. If they are mutually incomparable, suppose they are listed in lexicographic order and consider the meet of $t,u$ and the meet of $u,v$. One of these is the meet of all three nodes and the other is incomparable with one of the two ends $t$ or $v$. (This is where I use that $T$ is binary.) Set $c(t,u,v) = -1$ if $t$ is incomparable with the meet of $u,v$, and set $c(t,u,v) = 1$ if $v$ is incomparable with the meet of $t,u$.

An infinite homogeneous set $H$ of color $0$ is such that all nodes of $H$ are comparable except perhaps for one loner. An infinite homogeneous set of color $+1$ is a right-handed comb where all nodes branch on the left of a common branch (the prototypical example is $\lbrace0,10,110,1110,\dots\rbrace$). Symmetrically, an infinite homogeneous set of color $-1$ is a left-handed comb. In all three cases, we can easily compute an infinite branch through $T$.

---

As Tanmay explained, the general case of $\mathsf{KL}$ can be done by assigning a fourth color to incomparable $t,u,v$ that branch from the same node (so the meet of $t,u$ is the same as that of $u,v$). The fact that the tree is finitely branching ensures that there can be no infinite homogeneous set for this fourth color.