Vergleichbarkeitssatz

In der elementaren Mengenlehre gibt es zwei wichtige Vergleichbarkeitssätze:

1. Für beliebige Mengen $M$, $N$ gilt stets: $|M|\leq |N|$ oder $|N|\leq |M|$. wobei $|M|\leq |N|$ eine Kurzschreibweise für die Aussage, es gibt eine injektive Abbildung von $M$ nach $N$, ist.
   (Anmerkung: gelten beide Beziehungen, so sind die Mengen nach dem Cantor-Bernstein-Schröder-Theorem gleichmächtig.)
2. Wann immer $(A,<)$ und $(B,<)$ Wohlordnungen sind, ist eine dieser Wohlordnungen zu einem Anfangsabschnitt der anderen isomorph.

Beweisskizze des Satzes für wohlgeordnete Mengen

Für beliebige Wohlordnungen $(A,<)$ und $(B,<)$ definieren wir eine Relation $R_{A,B}\subseteq A\times B$ so:

$R_{A,B}:={\bigg \{}(a,b)\in A\times B:\{x\in A:x<a\}\simeq \{y\in B:y<b\}{\bigg \}}$

Man kann leicht zeigen, dass $R_{A,B}$ eine partielle injektive Funktion ist (rechtseindeutig und linkseindeutig), dass Definitionsbereich und Wertebereich Anfangsabschnitte von $A$ bzw. $B$ sind und dass diese Funktion streng monoton ist.

Die Annahme, dass sowohl Definitions- und Wertebereich echte Anfangsabschnitte von $A$ bzw. $B$ sind, führt auf einen Widerspruch; denn dann müsste es $a_{0}\in A$ und $b_{0}\in B$ geben, sodass $R_{A,B}$ eine Ordnungsisomorphie von $\{x\in A:x<a_{0}\}$ nach $\{y\in B:y<b_{0}\}$ wäre, also wäre nach Definition auch $(a_{0},b_{0})$ in $R_{A,B}$.

Daher ist entweder der Definitions- oder der Wertebereich von $R_{A,B}$ ganz $A$ bzw. ganz $B$. Damit ist dann $R_{A,B}$ entweder eine Isomorphie zwischen $A$ und einem Anfangsabschnitt von $B$, oder zwischen einem Anfangsabschnitt von $A$ und $B$.

Beweisskizze des Satzes für beliebige Mengen

Seien $M$ und $N$ beliebige Mengen. Nach dem Wohlordnungssatz gibt es auf $M$ und $N$ Wohlordnungen $(M,<)$ und $(N,<)$. Nach dem Vergleichbarkeitssatz für Wohlordnungen existiert ein Isomorphismus $f$ zwischen der einen Wohlordnung und einem Anfangsabschnitt der anderen. Diese Abbildung ist nun eine injektive Funktion von der einen in die andere Menge.

Die Notwendigkeit des Auswahlaxioms

Der Vergleichbarkeitssatz für wohlgeordnete Mengen kann ohne Verwendung des Auswahlaxioms bewiesen werden.

Aus dem Vergleichbarkeitssatz für beliebige Mengen folgt hingegen der Wohlordnungssatz, somit auch das Auswahlaxiom: Zu jeder Menge $M$ kann man nämlich nach dem Satz von Hartogs eine Ordinalzahl $\alpha$ finden, die nicht in $M$ injektiv eingebettet werden kann. Nach dem Vergleichbarkeitssatz muss es eine injektive Abbildung von $M$ nach $\alpha$ geben; so eine Abbildung induziert eine Wohlordnung auf $M$.

Der Vergleichbarkeitssatz für beliebige Mengen ist also (über der Theorie ZF) zum Auswahlaxiom äquivalent.

Geschichte

Der Satz wurde lange Zeit von Georg Cantor vermutet, konnte aber erst 1904 durch Ernst Zermelo bewiesen werden.

Literatur

• Oliver Deiser: Einführung in die Mengenlehre. Berlin 2004. ISBN 3-540-20401-6