Endliche Menge/Gleiche Anzahl/Injektiv ist surjektiv/Fakt/Beweis

Beweis

Wir führen Induktion über die Anzahl $n$ der beiden Mengen $M$ und $N$. Bei  $n=0$  gibt es nur die leere Abbildung (von der leeren Menge in die leere Menge), und diese erfüllt alle drei Eigenschaften. Es sei nun  $n\ge 1$  und die Aussage für alle endlichen Mengen $M$ mit einer Anzahl $<n$ bewiesen. Es muss lediglich die Äquivalenz von injektiv und surjektiv gezeigt werden. Es sei zunächst $F$ injektiv. Wir wählen ein Element  $x\in M$  und setzen  $y=F(x)$.  Wir setzen

$M^{\prime }=M\setminus \{x\}\text{ und }{N}^{\prime }=N\setminus \{y\}.$

Beide Mengen haben nach Fakt $n-1$ Elemente, und somit kann man darauf die Induktionsvoraussetzung anwenden. Es sei

$F^{\prime }:M^{\prime }⟶N^{\prime },x⟼F(x).$

Diese Abbildung ist wohldefiniert, da wegen der Injektivität nur das Element $x$ auf $y$ abgebildet wird, alle anderen Elemente aus $M^{\prime }$ werden auf andere Elemente abgebildet, d.h. sie landen in $N^{\prime }$. Die Injektivität von $F$ überträgt sich auf $F^{\prime }$. Nach der Induktionsvoraussetzung ist also $F^{\prime }$ auch surjektiv. Damit ist aber insgesamt $F$ surjektiv, da einerseits $y$ im Bild liegt (mit $x$ als Urbild) und da andererseits jedes Element  $z\ne y$  zu $N^{\prime }$ gehört und damit ein Urbild in $M^{\prime }$ besitzt.

Es sei nun $F$ surjektiv. Sei  $x\in M$  beliebig und  $y=F(x)$.  Wir betrachten die Einschränkung

$F^{\prime }:M^{\prime }=M\setminus \{x\}⟶N.$

Diese Abbildung kann nicht surjektiv sein. Andernfalls würde sich nämlich der Widerspruch

$n=\mathrm{\#}\left(M\right)>\mathrm{\#}(M\setminus \{x\})\ge \mathrm{\#}(F(M\setminus \{x\}))=\mathrm{\#}\left(N\right)=n$

ergeben. Daher muss $y$ im Bild von $F^{\prime }$ fehlen, und das heißt, dass eine surjektive Abbildung

$M\setminus \{x\}⟶N\setminus \{y\}$

vorliegt. Beide Mengen besitzen $n-1$ Elemente, sodass nach der Induktionsvoraussetzung hier eine Bijektion vorliegt. Damit ist auch die ursprüngliche Abbildung eine Bijektion.

Zur bewiesenen Aussage