HOME

TheInfoList



OR:

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 : \exp_r(\kappa)^+\longrightarrow(\kappa^+)^_\kappa where exp0(κ) = ''κ'' and inductively exp''r''+1(κ)=2exp''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