Erdős–Rado theorem

Remarks

The case $n = 0$ is the pigeonhole principle: a map from $\kappa^+$ points to $\kappa$ colours is constant on $\kappa^+$ points. The case $n = 1$ reads $(2^\kappa)^+ \to (\kappa^+)^2_\kappa$, and for $\kappa = \aleph_0$ it gives $(2^{\aleph_0})^+ \to (\aleph_1)^2_{\aleph_0}$. The proof goes by induction on $n$. It builds a long sequence in which the colour of an $(n+1)$-element set depends only on its $n$ smallest elements, and then applies the case $n - 1$. The bound is sharp for $n = 1$: by a theorem of Sierpiński, $2^{\aleph_0} \not\to (\aleph_1)^2_2$, so $2^{\aleph_0}$ points do not suffice even for two colours. The theorem extends the infinite Ramsey theorem $\aleph_0 \to (\aleph_0)^n_k$ to uncountable homogeneous sets.

Going deeper

For a student

The notation $\kappa \to (\lambda)^n_\mu$ is the arrow notation of the partition calculus of Erdős and Rado. The theorem is the basic positive result of uncountable Ramsey theory, and Sierpiński's colouring shows that it cannot be improved for pairs. It is used in model theory, for example to find indiscernible sequences in large models, and in the study of large cardinals defined by partition properties.