551, Fall '00                   A4a.    Free groups                   p. 1

Math 551 – Algebra – Fall 2000

A. Groups

4. Free groups and presentations.

We detour to this important way of describing groups.

4a. Free groups

Definition. Let S be a set. A word in S is a formal expression

s_{1}^{ϵ_{1}} ∗ s_{2}^{ϵ_{2}} ∗ ⋯ ∗ s_{n}^{ϵ_{n}}

where n ≥ 0, s_{1}, …, s_{n} ∈ S and ϵ_{i} ±1 for each i. We may also write s_{1}^{ϵ_{1}}s_{2}^{ϵ_{2}} ⋯ s_{n}^{ϵ_{n}}, although sometimes this requires care since this “product” expression may simultaneously have a different meaning. The above word is reduced if it does not contain two adjacent terms of the form s^{1} ∗ s^{−1} or s^{−1} ∗ s^{1} for any s ∈ S. In the case n = 0 there is one word, the empty word, also written 1. It is customary to write s^{3} in place of sss, etc.

If G is a group and S ⊆ G then every word in S represents an element of G. The elements so represented constitute the subgroup ⟨S⟩. Moreover, an element represented by a non-reduced word is also represented by a reduced word (obtained by making formal cancellations).

Definition. If G is a group and S ⊆ G then G is free on S if and only if G = ⟨S⟩ and distinct reduced words in S represent distinct elements of G. A group is free if and only if it is free on some subset.

We can thus think of elements of a free group as reduced words, multiplied formally. For example, an infinite cyclic group ⟨x⟩ is free on {x}.

Theorem. Let S be a set. Then there exists a free group on S. If G and H are free groups on S then there exists an isomorphism G → H fixing each element of S.

One proof is to assert that this is essentially obvious; we let G be the set of reduced words in S, and multiply them formally. This seems a triviality, but it is a little unsettling to realize that there is something to check: associativity, e.g. for S = {a, b}, what is

(baba)(a^{−1}b^{−1}b^{−1})(bbbab)?

p. 2         A4.    Free groups and presentations.           551, Fall '00

There really are two somewhat distinct ways of proceeding. What needs to be checked can be checked, but instead we construct a free group on S as follows. Let W be the set of all reduced words in S. Instead of putting a group structure on W we construct G as a group of permutations of W. Namely for each s ∈ S we define ρ_{s} ∈ Σ_{W} as follows:

ρ_{s}(s_{1}^{ϵ_{1}}s_{2}^{ϵ_{2}} ⋯ s_{n}^{ϵ_{n}}) = \{ \begin{matrix}ss_{1}^{ϵ_{1}}s_{2}^{ϵ_{2}} ⋯ s_{n}^{ϵ_{n}} & if s_{1}^{ϵ_{1}} ≠ s^{1} \\ s_{2}^{ϵ_{2}} ⋯ s_{n}^{ϵ_{n}} & if s_{1}^{ϵ_{1}} = s^{1} \end{matrix}

We define ρ_{s^{−1}} similarly. It is easy to check that ρ_{s}ρ_{s^{−1}} = ρ_{s^{−1}}ρ_{s} = id_{W}, so each ρ_{s} ∈ Σ_{W} and ρ_{s^{−1}} = ρ_{s}^{−1}. We then set

G = ⟨ρ_{s} | s ∈ S⟩,

identify each s ∈ S with ρ_{s} ∈ G, and argue that G is free on S. Namely, for any reduced word w = s_{1}^{ϵ_{1}}s_{2}^{ϵ_{2}} ⋯ s_{n}^{ϵ_{n}}), if we let ρ_{w} be the corresponding word in the ρ_{s_{i}}, then it is trivial that

ρ_{w}(1) = w,

so distinct w’s produce distinct ρ_{w}’s, which proves the freeness. The uniqueness is clear: reduced words go to the corresponding reduced word. The multiplication in G is accomplished by juxtaposition and cancellation, although that was not our definition of it.

