Satz von Erdős-Rado

aus Wikipedia, der freien Enzyklopädie
Zur Navigation springen Zur Suche springen

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 | Quelltext 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:

Ist eine Zerlegung von in (paarweise disjunkte) Teilmengen, so enthält wenigstens eine dieser Zerlegungsmengen eine Teilmenge der Form , wobei die Mächtigkeit hat.

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 die 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:

für alle natürlichen Zahlen .

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

oder genauer ,

wobei die Nachfolger-Kardinalzahl von bezeichnet.

Formulierung des Satzes

[Bearbeiten | Quelltext 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. Wegen der Monotonieeigenschaften der Pfeilnotation folgt aus dem Fall des Satzes von Erdős-Rado:

für alle unendlichen Kardinalzahlen .