In
partition calculus In mathematics, infinitary combinatorics, or combinatorial set theory, is an extension of ideas in combinatorics to infinite sets.
Some of the things studied include continuous graphs and trees, extensions of Ramsey's theorem, and Martin's axiom.
R ...
, 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 (say ...
to
uncountable set
In mathematics, an uncountable set (or uncountably infinite set) 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 nu ...
s. It is named after
Paul Erdős 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 th ...
. It is sometimes also attributed to
Đuro Kurepa who proved it under the additional assumption of the
generalised continuum hypothesis,
[''https://mathoverflow.net/questions/191326/where-is-the-erd%C5%91s-rado-theorem-stated-in-erd%C5%91s-and-rados-bull-ams-paper#comment495809_191327''] 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