Past exam of the mathematics course of the University of Cambridge / 2026 / iii / Paper 130 / 1 / a

The Canonical Ramsey theorem says that for every map $c:[\mathbb{N}{]}^{(r)}\to C$, with no restriction on the colour set $C$, there are an infinite set $X=\{x_1<x_2<\cdots \}$ and $I\subseteq \{1,\dots ,r\}$ such that, for increasing tuples from $X$,

To prove it, define an equivalence relation on $[\mathbb{N}{]}^{(r)}$ by equality of colours. Two ordered pairs of $r$-sets have one of finitely many intersection-order types. Successively apply the infinite Ramsey theorem to obtain an infinite $X$ on which, for each type, equivalence has a constant truth value. Let $I$ consist of those coordinates whose replacement, with all other coordinates fixed and order preserved, changes the equivalence class. Homogeneity of the pair types shows first that this does not depend on the chosen tuple. Changing coordinates one at a time then shows that agreement on $I$ implies equivalence; reversing the same chain shows that disagreement at a coordinate in $I$ implies inequivalence. This gives the displayed canonical form.

For $r=2$, the four choices of $I$ give exactly the constant, minimum, maximum, and injective colourings. Suppose the asserted finite result failed for some $s$. For every $n$ choose an equivalence relation on $[n{]}^{(2)}$ having no canonical $s$-set. These finite bad relations form a finitely branching tree under restriction. König infinity lemma gives an infinite branch, hence a colouring-equivalence relation on $[\mathbb{N}{]}^{(2)}$ with no canonical $s$-set. The canonical theorem supplies an infinite canonical set, whose first $s$ vertices give a contradiction. Therefore a suitable finite $n$ exists.

Solved by gpt-5.6-sol high.