- 1 Statement
- 2 Related facts
- 3 Related ideas
- 4 Proof
- 5 As an algorithm
Suppose is a subgroup of a group , and is a left transversal of in with the property that the representative of the coset itself is the identity element. Suppose is a generating set for . Then, define as the set of all elements in that can be written as where and are in and is in .
Then, is a generating set for .
Any subgroup of finite index in a finitely generated group (see also: subgroup of finite index in finitely generated group) is finitely generated. This follows because when and are both finite sets, so is .
- Local finiteness is extension-closed: A locally finite group is a group in which every finitely generated subgroup is finite. If is a group with a locally finite normal subgroup such that is also locally finite, then is locally finite. The proof of this uses Schreier's lemma.
- Freeness is subgroup-closed: Any subgroup of a free group is free, and moreover, if the subgroup has finite index, the number of generators of the subgroup is given as a function of the number of generators of the whole group, and the index of the subgroup. The proof of this is based on a closer analysis of the constructive statement of Schreier's lemma.
Analogues in other algebraic structures
- Artin-Tate lemma: This states that if are algebras over a commalg:Noetherian ring , with finitely generated as a -algebra and finitely generated as an -module, then is finitely generated as a -algebra. Here, being finitely generated as a -algebra plays the analogous role to being a finitely generated group, and being finitely generated as an -module plays the analogous role to a subgroup of finite index.
The key idea is to rewrite words originally in terms of in terms of , with a possible leading term from . If the word happens to be in the subgroup, the leading term from must be trivial, and thus, the word originally written in terms of is expressible in terms of .
Proof details in the form of a proof by induction
Given: A group with a subgroup having a left transversal . is a generating set for . is defined as the set of all elements of expressible as where and .
To prove: .
Proof: Let be the set of all elements of and their inverses. Let be the set of all elements of and their inverses. We will prove that for any :
where denote the elements of expressible as products of length at most from elements of , respectively.
We prove this claim by induction on . Let's first do the case . We need to show that any element of is in . We make two cases:
We now give the induction step.
Suppose . Then we can either write or write for . We examine both cases.
Thus, we have established that:
Now, any element of is in particular an element of , and since generates , every element of is in . Thus, for any element , we have:
But since , we have , so . In particular, this yields . But the coset representative in is by assumption trivial, so we get . Thus, . Since was arbitrary, this shows that every element of is in the subgroup generated by .
Proof details in the form of writing down expressionsPLACEHOLDER FOR INFORMATION TO BE FILLED IN: [SHOW MORE]
As an algorithm
Schreier's lemma can give an algorithm to compute a generating set for a subgroup starting from a generating set of the whole group and a system of coset representatives for the subgroup. The idea is to traverse all tuples of the form where and .
The problem of determining a system of coset representatives is solved by means of a bradth-first search in the Cayley graph of the action of on in terms of the specified generating set of .
Further information: Finding a generating set from a membership test