Beweisarchiv: Mengenlehre: Mächtigkeiten (Kardinalzahlen): Kardinalität und Bijektionen

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,B$ Mengen, so schreiben wir $|A|\leq |B|$ , falls es eine injektive Abbildung $f\colon A\to B$ gibt. Wir schreiben $|A|=|B|$ bzw. sagen, dass $A$ und $B$ gleichmächtig sind, falls $|A|\leq |B|$ und $|B|\leq |A|$ .

Satz

Zwei Mengen $A,B$ sind genau dann gleichmächtig, wenn es eine Bijektion $h\colon A\to B$ gibt.

Beweis

Falls es eine Bijektion $h\colon A\to B$ gibt, ist klar, dass $|A|=|B|$ gilt, da sowohl die Abbildung $h$ als auch deren Umkehrung injektiv ist.

Es gelte jetzt $|A|=|B|$ , und zwar seien $f\colon A\to B$ und $g\colon B\to A$ injektiv. Wir definieren jetzt eine Abbildung $h\colon A\to B$ wie folgt: Sei $A_{1}=A\setminus g(B)$ und dann rekursiv $A_{n+1}=g(f(A_{n}))$ . Sei $C=\bigcup _{n\geq 1}A_{n}$ .

Ist $a\in C$ , so setze $h(a)=f(a)$ .
Ist $a\not \in C$ , so folgt insbesondere $a\in g(B)$ , wir können somit $h(a)=g^{-1}(a)$ setzen.

Diese Abbildung $h$ ist injektiv: Es gelte $h(a_{1})=h(a_{2})$ für zwei Elemente $a_{1},a_{2}\in A$ .

Ist $a_{1}\in C$ und $a_{2}\not \in C$ , so ergibt sich mit $a_{2}=g(h(a_{2}))=g(h(a_{1}))=g(f(a_{1}))\in A_{n+1}$ ein Widerspruch.
Der Fall $a_{2}\in C$ und $a_{1}\not \in C$ ist ebenso ausgeschlossen.
Ist $a_{1}\in C$ und $a_{2}\in C$ , so folgt $f(a_{1})=h(a_{1})=h(a_{2})=f(a_{2})$ , also $a_{1}=a_{2}$ .
Ist weder $a_{1}\not \in C$ und $a_{2}\not \in C$ , so folgt $a_{1}=g(h(a_{1}))=g(h(a_{2}))=a_{2}$ .

Die Abbildung ist aber auch surjektiv: Sei $b\in B$ beliebig.

Ist $g(b)\in A_{n}$ für ein $n\geq 1$ , so folgt nach Definition von $A_{1}$ , dass sogar $n>1$ gilt. Folglich ist $g(b)=g(f(a))$ für ein $a\in A_{n-1}$ und $h(a)=f(a)=b$ .
Ansonsten gilt $h(g(b))=g^{-1}(g(b))=b$ .