Beweisarchiv: Mengenlehre: Mächtigkeiten (Kardinalzahlen): lineare Ordnung

Sind $A$ und $B$ zwei Mengen, so schreiben wir $|A|\le |B|$ genau dann, wenn es eine injektive Abbildung $f:A\to B$ gibt. Im folgenden wird gezeigt, dass diese Relation die Axiome einer linearen Ordnung erfüllt.

Hierdurch wird es sinnvoll, $|A|=|B|$ als $|A|\le |B|\wedge |B|\le |A|$ sowie $|A|<|B|$ als $|A|\le |B|\wedge \mathrm{\neg }(|B|\le |A|)$ zu definieren.

Reflexivität

Voraussetzung

Sei $A$ eine beliebige Menge.

Behauptung

$|A|\le |A|$.

Beweis

Die identische Abbildung $id:A\to A$ ist injektiv.

Transitivität

Voraussetzung

Seien $A,B,C$ Mengen mit $|A|\le |B|$ und $|B|\le |C|$.

Behauptung

$|A|\le |C|$.

Beweis

Nach Voraussetzung gibt es injektive Abbildungen $f:A\to B$ und $g:B\to C$. Da die Komposition injektiver Abbildungen injektiv ist, leistet $g\circ f:A\to C$ das Gewünschte.

Totalität

Voraussetzung

Seien $A,B$ zwei Mengen.

Behauptung

$|A|\le |B|$ oder $|B|\le |A|$.

Beweis

Dieser Beweis erfordert das Auswahlaxiom, hier in Form des Lemmas von Zorn.

Sei $T$ die Menge aller Graphen injektiver partieller Abbildungen von $A$ nach $B$, d. h. $T$ enthält $F$ als Element genau dann, wenn

1. $F\subseteq A\times B$
2. Aus $(a,b_1)\in F$ und $(a,b_2)\in F$ mit $a\in A$, $b_1,b_2\in B$ folgt $b_1=b_2$
3. Aus $(a_1,b)\in F$ und $(a_2,b)\in F$ mit $a_1,a_2\in A$, $b\in B$ folgt $a_1=a_2$.

Dann ist $T$ durch Mengeninklusion teilgeordnet. Sei $K\subseteq T$ eine linear geordnete Teilmenge von $T$. Setze

$S:=\bigcup K=\bigcup _{F\in K}F.$

Dann ist $S$ eine obere Schranke von $K$ in $T$, was sich wie folgt im Einzelnen zeigen lässt:

• Als Vereinigung von Teilmengen von $A\times B$ ist auch $S\subseteq A\times B$.
• Seien $a\in A$, $b_1,b_2\in B$ mit $(a,b_1)\in S$ und $(a,b_2)\in S$. Dann gibt es $F_1,F_2\in K$ mit $(a,b_1)\in F_1$ und $(a,b_2)\in F_2$. Da $K$ total geordnet ist, gilt $F_1\subseteq F_2$ oder $F_2\subseteq F_1$. Im ersten Fall folgt $(a,b_1)\in F_2$ und daher $b_1=b_2$ wegen $F_2\in T$, im zweiten Fall $(a,b_2)\in F_1$ und wiederum $b_1=b_2$.
• Dass aus $(a_1,b)\in S$ und $(a_2,b)\in S$ mit $a_1,a_2\in A$, $b\in B$ stets $a_1=a_2$ folgt, ergibt sich analog.

Somit gilt zumindest $S\in T$. Nach Konstruktion gilt aber $F\subseteq S$ für alle $F\in K$, so dass $S$ in der Tat eine obere Schranke ist.

Nach dem Lemma von Zorn enthält $T$ folglich ein maximales Element $M$. Man kann $M$ auffassen als den Graphen einer bijektiven Abbildung $f:A^{\prime }\to B^{\prime }$ mit $A^{\prime }:=\{a\in A\mid \mathrm{\exists }b\in B:(a,b)\in M\}$ und $B^{\prime }:=\{b\in B\mid \mathrm{\exists }a\in A:(a,b)\in M\}$.

Falls sowohl $A^{\prime }\ne A$ als auch $B^{\prime }\ne B$ gilt, so gibt es Elemente $a_0\in A\setminus A^{\prime }$ und $b_0\in B\setminus B^{\prime }$. Hiermit kann man die Menge $M^{\prime }:=M\cup \{(a_0,b_0)\}$ bilden. Diese erfüllt, wie sich direkt überprüfen lässt, die drei oben aufgeführten Eigenschaften, ist also ein Element von $T$. Da $M$ echte Teilmenge von $M^{\prime }$ ist, ergibt sich ein Widerspruch zur Maximalität von $M$ Folglich muss $A=A^{\prime }$ oder $B=B^{\prime }$ gelten.

Falls $A^{\prime }=A$, so ist $f$ auch eine injektive Abbildung $A\to B$, folglich $|A|\le |B|$. Falls dagegen $B^{\prime }=B$, so ist die Umkehrung $f^{-1}:B^{\prime }\to A^{\prime }$ auch eine injektive Abbildung $B\to A$, folglich $|B|\le |A|$.