§ 6 Free Groups

One way to define a group is to specify a collection of generators together with a collection of relations satisfied by those generators.

Question: What does a group with a set of generators but no relations look like? If the set of generators is $S$, such a group is called the free group on $S$.

$\begin{aligned} \textbf{Example 6.1}~\langle g\rangle=\mathrm{image}(\mathbb{Z}&\to G)\ n&\mapsto g^{n} \end{aligned}$

We are going to generalize $\mathbb{Z}$. An analogous description of $\mathbb{Z}$ is

For any map of sets

we will obtain a group homomorphism

where $F(S)$ is the free group on the set $S$.

§ 6.1 Words and Letters

Definition 6.1 Let $X$ be a set. A word on $X$ is a finite ordered collection of elements of $X$. Given a word $w$, an element of $w$ is called a letter of $w$.

Equivalently, a word is:

• an element of

• a sequence

where each $X_i\in X$ and $n\geqslant0$.

Remark The empty word is the word containing no letters.

We write $\mathrm{Word}(X)$ for the set of all words on $X$.

Example 6.2 If $X={a}$,

If $X={a,b}$,

Given two words in $X$, we may concatenate them to produce a new word:

Example 6.3

This is clearly associative, and the empty word looks like an identity element. But there are no inverses! Let us fix this.

Given a set

let $S^{\prime}$ be the set of symbols

Thus $S$ and $S^{\prime}$ are in bijection.

We define

Example 6.4 A word in $\overline{S}$ might look like

§ 6.2 Reduction of Words

Definition 6.2 A word in $\overline{S}$ is called unreduced if, for some $a\in S$, one of the strings

occurs in the word. If a word is not unreduced, it is called reduced.

Example 6.5

Definition 6.3 If $w^{\prime}$ is obtained from $w$ by removing, or cancelling, one occurrence of $aa^{-1}$ or $a^{-1}a$, then we say that $w^{\prime}$ is obtained from $w$ by cancellation. We write

Example 6.6

• The empty word is obtained by cancellation from $b^{-1}b$ and from $bb^{-1}$.

• $ab$ is obtained by cancellation from

Definition 6.4 If $w^{\prime}$ is obtained from $w$ through a sequence of cancellations,

and $w^{\prime}$ is reduced, then $w^{\prime}$ is called a reduction of $w$.

Proposition 6.1 If $w^{\prime}$ and $w^{\prime\prime}$ are reductions of $w$, then

Proof: We use induction on the length $l$ of the word $w$. Notice that

When $l=0$: the empty word is reduced.

When $l=1$: the word contains only one element, so it is impossible for $a$ and $a^{-1}$ to occur next to each other. Thus every word of length $1$ is reduced.

Assume that every word of length $l-1$ has a unique reduction. We prove the result for words of length $l$.

If $w$ has length $l$ and is already reduced, we are done.

Otherwise, somewhere in $w$ there is an occurrence of $aa^{-1}$ or $a^{-1}a$. There may be several such occurrences.

For example, consider

which has length $6$. Choose one occurrence

A reduction of $w$ may be obtained in one of the following ways:

(i) At some stage, cancel the chosen $\underline{a^{-1}a}$.

(ii) Never cancel the chosen $\underline{a^{-1}a}$.

Case (ii) can occur only in the following situations:

In (6.1), cancelling $\underline{a^{-1}a}a^{-1}$ using either or produces the same word.

The same is true for (6.2). Therefore, we may assume that the chosen $\underline{a^{-1}a}$ is cancelled at some stage. Any reduction obtained by (ii) can also be obtained by (i).

Thus, we have a reduction

Thus, whether we cancel $aa^{-1}$ at Step 1 or at some later stage, we obtain the same reduction.

§ 6.3 Definition of the Free Group

Definition 6.5 Let $S$ be a set. The free group $F(S)$ on $S$ is

where

• $F(S)$ is the set of reduced words in

where

• the map

sends $(w_1,w_2)$ to the reduction of $w_1w_2$.

Example 6.7 Consider a set with one element,

A word in $\overline{S}$ might look like

If a word is reduced, it looks like

or

Therefore,

is a bijection. It is an isomorphism.

Example 6.8 Consider a set with two elements,

Then $F(S)$ is the free group on two generators. Its elements look like

Proposition 6.2 The inverse of $S_1\cdots S_n$ is $S_n^{-1}\cdots S_1^{-1}$.

Proof: The inverse of $S_1\cdots S_n$ is $S_n^{-1}\cdots S_1^{-1}$ because

§ 6.4 Equivalence Relations

Definition 6.6 Let $X$ be a set. An equivalence relation on $X$ is a subset

satisfying:

(1) For every $x\in X$,

(2) If

then

(3) If

and

then

We write

if

Example 6.9 Let $G$ act on a set $X$. Define

if and only if

for some $g\in G$.

This is an equivalence relation because

(1)

so

(2)

for some $g$.

(3)

so

and hence

Thus, for every $x$, $\mathcal{O}_x$ is the equivalence class of $x$:

The orbit space $X/G$ is the set of equivalence classes.

Here is another example.

Example 6.10 Let $S$ be a set and define

§ 6.5 Existence of a Unique Reduction

Theorem 6.3 Every

has a unique reduction.

