Sei n eine positive natürliche Zahl und sei M eine n-elementige Menge.

(i)
Die einzige Abbildung, die eine einelementige Menge auf sich selbst abbildet, ist die Identität. Diese ist offenbar injektiv, damit ist der Induktionsanfang fertig.

Wir nehmen nun an, dass die Aussage für eine natürliche Zahl n stimmt (X) und folgern daraus, dass sie auch für n+1 stimmen muss.

Sei also f : M → M eine injektive Abbildung und |M|=n+1. Sei weiterhin m ein Element aus M. 

Weil f injektiv ist, ist auch die Einschränkung \(f'=f|_{M \backslash \{ m \} }\) eine injektive Abbildung. Die Injektivität von f sagt uns außerdem, dass wir aus der Bildmenge von f' problemlos f(m) entfernen können, da f(m) kein anderes Urbild als m haben kann. 

Damit ist f' : M\{m}  → M\{f(m)} eine injektive Abbildung zwischen zwei n-elementigen Mengen, die nach (X) auch surjektiv sein muss. 

Also hat jedes Element in M\{f(m)} ein f-Urbild in M - aber f(m) hat auch ein Urbild in M, nämlich m. Insgesamt hat also jedes Element in M ein Urbild in M, also ist f auch surjektiv.

(ii) Die Aussage gilt auch andersrum, ja: 

Wäre die Abbildung f : M → M nicht injektiv und |M|=n, so gäbe es m,m' in M, die ungleich sind, für die aber gilt f(m)=f(m'). In M\{m,m'} sind dann noch n-2 Elemente enthalten, die Bildmenge f(M\{m,m'}) hat also maximal n-2 Elemente. Da die Bildmenge f(M) aber die Vereinigung von f(M\{m,m'}) und {f(m)} ist (da ja f(m)=f(m') muss f(m') nicht mehr erwähnt werden), ist |f(M)| kleiner oder gleich n-2+1 und daher |f(M)|

vielen dank