Satz von Erdős-Rado

Für eine Menge ${\displaystyle A}$ sei ${\displaystyle [A]^{n}}$ die Menge aller ${\displaystyle n}$-elementigen Teilmengen von ${\displaystyle A}$, wobei ${\displaystyle n}$ eine natürliche Zahl sei. Für Kardinalzahlen ${\displaystyle \kappa }$,${\displaystyle \lambda }$, ${\displaystyle m}$ schreibt man

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

falls folgende Aussage richtig ist:

Ist ${\displaystyle [\kappa ]^{n}=\bigcup _{\alpha <m}X_{\alpha }}$ eine Zerlegung von ${\displaystyle [\kappa ]^{n}}$ in ${\displaystyle m}$ viele (paarweise disjunkte) Teilmengen, so enthält wenigstens eine dieser Zerlegungsmengen ${\displaystyle X_{\alpha }}$ eine Teilmenge der Form ${\displaystyle [H]^{n}}$, wobei ${\displaystyle H\subset A}$ die Mächtigkeit ${\displaystyle \lambda }$ hat.

Diese auf P. Erdős und R. Rado zurückgehende Pfeilnotation soll hier durch einige Beispiele verdeutlicht werden. Der Fall ${\displaystyle n=1}$ bedeutet einfach, dass bei einer Zerlegung von ${\displaystyle \kappa }$ in ${\displaystyle m}$ Teile wenigstens ein Teil die Mächtigkeit ${\displaystyle \lambda }$ haben muss. Allein aus Mächtigkeitsgründen gilt also für unendliche Kardinalzahlen ${\displaystyle \kappa >\lambda }$, dass ${\displaystyle \kappa \rightarrow (\lambda )_{2}^{1}}$ oder ${\displaystyle \kappa \rightarrow (\lambda )_{\aleph _{0}}^{1}}$, wobei ${\displaystyle \aleph _{0}}$ die Aleph-Notation für kleinste unendliche Kardinalzahl sei. Interessantere, das heißt weniger triviale, Aussagen erhält man erst für den Fall ${\displaystyle n\geq 2}$. So lässt sich der Satz von Ramsey in der Pfeilnotation wie folgt formulieren:

${\displaystyle \aleph _{0}\rightarrow (\aleph _{0})_{m}^{n}}$ für alle natürlichen Zahlen ${\displaystyle m,n}$.

Man beachte, dass die Aussage ${\displaystyle \kappa \rightarrow (\lambda )_{m}^{n}}$ richtig bleibt, wenn man zu größeren Kardinalzahlen ${\displaystyle \kappa }$ übergeht oder wenn man eine der Größen ${\displaystyle \lambda ,m,n}$ verkleinert. In der Pfeilnotation werden die Größen durch den Pfeil also nach ihrem Monotonieverhalten getrennt, was zumindest eine Merkhilfe ist.

Gilt die Aussage ${\displaystyle \kappa \rightarrow (\lambda )_{m}^{n}}$ nicht, so schreibt man auch ${\displaystyle \kappa \not \rightarrow (\lambda )_{m}^{n}}$. Ist ${\displaystyle m=2}$, so lassen manche Autoren den Index ${\displaystyle m}$ gerne weg.

W. Sierpiński hat für unendliche Kardinalzahlen ${\displaystyle \kappa }$ gezeigt, dass

