Topology/Free group and presentation of a group

Free monoid spanned by a set

Let $V$ be a vector space and $v_1,\dots ,v_n$ be a basis of $V$. Given any vector space $W$ and any elements $w_1,\dots ,w_n\in W$, there is a linear transformation $\phi :V\to W$ such that $\mathrm{\forall }i\in \{1,\dots ,n\},\phi (v_i)=w_i$. One could say that this happens because the elements $v_1,\dots ,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,\dots ,v_n$ wasn't linearly independent), then the linear transformation $\phi$ 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 $\phi :G\to H$ such that $\mathrm{\forall }i\in I,\phi (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=ℝ$ (with the adition operation) and the set $Y=\{2\}$. If there exists a group morphism $\phi :{\mathbb{Z}}_n\to ℝ$ such that $\phi (1)=2$, then $n2=n\phi (1)=\phi (n1)=\phi (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 $\phi (t)=2t$. Indeed, given any group $H$ and any $y\in H$, we have the group morphism $\phi :\mathbb{Z}\to H$ defined by $\phi (t)=y^t$ (in multiplicative notation) that verifies $\phi (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\dots 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\dots x_n$ where $x_1,\dots ,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,\dots ,x_n)$ with $x_i\in X$ and $n\in \mathbb{N}$ by $x_1\dots x_n$.
2. We denote $()$, that is $(x_1,\dots ,x_n)$ with $n=0$, by $1$.
3. We denote by $FM(X)$ the set $\{x_1\dots x_n:n\in \mathbb{N},x_i\in X\}$.
4. We define in $FM(X)$ the concatenation operation $*$ by $x_1\dots x_m*y_1\dots y_n=x_1\dots x_m{y}_1\dots 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\dots x_m,y_1\dots y_n,z_1\dots z_p\in FM(X)$, we have

$(x_1\dots x_m*y_1\dots y_n)*z_1\dots z_m$

$=x_1\dots x_m{y}_1\dots y_n*z_1\dots z_m$

$=x_1\dots x_m{y}_1\dots y_n{z}_1\dots z_m$

$=x_1\dots x_m*(y_1\dots y_n{z}_1\dots z_m)$

$=x_1\dots x_m(y_1\dots y_n*z_1\dots z_m)$.

