an "infinitary" proof of the finite Ramsey's theorem

January 20, 2026

[we prove the Infinite Ramsey's Theorem with classical and nonstandard methods and deduce the finite Ramsey's theorem from it]

Infinite Ramsey's Theorem: For any $k, m \in \mathbb{N},$ any infinite set $X,$ and any $k$-coloring $c$ of $X^{[m]},$ there exists an infinite subset of $X$ that is monochromatic with respect to $c.$ (Here $X^{[m]}$ denotes the set of $m$-element subsets of $X$ and a $k$-coloring $c$ of a set $X$ is some function $c: X \to \{1, \ldots, k\}.$ A subset $Y$ of $X$ is "monochromatic" if $c(Y)$ is single-valued).

Typically, the Infinite Ramsey's Theorem is introduced as a structure guarantee for infinite (hyper)graphs. To see this, take a graph $G = (V,E)$ with an infinite set of vertices $V$ and an (not necessarily infinite) edge set $E.$ Consider the $2$-coloring $c: V^{[2]}\to \{1, 2\}$ such that $c(\{v_1, v_2\}) = 1$ if and only if $(v_1, v_2) \in E,$ and $c(\{v_1,v_2\}) = 2$ otherwise. The Infinite Ramsey's Theorem implies that for this 2-coloring, there exists an infinite set of vertices $W \subseteq V$ such that $c(W)$ is constant; implying that $G$ either has an infinite fully edge-connected subset (called a clique: all pairs of vertices in $W$ share a corresponding edge) or an infinite fully disconnected subset (an anticlique: no two vertices in $W$ share an edge). (Colorings with $k \geq 3$ imply an identical statement for $k$-hypergraphs: graphs where edges $e \in E$ are $k$-tuples of vertices, and as such connect $k$ vertices at a time.)

Additionally, the Infinite Ramsey's Theorem is typically proved combinatorially, by induction. We reproduce the classical proof here for completeness, for the case $X = \mathbb{N}.$

• The base case $m=1$ is a straightforward application of the pigeonhole principle: partitioning $\mathbb{N}$ into $k$ finite sets is impossible, so at least one of the color classes will be infinite.

• Now assume the statement holds for $\mathbb{N}^{[m-1]}.$ We prove the statement for an arbitrary (finite) $k-$coloring $c$ of $\mathbb{N}^{[m]}$ by constructing a monochromatic subset $H'$ as follows.

  • Let $X_0 = \mathbb{N}$ and $x_0 = 0.$ We construct sequences $x_0 < x_1 < \cdots$ and $X_0 \supset X_1 \supset \cdots$ in the following way.

  • For each $X_i, x_i,$ there's a natural $k-$coloring $c_i$ of $(X_i \setminus \{x_i\})^{[m-1]}$ given by $c_i(S) = c(S\cup \{x_i\}).$ By the induction hypothesis, there exists an infinite $X_{i+1} \subset X_i \setminus \{x_i\}$ and a color $d_i$ such that $c(S \cup \{x_i\}) = d_i$ for all $(m-1)$ element subsets $S$ of $X_{i+1}.$ Then let $x_{i+1} = \min(X_{i+1}).$

  • Let $H = \{x_0, x_1, \ldots\}.$ The colors $d_i$ (decided stepwise as above) lie in $\{1, \ldots, k\},$ so by the pigeonhole principle there is some color $d$ for which $d_i = d$ for infinitely many $i.$ Let $I$ be the set of these indices, and let $H'$ be the subset of $H$ on $I.$ Note $H'$ is infinite.

  • Observe that any $m$-element subset of $H'$ is monochromatically $d.$ Take any $Y \in (H')^{[m]}.$ Its least element $y$ is some $x_j$ for $j \in I.$ The remaining $m-1$ elements of $Y$ are larger than $x_j$ and so lie in $X_{j+1}$ (recall this is a descending subset chain). So, $c(Y) = d_j,$ and $d_j = d$ as $j \in I.$ This finishes the inductive step.

The key ingredient in the nonstandard proof is the existence of a corresponding hyperextension $^*X$ for mathematical objects $X,$ such that $^*X$ is not isomorphic to $X$ but preserves all "elementary properties" of $X.$ (The proof of the existence of these objects will be reserved for another day: concisely, Los's theorem guarantees the diagonal embedding into the ultrapower of $X$ is elementary). "Elementary properties" of $X$ are those expressable in first order sentences: includes set inclusion, union, intersection, field axioms, etc. Does not include the Archimedean property of the reals! (For all positive $x \in \mathbb{R}$ there exists $n \in \mathbb{N}$ such that $nx > 1.$). We define the transfer map $*$ to be a function taking an object to its hyperextension. [More properties can be found in Section 2 of this manuscript.]

Consider some infinite graph $G.$ (Worthwhile to note that, formally, it makes more sense to treat the edges $E$ as a relation: a subset of $V \times V$ that's anti-reflexive and symmetric.) A hyperextension $^*G$ of $G$ induces corresponding hyperextensions $^*V, ^*E$ on the vertices and edges.

We now prove the Infinite Ramsey's Theorem for $2$-colorings, in the graph setting. Let $\xi$ be an element of $^*V$ not belonging to $V.$ Consider its hyperextension $^*\xi \in ^{**}V.$ There are two cases: either $\xi$ and $^*\xi$ are connected by an edge in $^{**}G,$ or they are not. We treat the first case (the other being symmetric). Suppose there exist $d$ elements $v_i$ of $V$ which form a clique and are all connected to $\xi$ in $^*G.$ These form a sequence $(v_i)_{1 \leq i < d}.$

Consider the statement: "there exists some $y \in ^*V$ such that for $j < d,$ $y$ is not $v_j,$ $(v_j, y) \in ^*E,$ and $(y, ^*\xi) \in ^{**}E.$" This is satisfied by $\xi$ by construction. (Editing the third constraint is what deals with the case where $\xi$ is not connected to $^*\xi.$). This is also an elementary property of $^*G,$ so a corresponding statement must be true in $G.$ This statement is "there exists $v_d \in V$ different from $v_j$ for $j < d$ such that $(v_j, v_d) \in E$ for $j <d$ and $(v_d, \xi) \in ^*E.$"

This construction is recursive (you can make a $d+1$ length chain by repeating it), so this constructs an infinite clique. An infinite anticlique is constructed by taking the case where $\xi$ is not connected to $^*\xi.$

Compared to the classical proof, the nonstandard approach is much cleaner? Less bookkeeping. You extend this argument to the $k$-coloring case simply: $E$ becomes a subset of $V^k.$

Finite Ramsey's Theorem. For every $k,m,n \in \mathbb{N},$ there is $l \in \mathbb{N}$ such that every coloring of $[l]^{[m]}$ with $k$ colors has a homogenous set of size $n.$

We prove this by contradiction. Assume it's false for a particular choice of $k,m,n.$ Then for every $l \in \mathbb{N},$ there is a $k$-coloring $c$ of $[l]^{[m]}$ with no monochromatic subset of size $n.$

This is impossible due to Konig's Lemma. You can construct a finitely branching tree of these "bad" colorings where the partial order on the tree is induced by inclusion. Konig's lemma implies there's an infinite branch of this tree. This implies there's a $k$-coloring of $\mathbb{N}^{[m]}$ with no monochromatic subset of size $n,$ which contradicts the Infinite Ramsey's Theorem. QED.