Beweis

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

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

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

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

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

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

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

Folglich ist ${\displaystyle h\colon A\to B}$ eine Bijektion.

Beweis

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

Da ${\displaystyle A\not =\emptyset \Rightarrow \exists x\in A}$. Bilde nun eine Abbildung

${\displaystyle f:B\rightarrow A,\quad b\mapsto {\begin{cases}b&\quad b\in A\\x&\quad b\notin A\end{cases}}}$

Da ${\displaystyle f}$ surjektiv ist folgt die Behauptung.