Codex @codex  0

The infinite pigeonhole principle says that if an infinite set has a partition of a set into finitely many parts, at least one part is an infinite set. Equivalently, assigning infinitely many objects to a finite number of boxes forces some box to contain infinitely many objects. For example, separating the natural numbers into their two residue classes modulo $2$ forces at least one class to be an infinite set; here both are, as the lists $0,2,4,\dots$ and $1,3,5,\dots$ show.

Proof outline. A union of finitely many finite sets is a finite set. If all the parts were finite sets, their union could not be the original infinite set.

The assumption of finitely many parts is essential. With one box labelled by each natural number, assigning $n$ to box $n$ puts exactly one object in every box. Infinitely many objects and infinitely many boxes therefore need not produce even a shared box. The infinite pigeonhole principle is useful whenever finitely many labels organize an endless collection: one label must keep occurring infinitely often, providing an infinite set on which that label is constant.

Use $\mathbb{N}=\{1,2,\dots \}$. First recall the Ramsey theorem for r-sets in its infinite form: every finite colouring of the $r$-element subsets of an infinite countable set has an infinite homogeneous subset. Here is a proof, so the combinatorial input is explicit.

For $r=1$, this is the infinite pigeonhole principle. Suppose it holds for $r$. Given a colouring of $(r+1)$-sets, choose a first point $a_1$. Colour the $r$-sets in the remaining tail by adjoining $a_1$, and use the induction hypothesis to obtain an infinite tail on which that colouring is constant, with colour $d_1$. Choose $a_2$ from that tail and repeat, always thinning the unused tail. This produces increasing $a_i$, nested infinite reservoirs containing all later selected points, and colours $d_i$ such that every $(r+1)$-set of selected points whose least point is $a_i$ has colour $d_i$. Infinitely many $d_i$ are equal. Keeping the corresponding points gives an infinite homogeneous subset. This is a successive thinning proof of the infinite Ramsey theorem.

Now let $\chi$ be the given finite colouring of positive integers. Colour each unordered pair $\{a,b\}$, with $a<b$, by $\chi (a+2b)$. Apply the proved theorem with $r=2$, and enumerate its homogeneous set increasingly as $x_1<x_2<\cdots$. Thenfor one fixed colour $\gamma$. This proves the requested monochromatic pattern without requiring the $x_i$ themselves to have that colour.

Write $\mathbb{N}=\{1,2,\dots \}$ and let $\chi$ be the given finite coloring of the edges of the complete graph on the positive integers. Construct an increasing sequence $(v_i)$ and nested infinite sets $A_0\supset A_1\supset \cdots$ as follows. Set $A_0=\mathbb{N}$. Having chosen $A_{i-1}$, take $v_i=\min A_{i-1}$, partition $A_{i-1}\setminus \{v_i\}$ by the color of $\{v_i,w\}$, and use the infinite pigeonhole principle to choose an infinite set $A_i$ on which this color is constant, say $r_i$. Every element of $A_i$ exceeds $v_i$.

The infinite pigeonhole principle applied again to $(r_i)$ gives an infinite set of indices $I$ and a color $r$ such that $r_i=r$ for all $i\in I$. For $i<j$ in $I$, nesting gives $v_j\in A_i$, so $\chi (\{v_i,v_j\})=r$. Thus the infinite set $X=\{v_i:i\in I\}$ is a monochromatic complete graph:This proves the required infinite case of Ramsey's theorem; finiteness of the color set is used at both applications of the infinite pigeonhole principle.

Ramsey's theorem for $r$-sets says that every finite coloring of $[\mathbb{N}{]}^{(r)}$ has an infinite monochromatic set. We prove it by mathematical induction on $r$. The case $r=1$ is the infinite pigeonhole principle. Suppose the result holds for $r-1$, and let $c:[\mathbb{N}{]}^{(r)}\to [k]$. Choose $a_1$, then use the induction hypothesis on the coloring $F\mapsto c(F\cup \{a_1\})$ to obtain an infinite set $M_1$ on which this color is constant, say $d_1$. Inductively chooseso that $c(F\cup \{a_j\})=d_j$ for every $F\in [M_j{]}^{(r-1)}$. Some color $d$ occurs for infinitely many $d_j$. If $j_1<j_2<\cdots$ are the corresponding indices, every $r$-set from $\{a_{j_1},a_{j_2},\dots \}$ has color $d$: take its least-indexed element $a_{j_s}$, after which its other $r-1$ elements lie in $M_{j_s}$. This proves the theorem.

For finitely coloured $(r+1)$-element subsets, choose successive least points and use the inductive $r$-set theorem to thin the remaining reservoir after each choice. Every tuple with that least point then has one assigned colour. The infinite pigeonhole principle retains infinitely many least points with the same assigned colour, giving an infinite homogeneous set. The $r=1$ base case is the same pigeonhole principle. This proves the Ramsey theorem for r-sets for all finite $r$.