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.
Die Pfeilnotation Bearbeiten
Für eine Menge sei die Menge aller -elementigen Teilmengen von , wobei eine natürliche Zahl sei. Für Kardinalzahlen ,, schreibt man
falls folgende Aussage richtig ist:
Diese auf P. Erdős und R. Rado zurückgehende Pfeilnotation soll hier durch einige Beispiele verdeutlicht werden. Der Fall bedeutet einfach, dass bei einer Zerlegung von in Teile wenigstens ein Teil die Mächtigkeit haben muss. Allein aus Mächtigkeitsgründen gilt also für unendliche Kardinalzahlen , dass oder , wobei die Aleph-Notation für kleinste unendliche Kardinalzahl sei. Interessantere, das heißt weniger triviale, Aussagen erhält man erst für den Fall . So lässt sich der Satz von Ramsey in der Pfeilnotation wie folgt formulieren:
Man beachte, dass die Aussage richtig bleibt, wenn man zu größeren Kardinalzahlen übergeht oder wenn man eine der Größen verkleinert. In der Pfeilnotation werden die Größen durch den Pfeil also nach ihrem Monotonieverhalten getrennt, was zumindest eine Merkhilfe ist.
Gilt die Aussage nicht, so schreibt man auch . Ist , so lassen manche Autoren den Index gerne weg.
W. Sierpiński hat für unendliche Kardinalzahlen gezeigt, dass
wobei die Nachfolger-Kardinalzahl von bezeichnet.
Formulierung des Satzes Bearbeiten
Unter Verwendung obiger Pfeilnotation und der Beth-Funktion lautet der Satz von Erdős-Rado:
- für alle natürlichen Zahlen .
Für ist und der Satz von Erdős-Rado besagt lediglich , das heißt bei einer Zerlegung von in abzählbar viele Teile muss wenigstens ein Teil die Mächtigkeit haben, und das bedeutet, dass nicht abzählbare Vereinigung abzählbarer Mengen ist. Erst für erhält man nicht-triviale Aussagen.
Die oben genannte auf Sierpiński zurückgehende Aussage besagt für , dass , oder wegen des Monotonieverhaltens für alle . Der Satz von Erdős-Rado trifft nun die positive Aussage für alle , denn für erhält man 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 definiere rekursiv
Dann gilt
- für alle natürlichen Zahlen und alle unendlichen Kardinalzahlen .
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 sein muss, damit die Partitionseigenschaft erfüllt ist: Es muss sein.
Für ist , und man erhält den zuvor genannten Satz von Erdős-Rado als Spezialfall. Aus dem Monotonieeigenschaften der Pfeilnotation folgt aus dem Fall des Satzes von Erdős-Rado:
Literatur Bearbeiten
- Thomas Jech: Set Theory, Springer-Verlag (2003), ISBN 3-540-44085-2, insbesondere Kapitel 9