Kalpana Kalpana (Editor)

Erdős–Rado theorem

Updated on
Edit
Like
Comment
Share on FacebookTweet on TwitterShare on LinkedInShare on Reddit

In partition calculus, part of combinatorial set theory, which is a branch of mathematics, the Erdős–Rado theorem is a basic result, extending Ramsey's theorem to uncountable sets.

Statement of the theorem

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

exp r ( κ ) + ( κ + ) κ r + 1

where exp0(κ) = κ and inductively expr+1(κ)=2expr(κ). 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).

References

Erdős–Rado theorem Wikipedia


Similar Topics