Endliche Menge/Gleiche Anzahl/Injektiv ist surjektiv/Fakt/Beweis
Wir führen Induktion über die Anzahl der beiden Mengen und . Bei gibt es nur die leere Abbildung (von der leeren Menge in die leere Menge), und diese erfüllt alle drei Eigenschaften. Es sei nun und die Aussage für alle endlichen Mengen mit einer Anzahl bewiesen. Es muss lediglich die Äquivalenz von injektiv und surjektiv gezeigt werden. Es sei zunächst injektiv. Wir wählen ein Element und setzen . Wir setzen
Beide Mengen haben nach Fakt Elemente, und somit kann man darauf die Induktionsvoraussetzung anwenden. Es sei
Diese Abbildung ist wohldefiniert, da wegen der Injektivität nur das Element auf abgebildet wird, alle anderen Elemente aus werden auf andere Elemente abgebildet, d.h. sie landen in . Die Injektivität von überträgt sich auf die Teilmenge . Nach der Induktionsvoraussetzung ist also surjektiv. Damit ist aber insgesamt surjektiv, da einerseits im Bild liegt (mit als Urbild) und da andererseits jedes Element zu gehört und damit ein Urbild in besitzt.
Es sei nun surjektiv. Sei beliebig und . Wir betrachten die Einschränkung
Diese Abbildung kann nicht surjektiv sein. Andernfalls würde sich nämlich der Widerspruch
ergeben. Daher muss im Bild von fehlen, und das heißt, dass eine surjektive Abbildung
vorliegt. Beide Mengen besitzen Elemente, sodass nach der Induktionsvoraussetzung hier eine Bijektion vorliegt. Damit ist auch die ursprüngliche Abbildung eine Bijektion.