Satz von Ramsey (Mengenlehre)

Der Satz v​on Ramsey i​st ein v​on F. P. Ramsey i​m Jahre 1929 bewiesener Satz a​us dem mathematischen Gebiet d​er Mengenlehre. Er verallgemeinert d​ie einfache Tatsache, d​ass bei e​iner Zerlegung e​iner unendlichen Menge i​n endlich v​iele Teilmengen wenigstens e​ine dieser Teilmengen ebenfalls unendlich s​ein muss.

Formulierung des Satzes

Ist ${\displaystyle A}$ eine unendliche Menge, so bezeichne ${\displaystyle [A]^{n}}$ die Menge aller ${\displaystyle n}$-elementigen Teilmengen von ${\displaystyle A}$. Zerlegt man ${\displaystyle [A]^{n}}$ in endlich viele Teilmengen, so muss eine der Teilmengen wieder unendlich sein. Darüber hinaus kann man folgende stärkere Aussage aufstellen, die als Satz von Ramsey bekannt ist:

• Ist ${\displaystyle \omega }$ die Menge der natürlichen Zahlen und ist ${\displaystyle [\omega ]^{n}=X_{1}\cup \ldots \cup X_{m}}$ eine Zerlegung in ${\displaystyle m}$ Teilmengen, wobei ${\displaystyle m}$ und ${\displaystyle n}$ natürliche Zahlen seien, so gibt es ein ${\displaystyle j\in \{1,\ldots ,m\}}$ und eine unendliche Teilmenge ${\displaystyle H\subset \omega }$ mit ${\displaystyle [H]^{n}\subset X_{j}}$.

Bemerkungen

Teilmengen von ${\displaystyle [\omega ]^{n}}$ der Form ${\displaystyle H^{n}}$ nennt man homogen. Nach dem Satz von Ramsey gilt also, dass jede Zerlegung von ${\displaystyle [\omega ]^{n}}$ in endlich viele Teilmengen, wenigstens eine unendliche homogene Teilmenge enthält. Der Fall ${\displaystyle n=1}$ reduziert sich auf die in der Einleitung genannte Tatsache, dass bei einer Zerlegung einer unendlichen Menge in endlich viele Teilmengen wenigstens eine dieser Teilmengen ebenfalls unendlich sein muss.

${\displaystyle \omega }$ ist der Prototyp einer Menge der Mächtigkeit ${\displaystyle \aleph _{0}}$ (siehe Aleph-Funktion) und kann im Satz von Ramsey natürlich durch jede andere Menge dieser Mächtigkeit ersetzt werden. Ist ${\displaystyle A}$ eine Menge der Mächtigkeit ${\displaystyle \aleph _{1}}$, so könnte man in Analogie zu obigem Satz fragen, ob bei einer Zerlegung der Menge ${\displaystyle [A]^{n}}$ in ${\displaystyle m}$ Teilmengen wenigstens eine der Zerlegungsmengen eine homogene Teilmenge der Mächtigkeit ${\displaystyle \aleph _{1}}$ enthalten muss. Für ${\displaystyle n=1}$ lautet die Antwort natürlich ja, aber schon für ${\displaystyle m=n=2}$ muss sie verneint werden. Die Existenz von Kardinalzahlen ${\displaystyle \kappa >\aleph _{0}}$, so dass bei einer Zerlegung von ${\displaystyle [\kappa ]^{2}}$ in zwei Teilmengen wenigstens eine dieser Teilmengen eine homogene Teilmenge der Mächtigkeit ${\displaystyle \kappa }$ umfassen muss, lässt sich in der ZFC-Mengenlehre nicht beweisen. Solche Kardinalzahlen nennt man schwach-kompakt und deren Nicht-Existenz ist zumindest relativ konsistent, das heißt, wenn die ZFC-Mengenlehre widerspruchsfrei ist, dann ist sie auch zusammen mit dem zusätzlichen Axiom der Nicht-Existenz schwach-kompakter Kardinalzahlen widerspruchsfrei.

Siehe auch

• Satz von Ramsey, ein Satz aus der kombinatorischen Graphentheorie
• Satz von Erdős-Rado, ein Satz über Partitionen von Mengen der Form ${\displaystyle [\kappa ]^{n}}$.

Literatur

• Thomas Jech: Set Theory, Springer-Verlag (2003), ISBN 3-540-44085-2, insbesondere Kapitel 9
• F. P. Ramsey: On a Problem of Formal Logic, Proc. London Mathematical Society 1929/1930, Band 30, Seiten 264–186