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$).



Deriving Konig's Lemma directly from Infinite Ramsey's Theorem for triples
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. 