Theorem. Let S be a set and F be a free group on S. Let G be a group and ψ : S → G be a mapping (of sets). Then there is a unique homomorphism Ψ : F → G such that Ψ|S = ψ.

Indeed if w ∈ G there is a unique way to write w = s_{1}^{ϵ_{1}}s_{2}^{ϵ_{2}} ⋯ s_{n}^{ϵ_{n}}) ∈ G, the word being reduced, and we set Ψ(w) = ψ(s_{1})^{ϵ_{1}} ⋯ ψ(s_{n})^{ϵ_{n}}. This is the only choice for Ψ, and in fact it gives a homomorphism.

This leads to the following alternative definition of a free group, essentially equivalent to the first.

Definition. Let S be a set. A free group on S is a group F, together with a mapping i : S → F, with the following universal mapping property: For every group G and every mapping j : S → G there is a unique homomorphism ϕ : F → G such that ϕi = j.

From this definition it follows easily that i is injective, and that any two free groups i : S → F and i′ : S → F′ are isomorphic, i.e., there is an isomorphism ϕ : F → F′ such that i′ = ϕi (in fact, a unique isomorphism).

4b. Presentations

A free group on S can be informally described as having a certain set (S) of generators which satisfy no relations (other than those entailed by the group axioms). Here a relation means an equation between two words in S, more precisely between the group elements which they represent. If one is willing to impose relations, we can describe other groups in a similar way. Indeed every group can be described in this way, although infinitely many generators and infinitely many relations may be involved. This is the content of the following trivial theorem:

551, Fall '00                  A4b.    Presentations                  p. 3

Theorem. Let G be a group and S a subset of G such that G = ⟨S⟩. Let F be a free group on S. Then there is a normal subgroup R ◁ F and an isomorphism F/R → G such that sR ↦ s for each s ∈ S.

Proof The universal mapping property above provides a homomorphism ϕ : F → G mapping s ↦ s for all s ∈ S. Since G = ⟨S⟩, ϕ is surjective. Let R = ker ϕ; the first isomorphism theorem completes the proof.

A consequence of the theorem is that

Every group is a homomorphic image of a free group;

in fact of many free groups. Thus homomorphic images of free groups are totally arbitrary groups.

(Remark: Subgroups, however, are not:

Theorem (Schreier). Subgroups of free groups are free.

However, they may require more generators than the group. )

Returning to the isomorphism F/R ≅ G, we say that G is generated by S, with defining relations given by R. Or, G is presented by the generators S and relations R.

Of course R is too large, and it can be replaced by any subset which generates R. Even less is required: a subset R_{0} of R such that R is the smallest normal subgroup of F containing R_{0}.

Lemma. The intersection of normal subgroups of a group G is a normal subgroup of G.

Thus given a set X ⊆ G, the intersection of all normal subgroups of G containing X is the smallest normal subgroup of G containing X. It is written ⟨X^{G}⟩, the reason being that it is the group generated by the union of all the G-conjugates of X.

In many cases R_{0} may be taken to be quite small.

Definition. Let S be a set and R_{0} a set of words in S. Then

gp⟨S | R_{0}⟩ = F/⟨R_{0}^{F} ⟩.

Here on the right side, F is a free group on S and R_{0} is interpreted as a subset of F. Notice that for each s ∈ S there is an element s⟨R_{0}^{F} ⟩ of this group, which we could call \overline{s}. The mapping s ↦ \overline{s} is not necessarily injective, though it frequently is. This group is presented by generators S with relators R_{0}.

By the uniqueness of free groups, this definition is okay up to isomorphism (preserving S).

Theorem. Let S and R_{0} be as in the previous definition. Let G be a group and i : S → G a mapping such that for each word w = w(s_{1}, …, s_{n}) in S, the corresponding word w(i(s_{1}), …, i(s_{n})) represents the identity element of G. Then there is a unique homomorphism

ϕ : gp⟨S | R_{0}⟩ → G

such that ϕ(\overline{s}) = i(s) for all s ∈ S.

