# Topology/Free group and presentation of a group

## Free monoid spanned by a set

Let $V$  be a vector space and $v_{1},\ldots ,v_{n}$  be a basis of $V$ . Given any vector space $W$  and any elements $w_{1},\ldots ,w_{n}\in W$ , there is a linear transformation $\varphi :V\rightarrow W$  such that $\forall i\in \{1,\ldots ,n\},\,\varphi (v_{i})=w_{i}$ . One could say that this happens because the elements $v_{1},\ldots ,v_{n}$  of a basis are not "related" to each other (formally, they are linearly independent). Indeed, if, for example, we had the relation $v_{1}=\lambda v_{2}$  for some scalar $\lambda$  (and then $v_{1},\ldots ,v_{n}$  wasn't linearly independent), then the linear transformation $\varphi$  could not exist.

Let us consider a similar problem with groups: given a group $G$  spanned by a set $X=\{x_{i}:i\in I\}\subseteq G$  and given any group $H$  and any set $Y=\{y_{i}:i\in I\}\subseteq H$ , does there always exist a group morphism $\varphi :G\rightarrow H$  such that $\forall i\in I,\,\varphi (x_{i})=y_{i}$ ? The answer is no. For example, consider the group $G=\mathbb {Z} _{n}=\mathbb {Z} /n\mathbb {Z}$  which is spanned by the set $X=\{1\}$ , the group $H=\mathbb {R}$  (with the adition operation) and the set $Y=\{2\}$ . If there exists a group morphism $\varphi :\mathbb {Z} _{n}\rightarrow \mathbb {R}$  such that $\varphi (1)=2$ , then $n2=n\varphi (1)=\varphi (n\,1)=\varphi (0)=0$ , which is impossible. But if instead we had choose $G=\mathbb {Z}$ , then such a group morphism does exist and it would be given by $\varphi (t)=2t$ . Indeed, given any group $H$  and any $y\in H$ , we have the group morphism $\varphi :\mathbb {Z} \rightarrow H$  defined by $\varphi (t)=y^{t}$  (in multiplicative notation) that verifies $\varphi (1)=y$ . In a way, we can think that this happens because the elements of the set $X=\{1\}\subseteq \mathbb {Z}$  (that spans $\mathbb {Z}$ ) don't verify relations like $nx=1$  (like $\mathbb {Z} _{n}$ ) or $xy=yx$ . So, it seems that $\mathbb {Z}$  is a group more "free" that $\mathbb {Z} _{n}$ .

Our goal in this section will be, given a set $X$ , build a group spanned by the set $X$  such that it will be the most "free" possible, in the sense that it doesn't have to obey relations like $x^{n}=1$  or $xy=yx$ . To do so, we begin by constructing a "free" monoid (in the same sense). Informally, this monoid will be the monoid of the words written with the letters of the alphabet $X$ , where the identity will be the word with no letters (the "empty word"), and the binary operation of the monoid will be concatenation of words. The notation $x_{1}\ldots x_{n}$  that we will use for the element of this monoid meets this idea that the elements of this monoid are the words $x_{1}\ldots x_{n}$  where $x_{1},\ldots ,x_{n}$  are letters of the alphabet $X$ . Here is the definition of this monoid.

Definition Let $X$  be a set.

1. We denote the $n$ -tuples $(x_{1},\ldots ,x_{n})$  with $x_{i}\in X$  and $n\in \mathbb {N}$  by $x_{1}\ldots x_{n}$ .
2. We denote $()$ , that is $(x_{1},\ldots ,x_{n})$  with $n=0$ , by $1$ .
3. We denote by $FM(X)$  the set $\{x_{1}\ldots x_{n}:n\in \mathbb {N} ,x_{i}\in X\}$ .
4. We define in $FM(X)$  the concatenation operation $*$  by $x_{1}\ldots x_{m}*y_{1}\ldots y_{n}=x_{1}\ldots x_{m}y_{1}\ldots y_{n}$ .

Next we prove that this monoid is indeed a monoid. It's an easy to prove result, we need to show associativity of $*$  and that $1*x=x*1=x$ .

Proposition $(FM(X),*)$  is a monoid with identity $1$ .

Proof The operation $*$  is associative because, given any $x_{1}\ldots x_{m},y_{1}\ldots y_{n},z_{1}\ldots z_{p}\in FM(X)$ , we have

$(x_{1}\ldots x_{m}*y_{1}\ldots y_{n})*z_{1}\ldots z_{m}$
$=x_{1}\ldots x_{m}y_{1}\ldots y_{n}*z_{1}\ldots z_{m}$
$=x_{1}\ldots x_{m}y_{1}\ldots y_{n}z_{1}\ldots z_{m}$
$=x_{1}\ldots x_{m}*(y_{1}\ldots y_{n}z_{1}\ldots z_{m})$
$=x_{1}\ldots x_{m}(y_{1}\ldots y_{n}*z_{1}\ldots z_{m})$ .

It's obvious that $(FM(X),*)$  has the identity $1$  as $1*x_{1}\ldots x_{n}=x_{1}\ldots x_{n}$  by the definition of $1$  and $*$ . $\square$

Following the idea that the monoid $(FM(X),*)$  is the most "free" monoid spanned by $X$ , we will call it the free monoid spanned by $X$ .

Definition Let $X$  be a set. We denote the free monoid spanned by $X$  by $(FM(X),*)$ .

Examples

1. Let $X=\{x\}$ . Then $FM(X)=\{1,x,xx,xxx,\ldots \}$  and, for example, $xx*xxx=xxxxx$ .
2. Let $X=\{x,y,z\}$ . Then $1,x,y,z,xxx,yxz,xyzzz\in FM(X)$  and, for example, $xxx*yxz=xxxyxz$ .

## Free group spanned by a set

Now let us construct the more "free" group spanned by a set $X$ . Informally, what we will do is insert in the monoid $FM(X)$  the inverse elements that are missing in it for it to be a group. In a more precise way, we will have a set ${\bar {X}}$  equipotent to $X$ , choose a bijection from $X$  to ${\bar {X}}$  and in this way achieve a "association" between the elements of $X$  and the elements of ${\bar {X}}$ . Then we face $x_{1}\ldots x_{n}\in FM(X)$  (with $x_{1},\ldots ,x_{n}\in X$ ) as having the inverse element ${\overline {x_{n}}}\ldots {\overline {x_{1}}}$  (with ${\overline {x_{1}}},\ldots ,{\overline {x_{n}}}\in X$ ), where $x_{1},\ldots ,x_{n}\in X$  is is associated with ${\overline {x_{1}}}\ldots {\overline {x_{n}}}$ , respectively. Let us note that the order of the elements in ${\overline {x_{n}}}\ldots {\overline {x_{1}}}$  is "reversed" because the inverse of the product $x_{1}\ldots x_{n}=x_{1}*\cdots *x_{n}$  must be $x_{n}^{-1}*\cdots *x_{1}^{-1}$ , and the $x_{1}^{-1},\ldots ,x_{n}^{-1}$  are, respectively, ${\overline {x_{1}}},\ldots ,{\overline {x_{n}}}$ . The way we do that ${\overline {x_{n}}}\ldots {\overline {x_{1}}}$  be the inverse of $x_{1}\ldots x_{n}$  is to take a congruence relation $R$  that identifies $x_{1}\ldots x_{n}{\overline {x_{n}}}\ldots {\overline {x_{1}}}$  with $1$ , and pass to the quotient $FM(X\cup {\bar {X}})$  by this relation (defining then, in a natural way, the binary operation of the group, $[u]_{R}\star [v]_{R}=[u*v]_{R}$ ). By taking the quotient, we are formalizing the intuitive idea of identifying $x_{1}\ldots x_{n}{\overline {x_{n}}}\ldots {\overline {x_{1}}}$  with $1$ , because in the quotient we have the equality $[x_{1}\ldots x_{n}{\overline {x_{n}}}\ldots {\overline {x_{1}}}]_{R}=_{R}$ . Let us give the formal definition.

Definition Let $X$  be a set. Let us take another set ${\overline {X}}$  equipotent to $X$  and disjoint from $X$  and let $f:X\rightarrow {\overline {X}}$  be a bijective application.

1. For each $x\in X$  let us denote $f(x)$  by ${\bar {x}}$ , for each $x\in {\overline {X}}$  let us denote $f^{-1}(x)$  by ${\bar {x}}$  and for each $x_{1}\ldots x_{n}\in FM(X\cup {\overline {X}})$  let us denote ${\overline {x_{n}}}\ldots {\overline {x_{1}}}$  by ${\overline {x_{1}\ldots x_{n}}}$ .
2. Let $R$  be the congruence relation of $FM(X\cup {\overline {X}})$  spanned by $G=\{(u*{\bar {u}},1):u\in X\cup {\overline {X}}\}$ , this is, $R$  is the intersection of all the congruence relations in $FM(X\cup {\overline {X}})$  wich have $G$  as a subset. We denote the quotient set $FM(X\cup {\overline {X}})/R$  by $FG(X)$ .

Frequently, abusing the notation, we represent an element $[u]_{R}\in FG(X)$  simply by $u$ .

Because the operation $[u]_{R}\star [v]_{R}=[u*v]_{R}$  that we want to define in $FM(X\cup {\bar {X}})/R$  is defined using particular represententes $u$  and $v$  of the equivalence classes $[u]_{R}$  and $[v]_{R}$ , a first precaution is to verify that the definition does not depend on the chosen representatives. It's an easy verification.

Lemma Let $X$  be a set. It is well defined in $FG(X)$  the binary operation $\star$  by $[u]_{R}\star [v]_{R}=[u_{r}*v_{r}]_{R}$  (where $R$  is the congruence relation of the previous definition).

Proof Let $u,u',v,v'\in FM(X)$  be any elements such that $[u]_{R}=[u']_{R}$  and $[v]_{R}=[v']_{R}$ , this is, $uRu'$  and $vRv'$ . Because $R$  is a congruence relation in $FM(X\cup {\bar {X}})$ , we have $u*vRu'*v'$ , this is, $[u*v]_{R}=[u'*v']_{R}$ . $\square$

Because the definition is valid, we present it.

Definition Let $X$  be a set. We define in $FG(X)$  the binary operation $\star$  by $[u]_{R}\star [v]_{R}=[u_{r}*v_{r}]_{R}$ .

Finally, we verify that the group that we constructed is indeed a group.

Proposition Let $X$  be a set. $(FG(X),\star )$  is a group with identity $_{R}$  and where $\forall [u]_{R}\in FG(X),\,{[u]_{R}}^{-1}=[{\bar {u}}]_{R}$ .

Proof

1. $(FG(X),\star )$  is associative because $\forall [u]_{R},[v]_{R},[w]_{R}\in FG(X),\,([u]_{R}\star [v]_{R})\star [w]_{R}=([u*v]_{R})\star [w]_{R}=[([u]_{R}*[v]_{R})*w]_{R}=$  $[u*(v*w)]_{R}=[u]_{R}\star [v*w]_{R}=[u]_{R}\star ([v]_{R}\star [w]_{R}).$
2. Let us see that $_{R}$  is the identity $(FG(X),\star )$ . Let $[u]_{R}\in FG(X)$  be any element. We have $[u]_{R}\star _{R}=[u*1]_{R}=[u]_{R}$  and, in the same way, $_{R}\star [u]_{R}=[u]_{R}$ .
3. Let $[u]_{R}\in FG(X)$  be any element and let us see that $[u]_{R}\star [{\bar {u}}]_{R}=_{R}$ . We have $[u]_{R}\star [{\bar {u}}]_{R}=[u*{\bar {u}}]_{R}$  and, by definition of $R$ , $u*{\bar {u}}R1$ , this is, $[u*{\bar {u}}]_{R}=_{R}$ , therefore $[u]_{R}\star [{\bar {u}}]_{R}=_{R}$  and, in the same way, $[{\bar {u}}]_{R}\star [u]_{R}=_{R}$ . $\square$

In the same way that we did with the free monoid, we will call free group spanned by the set $X$  to the more "free" group spanned by this set.

Definition Let $X$  be a set. We call free group spanned by $X$  to $(FG(X),\star )$ .

Example Let $X=\{x\}$ . Let us choose any set ${\bar {X}}=\{y\}$  disjoint (and equipotent) of $X$ . Let $f:X\rightarrow {\bar {X}}$  be any (in fact, the only) bijective application of $X$  in ${\bar {X}}$ . Then we denote $f(x)=y$  by ${\bar {x}}$  and we denote $f^{-1}(y)=x$  by ${\bar {y}}$ . We regard $x$  and $y$  as inverse elements. Let $R$  be the congruence relation of $FM(X\cup {\bar {X}})$  spanned by $G=\{(1,1),(x{\bar {x}},1),(xx{\bar {x}}{\bar {x}},1),\ldots \}$ . $FG(X)=FM(\{x,{\bar {x}}\})/R$  is the set of all "words" written in the alphabet $\{[x]_{R},[{\bar {x}}]_{R}\}$ . For example, $_{R},[x]_{R},[{\bar {x}}]_{R},[xx{\bar {x}}xx]_{R}\in FG(X)$ .

We have $G\subseteq R$  and, for example, $(xx{\bar {x}},1)\in R$ , because $(x{\bar {x}},1)\in G\subseteq R$  (therefore $x{\bar {x}}R1$ ) and because $R$  is a congruence relation, we can "multiply" both "members" of the relation $x{\bar {x}}R1$  by $x$  and obtain $xx{\bar {x}}Rx$ . We see $x{\bar {x}}R1$  as meaning that in $FG(X)$  We have $xx{\bar {x}}=x$  (more precisely, $[xx{\bar {x}}]_{R}=[x]_{R}$ ), and we think in this equality as being the result of one $x$  "cut out" with ${\bar {x}}$  in $xx{\bar {x}}$ .

Given $u\in FM(X\cup {\bar {X}})$ , let us denote the exact number of times that the "letter" $x$  appears in $u$  by $|u|_{x}$  and let us denote the exact number of times the "letter" ${\bar {x}}$  appears in $u$  by $|u|_{\bar {x}}$ . Then "cutting" $x$ 's with ${\bar {x}}$ 's it remains a reduced word word with $|u|_{x}-|u|_{\bar {x}}$  times the letter $x$  (if $|u|_{x}-|u|_{\bar {x}}<0$ , let us us consider that there aren't any letters $x$  and remains $-(|u|_{x}-|u|_{\bar {x}})$  times the letter ${\bar {x}}$ ). Let us denote $|u|_{x}-|u|_{\bar {x}}$  by $|u|_{x-{\bar {x}}}$ . We have

1. $[u]_{R}=[v]_{R}$  if and only if $|u|_{x-{\bar {x}}}=|v|_{x-{\bar {x}}}$  and
2. $\forall [u]_{R},[v]_{R}\in FG(X),\,|uv|_{x-{\bar {x}}}=|u|_{x-{\bar {x}}}+|v|_{x-{\bar {x}}}$ .

In this way, each element $[u]_{R}\in FG(X)$  is determined by the integer number $|u|_{x-{\bar {x}}}$  and the product $\star$  of two elements $[u]_{R},[v]_{R}\in FG(X)$  correspondent to the sum of they associated integers numbers $|u|_{x-{\bar {x}}}$  and $|v|_{x-{\bar {x}}}$ . Therefore, it seems that the group $(FG(X),\star )$  is "similar" to $(\mathbb {Z} ,+)$ . indeed $(FG(X),\star )$  is isomorph to $(\mathbb {Z} ,+)$  and the application $|\cdot |_{x-{\bar {x}}}:FG(X)\rightarrow \mathbb {Z}$  is a group isomorphism.

## Presentation of a group

Informally, it seems that $\mathbb {Z} _{n}$  is obtained from the "free" group $\mathbb {Z}$  imposing the relation $nx=1$ . Let us try formalize this idea. We start with a set $X$  that spans a group $G$  that que want to create and a set of relations $R$  (such as $x^{n}=1$  or $xy=yz$ ) that the elements of $G$  must verify and we obtain a group $G/R$  spanned by $G$  and that verify the relations of $R$ . More precisely, we write each relation $u=v$  in the form $uv^{-1}=1$  (for example, $xy=yx$  is written in the form $xyx^{-1}y^{-1}=1$ ) and we see each $uv^{-1}$  as a "word" of $FG(X)$ . Because $R$  doesn't have to be a normal subgroup of $G$ , we can not consider the quotient $FG(X)/R$ , so we consider the quotient $FG(X)/N$  where $N$  is the normal subgroup of $FG(X)$  spanned by $R$ . In $G/N$ , we will have $uv^{-1}N=1N$ , which we see as meaning that in $G/N$  the elements $uv^{-1}$  and $1$  are the same. In this way, $FG(X)/N$  will verify all the relations that we want and will be spanned by $X$  (more precisely, by $\{xN:x\in X\}$ ). Let us formalize this idea.

Definition Let $G$  be a group. We call presentation of $G$ , and denote by $$ , to a ordered pair $(X,R)$  where $X$  is a set, $R\subseteq FG(X)$  and $G\simeq FG(X)/N$ , where $N$  is the normal subgroup of $FG(X)$  spanned by $R$ . Given a presentation $$ , we call spanning set to $X$  and set of relations to $R$ .

Let us see some examples of presentations of the free group $FG(X)$  and the groups $\mathbb {Z} _{n}$ , $\mathbb {Z} \oplus \mathbb {Z}$ , $\mathbb {Z} _{m}\oplus \mathbb {Z} _{n}$  and $S_{3}$ . We also use the examples to present some common notation and to show that a presentation of a group does not need to be unique.

Examples

1. Let $X$  be a set. $$  is a presentation of $FG(X)$  because $FG(X)\simeq FG(X)/\{1\}$ , where $\{1\}$  is the normal subgroup of $FG(X)$  spanned by $\emptyset$ . In particular, $<\{x\}:\emptyset >$  is a presentation of $(\mathbb {Z} ,+)\simeq FG(\{x\})$ , more commonly denoted by $$ . Another presentation of $(\mathbb {Z} ,+)$  is $<\{x,y\}:\{xy^{-1}\}>$ , more commonly denoted by $$ . Informally, in the presentation $$  we insert a new element $y$  in the spanning set, but we impose the relation $xy^{-1}=1$ , this is, $x=y$ , which is the same as having not introduced the element $y$  and have stayed by the presentation $$ .
2. Let $X=\{x\}$ . $$  (where $x^{n}=x\star \cdots \star x\in FG(X)$  $n$  times) is a presentation of $\mathbb {Z} _{n}$ . Indeed, the subgroup of $FG(X)$  spanned by $\{x^{n}\}$  is $N=\{\ldots ,{\bar {x}}^{2n},{\bar {x}}^{n},1,x^{n},x^{2n},\ldots \}\simeq n\mathbb {Z}$  and $FG(X)\simeq \mathbb {Z}$ , therefore$\mathbb {Z} _{n}=\mathbb {Z} /n\mathbb {Z} \simeq FG(X)/N$ . Is more common to denote $<\{x\}:\{x^{n}\}>$  by $$ .
3. Let $X=\{x,y\}$  (with $x$  and $y$  distinct) and $R=\{xyx^{-1}y^{-1}\}$ . $$  is a presentation of $\mathbb {Z} \oplus \mathbb {Z}$ . Informally, what we do is impose comutatibility in $FG(X)$ , this is, $xy=yx$ , this is, $xyx^{-1}y^{-1}=1$ , obtaining a group isomorph to $\mathbb {Z} \oplus \mathbb {Z}$ . It's more usually denote $<\{x,y\}:\{xyx^{-1}y^{-1}\}>$  by $$ .
4. Let $X=\{x,y\}$  and $R=\{xyx^{-1}y^{-1},x^{m},y^{n}\}$ . $$  is a presentation of $\mathbb {Z} _{m}\times \mathbb {Z} _{n}$ . Informally, what we do is impose comutability in the same way as in the previous example, and we impose $x^{m}=1$  and $x^{n}=1$  to obtain $\mathbb {Z} _{m}\times \mathbb {Z} _{n}$  instead $\mathbb {Z} \oplus \mathbb {Z}$ . It's more common denote$<\{x,y\}:\{xyx^{-1}y^{-1},x^{m},y^{n}\}>$  by $$ .
5. $<\{a,b,c\}:\{aa,bb,cc,abac,cbab\}>$ , more commonly written $$ , is a presentation of $S_{3}$ , the group of the permutations of $\{1,2,3\}$  with the composition of applications. To verify this, one can verify that any group with presentation $$  as exactly six elements $id$ , $a$ , $b$ , $c$ , $a$ , $ab$  and $ac$ , and that the multiplication of this elements results in the following Cayley table that is equal to the Cayley table of $S_{3}$ . Just to give an idea how this can be achived, a group with presentation $$  as exactly the elements $id$ , $a$ , $b$ , $c$ , $a$ , $ab$  and $ac$  because none of this elements are the same (the relations $a^{2}=b^{2}=c^{2}=abac=cbab=1$  don't allow us to conclude that two of the elements are equal) and because "another" elements like $bc$  are actually one of the previous elements (for example, from $cbab=id$  we have $cb=ab$ , and taking inverses of both members, we have $b^{-1}c^{-1}=b^{-1}a^{-1}$ , which, using $a^{2}=b^{2}=c^{2}=id$ , this is, $a=a^{-1}$ , $b=b^{-1}$  and $c=c^{-1}$ , results in $bc=ba$ ). Then, using the relations of the presentation, one can compute the Cayley table. For example, $a(ab)=b$  because we have the relation $a^{2}=1$ . Another example: we have $b(ac)=a$  because we can multiply both members of the relation $abac=id$  by $a$  and then use $a^{2}=id$ . One could have suspected of this presentation by taking $a=(1\ 2)$ , $b=(1\ 3)$  and $c=(2\ 3)$  and then, trying to construct the Cayley table of $S_{3}$ , found out that it was possible if one know that $a^{2}=b^{2}=c^{2}=abac=cbab=1$ .
$\times$  $id$  $a$  $b$  $c$  $ab$  $ac$
$id$  $id$  $a$  $b$  $c$  $ab$  $ac$
$a$  $a$  $id$  $ab$  $ac$  $b$  $c$
$b$  $b$  $ac$  $id$  $ab$  $c$  $a$
$c$  $c$  $ab$  $ac$  $id$  $a$  $b$
$ab$  $ab$  $c$  $a$  $b$  $ac$  $id$
$ac$  $ac$  $b$  $c$  $a$  $id$  $ab$

It's natural to ask if all groups have a presentation. The following theorem tell us that the answer is yes, and it give us a presentation.

Theorem Let $(G,\times )$  be a group.

1. The application $\varphi :FG(G)\rightarrow G$  defined by $\varphi ([x_{1}]_{R}\star \cdots \star [x_{n}]_{R})=x_{1}\times \cdots \times x_{n}$  (where $x_{1},\ldots ,x_{n}\in G$ ) is an epimorphism of groups.
2. $$  is a presentation of $(G,\times )$ .

Proof

1. $\varphi$  is well defined because every element of $FG(X)$  as a unique representations in the form $[x_{n}]\star \cdots [x_{n}]_{R}$  with $x_{1},\ldots ,x_{n}\in G$ , with the exception of $_{R}$  appears several times in the representation, but that doesn't affect the value of $x_{1}\times \cdots \times x_{n}$  Let $[x_{1}]_{R}\star \cdots \star [x_{m}]_{R},[y_{1}]_{R}\star \cdots \star [y_{n}]_{R}\in FG(X)$  be any elements, where $x_{1},\ldots ,x_{m},y_{1},\ldots ,y_{n}\in G$ . We have $\varphi (([x_{1}]_{R}\star \cdots \star [x_{m}]_{R})\star ([y_{1}]_{R}\star \cdots \star [y_{n}]_{R}))=(x_{1}\times \cdots \times x_{m})\times (y_{1}\times \cdots \times y_{n})=$  $\varphi ([x_{1}]_{R}\star \cdots \star [x_{m}]_{R})\times \varphi ([y_{1}]_{R}\star \cdots \star [y_{n}]_{R})$ , therefore $\varphi$  is a morphism of groups. Because $\forall x\in G,\,\varphi ([x]_{R})=x$ , then $G$  is a epimorphism of groups.
2. Using the first isomorphism theorem (for groups), we have $FG(G)/{\textrm {ker}}\,\varphi \simeq \varphi (G)=G$ , therefore $$  is a presentation of $(G,\times )$ . $\square$

The previous theorem, despite giving us a presentations of the group $G$ , doesn't give us a "good" presentation, because the spanning set $G$  is usually much larger that other spanning sets, and the set of relations $\mathrm {ker} \,\varphi$  is also usually much larger then other sufficient sets of relations (it is even a normal subgroup of $FG(G)$ , when it would be enough that it span an appropriated normal subgroup).