Fehler beim Parsen (SVG (MathML kann über ein Browser-Plugin aktiviert werden): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „http://localhost:6011/de.wikipedia.org/v1/“:): {\displaystyle 2^\kappa \not\rightarrow (\kappa^+)^2} , oder genauer ${\displaystyle 2^{\kappa }\not \rightarrow (\kappa ^{+})_{2}^{2}}$

wobei ${\displaystyle \kappa ^{+}}$ die Nachfolger-Kardinalzahl von ${\displaystyle \kappa }$ bezeichnet.

Unter Verwendung obiger Pfeilnotation und der Beth-Funktion ${\displaystyle \beth }$ lautet der Satz von Erdős-Rado:

• ${\displaystyle \beth _{n}^{+}\rightarrow (\aleph _{1})_{\aleph _{0}}^{n+1}}$ für alle natürlichen Zahlen ${\displaystyle n}$.

Für ${\displaystyle n=0}$ ist ${\displaystyle \beth _{0}^{+}=\aleph _{0}^{+}=\aleph _{1}}$ und der Satz von Erdős-Rado besagt lediglich ${\displaystyle \aleph _{1}\rightarrow (\aleph _{1})_{\aleph _{0}}^{1}}$, das heißt bei einer Zerlegung von ${\displaystyle \aleph _{1}}$ in abzählbar viele Teile muss wenigstens ein Teil die Mächtigkeit ${\displaystyle \aleph _{1}}$ haben, und das bedeutet, dass ${\displaystyle \aleph _{1}}$ nicht abzählbare Vereinigung abzählbarer Mengen ist. Erst für ${\displaystyle n\geq 1}$ erhält man nicht-triviale Aussagen.

Die oben genannte auf Sierpiński zurückgehende Aussage besagt für ${\displaystyle \kappa =\aleph _{0}}$, dass ${\displaystyle 2^{\aleph _{0}}\not \rightarrow (\aleph _{1})_{2}^{2}}$, oder wegen des Monotonieverhaltens ${\displaystyle \kappa \not \rightarrow (\aleph _{1})_{2}^{2}}$ für alle ${\displaystyle \kappa \leq 2^{\aleph _{0}}}$. Der Satz von Erdős-Rado trifft nun die positive Aussage ${\displaystyle \kappa \rightarrow (\aleph _{1})_{2}^{2}}$ für alle ${\displaystyle \kappa >2^{\aleph _{0}}}$, denn für ${\displaystyle n=1}$ erhält man ${\displaystyle (2^{\aleph _{0}})^{+}\rightarrow (\aleph _{1})_{\aleph _{0}}^{2}}$ und das Monotonieverhalten der Pfeilnotation führt zur gewünschten Aussage.

Obiger Satz lässt folgende Verallgemeinerung auf höhere Mächtigkeiten zu, die ebenfalls als Satz von Erdős-Rado bezeichnet wird. Für eine unendliche Kardinalzahl ${\displaystyle \kappa }$ definiere rekursiv

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

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

Dann gilt

• ${\displaystyle \exp _{n}(\kappa )^{+}\rightarrow (\kappa ^{+})_{\kappa }^{n+1}}$ für alle natürlichen Zahlen ${\displaystyle n}$ und alle unendlichen Kardinalzahlen ${\displaystyle \kappa }$.

Dieses Ergebnis ist scharf, das heißt die Kardinalzahl auf der linken Seite des Pfeils kann nicht durch eine kleinere ersetzt werden. Daher ist der Satz von Erdős-Rado eine Aussage darüber, wie groß eine Kardinalzahl ${\displaystyle \mu }$ sein muss, damit die Partitionseigenschaft ${\displaystyle \mu \rightarrow (\kappa ^{+})_{\kappa }^{2}}$ erfüllt ist: Es muss ${\displaystyle \mu \,>\,\exp _{n}(\kappa )}$ sein.

Für ${\displaystyle \kappa =\aleph _{0}}$ ist ${\displaystyle \exp _{n}(\kappa )=\beth _{n}}$, und man erhält den zuvor genannten Satz von Erdős-Rado als Spezialfall. Aus dem Monotonieeigenschaften der Pfeilnotation folgt aus dem Fall ${\displaystyle n=1}$ des Satzes von Erdős-Rado:

${\displaystyle (2^{\kappa })^{+}\rightarrow (\kappa ^{+})^{2}}$ für alle unendlichen Kardinalzahlen ${\displaystyle \kappa }$.

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