LEC ALG2 13

Free groups

Refer Balsdon et al. (n.d.), Sury (2010).
See Robinson (2015) for an interesting application of free groups.

Intuitively, a free group is a group which has no nontrivial relations among its elements - it satisfies the bare minimum requirements to be called a group (the group axioms) and nothing more.

Definition 102.1(Definition).

Given a non-empty set $S$, and a map $\theta :S\to F$ into a group $F$, the pair $(F,\theta )$ is said to be a free group on the set $S$ if, for any function $\phi :S\to G$ to any group $G$, there is a unique homomorphism $\overline{\phi }:F\to G$ such that $\phi =\overline{\phi }\circ \theta$. When $\theta$ is an inclusion, we call $\overline{\phi }$ the unique extension of $\phi$ to $F$.

1e47e5

Proposition 102.2(Proposition).

If $(F,\theta )$ is a free group on a set $S$, then

1. $\theta$ must be injective.

2. $(F,\text{inclusion})$ is free on $\text{im}(\theta )$.

3. $\text{im}(\theta )$ generates $F$.

Proof.

$(1)$ and $(2)$ are clear, so $S\subseteq F$. Let $i$ be the inclusion $S\hookrightarrow F$. The unique extension of $i$ to $F$ is clearly the identity ¹. Consider the inclusions $i_1:S\hookrightarrow ⟨S⟩$ and $i_2:⟨S⟩\hookrightarrow F$. Clearly, $i=i_2\circ i_1$. Let $\pi$ be the unique extension of $i_1$ to $F$. Then, we have $i=i_2\circ \pi \circ i$, forcing $i_2\circ \pi =\text{id}$. Since $i_2$ is an inclusion, this forces $⟨S⟩=F$.

□

Constructing a free group on any arbitrary set

To construct a free group, start with an arbitrary set, say $S=\{a,b,\dots \}$. Let $S^{\prime }$ be the set that contains the symbols $a$ and $a^{-1}$ for every $a\in S$, $i$.$e$, $S^{\prime }=\{a,a^{-1},b,b^{-1},\dots \}$. The elements of $S^{\prime }$ are called symbols. Define a word to be a finite string of symbols, in which repetition is allowed. Let $W$ be the set of all words along with the empty string $e$. Define the product operation on $W$ to be concatenation. Obviously, $W$ is not a group, since inverses do not exist (yet).

If a word looks like $\dots x{x}^{-1}\dots$ for some $x\in S^{\prime }$, we may agree to “cancel” the two symbols $x$ and $x^{-1}$. Call a word reduced if no such reduction can be made. Starting with any $w\in W$, we can make a finite sequence of reductions to arrive at a reduced word $\overline{w}$, which is called the reduced form of $w$. There may be more than one way to arrive at the reduced word. If we want the notion of a reduced word to be well defined, we must ensure that all paths lead to $\overline{w}$.

Lemma 102.3(Lemma).

There is only one reduced word for a given word $w$.

Proof by induction on $n$ (easy). See Artin (2011, p. 211).

Define an equivalence relation $\sim$ on $W$ by $w\sim w^{\prime }$ if $w$ and $w^{\prime }$ have the same reduced word. Next, observe that products of equivalent words are equivalent, that is, $w\sim w^{\prime }$ and $v\sim v^{\prime }$ imply $wv\sim w^{\prime }{v}^{\prime }$. Therefore, it follows that the equivalence classes of words can be multiplied.

Lemma 102.4(Lemma).

The set $W/\sim$ of equivalence classes is a group, with the law of composition induced from multiplication in $W$.

Proof.

The facts that multiplication is associative and that the class of the empty word$e$ is an identity follows from the corresponding facts in $W$. Also, for any $[xy\dots z]\in W/\sim$, $[z^{-1}\dots y^{-1}{x}^{-1}]\in W/\sim$ is clearly its inverse.□

Let $F:=W/\sim$. Defining the map $\theta :S\to F$ by $x\mapsto [x]$, let us show that $(F,\theta )$ is free on $S$.

Proposition 102.5(Proposition).

$(F,\theta )$ is free on $S$.

Proof.

Let $\phi :S\to G$ be a map into any group. Let $S=\{s_{\alpha }:\alpha \in I\}$, and the image $\text{im}(\theta )$ of $S$ in $F$ be denoted by $\{s_{\alpha }^{\prime }:\alpha \in I\}$. $\overline{\phi }$ from Def 1, if it exists, must agree with $\phi$ on $S$, that is, $\overline{\phi }(s_{\alpha }^{\prime })=\phi (s_{\alpha })$. Since $\text{im}(\theta )$ generates $F$, this can be uniquely extended to a homomorphism $F\to G$.□

