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

Rechenregeln für Mengenoperationen: Assoziativgesetze · Distributivgesetze · Differenzgesetze · Grundeigenschaften der Inklusion · De Morgansche Regeln für Mengen · Bild und Urbild

Ordinalzahlen: Ordinalzahlen enthalten sich nicht selbst als Element · Elemente von Ordinalzahlen sind Ordinalzahlen · Durchschnitte von Ordinalzahlen sind Ordinalzahlen · Wohlordnung der Klasse aller Ordinalzahlen · Ordinalzahlen bilden eine echte Klasse · Der Nachfolger einer Ordinalzahl ist Ordinalzahl · Vereinigungen von Ordinalzahlen sind Ordinalzahlen · Limes- und Nachfolgerzahlen · Äquivalenz verschiedener Definitionen

Sätze die in ZF Äquivalent zum Auswahlaxiom sind: Alternative Darstellung des Auswahlaxioms · Wohlordnungssatz · Lemma von Zorn

Sind $A$ und $B$ zwei Mengen, so schreiben wir $|A|\leq |B|$ genau dann, wenn es eine injektive Abbildung $f\colon 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|\leq |B|\land |B|\leq |A|$ sowie $|A|<|B|$ als $|A|\leq |B|\land \neg (|B|\leq |A|)$ zu definieren.

Reflexivität

Voraussetzung

Sei $A$ eine beliebige Menge.

Behauptung

$|A|\leq |A|$ .

Beweis

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

Transitivität

Voraussetzung

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

Behauptung

$|A|\leq |C|$ .

Beweis

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

Totalität

Voraussetzung

Seien $A,B$ zwei Mengen.

Behauptung

$|A|\leq |B|$ oder $|B|\leq |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

$F\subseteq A\times B$
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}$
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\colon A'\to B'$ mit $A':=\{a\in A\mid \exists b\in B\colon (a,b)\in M\}$ und $B':=\{b\in B\mid \exists a\in A\colon (a,b)\in M\}$ .

Falls sowohl $A'\neq A$ als auch $B'\neq B$ gilt, so gibt es Elemente $a_{0}\in A\setminus A'$ und $b_{0}\in B\setminus B'$ . Hiermit kann man die Menge $M':=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'$ ist, ergibt sich ein Widerspruch zur Maximalität von $M$ Folglich muss $A=A'$ oder $B=B'$ gelten.

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