次の命題は周知だが復習もかねて証明する。

命題
n > 0 を整数とし、集合 {1, ..., n} の置換全体のなす
対称群を S_n とする。
S_n の任意の元 σ はいくつかの互換の積として表すことが出来る。

証明
n に関する帰納法を使う。
n = 1 なら明らか(零個の互換の積は恒等置換とみなす)。
n ≧ 2 とする。
σ(n) = n なら σ は S_(n-1) の元とみなせる。
よって帰納法の仮定より、σ は互換の積となる。
よって σ(n) ≠ n とする。σ(n) = j とおく。
τ = (j, n)σ とおく。
τ(n) = (j, n)(σ(n)) = n である。
よって τは S_(n-1) の元とみなせる。
よって帰納法の仮定より、τ は互換の積となる。
よってσ = (j, n)τも互換の積となる。
証明終