Endliche Mengen und Bijektionen

Im Fall der Abbildung einer endlichen Menge auf sich sind die Eigenschaften injektiv und bijektiv gleichwertig. Es gilt:

$f:A \rightarrow A$ eine Abbildung einer endlichen Menge $A$ auf sich. Dann sind die folgenden Aussagen paarweise äquivalent.

Wir zeigen, dass aus der Injektivität von $f$ die Surjektivität folgt. Danach ergibt sich die Gültigkeit der Äquivalenzen aus der Definition der Bijektivität und aussagenlogischen Identitäten.

Endlichkeit bedeutet die bijektive Abbildbarkeit auf einen Abschnitt der natürlichen Zahlen $A_n=\{1,\dots,n\}$. Daher reicht es, die Behauptungen für solche Abschnitte $A_n$ zu zeigen. Diesen Beweis führen wir durch vollständige Induktion.

Betrachten wir nun eine beliebige injektive Abbildung $f:A_n\to A_n$. Injektivität bedeutet, dass verschiedenen Elemente aus $A_n$ auch verschiedene Werte zugeordnet werden. Da es nun aber genau $n$ Elemente gibt, muss jedes auch als Bild auftreten. Daher ist $f$ surjektiv. $\qed$