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.