Schreier's lemma

In group theory, Schreier's lemma is a theorem used in the Schreier–Sims algorithm and also for finding a presentation of a subgroup.

Statement

Suppose is a subgroup of with generating set, that is,.
Let be a right transversal of in with the neutral element in. In other words, let be a set containing exactly one element from each right coset of in.
For each, we define as the chosen representative of the coset in the transversal.
Then is generated by the set
Hence, in particular, Schreier's lemma implies that every subgroup of finite index of a finitely generated group is again finitely generated.

Example

The group is cyclic. Via Cayley's theorem, is isomorphic to a subgroup of the symmetric group. Now,
where is the identity permutation. Note that is generated by.
has just two right cosets in, namely and, so we select the right transversal, and we have
Finally,
Thus, by Schreier's lemma, generates, but having the identity in the generating set is redundant, so it can be removed to obtain another generating set for,.