Is this proof valid? Infinite Ramsey theorem from the finite

Question

It has been stated in many places (e.g. here) that the infinite Ramsey theorem cannot be deduced from the finite. I seem to have found a proof of finite -> infinite via a standard compactness argument - I was hoping someone could point out the error(s) in my proof.

---

To fix the notation, we will often let $n = \{ 0, 1, \ldots, n-1 \}$. For a set $A$ and $d \in \mathbb{N}$, we will let $$ A^{(d)} = [A]^{(d)} = \{ B \subseteq A: |B| = d \} $$ I am using the following statements of the theorem:

Finite Ramsey: for each $r, d \leq k \in \mathbb{N}$, there exists $R(r,d,k) \in \mathbb{N}$, such that for every $r$-colouring $\Delta: [R(r,d,k)]^{(d)} \to r$, there exists a subset $A \subseteq R(r,d,k)$ such that $|A| = k$ and $A^{(d)}$ is $\Delta$-monochromatic.

Infinite Ramsey: for each $r, d \in \mathbb{N}$, and for every $r$-colouring $\Delta: \mathbb{N}^{(d)} \to r$, there exists an infinite subset $A \subseteq \mathbb{N}$ such that $A^{(d)}$ is $\Delta$-monochromatic.

---

Proof: fix $r, d \in \mathbb{N}$, and an $r$-colouring $\Delta: \mathbb{N}^{(d)} \to r$. Let $R(k) = R(r,d,k)$, as per the FRT. For each $k \in \mathbb{N}$, let $\Delta_k = \Delta |_{[R(k)]^{(d)}}$

We construct a tree $T$ as follows: the nodes of $T$ on level $k$ will be subsets $A \subseteq R(k)$ such that $|A| = k$ and $A^{(d)}$ is $\Delta_k$-monochromatic. We declare a node $A'$ on level $k+1$ to be a child of a node $A$ on level $k$ iff $A \subseteq A'$.

Then, $T$ is infinite, since by the FRT, each level is nonempty. $T$ is finitely branching, since any node $A$ on level $k$ can have at most $R(k+1)-k < \omega$ extensions. Thus, by Kőnig's lemma, $T$ has an infinite branch $(A_i)_{i \in \mathbb{N}}$ such that for each $k$:

• $A_k \subseteq R(k)$;
• $|A_k| = k$; and
• $A_k$ is $\Delta_k$-monochromatic.

Let $A = \bigcup_{k \in \mathbb{N}} A_k$: then $|A| = \aleph_0$. We claim $A$ is $\Delta$-monochromatic: suppose it were not, then there exist subsets $B,C \subseteq A$ with $|B| = |C| = d$, such that $\Delta(B) \neq \Delta(C)$. But $B \cup C$ is finite, thus $B \cup C \subseteq A_j$ for sufficiently large $j$. Then, $\Delta_j(B) = \Delta(B) \neq \Delta(C) = \Delta_j(C)$, contradicting that $[A_j]^{(d)}$ is $\Delta_j$-monochromatic.

Answer 1

The problem is that $T$ is not a tree: a node $A$ on level $k+1$ need not have a predecessor on level $k$. In particular, it will only have a predecessor if $|A\cap R(k)|\geq k$, but there is no reason to expect that to be true. So König's lemma does not apply, and what could happen is that each node of $T$ has only finitely many descendants, but every level manages to be nonempty since you keep having new nodes pop up which have no predecessors.