It's obvious that $(FM(X),*)$ has the identity $1$ as $1*x_1\dots x_n=x_1\dots x_n$ by the definition of $1$ and $*$. $◻$

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,\dots \}$ 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 $\overline{X}$ equipotent to $X$, choose a bijection from $X$ to $\overline{X}$ and in this way achieve a "association" between the elements of $X$ and the elements of $\overline{X}$. Then we face $x_1\dots x_n\in FM(X)$ (with $x_1,\dots ,x_n\in X$) as having the inverse element $\overline{x_n}\dots \overline{x_1}$ (with $\overline{x_1},\dots ,\overline{x_n}\in X$), where $x_1,\dots ,x_n\in X$ is is associated with $\overline{x_1}\dots \overline{x_n}$, respectively. Let us note that the order of the elements in $\overline{x_n}\dots \overline{x_1}$ is "reversed" because the inverse of the product $x_1\dots x_n=x_1*\cdots *x_n$ must be $x_n^{-1}*\cdots *x_1^{-1}$, and the $x_1^{-1},\dots ,x_n^{-1}$ are, respectively, $\overline{x_1},\dots ,\overline{x_n}$. The way we do that $\overline{x_n}\dots \overline{x_1}$ be the inverse of $x_1\dots x_n$ is to take a congruence relation $R$ that identifies $x_1\dots x_n\overline{x_n}\dots \overline{x_1}$ with $1$, and pass to the quotient $FM(X\cup \overline{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\dots x_n\overline{x_n}\dots \overline{x_1}$ with $1$, because in the quotient we have the equality $[x_1\dots x_n\overline{x_n}\dots \overline{x_1}{]}_R=[1{]}_R$. Let us give the formal definition.

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

1. For each $x\in X$ let us denote $f(x)$ by $\overline{x}$, for each $x\in \bar{X}$ let us denote $f^{-1}(x)$ by $\overline{x}$ and for each $x_1\dots x_n\in FM(X\cup \bar{X})$ let us denote $\overline{x_n}\dots \overline{x_1}$ by $\overline{x_1\dots x_n}$.
2. Let $R$ be the congruence relation of $FM(X\cup \bar{X})$ spanned by $G=\{(u*\overline{u},1):u\in X\cup \bar{X}\}$, this is, $R$ is the intersection of all the congruence relations in $FM(X\cup \bar{X})$ wich have $G$ as a subset. We denote the quotient set $FM(X\cup \bar{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 \overline{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^{\prime },v,v^{\prime }\in FM(X)$ be any elements such that $[u{]}_R=[u^{\prime }{]}_R$ and $[v{]}_R=[v^{\prime }{]}_R$, this is, $uR{u}^{\prime }$ and $vR{v}^{\prime }$. Because $R$ is a congruence relation in $FM(X\cup \overline{X})$, we have $u*vR{u}^{\prime }*v^{\prime }$, this is, $[u*v{]}_R=[u^{\prime }*v^{\prime }{]}_R$. $◻$

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 $[1{]}_R$ and where $\mathrm{\forall }[u{]}_R\in FG(X),{[u{]}_R}^{-1}=[\overline{u}{]}_R$.

Proof

1. $(FG(X),\star )$ is associative because $\mathrm{\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 $[1{]}_R$ is the identity $(FG(X),\star )$. Let $[u{]}_R\in FG(X)$ be any element. We have $[u{]}_R\star [1{]}_R=[u*1{]}_R=[u{]}_R$ and, in the same way, $[1{]}_R\star [u{]}_R=[u{]}_R$.
3. Let $[u{]}_R\in FG(X)$ be any element and let us see that $[u{]}_R\star [\overline{u}{]}_R=[1{]}_R$. We have $[u{]}_R\star [\overline{u}{]}_R=[u*\overline{u}{]}_R$ and, by definition of $R$, $u*\overline{u}R1$, this is, $[u*\overline{u}{]}_R=[1{]}_R$, therefore $[u{]}_R\star [\overline{u}{]}_R=[1{]}_R$ and, in the same way, $[\overline{u}{]}_R\star [u{]}_R=[1{]}_R$. $◻$

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 $\overline{X}=\{y\}$ disjoint (and equipotent) of $X$. Let $f:X\to \overline{X}$ be any (in fact, the only) bijective application of $X$ in $\overline{X}$. Then we denote $f(x)=y$ by $\overline{x}$ and we denote $f^{-1}(y)=x$ by $\overline{y}$. We regard $x$ and $y$ as inverse elements. Let $R$ be the congruence relation of $FM(X\cup \overline{X})$ spanned by $G=\{(1,1),(x\overline{x},1),(xx\overline{x}\overline{x},1),\dots \}$. $FG(X)=FM(\{x,\overline{x}\})/R$ is the set of all "words" written in the alphabet $\{[x{]}_R,[\overline{x}{]}_R\}$. For example, $[1{]}_R,[x{]}_R,[\overline{x}{]}_R,[xx\overline{x}xx{]}_R\in FG(X)$.

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

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

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

In this way, each element $[u{]}_R\in FG(X)$ is determined by the integer number $|u{|}_{x-\overline{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-\overline{x}}$ and $|v{|}_{x-\overline{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-\overline{x}}:FG(X)\to \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 $u{v}^{-1}=1$ (for example, $xy=yx$ is written in the form $xy{x}^{-1}{y}^{-1}=1$) and we see each $u{v}^{-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 $u{v}^{-1}N=1N$, which we see as meaning that in $G/N$ the elements $u{v}^{-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 $<X:R>$, 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 $<X:R>$, 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. $<X:\mathrm{\varnothing }>$ is a presentation of $FG(X)$ because $FG(X)\simeq FG(X)/\{1\}$, where $\{1\}$ is the normal subgroup of $FG(X)$ spanned by $\mathrm{\varnothing }$. In particular, $<\{x\}:\mathrm{\varnothing }>$ is a presentation of $(\mathbb{Z},+)\simeq FG(\{x\})$, more commonly denoted by $<x:\mathrm{\varnothing }>$. Another presentation of $(\mathbb{Z},+)$ is $<\{x,y\}:\{x{y}^{-1}\}>$, more commonly denoted by $<x,y:x{y}^{-1}>$. Informally, in the presentation $<x,y:x{y}^{-1}>$ we insert a new element $y$ in the spanning set, but we impose the relation $x{y}^{-1}=1$, this is, $x=y$, which is the same as having not introduced the element $y$ and have stayed by the presentation $<x:\mathrm{\varnothing }>$.
2. Let $X=\{x\}$. $<X:\{x^n\}>$ (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=\{\dots ,{\overline{x}}^{2n},{\overline{x}}^n,1,x^n,x^{2n},\dots \}\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 $<x:x^n>$.
3. Let $X=\{x,y\}$ (with $x$ and $y$ distinct) and $R=\{xy{x}^{-1}{y}^{-1}\}$. $<X:R>$ 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, $xy{x}^{-1}{y}^{-1}=1$, obtaining a group isomorph to $\mathbb{Z}\oplus \mathbb{Z}$. It's more usually denote $<\{x,y\}:\{xy{x}^{-1}{y}^{-1}\}>$ by $<x,y:xy{x}^{-1}{y}^{-1}>$.
4. Let $X=\{x,y\}$ and $R=\{xy{x}^{-1}{y}^{-1},x^m,y^n\}$. $<X,R>$ is a presentation of ${\mathbb{Z}}_m\times {\mathbb{Z}}_n$. Informally, what we do is impose commutability 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\}:\{xy{x}^{-1}{y}^{-1},x^m,y^n\}>$ by $<x,y:xy{x}^{-1}{y}^{-1},x^m,y^n>$.
5. $<\{a,b,c\}:\{aa,bb,cc,abac,cbab\}>$, more commonly written $<a,b,c:a^2,b^2,c^2,abac,cbab>$, 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 $<a,b,c:a^2,b^2,c^2,abac,cbab>$ 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 achieved, a group with presentation $<a,b,c:a^2,b^2,c^2,abac,cbab>$ 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=(12)$, $b=(13)$ and $c=(23)$ 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 $\phi :FG(G)\to G$ defined by $\phi ([x_1{]}_R\star \cdots \star [x_n{]}_R)=x_1\times \cdots \times x_n$ (where $x_1,\dots ,x_n\in G$) is an epimorphism of groups.
2. $<G:\text{ker}\phi >$ is a presentation of $(G,\times )$.

Proof

1. $\phi$ 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,\dots ,x_n\in G$, with the exception of $[1{]}_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,\dots ,x_m,y_1,\dots ,y_n\in G$. We have $\phi (([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)=$ $\phi ([x_1{]}_R\star \cdots \star [x_m{]}_R)\times \phi ([y_1{]}_R\star \cdots \star [y_n{]}_R)$, therefore $\phi$ is a morphism of groups. Because $\mathrm{\forall }x\in G,\phi ([x{]}_R)=x$, then $G$ is a epimorphism of groups.
2. Using the first isomorphism theorem (for groups), we have $FG(G)/\text{ker}\phi \simeq \phi (G)=G$, therefore $<G:\text{ker}\phi >$ is a presentation of $(G,\times )$. $◻$

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{k}\mathrm{e}\mathrm{r}\phi$ 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).