Proposition 8

Let E be a finite set. The group $\mathfrak{S}_E$ is generated by the transpositions.

For every permutation $\sigma$ let $F_\sigma$ be the set of $x \in E$ such that $\sigma(x) = x$. We show by descending induction on $p$ that every permutation $\sigma$ such that $\mathrm{Card}(F_\sigma) = p$ is a product of transpositions. If $p \geq \mathrm{Card}(E)$, the permutation $\sigma$ is the identity mapping of E; it is the product of the empty family of transpositions. If $p < \mathrm{Card}(E)$, suppose that the property is proved for every permutation $\sigma'$ such that $\mathrm{Card}(F_{\sigma'}) > p$. Now $E - F_\sigma \neq \varnothing$; let $x \in E - F_\sigma$ and $y \in \sigma(x)$. Then $y \neq x$ and $y \in E - F_\sigma$. Let $\sigma' = \tau_{x,y} \cdot \sigma$. The set $F_{\sigma'}$ contains $F_\sigma$ and $x$ and hence $\mathrm{Card}(F_{\sigma'}) > \mathrm{Card}(F_\sigma) = p$. By the induction hypothesis $\sigma'$ is a product of transpositions and hence $\sigma = \tau_{x,y} \cdot \sigma'$ is a product of transpositions.