Topology/Free group and presentation of a group

From Wikibooks, the open-content textbooks collection

Current revision (unreviewed)

[edit] 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 = λ v 2$ for some scalar $λ$ (and then $v_1,\ldots,v_n$ wasn't anymore 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 always exists an 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 would 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 would exists 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 $n x = 1$ (like $\mathbb{Z}_n$ ) or $x y = y x$ . 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 more "free" possible, in the sense that it doesn't have to obey relation like $x n = 1$ or $x y = y x$ . 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 without letter (the "empty word"), and the binary operation of the monoid will be put together two words to form a new word. 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.

We denote the $n$ -tuples $(x_1,\ldots,x_n)$ (with $x_1,\ldots,x_n \in X$ and $n \in \mathbb{N} \cup \{0\}$ ) by $x_1 \ldots x_n$ .
We denote $()$ , this is, $(x_1,\ldots,x_n)$ with $n = 0$ , by $1$ .
We denote by $F M (X)$ the set $\{x_1 \ldots x_n : n \in \mathbb{N} \cup \{0\} \, \wedge \, x_1,\ldots,x_n \in X \}$ .
We define in $F M (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.

Proposition $(F M (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 $(F M (X), * )$ as the identity $1$ . $\square$

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

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

Examples

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

[edit] 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 $F M (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 = [1]_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.

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}$ .
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 $F G (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 $F G (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, $u R u'$ and $v R v'$ . Because $R$ is a congruence relation in $FM(X \cup \bar X)$ , we have $u * v R u' * 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 $F G (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 $\forall [u]_R \in FG(X), \, {[u]_R}^{-1} = [\bar u]_R$ .

Proof

$(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).$
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$ .
Let $[u]_R \in FG(X)$ be any element and let us see that $[u]_R \star [\bar u]_R = [1]_R$ . We have $[u]_R \star [\bar u]_R = [u * \bar u]_R$ and, by definition of $R$ , $u * \bar u R 1$ , this is, $[u * \bar u]_R = [1]_R$ , therefore $[u]_R \star [\bar u]_R = [1]_R$ and, in the same way, $[\bar u]_R \star [u]_R = [1]_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, $[1]_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 R 1$ ) and because $R$ is a congruence relation, we can "multiply" both "members" of the relation $x \bar x R 1$ by $x$ and obtain $xx \bar x R x$ . We see $x \bar x R 1$ as meaning that in $F G (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

$[u] R = [v] R$ if and only if $|u|_{x - \bar x} = |v|_{x - \bar x}$ and
$\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.

[edit] Presentation of a group

Informally, it seems that $\mathbb{Z}_n$ is obtained from the "free" group $\mathbb{Z}$ imposing the relation $n x = 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 $x y = y z$ ) 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, $x y = y x$ is written in the form $x y x - 1 y - 1 = 1$ ) and we see each $u v - 1$ as a "word" of $F G (X)$ . Because $R$ doesn't have to be a normal subgroup of $G$ , we can not consider the quotient $F G (X) / R$ , so we consider the quotient $F G (X) / N$ where $N$ is the normal subgroup of $F G (X)$ spanned by $R$ . In $G / N$ , we will have $u v - 1 N = 1 N$ , which we see as meaning that in $G / N$ the elements $u v - 1$ and $1$ are the same. In this way, $F G (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 $F G (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 $F G (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

Let $X$ be a set. $<X:{\emptyset}>$ is a presentation of $F G (X)$ because $FG(X) \simeq FG(X)/\{1\}$ , where ${1}$ is the normal subgroup of $F G (X)$ spanned by $\emptyset$ . In particular, $<\{x\}:\emptyset >$ is a presentation of $(\mathbb{Z},+) \simeq FG(\{x\})$ , more commonly denoted by $<x:\emptyset>$ . 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:\emptyset>$ .
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 $F G (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 $< x : x n >$ .
Let $X = {x, y}$ (with $x$ and $y$ distinct) and $R = {x y x - 1 y - 1}$ . $< X : R >$ is a presentation of $\mathbb{Z} \oplus \mathbb{Z}$ . Informally, what we do is impose comutatibility in $F G (X)$ , this is, $x y = y x$ , this is, $x y x - 1 y - 1 = 1$ , obtaining a group isomorph to $\mathbb{Z} \oplus \mathbb{Z}$ . It's more usually denote $< {x, y}:{x y x - 1 y - 1} >$ by $< x, y : x y x - 1 y - 1 >$ .
Let $X = {x, y}$ and $R = {x y 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 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}:{x y x - 1 y - 1, x m, y n} >$ by $< x, y : x y x - 1 y - 1, x m, y n >$ .
$< {a, b, c}:{a a, b b, c c, a b a c, c b a b} >$ , more commonly written $< a, b, c : a 2, b 2, c 2, a b a c, c b a b >$ , 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, a b a c, c b a b >$ as exactly six elements $i d$ , $a$ , $b$ , $c$ , $a$ , $a b$ and $a c$ , 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 $< a, b, c : a 2, b 2, c 2, a b a c, c b a b >$ as exactly the elements $i d$ , $a$ , $b$ , $c$ , $a$ , $a b$ and $a c$ because none of this elements are the same (the relations $a 2 = b 2 = c 2 = a b a c = c b a b = 1$ don't allow us to conclude that two of the elements are equal) and because "another" elements like $b c$ are actually one of the previous elements (for example, from $c b a b = i d$ we have $c b = a b$ , and taking inverses of both members, we have $b - 1 c - 1 = b - 1 a - 1$ , which, using $a 2 = b 2 = c 2 = i d$ , this is, $a = a - 1$ , $b = b - 1$ and $c = c - 1$ , results in $b c = b a$ ). Then, using the relations of the presentation, one can compute the Cayley table. For example, $a (a b) = b$ because we have the relation $a 2 = 1$ . Another example: we have $b (a c) = a$ because we can multiply both members of the relation $a b a c = i d$ by $a$ and then use $a 2 = i d$ . 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 = a b a c = c b a b = 1$ .

$\times$	$i d$	$a$	$b$	$c$	$a b$	$a c$
$i d$	$i d$	$a$	$b$	$c$	$a b$	$a c$
$a$	$a$	$i d$	$a b$	$a c$	$b$	$c$
$b$	$b$	$a c$	$i d$	$a b$	$c$	$a$
$c$	$c$	$a b$	$a c$	$i d$	$a$	$b$
$a b$	$a b$	$c$	$a$	$b$	$a c$	$i d$
$a c$	$a c$	$b$	$c$	$a$	$i d$	$a b$

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.

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.
$<G:\textrm{ker} \, \varphi>$ is a presentation of $(G,\times)$ .

Proof

$\varphi$ is well defined because every element of $F G (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 $[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,\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.
Using the first isomorphism theorem (for groups), we have $FG(G)/\textrm{ker} \, \varphi \simeq \varphi(G) = G$ , therefore $<G:\textrm{ker} \, \varphi>$ 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 $F G (G)$ , when it would be enough that it span an appropriated normal subgroup).

Topology/Free group and presentation of a group

From Wikibooks, the open-content textbooks collection

[edit] Free monoid spanned by a set

[edit] Free group spanned by a set

[edit] Presentation of a group

Views

Personal tools

Navigation

Search

community

Print/export

Toolbox