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
In combinatorics, Ramsey's theorem, in one of its graph-theoretic forms, states that one will find monochromatic cliques in any edge labelling (with colours) of a sufficiently large complete graph. To demonstrate the theorem for two colours (sa ...
to
uncountable set
In mathematics, an uncountable set, informally, is an infinite set that contains too many elements to be countable. The uncountability of a set is closely related to its cardinal number: a set is uncountable if its cardinal number is larger t ...
s. It is named after
Paul Erdős
Paul Erdős ( ; 26March 191320September 1996) was a Hungarian mathematician. He was one of the most prolific mathematicians and producers of mathematical conjectures of the 20th century. pursued and proposed problems in discrete mathematics, g ...
and
Richard Rado
Richard Rado FRS (28 April 1906 – 23 December 1989) was a German-born British mathematician whose research concerned combinatorics and graph theory. He was Jewish and left Germany to escape Nazi persecution. He earned two PhDs: in 1933 from t ...
. It is sometimes also attributed to
Đuro Kurepa who proved it under the additional assumption of the
generalised continuum hypothesis
In mathematics, specifically set theory, the continuum hypothesis (abbreviated CH) is a hypothesis about the possible sizes of infinite sets. It states:
Or equivalently:
In Zermelo–Fraenkel set theory with the axiom of choice (ZFC), this ...
, 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
:
where exp
0(κ) = ''κ'' 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
References
*
*
*
{{DEFAULTSORT:Erdos-Rado theorem
Set theory
Theorems in combinatorics
Rado theorem