MATH 422 Lecture Note #7 (2018 Spring)
Free groups and group presentations

Jae Choon Cha
POSTECH $\def\id{\operatorname{id}} \def\rel{\text{ rel }} \def\Z{\mathbb{Z}} \def\Q{\mathbb{Q}} \def\R{\mathbb{R}} \def\C{\mathbb{C}} \def\sm{\smallsetminus}$

Free groups

Consider a collection $S=\{x_i\}_{i\in I}$ of symbols $x_i$. For each $i\in I$, let $x_i^{-1}$ be another formal symbol, and let $\overline S=\{x_i^{-1}\}_{i\in I}$. Recall that a word on $S\cup\overline S$ is an expression of the form $w=x_{i_1}^{\epsilon_1}\cdots x_{i_\ell}^{\epsilon_\ell}$ where $\epsilon_k\in \{1,-1\}$. We allow $\ell=0$, that is, the empty word, which we denote by $e$, is a word too. Define the concatenation, or product, of words as follows: for $w =x_{i_1}^{\epsilon_1}\cdots x_{i_r}^{\epsilon_r}$ and $v =x_{j_1}^{\delta_1}\cdots x_{j_s}^{\delta_s}$,

\[wv = x_{i_1}^{\epsilon_1}\cdots x_{i_r}^{\epsilon_r} x_{j_1}^{\delta_1}\cdots x_{j_s}^{\delta_s}.\]

Define a relation $\sim$ on the set of words on $S$ as follows: $w\sim v$ if there is a finite sequence of words $w=w_0,w_1,\ldots,w_n=v$ such that for each $i=1,\ldots,n$, there are words $u,u'$ such that $\{w_{i-1},w_i\}=\{uu', ux_j^\epsilon x_j^{-\epsilon}u'\}$ for some $j$ and $\epsilon$. It is easily seen that $\sim$ is an equivalence relation.

Theorem. The set

\[F\langle S\rangle=\{\text{words on }S\cup \overline S\}/\mathord{\sim}\]
of equivalence classes is a group under concatenation.

Proof. The well-definedness of the operation and its associativity is straightforward to verify. Also, it is easy to check that the identity is the empty word $e$, and the inverse of (the equivalence class of) $w=x_{i_1}^{\epsilon_1}\cdots x_{i_\ell}^{\epsilon_\ell}$ is (represented by) $w^{-1}=x_{i_\ell}^{-\epsilon_\ell}\cdots x_{i_1}^{-\epsilon_1}$. $\quad\square$

The group $F\langle S\rangle$ is called the free group on the generators $x_i$, or the free group generated by $x_i$. The symbols $x_i$ are called generators.

Note that $F\langle S\rangle$ and $F\langle T\rangle$ are isomorphic if there is a bijection between $S$ and $T$. When $S$ is a finite set with $n$ elements, $F\langle S\rangle$ is called a free group of rank $n$.

For brevity, we denote the equivalence class of a word $w$ by $w$. Also, as done before, we write the product of $n$ copies of $w$ by $w^n$.

The function $i\colon S\to F\langle S\rangle$ defined by $i(x_i)=x_i$ is one-to-one. (Exercise: prove it!) So, we may regard $S$ as a subset of $F\langle S\rangle$, by viewing $x_i\in S$ as a one-letter word representing an element of $F\langle S\rangle$.

The following fundamental property characterizes a free group.

Theorem (Universal property of the free group). For any function $f\colon S \to G$ to a group $G$, there is a unique group homomorphism $h\colon F\langle S\rangle \to G$ such that $h(x_i)=f(x_i)$ for all generators $x_i$.

▶︎
all
running…

Furthermore, if $H$ is another group equipped with a function $j\colon S\to H$ such that $(H,j)$ has the above property of $(F\langle S\rangle, i)$, then there is an isomorphism $\phi\colon F\langle S\rangle \to H$ such that $\phi i= j$.

