Misplaced Pages

Erdős–Rado theorem

Article snapshot taken from[REDACTED] with creative commons attribution-sharealike license. Give it a read and then ask your questions in the chat. We can research this topic together.
(Redirected from Erdos-Rado theorem) For the discrete mathematics theorem, see Erdős–Ko–Rado theorem. Theorem in combinatorial set theory extending Ramsey's theorem to uncountable sets

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 ⁡ ( κ ) + ⟶ ( κ + ) κ r + 1 {\displaystyle \exp _{r}(\kappa )^{+}\longrightarrow (\kappa ^{+})_{\kappa }^{r+1}}

where exp0(κ) = κ and inductively expr+1(κ)=2. This is sharp in the sense that expr(κ) cannot be replaced by expr(κ) 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 expr(κ), 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

  1. Erdős & Rado (1956).
  2. Erdős, Hajnal & Rado (1965).

References

Categories:
Erdős–Rado theorem Add topic