We begin with a lemma that among other things demonstrates that most free groups are non-trivial
Lemma 1: If are sets then the map , induced by inclusion has a left inverse. Consequently, is injective.
Proof: Let and be the roses with petals indexed by and respectively. In particular we have that and . If we view as a subspace of in the obvious way then there exists such that (One such map is obtained by crushing the petals in ). This map induces a function and this map can easily be seen to be the desired left inverse. QED
The next thing that we would like to do is examine exactly what do elements of free groups “look like.” Informally, elements look like words in the elements of where only the obvious cancellations by inverses are allowed. More formally, we will identify the elements of with their images under the map (This is not the same from Lemma 1). Next we consider products of the form , where and . Next, we prove a theorem that formalizes the previous intuition about free groups
Normal Form Theorem: Given a free group the following 2 statements are true
- Every element of is of the form .
- If then is either the empty word or there exists such that and
Proof: We will prove the theorem when , but the proof generalizes to sets of all cardinality. Let be the rose with 2 petals and wedge point and so we have that . Next, let be the universal cover of based at . Because acts freely on and has only one vertex we see that the vertices of are in bijection with the elements of . We next observe 2 facts. First, from lemma 1 we see that since is simply connected that it must be a tree. Second, since each vertex of looks locally like we see that every vertex of is 4-valent. From covering space theory we know that if and is a vertex of then the lift of to that starts at ends at .
We proceed by induction on , which is the minimum number of edges between and . Suppose that . Since is a tree with all 4-valent vertices we see that there exists such that and . Next, observe that there exists such that when is lifted at ends at . Therefore we see that and since the group action is free this implies that which proves 1.
For the second proposition, suppose that and that the second proposition is not true. From covering space theory we know that the lift of at is a loop based at . First, since is not the empty word we see that it will not lift to the constant path. Finally, since contains no obvious cancellations we see that must contain a loop based at that is not the constant loop, which contradicts the fact that is a tree. Thus 2 must hold. QED
As a consequence of the previous theorem we see that it is possible to solve the word problem of whether it is algorithmically possible to decide if a group element is the identity.
Definition: A group is finitely generated if and only if there exists a surjection from to for some finite .
- Show that if then has finitely many subgroups of index .
- Deduce that the same holds for any finitely generated group .