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

Beweisarchiv: Mengenlehre

Charakteristikum unendlicher Mengen

Injektivität Surjektivität Bijektivität: Faktoren · Komposition · Linksinverse · Linkskürzbarkeit · Rechtsinverse · Rechtskürzbarkeit

Verkettungen: Assoziativgesetz der Hintereinanderausführung

Mächtigkeiten (Kardinalzahlen): lineare Ordnung · Kardinalität und Bijektionen · Potenzmenge

Deskriptive Mengenlehre: Satz von Young

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

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\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|$.