383842

Thus, given a set $S$, we have constructed a free group on $S$. We will now show that free groups constructed on sets of the same cardinality are isomorphic.

Rank of a free group

Proposition 102.6(Proposition).

If $|X_1|=|X_2|$, then $F(X_1)\cong F(X_2)$.

Proof.

Let $\alpha :X_1\to X_2$ be an isomorphism, and $(F_1,{\theta }_1)$, $(F_2,{\theta }_2)$ be free groups on $X_1$ and $X_2$ respectively. Let ${\phi }_1:F_1\to F_2$ and ${\phi }_2:F_2\to F_1$ be the unique homomorphisms given by Def 1 corresponding to ${\theta }_2\circ \alpha$ and ${\theta }_1\circ {\alpha }^{-1}$ respectively.

For all $x\in X_1$,

$$\begin{array}{rl}{\phi }_2({\phi }_1({\theta }_1(x)))& ={\phi }_2({\theta }_2(\alpha (x)))\\ & ={\theta }_1({\alpha }^{-1}(\alpha (x)))\\ & ={\theta }_1(x).\end{array}$$

Therefore, ${\phi }_2\circ {\phi }_1$ makes this diagram commute:

Since the identity ${\text{id}}_{F_1}:F_1\to F_1$ also makes the above diagram commute, it follows that ${\phi }_2\circ {\phi }_1={\text{id}}_{F_1}$. Similarly, ${\phi }_1\circ {\phi }_2={\text{id}}_{F_2}$. Thus, $F_1\cong F_2$.□

0409cd

The converse is also true: isomorphic free groups must be on isomorphic sets.

Proposition 102.7(Proposition).

If $F(X_1)\cong F(X_2)$, then $|X_1|=|X_2|$.

Proof.

Consider the sets $\text{Hom}(F(X_1),{\mathbb{F}}_2)$ and $\text{Hom}(F(X_2),{\mathbb{F}}_2)$ of group homomorphisms to the field ${\mathbb{F}}_2$. These sets are vector spaces over ${\mathbb{F}}_2$ with bases $X_1$ and $X_2$ respectively. Fixing an isomorphism $\theta :F(X_1)\to F(X_2)$, we have an isomorphism of ${\mathbb{F}}_2$-vector spaces from $\text{Hom}(F(X_2),{\mathbb{F}}_2)$ to $\text{Hom}(F(X_1),{\mathbb{F}}_2)$ given by $\phi \mapsto \phi \circ \theta$ ². Thus, their bases must have the same cardinality, which proves $|X_1|=|X_2|$.□

cb59c5

In light of Prp 6 and Prp 7, one may define

Definition 102.8(Definition).

The rank of any free group is the cardinality of a set $X$ on which it is free.

Generators and relations

Definition 102.9(Definition).

A relation among elements $x_1,x_2,\dots ,x_n$ of a group $G$ is a word $r$ in the free group on the set $\{x_1,x_2,\dots ,x_n\}$ that evaluates to $1$ in $G$.

The following should be easy to see:

Proposition 102.10(Proposition).

Let $R$ be a subset of a group $G$. There exists a unique smallest normal subgroup $N$ of $G$ which contains $R$, called the normal subgroup generated by $R$. If a normal subgroup of $G$ contains $R$, it contains $N$. The elements of $N$ can be described as follows: Let $R^{\prime }$ be the set consisting of elements $r$ and $r^{-1}$ with $r\in R$. An element of $G$ is in $N$ if it can be written as a product $y_1\dots y_r$ of some arbitrary length, where each $y_v$ is a conjugate of an element in $R^{\prime }$.

Definition 102.11(Definition).

Let $\mathcal{F}$ be the free group on a set $S=\{x_1,\dots ,x_n\}$, and let $R=\{r_1,\dots ,r_k\}$ be a set of elements of $\mathcal{F}$. The group generated by $S$ with relations $r_1,r_2,\dots ,r_k$ is the quotient group $\mathcal{G}=\mathcal{F}/\mathcal{R}$, where $\mathcal{R}$ is the normal subgroup of $\mathcal{F}$ generated by $R$. $\mathcal{G}$ is denoted by $⟨x_1,\dots ,x_n|r_1,\dots ,r_k⟩$.

