The symmetric group is generated by transpositions
ProvedFamousTheorems.perm_generated_by_transpositions_7bThe symmetric group is generated by transpositions. Let be a finite set. Every permutation of is a product of transpositions, that is, the subgroup of generated by the transpositions is the whole group.
This is the basic generation result for the symmetric group. It is used to define the sign of a permutation, to prove that a function that is multiplicative and on transpositions is the sign, and in the proof of the Leibniz formula for determinants. It follows by writing each cycle as .
Formalization note. Mathlib's Equiv.Perm.closure_isSwap. σ.IsSwap says that is the transposition of two distinct elements, and Subgroup.closure is the subgroup generated by a set.
Preamble
import Mathlib
Formal statement
namespace FamousTheorems
theorem perm_generated_by_transpositions_7b (α : Type*) [DecidableEq α] [Finite α] : Subgroup.closure {σ : Equiv.Perm α | σ.IsSwap} = ⊤ := by sorry
end FamousTheoremsSource
Listed in Mathlib's curated theorem manifests (docs/1000.yaml); formalized in Mathlib as `Equiv.Perm.closure_isSwap`. Proof here reduces to that Mathlib result.