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

Sind $A,B$ Mengen, so schreiben wir $|A|\le |B|$, falls es eine injektive Abbildung $f:A\to B$ gibt. Wir schreiben $|A|=|B|$ bzw. sagen, dass $A$ und $B$ gleichmächtig sind, falls $|A|\le |B|$ und $|B|\le |A|$.

Satz

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

Beweis

Falls es eine Bijektion $h: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:A\to B$ und $g:B\to A$ injektiv. Wir definieren jetzt eine Abbildung $h: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\ge 1}{A}_n$.

• Ist $a\in C$, so setze $h(a)=f(a)$.
• Ist $a\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\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\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\in ̸C$ und $a_2\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\ge 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$.

Folglich ist $h:A\to B$ eine Bijektion.

Satz

Sei $A\subseteq B$ so gilt, dass $|A|\le |B|$

Beweis

Für den Fall, dass $A=\mathrm{\varnothing }$ ist die Aussage trivial, also betrachten wir nur den Fall, dass $A=\mathrm{\varnothing }$.

Da $A=\mathrm{\varnothing }\Rightarrow \mathrm{\exists }x\in A$. Bilde nun eine Abbildung

$f:B\to A,b\mapsto \{\begin{array}{cc}b& b\in A\\ x& b\notin A\end{array}$

Da $f$ surjektiv ist folgt die Behauptung.