Note that $\mathcal{R}$ is precisely the set of words in $\mathcal{F}$ which equate to the identity in $\mathcal{G}$. Let $R^{\prime }$ be the set consisting of elements $r$ and $r^{-1}$ with $r\in R$. Let $R^{\ast }$ be the set of all conjugates of the members of $R^{\prime }$: $\{xr{x}^{-1}|x\in \mathcal{F},r\in R^{\prime }\}$. Observe that any word in $\mathcal{G}$ which evaluates to the identity can be expressed as a product of the elements of $R^{\ast }$. For example, if $p,q\in \mathcal{F}$, we know that the word $pq{r}_1{r}_3^{-1}{q}^{-1}{r}_2^4{p}^{-1}$ evaluates to the identity in $G$. It can be represented as a product of members of $R^{\ast }$ as

$$(pq{r}_1{q}^{-1}{p}^{-1})(pq{r}_3^{-1}{q}^{-1}{p}^{-1})(p{r}_2^4{p}^{-1}).$$

Now, for $x\in \mathcal{F}$, consider the coset $x\mathcal{R}$. These are a set of words whose equivalence can be established using the relations $R$ (observe that since $\mathcal{R}$ is normal, $x\mathcal{R}$ contains every possible word equivalent to $x$ that you can think of: $x\mathcal{R}=\mathcal{R}x=\mathcal{R}x\mathcal{R}=\mathcal{R}{x}^2\mathcal{R}{x}^{-1}\mathcal{R}=\dots$). Thus, the cosets of $\mathcal{R}$ in $\mathcal{F}$ correspond to the distinct words in the group $\mathcal{G}$, modulo the relations in $R$.

Theorem 102.12(Theorem).

Let $G$ be a group and $S=\{x_1,\dots ,x_n\}\subseteq G$. Let $R=\{r_1,\dots ,r_k\}$ be a set of relations satisfied by the elements of $S$ in $G$. Let $\mathcal{F}$ be the free group on $S$, and $\mathcal{R}$ be the normal subgroup of $\mathcal{F}$ generated by $R$. Let $\mathcal{G}:=\mathcal{F}/\mathcal{R}$. Then, there is a canonical homomorphism $\psi :\mathcal{G}\to G$ which is

1. surjective iff $S$ generates $G$;
2. injective iff every relation among the elements of $S$ is in $\mathcal{R}$. In other words, $\psi$ is injective iff $\mathcal{R}=\ker \psi$.

If $\psi$ is bijective, we say $R$ forms a complete set of relations among the generators $S$, and $G\cong \mathcal{G}$.

Proof.

Def 1 gives us a homomorphism $\phi :\mathcal{F}\to G$ with $\phi (x_i)=x_i$. Clearly, $R\subseteq \ker \phi$. Since $\ker \phi$ is a normal subgroup and thus is closed under the operations we used to construct $\mathcal{R}$, $\mathcal{R}$ must also be contained in $\ker \phi$. The universal property of quotient groups gives us a map $\overline{\phi }:\mathcal{G}\to G$. This is the map $\psi$.

$(1)$ is obvious; to see $(2)$, assume there exists a relation $\rho =1$ among the elements of $S$ which is not present in $\mathcal{R}$. Then, $\mathcal{R}$ and $\rho \mathcal{R}$ will be distinct elements of $\mathcal{F}/\mathcal{R}$. However, since both $\mathcal{R}$ and $\rho \mathcal{R}$ will be contained in $\ker \phi$, we have $\psi (\mathcal{R})=\psi (\rho \mathcal{R})=1$.□

Corollary 102.13(Corollary).

A group is finitely generated iff it is a quotient of a finitely generated free group.

Proof.

A quotient of a finitely generated group is finitely generated (the image of the generators generate the image). Conversely, let $G$ be a finitely generated group, say generated by the finite set $S\subseteq G$. Let $\mathcal{F}$ be the free group generated by $S$. The homomorphism $\phi :\mathcal{F}\to G$ supplied by Def 1 is the identity on $S$, making it surjective. Therefore, $G\cong F/\ker \phi$.□

Footnotes

1. The identity works, and it must be the only one because it does! ↩

2. This is an easy verification - injectivity and surjectivity of this map follow directly from the invertibility of $\theta$. ↩

---

References

Artin, M. (2011). Algebra (2. ed). Pearson Education, Prentice Hall.

Balsdon, P. D., Horawa, A., Lenain, R. M., & Yang, H. (n.d.). FREE GROUPS AND GEOMETRY.

Robinson, A. (2015). THE BANACH-TARSKI PARADOX. https://math.uchicago.edu/~may/REU2014/REUPapers/Robinson.pdf

Sury, B. (2010). Free Groups - Basics.