Every finitely generated submonoid N ⊆ M is rational, but there also exist rational submonoids which are not finitely generated. The standard example for this is N = {(0, 0)}∪{ (m, n) ∈ℕ×ℕ|m ≥ 1 }; N is a submonoid of ℕ×ℕ but it cannot be finitely generated because for any finite set of pairs (mi , ni) the element (1, 1 + max{ni}) is in N but not in the submonoid generated by the pairs (mi , ni). The submonoid N is rational because N = {(0, 0)} ∪ {(1, 0)} + ({(1, 0)} ∪ {(0, 1)})∗. For groups the situation is different.

Theorem 8.21. Let H be a rational subgroup of a group G. Then H is finitely generated.

Proof: Since H is rational, there is a finite subset A ⊆ G such that H can be described as a rational set over A∗. For this let π : A∗ → G be the homomorphism induced by the inclusion of A in G, then there is a regular set R ⊆ A∗ with π(R) = H. By Kleene’s theorem, Theorem 7.17, the language R will be recognized by a deterministic finite automaton A over the alphabet A and therefore π(L(A)) = H. Without loss of generality we have A = A−1, and for each u ∈ A∗ there is a word ū ∈ A∗ with π(uū) = π(ūu) = 1.

Let n be the number of states of A. It is enough to show that the finite set π(W) with

generates the subgroup H.

Since π(L(A)) = H, it is sufficient to show that for each word w ∈ L(A) the element π(w) is in the subgroup generated by π(W). We show this by induction on |w|. If |w| ≤ n, then w ∈ W because in this case we may choose the empty word for u. Now, let |w| > n. When reading the word in A, we must see one of the n states at least twice. Therefore, let uυ be a prefix of w with |u| < |uυ| ≤ n such that the words u and uυ lead to the same state of A. We write w = uυz. Since the automaton is deterministic, the word uz is recognized, too. Hence, by induction, π(uz) is in the subgroup generated by π(W). Because π(uυū uz) = π(uυz) = π(w) ∈ H and π(uz) ∈ H, we must have π(uυū) ∈ H. Therefore, uυū ∈ W.

□

A classical theorem in formal language theory, Theorem 7.17, states that the rational sets of finitely generated free monoids form an effective Boolean algebra. As soon as we meet partial commutation, the situation changes. Let Σ = {a, b, c} be an alphabet with three generators. Consider the (free partially commutative) monoid M = {a, b, c}∗/{ab = ba, bc = cb}. Exercise 8.6 shows that the family of rational subsets in M is not closed under intersection.

We are particularly interested in rational sets of finitely generated free groups F (Σ) and want to show that they form an effective Boolean algebra, that is, the family of rational sets is closed under finite union and complementation, and moreover we may effectively compute the finite union and the complementation (and hence the intersection). This statement about free groups was published in 1969 by Benois [6]. Her proof can be extended to other finitely generated groups and monoids which may be presented by certain confluent semi-Thue systems.

We start very general. For a finite alphabet Γ, a finite semi-Thue system S ⊆ Γ × Γ is called monadic if the following condition is satisfied: for all rules (ℓ, r) ∈ S, we have |ℓ| > |r| ≤ 1. A monadic system is therefore length reducing and right components are either empty or have exactly one letter. For infinite systems, we additionally require that for each r ∈ Γ ∪ {1} the set L(r) = {ℓ ∈ Γ∗ | (ℓ, r) ∈ S } of the left components is regular. For finite systems this requirement is automatically satisfied.

Theorem 8.22. Let Γ be finite, S ⊆ Γ × Γ be a confluent monadic semi-Thue system, and let M = Γ∗/S be the quotient monoid. Then the family of the rational sets RAT(M) is an effective Boolean algebra. In particular, membership in a rational set is decidable.

Proof: Let π : Γ∗ → M = Γ∗/S be the canonical projection. As just described, we define for r ∈ Γ ∪ {1} the regular set L(r) = {ℓ ∈ Γ∗ | (ℓ, r) ∈ S } of the left components.

