Topology/Free group and presentation of a group

From Wikibooks, open books for an open world
< Topology
Jump to: navigation, search

Free monoid spanned by a set[edit]

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[edit]

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 = [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.

  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 [1]_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 [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 [\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 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[edit]

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 < 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:{\emptyset}> 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 <x:\emptyset>. Another presentation of (\mathbb{Z},+) is <\{x,y\}:\{xy^{-1}\}>, more commonly denoted by <x,y:xy^{-1}>. Informally, in the presentation <x,y:xy^{-1}> 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 <x:\emptyset>.
  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 = \{\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>.
  3. Let X = \{x,y\} (with x and y distinct) and R = \{xyx^{-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, 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 <x,y : xyx^{-1}y^{-1}>.
  4. Let X = \{x,y\} and R = \{xyx^{-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\}:\{xyx^{-1}y^{-1},x^m,y^n\}> by <x,y:xyx^{-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 achived, 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 = (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. <G:\textrm{ker} \, \varphi> 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 [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.
  2. 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 FG(G), when it would be enough that it span an appropriated normal subgroup).