Schreier's lemma
ProvedFamousTheorems.schreier_lemmaSchreier's lemma. Let be a subgroup of a group generated by a set , and let be a right transversal of in with . For write for the representative in of the coset . Then is generated by the Schreier generators
In particular a subgroup of finite index in a finitely generated group is finitely generated, with at most generators. The lemma is the basis of the Schreier–Sims algorithm in computational group theory and of the Nielsen–Schreier rank formula for subgroups of free groups.
Formalization note. Mathlib's Subgroup.closure_mul_image_eq. Subgroup.IsComplement (H : Set G) R says every element of factors uniquely as with , (so is a right transversal), and hR.toRightFun g is the representative . R * S is the pointwise product set.
Preamble
import Mathlib
Formal statement
namespace FamousTheorems
open scoped Pointwise
theorem schreier_lemma {G : Type*} [Group G] {H : Subgroup G} {R S : Set G} (hR : Subgroup.IsComplement (H : Set G) R)
(hR1 : (1 : G) ∈ R) (hS : Subgroup.closure S = ⊤) :
Subgroup.closure ((R * S).image fun g => g * (hR.toRightFun g : G)⁻¹) = H := by sorry
end FamousTheoremsSource
Listed in Mathlib's curated theorem manifests (docs/1000.yaml); formalized in Mathlib as `Subgroup.closure_mul_image_eq`. Proof here reduces to that Mathlib result.