For the specification of a rational set R ⊆ M, we use a nondeterministic finite automaton A on Γ such that π(L(A)) = R. We allow ε-edges, which could be removed if necessary, but we require that the edges are labeled only with letters or the empty word. If two nondeterministic finite automata R and R' are given, then the standard constructions in Section 7.2 provide automata for R ∪ R, R ⋅ R, and R∗. Intersection can be obtained quite naturally using union and complementation. Hence, for a nondeterministic finite automaton A, it suffices to effectively construct another nondeterministic finite automaton A' with π(L(A')) = M π(L(A)).

Next, we give the construction of A' step by step. First, we enlarge the language L(A) within Γ∗ without changing R = π(L(A)). We “flood” the automaton by more edges. Let Q be the state set of A. For each pair (p, q) ∈ Q2, we define a regular set L(p, q) ⊆ Γ∗, which consists of all words that we would accept if p, were the only initial state and q the only final state. Then we test for each r ∈ Γ ∪ {1} whether L(p, q) ∩ L(r) ≠ 0. This is an effective test. If the intersection is nonempty, then we insert an edge from p to q with label r in the automaton A, provided it does not already exist. We iterate this procedure repeatedly, until (after a maximum of (|Γ|+1)|Q|2 rounds) finally no new edges can be included. Note, the monadic property implies that we increase the number of edges, but we do not insert new states. The language L(A) was not changed: to see this, consider an accepted word urυ, which, when reading r, passes a new edge from the state p to the state q. Then there is a rule (ℓ, r) ∈ S with ℓ ∈ L(p, q). Hence, also uℓυ is accepted, and the accepting path uses the new edge less frequently. This implies π(urυ) = π(uℓυ), which means that the flooding does not change the rational set R. By a slight abuse of language, we continue to refer to the new automaton as A. It now has the following important property: from and u ∈ L(A) it follows υ ∈ L(A). We define

Then R̂ is a set of normal forms for R, and π provides a bijection between R̂ and R. Furthermore R̂ ⊆ L(A).

As the next step, we construct a nondeterministic finite automaton A'' which accepts the complement Γ∗ L(A); see Theorem 7.17. The set π(L(Aˮ)) contains more elements than the complement M R, but if we consider the intersection with the irreducible words, then, as desired, we obtain

It remains to show that IRR(S) is regular. For this purpose, we write the complement of IRR(S) as the union of finitely many regular languages Γ∗L(r)Γ∗. Thus, we have effectively found an automaton A' with

It follows π(L(A)) = M R which proves the theorem.

□

Corollary 8.23 (Benois). The rational sets in a finitely generated free group form an effective Boolean algebra.

Proof: Example 8.6 shows that the monadic system S = {aā → 1 | a ∈ Γ } is strongly confluent.

□

8.10 Free groups

A central theorem about free groups says that their subgroups are free, too. This theorem was first shown by Jacob Nielsen (1890–1959) for finitely generated subgroups [82] and by Otto Schreier (1901–1929) in general. Like vector spaces and free monoids, free groups are, up to isomorphism, completely determined by their rank, that is, by the cardinality of their basis. For subgroups of finite index we present the rank formula by Schreier, which allows the computation of the rank of the subgroup. We already know from Corollary 8.23 that the membership problem in finitely generated subgroups is solvable, because finitely generated subgroups are rational subsets.

Some classical proofs of these results are technical and complicated. In a modern approach one typically follows the ideas of Serre. In [93], it is shown that a group is free if and only if it acts “freely and without inversion” on trees. Another approach uses Stallings graphs [99]. These are special deterministic automata on free groups. They are named after John Robert Stallings, Jr. (1935–2008). The approaches of Serre and Stallings are closely related. Essential parts in Stallings’ method can be derived from the ideas of Benois, which we presented in Section 8.9. These results were historically more than a decade ahead of Stallings’ graphs, but hardly known among group theorists.

In the following, let F = F (Σ) be a free group with basis Σ. The rank of F is defined as the cardinality |Σ| of Σ. Let us convince ourselves that the rank is well defined, that is, it does not depend on the chosen basis. The proof uses the well-known fact that a vector space, up to isomorphism, is uniquely determined by its dimension.

Theorem 8.24. Let F (Σ) and F (Σ) be isomorphic free groups. Then there is a bijection between the bases Σ and Σ.

Proof: Let F = F (Σ). Consider the subgroup N of F generated by the squares. N consists of products of the form with k ∈ ℕ and xi ∈ F. The subgroup N of F is normal because In the quotient group F/N all elements have order 2. It is therefore Abelian, because xy = xy(yx)2 = (x(yy)x)yx = yx ∈ F /N. Therefore, F /N is an 2-vector space. Now we consider the 2-vector space which consists of the maps χ : Σ → 2 with χ(b) = 0 for almost all letters b. The set { χa | a ∈ Σ } with χa(a) = 1 and χa(b) = 0 for b ≠ a forms a basis of defines a surjective linear map. The inverse map is induced by the homomorphism ρ a ↦ χa, and this homomorphism gives a linear map ψ: , a ↦ χa; and we have χa = ψ(φ(χa)) for all χa from the base of In particular, φ is injective and hence an isomorphism between 2-vector spaces:

The definition of F /N is independent of the basis of F; and therefore also the dimension of F /N as an 2-vector space. This dimension is equal to the dimension of that is, equal to |Σ|. Hence, if F (Σ) and F (Σ) are isomorphic, then there is a bijection between Σ and Σ. Certainly, if there is a bijection between Σ and Σ, then F (Σ) and F (Σ) are isomorphic.

In the following, let Γ = Σ ∪ Σ−1 and let π : Γ∗ → F be the homomorphism induced by the inclusion of Γ in F. We may interpret words in Γ∗ as group elements of F. For a word w ∈ Γ∗, we often write w ∈ F instead of π(w) ∈ F. As usual, a word w ∈ Γ∗ is called reduced if it does not contain any factor aa−1 with a ∈ Γ. Now, let G be a subgroup of F. We want to show that G is free. Our goal is more ambitious and, therefore, it can only be achieved with a little additional effort. We present a method for determining the rank of finitely generated groups.

We start with the Schreier graph of the right cosets GF for G in F. The set of vertices is V = G F. The set E of directed edges consists of pairs (u, a) ∈ V × Γ with source s(u, a) = u and target t(u, a) = ua. Note that this graph may contain multiple edges and loops. The number of vertices is the index [F : G], which we denote by n. Here, n is finite or n = ∞. We label the edge (u, a) by λ(u, a) = a. If we define G as the unique initial and final state, then we obtain a deterministic automaton that recognizes the language L ⊆ Γ∗ with π(L) = G.

It proves advantageous to move to a partial automaton. For this, let Q be the set of right cosets Gu that are in the Schreier graph on a path, which is labeled by a reduced word uυ with π(uυ) ∈ G. The set Q may be infinite, and we have

Now, let K(G, Σ) be the subgraph of the Schreier graph, which is induced by Q. We let E be its edge set. The edges are labeled, and we have G ∈ Q. Hence, we may interpret K(G, Σ) as an automaton by defining G to be the initial and final state. The automaton accepts a language R ⊆ Γ∗ with π(R) ⊆ G. Since each element in G is represented by a reduced word, we actually have π(R) = G. We call the automaton K(G, Σ) the kernel of the Schreier graph.

The graph K(G, Σ) = (Q, E) is connected and it has an edge labeling λ : E → Γ. We orient the edges via their labeling by E+ = {e ∈ E | λ(e) ∈ Σ }. An undirected edge is, according to our convention, a collection {e, ē} of two oriented edges e and e. In our case e is a tuple e = (p, a) with p ∈ Q and a ∈ Γ. Letting ē = (pa, a−1), we have λ(ē) = a−1. If we want to stress that we consider an oriented edge we call it arc. Thus, an arc is the same as an oriented edge.

A tree is a nonempty connected undirected graph (U, T) without loops, multiple edges or cycles. A tree (Q, T) with T ⊆ E is called a spanning tree of (Q, E). Like any connected graph, (Q, E) has a spanning tree (Q, T). In our applications, (Q, E) is connected and countable. In order to show that it has a spanning tree, we arrange the edges in some linear list (e1, e2, . . . ). Let T0 = Ø and inductively define Ti for i ≥ 1 as follows: if the edges in Ti−1 ∪{ ej | j > i } connect all vertices of Q, then let Ti = Ti−1; otherwise let Ti = Ti−1 ∪ {ei}. Finally, define T = ∪i∈ℕTi; and (Q, T) becomes a spanning tree of (Q, T). For arbitrary graphs, the proof is similar using transfinite induction or Zorn’s lemma.

Theorem 8.25. Let G be a subgroup of F = F(Σ). Then G is a free group. In the notation just introduced G is isomorphic to the free group F (Δ) with Δ = E+ T where T is a spanning tree (Q, T) of the graph K(G, Σ). Moreover, if Q is finite and if m = |E|/2 ∈ ℕ ∪ {∞} denotes the number of undirected edges in K(G, Σ), then G has rank

Proof: We interpret G in the free group F (E+). In other words, we interpret K(G, Σ) as an undirected graph and we want to find G as a subgroup in the free group whose generators are the arcs in E+. Recall that we have λ(ē) = λ(e)−1 for all edges e. Hence, we obtain a well-defined homomorphism

For any two vertices p, q ∈ Q, the uniquely determined shortest path in the spanning tree from p to q is denoted by T[p, q]. This is a sequence of arcs; in particular, we may interpret T[p, q] as an element of F(E+). In the group F(E+), we then have T[p, q] = T[q, p]−1. Next, we define for each arc e an element τ(e) ∈ F (E+) by the sequence of arcs:

So, we walk in the spanning tree from the coset G to the source of e, pass through e and then, in the spanning tree, go back to the initial vertex G. In particular, we have λ(τ(e)) ∈ G. Moreover, in order to compute λ(τ(e)) ∈ G, we can use any path in K(G, Σ) which starts and ends in the coset G and passes through the arc e.

If t(e) = s(f) for arcs e, f then τ(e) ⋅ τ(f) = T[G, s(e)] ⋅ e ⋅ f ⋅ T[f(e), G] ∈ F(E+) because the middle paths between G and t(e) = s(f) cancel each other.

Now, let e1 ⋅⋅ ⋅ em ∈ E ∗ be a sequence of arcs from G to G; then we have

for the labeling. In particular, λ(τ(F(E+)) = G because the labels for the sequences of arcs in K(G, Σ) are sufficient to generate G. Note that τ(e) = 1 ∈ F(E+) and λ(τ(e)) = 1 ∈ G for e ∈ T. Thus, we obtain a surjective homomorphism

It only remains to show that λ ∘ τ is injective because, for nonempty graphs with |Q| vertices, a spanning tree has |Q| − 1 undirected edges. Suppose that λ(τ(w)) = 1 for a reduced word w = e1 ⋅⋅ ⋅ ek with and k ≥ 0. Then for 2 ≤ i ≤ k, and no edge ei belongs to T for 1 ≤ i ≤ k.

The sequence of arcs

can be reduced for k ≥ 2 by the rules eē → 1 possibly within factors

T[t(ei−1), G]T[G, s(ei )]. But no reduction can involve an arc because the neighbors remain edges of the spanning tree or have the form ei−1 or ei+1. By performing all reductions, we obtain a reduced chain of arcs f1 ⋅⋅ ⋅ fℓ from G to G with k ≤ ℓand for all 2 ≤ i ≤ ℓ. We still have λ(f1 ⋅⋅ ⋅ fℓ) = 1. Suppose that ℓ ≥ 1, then there is an index i with But t(fi−1) = s(fi ) because we have a sequence of arcs, and this means which does not hold. This shows that ℓ = 0 and, hence, we have k = 0. Therefore, w is the empty word.

□

We say that K(G, Σ) is complete if, for each letter a ∈ Γ and every state Gu ∈ Q, we have Gua ∈ Q, too. In this case, there is an edge from Gu to Gua in K(G, Σ) labeled by a. Since in the Schreier graph there is exactly one edge labeled by a from Gu to Gua, the graph K(G, Σ) is complete if and only if it coincides with the Schreier graph. Two situations are of special interest:

Lemma 8.26. If G is a nontrivial normal subgroup or if G is of finite index in F(Σ), then K(G, Σ) is complete and, hence, K(G, Σ) is the Schreier graph.

Proof: Let Gu be a right coset and u = a1 ⋅⋅ ⋅ ak reduced with k ≥ 0 and ai ∈ Γ. We show that Gu ∈ Q. Then K(G, Σ) is the whole Schreier graph, and K(G, Σ) is therefore complete. This is true for k = 0. Now, let k ≥ 1. If Σ = {a} is a singleton then G is of finite index n; and by means of Gai for 0 ≤ i ≤ n, we travel through the Schreier graph. Now, let |Σ| ≥ 2 and b ∈ Σ with ak ≠ b. The map Gw ↦ Gwb permutes the right cosets. If G has finite index, then there exists n ≥ 1 with Gubn = Gu. Since is reduced, it defines a path from G to G. In particular, Gu ∈ Q.

□

Now assume that G is a nontrivial normal subgroup of infinite index in F (Σ) and u = a1 ⋅ ⋅⋅ ak as above. In particular, |Σ| ≥ 2 and there exist a, b ∈ Σ with ak = a ≠ b. By assumption G ≠̸ {1}.Hence, there is a shortest nonempty reduced word w ∈ G. This word cannot have the form cυc−1 with c ∈ Γ because cυc−1 ∈ G implies υ ∈ G, since G is normal. If w neither begins with a−1 nor ends in a, then is reduced and it describes a path from G to G in K(G, Σ). As a consequence Gu ∈ Q. Thus, we may assume that w either begins with a−1 or ends in a. It cannot be both as we pointed out above. By symmetry let w end in a. Then the first letter of w is some c ≠ a−1. By interchanging the role of b and b−1 if necessary, we may assume that b ≠ c ≠ a−1. As a consequence, is reduced. Again, uυ describes a path from G to G in K(G, Σ) and therefore Gu ∈ Q.

Lemma 8.27. Let G be a subgroup of a finitely generated free group F (Σ). Then the following statements are equivalent:

Proof: If K(G, Σ) is finite then G is rational. A rational subgroup is finitely generated by Theorem 8.21. Hence, let G be finitely generated. We only have to show that Q is finite, where as above K(G, Σ) = (Q, E). Since G is finitely generated, there are finitely many words w1, . . . , wk ∈ Γ∗ such that each element in G can be represented as a product over A = {w1, . . . , wk}. The reading of a word w ∈ A∗ in the Schreier graph uses only a finite part Q' of the right cosets, and all reduced words are formed by reduction of words from A∗. Let Q' be the finite set of vertices that are visited when reading w1w2 ⋅⋅ ⋅ wk in the Schreier graph. Remember that, after reading any of the words wi, we return to the starting node G. Thus, when reading a word from A∗, only vertices from Q' are visited. Since any reduced word representing an element in G can be obtained by reducing a word from A∗, it follows Q ⊆ Q' and Q is finite.

□

Theorem 8.28. Let F = F (Σ) be a finitely generated free group and let G be a nontrivial normal subgroup. Then, G has finite index in F if and only if G is finitely generated.

Proof: If G has finite index then K(G, Σ) is finite and, hence, G is finitely generated by Lemma 8.27. Conversely, if G is finitely generated, then K(G, Σ) is finite. Now, Lemma 8.26 shows that K(G, Σ) is the Schreier graph. Therefore, the index is finite.

□

We now give the classical form of Theorem 8.25.

Theorem 8.29 (Nielsen and Schreier). Subgroups of free groups are free. If F is a finitely generated free group of rank r and G a subgroup of finite index n, then G has finite basis Δ and the following rank formula holds:

Proof: Let F = F (Σ). The statement was already proved in Theorem 8.25; only the rank formula had a slightly different form. We obtain the classical version directly from Lemma 8.26,which says that K(G, Σ) is the Schreier graph. Therefore, |Q| = n = [F : G] and m = n ⋅ r.

Corollary 8.30. If x and y are commuting elements of a free group, then x and y generate a cyclic subgroup.

Proof: The subgroup G generated by x and y is free by Theorem 8.29 and commutative by assumption. Hence, G is either trivial or of rank 1. In both cases G is cyclic.

□

Corollary 8.30 corresponds to Theorem 6.5 (b) for free monoids. To conclude this section, we show the corresponding result to Theorem 6.5 (a) for free groups. For the remainder of this section, let F (Σ) be the free group over Σ and Γ = Σ ∪ Σ−1 ⊆ F (Σ). We write a = a−1 for a ∈ Γ. A word w ∈ Γ∗ is called cyclically reduced if ww is reduced. In particular, w is reduced; and if w begins with a letter a ∈ Γ, then it does not end with a. Each element x ∈ F (Σ) is conjugated to an element, which can be represented by a cyclically reduced word w. Recall that words x, y ∈ Γ∗ are transposed if and only if we can write x = rs and y = sr. Clearly, transposed words represent conjugated words in F (Σ). The next theorem states the converse for cyclically reduced words. It was published by Lyndon and Schützenberger in 1962.

Theorem 8.31. Let F (Σ) be the free group over Σ and x, y ∈ Γ∗ be cyclically reduced. If zxz−1 = y in F (Σ) for some z, then there exist reduced words r, s ∈ Γ∗ with x = sr and y = rs in Γ∗.

Proof: We may assume that z is given by a reduced word in Γ∗. If zx and yz are both reduced then the words are identical and the statement follows from Theorem 6.5 (a). Now, let zx be not reduced (the arguments for yz are analogous). Then there is a letter a ∈ Γ such that z = za−1 and x = ax. It follows zxa = zxa = yza = yz' in F(Σ). Since x is cyclically reduced, xa is cyclically reduced, too. By induction on |z| there exist reduced words r' , s' ∈ Γ∗ with xa = s' r' and y = rs. Now, x = ax' and xa are transposed, and also xa and y are transposed. By Theorem 6.5 (a) transposition is transitive, and therefore x and y are transposed words.

□

Corollary 8.32. Dehn’s problems, that is, the word problem, the conjugacy problem, and the isomorphism problem are algorithmically solvable for finitely generated free groups.

Proof: The word problem can be solved by free reduction. To solve the conjugacy problem we need to cyclically reduce two input words. Then we have to test if these cyclically reduced words are transposed. This test gives the correct answer by Theorem 8.31. Finally, two free groups are isomorphic if and only if their bases have the same cardinality.

□

8.11 The automorphism group of free groups

In this section, we give a graph theoretic interpretation of a classical result by Nielsen [83]: the automorphism group Aut(F) of a finitely generated free group F is finitely generated. The classical proof uses elementary transformations. Our proof is based on the notion of Whitehead automorphisms. In fact, the automorphism group Aut(F) is finitely presented [70], but we do not show this here.

Whitehead automorphisms

Let F = F (Σ) be a free group of rank n, that is, |Σ| = n. We define a finite family of automorphisms of F which are named after John Henry Constantine Whitehead (1904–1960). Every permutation of Σ induces a Whitehead automorphism of F. There are n! automorphisms of this type. For a ∈ Σ, we define a Whitehead automorphism ia as follows:

The automorphism ia inverts the letter a and leaves all other letters invariant. There are n automorphisms of this type.

The last set of Whitehead automorphisms is defined for a ∈ Σ and three pairwise disjoint subsets L, R, M of Σ with a ∈ M. Each tuple (a, L, R, M) defines a Whitehead automorphism W(a,L,R,M) as follows:

There are n4n−1 automorphisms of this type. Sometimes one also counts the inverse automorphism as a Whitehead automorphism but this does not really matter, because we have Among the Whitehead automorphisms,we find the subset of elementary Nielsen transformations which consists of the automorphisms ia and λab = W(a,{b},0,{a}).

The following theorem shows that Aut(F(Σ)) is finitely generated. Exercise 8.14 (a) then shows that only four elementary Nielsen transformations are sufficient to generate Aut(F).

Theorem 8.33. The automorphism group Aut(F(Σ)) is generated by the Whitehead automorphisms.

Our proof is based on lectures by Saul Schleimer given at the Centre de Recerca Matemàtica in Barcelona (Catalonia) in September 2012. According to Schleimer and [107], our proof of Theorem 8.33 follows unpublished ideas of Stallings. The intention is not to present the shortest possible proof, but to understand why Whitehead automorphisms form a natural set of generators for Aut(F(Σ)). In fact, we can get even a little more from the proof: without any additional effort it shows that finitely generated free groups are Hopfian.

In the following, X and Y describe finite sets and F (X) and F (Y) the corresponding free groups. Let then X̃ = X ∪ X−1 ⊆ F(X) and Ỹ = Y ∪ Y−1 ⊆ F(Y). We want to study surjective homomorphisms of F (X) onto F (Y). Without loss of generality, wemay assume that Y ≠ 0. We call a homomorphism π : F (X) → F (Y) a projection if

That is, a projection is surjective, and letters are either deleted or mapped to letters or their inverses. For X = Y every projection is a product of Whitehead automorphisms. Hence, the following statement generalizes Theorem 8.33.

Theorem 8.34. Let φ: F(X) → F(Y) be a homomorphism.

Theorem 8.34 provides the assertion that finitely generated free groups are Hopfian, because for |X| = |Y| projections are isomorphisms. We also see that if finitely generated free groups are isomorphic, then their rank is equal. (See Theorem 8.24 for the general statement including infinitely generated free groups.) Indeed, if |X| < |Y|, then there are no projections from F (X) to F (Y). Thus, epimorphisms (resp. isomorphisms) from F(X) onto F(Y) exist if and only if |X| ≥ |Y| (resp. |X| = |Y|).

The rest of this section is devoted to the proof of Theorem 8.34. Without loss of generality, we may assume that X and Y are nonempty finite sets. A graphical realization of a homomorphism of F (X) to F (Y) is a pair (Γ, Φ) where Γ is a marked, connected, edge labeled, finite graph, together with a spanning tree, and Φ is a mapping of X̃ to the set of edges of Γ. Formally, Γ is a tuple (1, V, E, T, λ) and Φ: X̃ → E is a mapping with the following properties:

Every graphical realization defines a homomorphism φ: F (X) → F (Y) as follows. Let p, q ∈ V be two vertices. As done earlier, T[p, q] denotes the shortest path in the spanning tree (V, T) from p to q. For a ∈ X and e = Φ(a) ∈ E, we put

Thus, φΓ (a) is a closed path in (V, E) which starts at the marked vertex 1, walks in the spanning tree from 1 to the source of Φ(a), passes through the edge Φ(a) and then goes back in the spanning tree to the marked vertex 1. Hence, we may interpret the word φΓ (a) ∈ E∗ also in the free group F(E+). Since φΓ (a−1) = φΓ (a)−1 holds in F (E+),we obtain a well-defined homomorphism φΓ : F (X) → F (E+). Finally, we define

We obtain the following picture:

We say that (Γ, Φ) is a graphical realization of φ: F (X) → F (Y). A graphical realization of a homomorphism is by no means unique; see, for example, Figure 8.5.

Before we proceed further, let us show that every homomorphism φ: F (X) → F (Y) has some graphical realization (Γ, Φ). This is simple. Consider a ∈ X , then we may write φ(a) as φ(a) = y1 ⋅⋅ ⋅ ym with yi ∈ Ỹ. Because Y ≠ 0 and since we allow factors of the form yy−1, we may assume that m ≥ 2. For each letter a ∈ X , we draw a cycle of length |φ(a)| with initial and target 1 and label the ith edge with the ith letter in the word φ(a). We add the first m − 1 edges of the cycle to the spanning tree and the last edge em becomes a bridge. Finally, we define Φ(a) = em. The resulting graphical realization of φ looks like a flower with petals of different size.