Wenn
injektiv
ist, so ist
auch
bijektiv
und damit eine
Permutation,
und die Aussage gilt nach
Fakt
allein mit Transpositionen. Es sei also
nicht injektiv und seien
Elemente die beide auf das gleiche Element abgebildet werden. Es sei
die Abbildung, die
und
auf
abbildet und ansonsten die Identität ist. Dann
kann man
-

schreiben, wobei man
setzt, wobei
ein Element sei, das nicht zum Bild von
gehört, und man ansonsten
setzt - also insbesondere
. Wenn
ebenfalls nicht injektiv ist, so können wir mit entsprechenden Festsetzungen
-

schreiben. So machen wir Schritt für Schritt weiter. Da sich dabei bei jedem Schritt die Anzahl der Elemente im Bild von
erhöht, erreichen wir schließlich die Situation
-

wobei

bijektiv ist. Diese Bijektion können wir als Produkt von Transpositionen darstellen.