Proof. For a given $f\colon S\to G$, define $h\colon F\langle S\rangle \to G$ by $h(x_{i_1}^{\epsilon_1}\cdots x_{i_\ell}^{\epsilon_\ell}) = f(x_{i_1})^{\epsilon_1}\cdots f(x_{i_\ell})^{\epsilon_\ell}$. It is straightforward to verify that $h$ is a well-defined group homomorphism. If $h'\colon F\langle S\rangle \to G$ is another homomorphism satisfying $h'(x_i)=f(x_i)$, then $h'(x_{i_1}^{\epsilon_1}\cdots x_{i_\ell}^{\epsilon_\ell})$ must be equal to $f(x_{i_1})^{\epsilon_1}\cdots f(x_{i_\ell})^{\epsilon_\ell}$, by the homomorphic property of $h'$. This proves the uniqueness of $h$.

The last statement is proven by a standard argument using the universal property. Details are left as an exercise. $\quad\square$

Group presentations

We will present a method to express a group as a quotient of a free group. For this purpose, we want to describe a normal subgroup of a free group. First, recall that the subgroup generated by a given subset $A$ of a group is defined to be the smallest subgroup of $G$ containing $A$. It is equal to the intersection of all subgroups containing $A$. (Exercise: prove this!) Alternatively, consider the following subset of $G$:

\[H := \{ a_1^{\epsilon_1} \cdots a_r^{\epsilon_r} \mid a_i\in A,\, \epsilon_i\in \{1,-1\}\}\]

Since $H$ is closed under product and inversion, $H$ is a subgroup. Also, if $K$ is another subgroup of $G$ which contains $A$, then for each $a_i\in A$, we have $a_1^{\epsilon_1} \cdots a_r^{\epsilon_r} \in K$. So the above $H$ is contained in $K$. It follows that $H$ is the smallest subgroup containing $A$. That is, $H$ is the subgroup generated by $A$.

Now, given a subset $A$ of a group $G$, the normal subgroup generated by $A$ is defined to be the smallest normal subgroup in $G$ containing $A$. Similarly to the above paragraph, it is equal to the intersection of all normal subgroups in $G$ containing $A$, and equal to the following subgroup:

\[N = \{g_1a_1^{\epsilon_1}g_1^{-1} \cdots g_r a_r^{\epsilon_r}g_r^{-1} \mid a_i\in A,\, \epsilon_i\in \{1,-1\},\, g_i\in G\}\]

In particular, the normal subgroup generated by $A$ is equal to the subgroup generated by conjugates of elements in $A$.

Definition. For a subset $R\in F\langle S\rangle$, define

\[\langle S\mid R\rangle = F\langle S\rangle / (\text{the normal subgroup generated by }R).\]

The expression $\langle S\mid R\rangle$ is called a group presentation. When $S=\{x_1,\ldots,x_n\}$ and $R=\{r_1,\ldots,r_m\}$ with each $r_i$ a word, we write

\[\langle x_1,\ldots,x_n \mid r_1,\ldots,r_m\rangle\]

instead of $\langle S\mid R\rangle$. We call an element $x_i$ of $S$ a generator, and an element $r_j$ of $R$ a relator. An element in the normal subgroup generated by $R$ is called a relation.

We often view a word in $x_i$ as an element in $\langle S\mid R\rangle$.

The following is a fundamental property of a group presentation.

Theorem. Suppose $S$ is a set and $G$ is a group. Suppose $f\colon S\to G$ is a function such that $f(x_{i_1}^{\epsilon_1})\cdots f(x_{i_\ell}^{\epsilon_\ell}) = e$ for each $x_{i_1}^{\epsilon_1}\cdots x_{i_\ell}^{\epsilon_\ell}\in R$. Then there is a unique homomorphism $h\colon \langle S\mid R\rangle \to G$ satisfying $h(x_i)=f(x_i)$ for each $x_i\in S$.

