Vergleichbarkeitssatz
# Vergleichbarkeitssatz

In der elementaren Mengenlehre gibt es zwei wichtige Vergleichbarkeitssätze:
* 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.)
* 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.