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 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.
Re ...
, 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 numb ...
s. It is named after
Paul Erdős
Paul Erdős ( hu, Erdős Pál ; 26 March 1913 – 20 September 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 ...
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
Đuro Kurepa (Serbian Cyrillic: Ђуро Курепа, ; 16 August 1907 – 2 November 1993) was a Yugoslav mathematician.
Throughout his life, Kurepa published over 700 articles, books, papers, and reviews and over 1,000 scientific reviews. He l ...
who proved it under the additional assumption of the
generalised continuum hypothesis
In mathematics, the continuum hypothesis (abbreviated CH) is a hypothesis about the possible sizes of infinite sets. It states that
or equivalently, that
In Zermelo–Fraenkel set theory with the axiom of choice (ZFC), this is equivalent to ...
,
[''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
In mathematics, transfinite numbers are numbers that are "infinite" in the sense that they are larger than all finite numbers, yet not necessarily absolutely infinite. These include the transfinite cardinals, which are cardinal numbers used to qua ...
, 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