Proof. By the universal property of a free group, there is a homomorphism $g\colon F\langle S\rangle \to G$ satisfying $g(x_i)=f(x_i)$ for all $x_i\in S$. It follows that $g(r)=e$ for each $r\in R$, by the hypothesis. Therefore $g$ induces a homomorphism $h\colon\langle S \mid R \rangle \to G$. Since the elements $x_i$ generate $\langle S \mid R\rangle$, the property $h(x_i)=f(x_i)$ determines the homomorphism $h$ uniquely. $\quad\square$

The group presentation is a very useful method to describe a group.

Theorem. Every group $G$ has a group presentation. That is, $G\cong \langle S\mid R\rangle$ for some set $S$ and some subset $R$ of $F\langle S\rangle$.

Proof. First, observe that there exists an epimorphism $F\langle S\rangle \to G$ for some set $S$. For instance, take $G$ itself as $S$, and define a homomorphism $h\colon F\langle S\rangle \to G$ by $g\mapsto g$ for each $g\in G$. This homomorphism $h$ exists by the universal property of the free group $F\langle S\rangle$, and $h$ is obviously surjective. Let $N$ be the kernel of $h$. Choose a set $R$ which normally generates $N$. For instance, one may take $N$ itself as $R$. Then, by the first isomorphism theorem, $h$ induces an isomorphism $F\langle S\rangle / N \cong G$. This shows that $G\cong \langle S\mid R\rangle$.

Note that there are more than one group presentation which represent the same group. In general, it is a very difficult problem to determine when two group presentations give the same group.

Observe that a group presentation given by the construction in the proof of the above theorem is not very efficient in general. For example, for the infinite cyclic group, the proof gives us a group presentation with infinitely many generators. In practice, we often prefer working with simpler group presentations.

Definition. A group is finitely generated if it has a presentation with finitely many generators. A group is finitely presented if it has a presentation with finitely many generators and finitely many relators.

Examples.

  1. The presentation $\langle x \mid \cdot \rangle$ gives an infinite cyclic group. To give a proof, define a homomorphism $\phi\colon \langle x \mid \cdot \rangle \to \Z$ by $\phi(x)=1$, using the above theorem. Since $\phi(x^n)=n$ for any integer $n$, $\phi$ is 1-1 and onto. It follows that $\phi$ is an isomorphism.

  2. A similar argument shows that $\langle x \mid x^n \rangle \cong \Z_n$, the cyclic group of order $n$.

  3. Let $D_{2n}$ be the dihedral group of order $2n$. That is, $D_{2n}$ is the group of plane isometries preserving the set $\{e^{2\pi k i/n}\mid k=0,1,\dots,n-1\}$. Recall that an element of $D_{2n}$ is either the $(2\pi k/n)$-rotation, or a reflection about the line $\theta=\pi k/n$.

    We claim that $D_{2n}$ has the presentation $\langle x,y\mid x^2,\, y^n,\, xyxy\rangle$. To verify this, let $G=\langle x,y\mid x^2,\, y^n,\, xyxy\rangle$, and define a homomorphism $\phi\colon G \to D_{2n}$ by letting $\phi(x)$ be the reflection about the $x$-axis, and $\phi(y)$ be the rotation by $2\pi/n$. Our $\phi$ is well-defined since $\phi(x)^2$, $\phi(y)^n$ and $\phi(x)\phi(y)\phi(x)\phi(y)$ are equal to the identity. (Check!) Furthermore, $\phi$ is onto since the subset $\{\phi(x),\phi(y)\}$ generates $D_{2n}$. Finally, to show that $\phi$ is 1-1, choose an element of $G$, which is represented by a word $w$ in $x$ and $y$. Since $xy=y^{-1}x^{-1}$ in $G$, we may assume $w$ is of the form $w=x^a y^b$. Furthermore, since $x^2=e$ and $y^n=e$, we may assume $0\le a\le 1$ and $0\le b \le n-1$. This shows that $G$ has at most $2n$ elements. Since $D_{2n}$ has $2n$ elements and $\phi$ is onto, it follows that $G$ has exactly $2n$ elements and $\phi$ is 1-1. This completes the proof that $\phi$ is an isomorphism.