Example. Let

G = gp⟨x, y | x^{2}, y^{5}, xyxy⟩ or equivalentlyG = gp⟨x, y | x^{2} = 1, y^{5} = 1, xyx = y^{−1}⟩

Recall that D_{10} has generators a, b (a rotation of order 5 and a reflection) such that b^{2} = 1, a^{5} = 1 and bab = a^{−1}. Therefore there exists a homomorphism

ϕ : G → D_{10}, ϕ(x) = b, ϕ(y) = a,

which we shall show is an isomorphism. As a result we will be able to say that the relations we have given on a and b are defining relations for D_{10}, or present D_{10}.

Since a and b generate D_{10}, ϕ is surjective. To prove that ϕ is injective is harder. We shall do it in this case by proving that |G| ≤ 10. Namely, G contains elements \overline{x} and \overline{y} satisfying the given relations. Let us be sloppy and call them x and y. The relation xyx = y^{−1} means that xy = y^{−1}x, and hence in G any product x^{i}y^{j} may be rewritten as a product y^{k}x^{l} for some k, l. The set of products x^{i}y^{j} is therefore closed under multiplication (and inversion) in G, and contains x and y, so equals G. Finally there are at most 5 distinct powers of x and 2 of y in G, so |G| ≤ 10. Therefore ϕ is an isomorphism.

Another example: let

G = gp⟨x | x^{7} = 1⟩.

Then G ≅ Z_{7}.

A more surprising example:

G = gp⟨x, y | xyx^{−1} = y^{2}, yxy^{−1} = x^{3}⟩.

In G we have [x, y] = xyx^{−1}y^{−1} = y and [y, x] = yxy^{−1}x^{−1} = x^{2}. But always [x, y] = [y, x]^{−1}, and so y = x^{−2}. Consequently y and x commute, so y = y^{2} and x = x^{3}. Therefore y = 1 and x^{2} = 1. The group Z_{2} does satisfy the relations (with y = 1 and x ≠ 1), so G ≅ Z_{2}. If we imposed the additional condition x^{79} = 1, for instance, then G would be 1.

The moral is that collapse is hard to detect a priori.

One upside of considering groups by presentations is that convenient presentations make homomorphisms easy to define. By the theorem above, for instance, since we know that D_{10} ≅ gp⟨x, y | x^{5} = y^{2} = (xy)^{2} = 1⟩, in order to define a homomorphism ϕ : D_{10} → H for any H, it suffices to specify the elements ϕ(a) and ϕ(b) of H, as long as they satisfy (ϕ(a))^{5} = (ϕ(b))^{2} = (ϕ(a)ϕ(b))^{2} = 1. For example, there is a homomorphism D_{10} → Σ_{5} taking a ↦ (1 2 3 4 5) and b ↦ (1 4)(2 3).

Another is that it quickly gives lots of examples of groups; for example,

G(m, n, p) = gp⟨x, y, z | x^{m} = y^{n} = z^{p} = xyz = 1⟩.

551, Fall '00        A4c.    Some Universal Mapping Properties        p. 5

It is known for example that G(2, 2, p) ≅ D_{2p}; G(2, 3, 2) ≅ Σ_{3}, G(2, 3, 3) ≅ A_{4}, G(2, 3, 4) ≅ Σ_{4}, G(2, 3, 5) ≅ A_{5}, and G(2, 3, p) is infinite for p > 5.

A downside is that it can be tricky to obtain a convenient presentation of a given group. Nevertheless for many examples of groups, nice presentations have been discovered.

Exercise. Consider the integers

