Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

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

share|improve this question
add comment

2 Answers

up vote 7 down vote accepted

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.

share|improve this answer
2  
This is the same argument as that of Francois, only that you describe the general case, not just the binary. The crucial observation is that the bad color (in this case 0) only has finite homogeneous sets. –  Stefan Geschke Apr 24 '13 at 18:38
    
Thanks for figuring out the missing piece in my answer! –  François G. Dorais Apr 24 '13 at 19:08
    
I agree. I saw he'd posted an answer while I was writing, but I didn't check if it was the same solution. I hope the person asking takes note... –  Tanmay Inamdar Apr 24 '13 at 19:12
    
It seems to me that the coloring $g$ is ill-defined. Perhaps there is an ordering other than the lexicographic one we should know about? –  François G. Dorais Apr 25 '13 at 0:33
    
I see the problem, that I'm mixing the Ramsey theorem for 2 element sets and 2 element sequences. I also see that you don't need this application of the Ramsey theorem, because the infinite homogenous set for the case that I have sketched out is a `left-handed comb' in the terminology from your answer. This also tells me why you didn't need the extra Ramsey theorem, and that my argument is literally the same argument as yours except for the part of what gets coloured by a 0... –  Tanmay Inamdar Apr 25 '13 at 1:08
show 1 more comment

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.

share|improve this answer
1  
Both answers are helpful (thanks!) and I would like to set both of them as answering my question, but MO will allow checking only one answer. –  Dave Albert Apr 24 '13 at 19:52
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.