Erdős–Rado theorem

For the discrete matematics theorem, see Erdős–Ko–Rado theorem.

In partition calculus, part of combinatorial set theory, a branch of mathematics, the Erdős–Rado theorem is a basic result extending Ramsey's theorem to uncountable sets. It is named after Paul Erdős and Richard Rado. It is sometimes also attributed to Đuro Kurepa who proved it under the additional assumption of the generalised continuum hypothesis, and hence the result is sometimes also referred to as the Erdős–Rado–Kurepa theorem.

Statement of the theorem

If r ≥ 0 is finite and κ is an infinite cardinal, then

$\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).

References

• Erdős, Paul; Hajnal, András; Máté, Attila; Rado, Richard (1984), Combinatorial set theory: partition relations for cardinals, Studies in Logic and the Foundations of Mathematics, vol. 106, Amsterdam: North-Holland Publishing Co., ISBN 0-444-86157-2, MR 0795592
• Erdős, P.; Rado, R. (1956), "A partition calculus in set theory", Bull. Amer. Math. Soc., 62 (5): 427–489, doi:10.1090/S0002-9904-1956-10036-0, MR 0081864
• Erdős, Paul; Hajnal, András; Rado, Richard (1965), "Partition relations for cardinal numbers", Acta Math. Acad. Sci. Hung., 16 (1–2): 93–196, CiteSeerX 10.1.1.299.7622, doi:10.1007/BF01886396, MR 0202613