Proof: We use induction on the length $l$.

The case $l=0$ is clear.

The case $l=1$ is clear.

Assume that for every word $w^{\prime}$ of length $\leqslant l-1$, the set

has exactly one element.

We must prove the same for every word $w$ of length $l$.

• If $w$ is already reduced, then no other word can be obtained from $w$ by cancellation. Therefore

• Otherwise, somewhere in $w$ there is an occurrence of

Fix one such occurrence:

We have underlined it.

Consider the following:

$\textcircled{\small 1}$ is an equality because if the chosen $\underline{aa^{-1}}$ is cancelled at Step $N$, then we may instead cancel it first and then perform Steps $1$ through $N-1$, obtaining the same reduction.

$\textcircled{\small 2}$ is either an equality or the set is empty, because not cancelling $\underline{aa^{-1}}$ means that at some stage one must perform a cancellation like or .

Together, $\textcircled{\small 1}$ and $\textcircled{\small 2}$ tell us that every reduction of $w$ can be obtained by first cancelling the chosen $\underline{aa^{-1}}$.

But

is a word of length less than $l$!

Moreover, every reduction of $w$ obtained by first cancelling $\underline{aa^{-1}}$ is a reduction of $w^{\prime}$.

Therefore,

Example 6.11 If

then $\mathrm{Word}(S)$ is a set containing one element—the empty word, which has length zero.

Example 6.12 If

then

which is the set containing the empty word.

Therefore, when $S=\varnothing$, $\mathrm{Free}(S)$ is a group containing exactly one element.

§ 6.6 Applications of Free Groups

Proposition 6.4 Let $G$ be a group. Suppose

is a map of sets. Then it extends to a group homomorphism

Proof: Let $s\in S$ be an element of the set, and let $j(s)\in G$ be its image in $G$.

Let

be the function defined by

We then define a function

by sending any word

where $s_i\in\overline{S}$, to

We must prove that this gives a well-defined map on $F(S)$ and that it is a homomorphism.

Indeed, if $w$ is a reduced word obtained from $W$, then it is obtained by cancelling adjacent inverse pairs. On the other hand, whenever a letter $s$ occurs next to its inverse $s^{-1}$ in $W$, the corresponding product in $G$ contains

next to

Thus, if we cancel two inverse letters in the word $W$ to obtain a new word $w^{\prime}$, then

More explicitly, in a product of several elements of $G$, removing an occurrence of

or

does not change the value of the product:

The same applies when cancelling an occurrence of $\phi_j(s)^{-1}\phi_j(s)$.

Thus, if the words $w_i^{\prime}$, $i=1,\ldots,I$, are the intermediate words appearing while reducing $W$ to its reduced word $w$, then

This shows that $\phi_j$ is well defined on $F(S)$.

To prove that $\phi_j$ defines a homomorphism, let

be the concatenation of two words, and let $w$ be its reduction. We must prove

By well-definedness, it is enough to prove

This is immediate because if

then

Proposition 6.5 There is a bijection of sets

Proof: Above, for every function

we defined a homomorphism

This defines a function

given by

We define an inverse map $\Psi$ as follows.

If $\phi$ is a group homomorphism, it assigns a value to every one-letter reduced word $s\in S$. Thus we define

to be the function sending

We must show that

and

are identity maps.

Indeed, given a homomorphism

let

where each $s_i$ is a letter of $w$ lying in $\overline{S}$.

By the group homomorphism property, together with the fact that every word is a product of one-letter words,

Therefore, the values of $\phi$ on one-letter words—that is, its values on $S$—determine its value on every element of $F(S)$. This shows that

is the identity.

On the other hand, $\Phi$ was defined so that

simply sends a one-letter word $s$ to $j(s)$. Therefore,

is also the identity.

Example 6.13 Let $S$ be a set and $G$ a group. For every function

there exists a group homomorphism

When

there is a unique function

What is the corresponding group homomorphism

It sends the empty word to

Proposition 6.6 If $w_1$ and $w_2$ have the same reduced word, then

defines an equivalence relation.

Proof: $w_1\sim w_2$ is an equivalence relation because

(1)

is immediate:

(2)

is immediate because

(3)

because

All of these follow from the uniqueness of reduction and from the fact that equality is an equivalence relation.

Remark Therefore, if

by cancellation, then

The converse need not hold.

Proposition 6.7 Let $F(S)$ be the set of reduced words in $\overline{S}$. There is a bijection

Proof: Send

i.e. send $w$ to its equivalence class.

Every equivalence class has a unique element of shortest length—namely the common reduced word of any

This defines the inverse map.

Proposition 6.8 The operation

is well defined.

Proof: Let $r_1$ and $r_2$ be the reduced words of $w_1^{\prime}$ and $w_2^{\prime}$, respectively.

Notice that

Simply perform all cancellations in the $w_1^{\prime}$ part of the word, and then all cancellations in the $w_2^{\prime}$ part.

Thus, for any

we have

and hence

Therefore, regardless of which representatives

we choose, the equivalence class of $w_1^{\prime}w_2^{\prime}$ does not change.

Corollary 6.9 The free-group operation

is associative.

Proof:

Therefore, it is enough to prove that the operation

is associative.

Indeed,

where the third equality follows from associativity of ordinary word concatenation.