imported>Cgolds: /* Die Pfeilnotation */ Die originelle Menge hier is kappa, nicht A

2024-08-12T13:28:41Z

Die Pfeilnotation: Die originelle Menge hier is kappa, nicht A

Neue Seite

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 ==
Für eine Menge <math>A</math> sei <math>[A]^n</math> die Menge aller <math>n</math>-elementigen Teilmengen von <math>A</math>, wobei <math>n</math> eine natürliche Zahl sei. Für [[Kardinalzahl (Mathematik)|Kardinalzahlen]] <math>\kappa</math>, <math>\lambda</math>, <math>m</math> schreibt man
:<math>\kappa \rightarrow (\lambda)^n_m</math>,
falls folgende Aussage richtig ist:
: Ist <math>[\kappa]^n = \bigcup _{\alpha<m}X_\alpha</math> eine Zerlegung von <math>[\kappa]^n</math> in <math>m</math> (paarweise disjunkte) Teilmengen, so enthält wenigstens eine dieser Zerlegungsmengen <math>X_\alpha</math> eine Teilmenge der Form <math>[H]^n</math>, wobei <math>H\subset \kappa</math> die [[Mächtigkeit (Mathematik)|Mächtigkeit]] <math>\lambda</math> hat.

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

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

Gilt die Aussage <math>\kappa \rightarrow (\lambda)^n_m</math> nicht, so schreibt man auch <math>\kappa \not\rightarrow (\lambda)^n_m</math>. Ist <math>m=2</math>, so lassen manche Autoren den Index <math>m</math> gerne weg.

[[Wacław Sierpiński|W. Sierpiński]] hat für unendliche Kardinalzahlen <math>\kappa</math> gezeigt, dass
: <math>2^\kappa \not\rightarrow (\kappa^+)^2</math> oder genauer <math>2^\kappa \not\rightarrow (\kappa^+)^2_2</math>,
wobei <math>\kappa^+</math> die Nachfolger-Kardinalzahl von <math>\kappa</math> bezeichnet.

== Formulierung des Satzes ==
Unter Verwendung obiger Pfeilnotation und der [[Beth-Funktion]] <math>\beth</math> lautet der Satz von Erdős-Rado:
* <math>\beth_n^+ \rightarrow (\aleph_1)_{\aleph_0}^{n+1}</math> für alle natürlichen Zahlen <math>n</math>.

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

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

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 <math>\mu</math> sein muss, damit die Partitionseigenschaft <math>\mu\rightarrow (\kappa^+)^2_{\kappa}</math> erfüllt ist: Es muss <math>\mu \,>\, \exp_n(\kappa)</math> sein.

Für <math>\kappa = \aleph_0</math> ist <math>\exp_n(\kappa) = \beth_n</math>, und man erhält den zuvor genannten Satz von Erdős-Rado als Spezialfall. Wegen der Monotonieeigenschaften der Pfeilnotation folgt aus dem Fall <math>n=1</math> des Satzes von Erdős-Rado:
: <math>(2^\kappa)^+\rightarrow (\kappa^+)^2</math> für alle unendlichen Kardinalzahlen <math>\kappa</math>.

== Literatur ==
* [[Thomas Jech]]: ''Set Theory'', Springer-Verlag (2003), ISBN 3-540-44085-2, insbesondere Kapitel 9.

[[Kategorie:Ramseytheorie]]
[[Kategorie:Satz (Mengenlehre)|ErdosRado, Satz von]]
[[Kategorie:Paul Erdős]]

Satz von Erdős-Rado - Versionsgeschichte

imported>Cgolds: /* Die Pfeilnotation */ Die originelle Menge hier is kappa, nicht A