Erdős–Rado theorem

Statement of the theorem

If r ≥ 0 is finite and κ is an

${\displaystyle \exp _{r}(\kappa )^{+}\longrightarrow (\kappa ^{+})_{\kappa }^{r+1}}$

where exp₀(κ) = κ and inductively exp_r+1(κ)=2^exp_r(κ). This is sharp in the sense that exp_r(κ)⁺ cannot be replaced by exp_r(κ) on the left hand side.

The above partition symbol describes the following statement. If f is a coloring of the r+1-element subsets of a set of cardinality exp_r(κ)⁺, in κ many colors, then there is a homogeneous set of cardinality κ⁺ (a set, all whose r+1-element subsets get the same f-value).

Notes