m_{ij} = \{ \begin{matrix}1 & if i = j \\ 3 & if |i − j| = 1 \\ 2 & otherwise \end{matrix} , for i, j = 1, 2, . . ..

Show that for any n ≥ 1,

gp⟨t_{1}, …, t_{n} | (t_{i}t_{j})^{m_{ij}} = 1 ∀i, j = 1, …, n⟩ ≅ Σ_{n+1}.

There has been considerable computational research on finitely presented groups, i.e., those which have a presentation consisting of finitely many generators and finitely many relators. Not every group, indeed even not every countable group, is finitely presented. But finite groups of course are finitely presented.

4c. Some Universal Mapping Properties

The critical properties of many algebraic constructions can be formulated as “universal mapping properties”. Examples:

1. Given a set S, a free group on S is a mapping i from the set S into the group F such that for every mapping from the set S into an arbitrary group G,

\begin{matrix}S & \underrightarrow{i} & F \\ ↓ \\ G \end{matrix}

there exists a unique group homomorphism F → G making the diagram commute. We usually speak of F as being the free group, but the objects S and F and the mapping i are really all part of the concept.

2. Given a group G and a normal subgroup K ◁ g, the quotient group G/K of G, the canonical projection π_{K} : G → G/K has the following property. It contains K in its kernel, and for any homomorphism ϕ : G → H from G to an arbitrary group such that K ≤ ker ϕ,

\begin{matrix}G & \underrightarrow{π_{K}} & G/K \\ ↓ \\ H \end{matrix}

there exists a unique group homomorphism G/K → H making the diagram commute. We usually speak of G/K as being the quotient group, but the projection π_{K} is an integral part of this notion, as the multiplication in G/K has been defined as

gKg′K = gg′K, or equivalently π_{K}(g)π_{K}(g′) = π_{K}(gg′).

Two remarks: of course the kernel of π_{K} is exactly K, but the above property is that among all homomorphisms whose kernel contains K, it is universal. Second, the mapping from G/K → H which makes the above diagram commute is the mapping ψ defined by

ψ(gK) = ϕ(g).

Since K ≤ ker ϕ, we have ϕ(g) = ϕ(g)ϕ(k) for all k ∈ K, and so ψ is well-defined. That it is a homomorphism and makes the diagram commute is then easy to check.

3. By combining these two we get a universal property of groups given by a presentation (i.e. generators and relations). Suppose that we are given a set S and a set R of reduced words in S. The group gp⟨S|R⟩, or more precisely the natural map j : S → gp⟨S|R⟩, has the property that if s_{1}^{ϵ_{1}} ⋯ s_{n}^{ϵ_{n}} ∈ R, then the corresponding expression in j(s_{1}), …, j(s_{n}) represents the identity element of gp⟨S|R⟩. It is universal with this property, namely, for any group G and any mapping f : S → G such that f(s_{1})^{ϵ_{1}} ⋯ f(s_{n})^{ϵ_{n}} = 1 for every word s_{1}^{ϵ_{1}} ⋯ s_{n}^{ϵ_{n}} ∈ R,

\begin{matrix}S & \underrightarrow{j} & gp⟨S|R⟩ \\ ↓ \\ G \end{matrix}

there is a unique homomorphism gp⟨S|R⟩ → G making the diagram commute. This can be proved by noting that gp⟨S|R⟩ = F/⟨^{F} R⟩ by definition, where F is a free group on S, and j is the composite π_{⟨^{F} R⟩} : S → F → F/⟨^{F} R⟩; the previous two universal properties show that the given map S → G lifts uniquely by example 1 to a homomorphism F → G (which sends all words in R to the identity, and therefore contains R in its kernel, and therefore contains ⟨^{F} R⟩ in its kernel), and then lifts uniquely by example 2 to a homomorphism F/⟨^{F} R⟩ → G.

The “same” proof shows in each case that given two universal objects, there is a unique “isomorphism” between them. Here “isomorphism” means not just an isomorphism in the ordinary sense, but one making an appropriate diagram commute. For instance, given two free groups

S → F and S → F′

on S, we use

a) the universal property of S → F to get a homomorphism ϕ : F → F′ making diagram a) commute;

b) the universal property of S → F′ to get a homomorphism ψ : F′ → F; making diagram b) commute;

551, Fall '00                  A4d.    Free Products                  p. 7

