Erdős-Rado's theorem

The Erdős-Rado theorem , named after Paul Erdős and Richard Rado , is a mathematical theorem in the field of set theory . It makes a statement about how large a quantity must be in order to have a certain decomposition property.

The arrow notation

For a set, let the set of all -element subsets of , where be a natural number. For cardinal numbers , , one writes ${\displaystyle A}$ ${\displaystyle [A]^{n}}$ ${\displaystyle n}$ ${\displaystyle A}$ ${\displaystyle n}$ ${\displaystyle \kappa }$ ${\displaystyle \lambda }$ ${\displaystyle m}$

${\displaystyle \kappa \rightarrow (\lambda )_{m}^{n}}$,

if the following statement is correct:

If there is a decomposition of into many (pairwise disjoint) subsets, then at least one of these decomposition sets contains a subset of the form , where has cardinality . ${\displaystyle [\kappa ]^{n}=\bigcup _{\alpha <m}X_{\alpha }}$ ${\displaystyle [\kappa ]^{n}}$ ${\displaystyle m}$ ${\displaystyle X_{\alpha }}$ ${\displaystyle [H]^{n}}$ ${\displaystyle H\subset A}$ ${\displaystyle \lambda }$

This arrow notation, which can be traced back to P. Erdős and R. Rado, should be illustrated here with a few examples. The case simply means that when a is broken down into parts, at least one part must have the power . So alone thickness reasons applies to infinite cardinal numbers that , or , where the Aleph notation is for the smallest infinite cardinal. You only get more interesting, i.e. less trivial, statements just in case . So Ramsey's theorem can be formulated in arrow notation as follows: ${\displaystyle n=1}$ ${\displaystyle \kappa }$ ${\displaystyle m}$ ${\displaystyle \lambda }$ ${\displaystyle \kappa >\lambda }$ ${\displaystyle \kappa \rightarrow (\lambda )_{2}^{1}}$ ${\displaystyle \kappa \rightarrow (\lambda )_{\aleph _{0}}^{1}}$ ${\displaystyle \aleph _{0}}$ ${\displaystyle n\geq 2}$

${\displaystyle \aleph _{0}\rightarrow (\aleph _{0})_{m}^{n}}$for all natural numbers . ${\displaystyle m,n}$

Note that the statement remains correct if you go to larger cardinal numbers or if you reduce one of the sizes . In the arrow notation, the sizes are separated by the arrow according to their monotony behavior, which is at least a memory aid. ${\displaystyle \kappa \rightarrow (\lambda )_{m}^{n}}$ ${\displaystyle \kappa }$ ${\displaystyle \lambda ,m,n}$

If the statement does not apply, one also writes . If so, some authors make the index like away. ${\displaystyle \kappa \rightarrow (\lambda )_{m}^{n}}$ ${\displaystyle \kappa \not \rightarrow (\lambda )_{m}^{n}}$ ${\displaystyle m=2}$ ${\displaystyle m}$

W. Sierpiński has shown for infinite cardinal numbers that ${\displaystyle \kappa }$

${\displaystyle 2^{\kappa }\not \rightarrow (\kappa ^{+})^{2}}$, or more precisely ${\displaystyle 2^{\kappa }\not \rightarrow (\kappa ^{+})_{2}^{2}}$

where denotes the successor cardinal number of . ${\displaystyle \kappa ^{+}}$ ${\displaystyle \kappa }$

Formulation of the sentence

Using the above arrow notation and the Beth function , Erdős-Rado's theorem reads: ${\displaystyle \beth }$

• ${\displaystyle \beth _{n}^{+}\rightarrow (\aleph _{1})_{\aleph _{0}}^{n+1}}$for all natural numbers . ${\displaystyle n}$

For is and Erdős-Rado's theorem only says , that is, when dividing into countably many parts, at least one part must have cardinality , and that means that there is an uncountable union of countable sets. Only for do you get non-trivial statements. ${\displaystyle n=0}$ ${\displaystyle \beth _{0}^{+}=\aleph _{0}^{+}=\aleph _{1}}$ ${\displaystyle \aleph _{1}\rightarrow (\aleph _{1})_{\aleph _{0}}^{1}}$ ${\displaystyle \aleph _{1}}$ ${\displaystyle \aleph _{1}}$ ${\displaystyle \aleph _{1}}$ ${\displaystyle n\geq 1}$

The above statement, which goes back to Sierpiński, says for that , or because of the monotony for everyone . Erdős-Rado's theorem now makes the positive statement for everyone , because one receives for and the monotony of the arrow notation leads to the desired statement. ${\displaystyle \kappa =\aleph _{0}}$ ${\displaystyle 2^{\aleph _{0}}\not \rightarrow (\aleph _{1})_{2}^{2}}$ ${\displaystyle \kappa \not \rightarrow (\aleph _{1})_{2}^{2}}$ ${\displaystyle \kappa \leq 2^{\aleph _{0}}}$ ${\displaystyle \kappa \rightarrow (\aleph _{1})_{2}^{2}}$ ${\displaystyle \kappa >2^{\aleph _{0}}}$ ${\displaystyle n=1}$ ${\displaystyle 2^{\aleph _{0}}\rightarrow (\aleph _{1})_{\aleph _{0}}^{2}}$

The above theorem allows the following generalization to higher thicknesses, which is also referred to as Erdős-Rado's theorem. For an infinite cardinal number, define recursively ${\displaystyle \kappa }$

${\displaystyle \exp _{0}(\kappa )\,=\,\kappa }$

${\displaystyle \exp _{n+1}(\kappa )\,=\,2^{\exp _{n}(\kappa )}}$.

Then applies

• ${\displaystyle \exp _{n}(\kappa )^{+}\rightarrow (\kappa ^{+})_{\kappa }^{n+1}}$for all natural numbers and all infinite cardinal numbers . ${\displaystyle n}$ ${\displaystyle \kappa }$

This result is sharp, i.e. the cardinal number on the left side of the arrow cannot be replaced by a smaller one. Therefore Erdős-Rado's theorem is a statement about how large a cardinal number must be in order for the partition property to be fulfilled: It must be. ${\displaystyle \mu }$ ${\displaystyle \mu \rightarrow (\kappa ^{+})_{\kappa }^{2}}$ ${\displaystyle \mu \,>\,\exp _{n}(\kappa )}$

For is , and one obtains the Erdős-Rado theorem mentioned above as a special case. From the monotonic properties of the arrow notation it follows from the case of Erdős-Rado's theorem: ${\displaystyle \kappa =\aleph _{0}}$ ${\displaystyle \exp _{n}(\kappa )=\beth _{n}}$ ${\displaystyle n=1}$

${\displaystyle (2^{\kappa })^{+}\rightarrow (\kappa ^{+})^{2}}$for all infinite cardinal numbers . ${\displaystyle \kappa }$

literature

• Thomas Jech : Set Theory , Springer-Verlag (2003), ISBN 3-540-44085-2 , especially chapter 9