Satz von Erdős-Rado

aus Wikipedia, der freien Enzyklopädie
(Weitergeleitet von Satz von Erdös-Rado)
Wechseln zu: Navigation, Suche

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 A sei [A]^n die Menge aller n-elementigen Teilmengen von A, wobei n eine natürliche Zahl sei. Für Kardinalzahlen \kappa,\lambda, m schreibt man

\kappa \rightarrow (\lambda)^n_m,

falls folgende Aussage richtig ist:

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

Diese auf P. Erdős und R. Rado zurückgehende Pfeilnotation soll hier durch einige Beispiele verdeutlicht werden. Der Fall n=1 bedeutet einfach, dass bei einer Zerlegung von \kappa in m Teile wenigstens ein Teil die Mächtigkeit \lambda haben muss. Allein aus Mächtigkeitsgründen gilt also für unendliche Kardinalzahlen \kappa > \lambda, dass \kappa \rightarrow (\lambda)^1_2 oder \kappa \rightarrow (\lambda)^1_{\aleph_0}, wobei \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 n\ge 2. So lässt sich der Satz von Ramsey in der Pfeilnotation wie folgt formulieren:

\aleph_0 \rightarrow (\aleph_0)^n_m für alle natürlichen Zahlen m,n.

Man beachte, dass die Aussage \kappa \rightarrow (\lambda)^n_m richtig bleibt, wenn man zu größeren Kardinalzahlen \kappa übergeht oder wenn man eine der Größen \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 \kappa \rightarrow (\lambda)^n_m nicht, so schreibt man auch \kappa \not\rightarrow (\lambda)^n_m. Ist m=2, so lassen manche Autoren den Index m gerne weg.

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

2^\kappa \not\rightarrow (\kappa^+)^2, oder genauer 2^\kappa \not\rightarrow (\kappa^+)^2_2

wobei \kappa^+ die Nachfolger-Kardinalzahl von \kappa bezeichnet.

Formulierung des Satzes[Bearbeiten]

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

  • \beth_n^+ \rightarrow (\aleph_1)_{\aleph_0}^{n+1} für alle natürlichen Zahlen n.

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

Die oben genannte auf Sierpiński zurückgehende Aussage besagt für \kappa=\aleph_0, dass 2^{\aleph_0}\not\rightarrow (\aleph_1)^2_2, oder wegen des Monotonieverhaltens \kappa \not\rightarrow (\aleph_1)^2_2 für alle \kappa \le 2^{\aleph_0}. Der Satz von Erdős-Rado trifft nun die positive Aussage \kappa \rightarrow (\aleph_1)^2_2 für alle \kappa > 2^{\aleph_0}, denn für n=1 erhält man 2^{\aleph_0} \rightarrow (\aleph_1)^2_{\aleph_0} 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 \kappa definiere rekursiv

\exp_0(\kappa) \,=\, \kappa
\exp_{n+1}(\kappa) \,=\, 2^{\exp_n(\kappa)}.

Dann gilt

  • \exp_n(\kappa)^+ \rightarrow (\kappa^+)^{n+1}_{\kappa} für alle natürlichen Zahlen n und alle unendlichen Kardinalzahlen \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 \mu sein muss, damit die Partitionseigenschaft \mu\rightarrow (\kappa^+)^2_{\kappa} erfüllt ist: Es muss \mu \,>\, \exp_n(\kappa) sein.

Für \kappa = \aleph_0 ist \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 n=1 des Satzes von Erdős-Rado:

(2^\kappa)^+\rightarrow (\kappa^+)^2 für alle unendlichen Kardinalzahlen \kappa.

Literatur[Bearbeiten]