c) the universal property of S → F, and the observation that both ψϕ and id_{F} make diagram c) commute, to conclude that ψϕ = id_{F};

d) the universal property of S → F′ and a similar argument to get ϕψ = id_{F′}.

Then by c) and d), ϕ is an isomorphism, and by a) it is unique subject to making the diagram commute.

S ⟶F  S⟶F′  S⟶F
↓  ↓  ↓
F′  F  F
a)  b)  c)

This uniqueness is what makes it possible to define free group by the universal mapping property, as an alternative to the concrete definition we have given. (Either way, one has to prove that free groups exist!)

In category theory, the uniqueness argument just given is formalized, and is just the theorem that in any category, given any two initial objects, there is a unique isomorphism between them.

4d. Free Products

Related to free groups there is the construction of free products. Let {G_{i} | i ∈ I} be a family of groups. The free product

⋆_{i∈I} G_{i}

can be defined either in a “word” way or by a universal mapping property.

First a technicality: replace the G_{i} by isomorphic copies if necessary to insure that as sets, they are pairwise disjoint. Then define a reduced word to be a word in the alphabet

⋃_{i∈I}(G_{i} − {1})

such that any two adjacent terms come from two different G_{i}’s. Informally the free product ⋆_{i∈I} G_{i} is the set of all such reduced words, multiplication consisting of juxtaposition followed by reduction (reduction consisting of multiplying any two adjacent letters which happen to lie in the same G_{i}, and throwing out any terms which are 1, and iterating). The same problem exists here as with the definition of free group, and is finessed the same way. Let W be the set of all reduced words. For each g ∈ ∪G_{i} − {1}, let ρ_{g} ∈ Σ_{W} be the permutation of W defined by “appending g on the left and reducing”. Notice that for this kind of reducing, there is at most one step to be done (or two, if the word begins with g^{−1}) and there is no possible ambiguity. Then let

⋆_{i∈I} G_{i} = ⟨ρ_{g} | g ∈ ∪_{i∈I}G_{i} − {1}⟩.

Technically this is a subgroup of Σ_{W}. However we may represent the element ρ_{g}ρ′_{g} ⋯ just by the word gg′ ⋯, and if we do so, then the elements of the free product are just the reduced words, and distinct reduced words represent distinct group elements (as can be seen by applying the permutations to the empty word).

The free product has the following universal mapping property. It comes equipped with a family of homomorphisms j_{i} : G_{i} → (⋆_{i∈I} G_{i}), one for each i ∈ I, namely j_{i}(g) = g. Then for any group H and any family of homomorphisms f_{i} : G_{i} → H, one for each i, there is a unique homomorphism (⋆_{i∈I} G_{i}) → H making the following diagram commute for each i:

\begin{matrix}G_{i} & ⟶ & ⋆_{i∈I} G_{i} \\ ↓ \\ H \end{matrix}

We leave the checking of this property to the reader.

As an example, if a group G is generated by an element a of order m and an element b of order n, then it is a quotient of Z_{m} ⋆ Z_{n}. Namely there exist homomorphisms Z_{m} → G and Z_{n} → G taking generators to a and b, respectively. By the universal property there is a homomorphism Z_{m} ⋆ Z_{n} → G taking generators of Z_{m} and Z_{n} to a and b, respectively. Since a and b generate G this homomorphism is surjective. By the first isomorphism theorem, G is a quotient of Z_{m} ⋆ Z_{n}.

For instance, we know that P SL_{2}(Z) is generated by the images of the two matrices

[ \begin{matrix}0 & 1 \\ −1 & 0 \end{matrix} ] , [ \begin{matrix}0 & 1 \\ −1 & −1 \end{matrix} ] ,

of orders 2 and 3 respectively. Hence there is a homomorphism

Z_{2} ⋆ Z_{3} → P SL_{2}(Z)

taking generators of Z_{2} and Z_{3} to the images of these matrices, and P SL_{2}(Z) is thus a quotient of Z_{2} ⋆ Z_{3}. In this particular case this mapping turns out to be an isomorphism!