Satz von Erdős-Rado

Der Satz von Erdős-Rado, benannt nach Paul Erdős und Richard Rado, ist ein mathematischer Satz aus dem Gebiet der Mengenlehre. Er trifft eine Aussage darüber, wie groß eine Menge sein muss, um eine gewisse Zerlegungseigenschaft zu haben.

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}$ (paarweise disjunkte) Teilmengen, so enthält wenigstens eine dieser Zerlegungsmengen ${\displaystyle X_{\alpha }}$ eine Teilmenge der Form ${\displaystyle [H]^{n}}$, wobei ${\displaystyle H\subset \kappa }$ 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 die 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

${\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. Wegen der 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.