6. 自由群

定义一个群的一种方法是指定一组生成元和生成元所满足的一组关系.

问题: 具有一组生成元但没有关系的群是什么样的? 如果生成元集是 $S$, 这个群称为在 $S$ 上的自由群.

例 6.0.1. $\begin{array}{rl}⟨g⟩=\mathrm{image}(\mathbb{Z}& \to G)\\ n& \mapsto g^n\end{array}$

我们将要推广 $\mathbb{Z}$, 对于 $\mathbb{Z}$ 的类似表述:$$\begin{array}{rcl}\ast & \stackrel{g}{\to }& G\\ & \Downarrow & \\ \mathbb{Z}& ⟶& G\end{array}$$对于任何集合之间的映射$$S\to G,$$我们将产生一个群同态$$F(S)\to G$$其中 $F(S)$ 是在集合 $S$ 上的自由群.

6.1词和字母

定义 6.1.1. 设 $X$ 是一个集合. 一个在 $\mathbf{X}$ 上的词是 $X$ 中元素的有限有序集合. 给定一个词 $w$, 我们称 $w$ 的一个元素为 $w$ 的一个字母.

等价地, 一个词是:

•	属于$$X^n\text{\hspace{1em}对于某个 n⩾0}$$的一个元素.
•	一个序列$$X_1{X}_2\cdots X_{n-1}{X}_n$$其中每个 $X_i\in X$ 且 $n⩾0$.

注 6.1.2. 空词是没有字母的词.

我们令 $\mathrm{Word}(X)$ 表示在 $X$ 上的所有词的集合.

例 6.1.3. 如果 $X=\{a\}$ $$\mathrm{Word}(X)=\{\varnothing ,a,aa,aaa,\dots \}$$如果 $X=\{a,b\}$ $$\mathrm{Word}(X)=\{\varnothing ,a,b,ab,ba,aa,bb,\dots \}$$给定 $X$ 中的两个词, 我们可以将它们连接起来生成一个新词: $$\begin{array}{rl}\mathrm{Word}(X)\times \mathrm{Word}(X)& \to \mathrm{Word}(X)\\ (w_1,w_2)& \mapsto w_1{w}_2\end{array}$$

例 6.1.4. $$\begin{array}{rl}(ba,ab)& \mapsto baab\\ (ab,ba)& \mapsto abba\end{array}$$这显然是结合的, 且空词看起来像是单位元素. 但没有逆元! 让我们修正这一点.

给定一个集合$$S=\{a,b,c\}$$令 $S^{\prime }$ 为如下符号的集合$$S^{\prime }=\{a^{-1},b^{-1},c^{-1},\dots \}$$(因此 $S$ 和 $S^{\prime }$ 是一一对应的.)

我们令$$\begin{array}{rl}\overline{S}& =S\cup S^{\prime }\\ & =\{a,a^{-1},b,b^{-1},\dots \}\end{array}$$

例 6.1.5. 在 $\overline{S}$ 中的一个词可能像$$w=bab{b}^{-1}{a}^{-1}{c}^{-1}ca.$$

6.2词的约化

定义 6.2.1. 在 $\overline{S}$ 中的一个词, 如果对于某个 $a\in S$, 序列$$a{a}^{-1}\text{or}{a}^{-1}a$$出现在该词中, 则称其为未约化词. 如果一个词不是未约化的, 则称其为约化的.

例 6.2.2. $$\begin{array}{rl}aaa{b}^{-1}{a}^{-1}b& \text{是约化的}\\ \begin{array}{r}acbc{b}^{-1}b{c}^{-1}\\ acbcb{b}^{-1}{c}^{-1}\end{array}\}& \text{都是未约化的}\end{array}$$

定义 6.2.3. 如果从 $w$ 中移除 (也称为消去) 一个 $a{a}^{-1}$ 或 $a^{-1}a$ 的出现得到 $w^{\prime }$, 则称 $w^{\prime }$ 是通过消去从 $w$ 得到的. 我们记为 $w⇝w^{\prime }$.

例 6.2.4.  

•	空词是通过消去从 $b^{-1}b$(以及 $b{b}^{-1}$) 得到的.
•	$ab$ 是通过消去从以下得到的$$\begin{array}{r}ab{b}^{-1}b\\ c^{-1}cab\\ ac{c}^{-1}b\end{array}\text{\hspace{1em}可以移除abb−1b或abb−1b}$$

定义 6.2.5. 如果 $w^{\prime }$ 是通过消去从 $w$ 得到的, $$w⇝\cdots ⇝w^{\prime }$$且 $w^{\prime }$ 是约化的, 则称 $w^{\prime }$ 是 $w$ 的一个约简.

命题 6.2.6. 如果 $w^{\prime }$ 和 $w^{\prime \prime }$ 是 $w$ 的约简, 那么$$w^{\prime }=w^{\prime \prime }.$$

证明. 对词 $w$ 的长度 $l$ 进行归纳. (注意 $w⇝u$ $\Rightarrow$ $\mathrm{length}(u)<\mathrm{lenght}(w)$).

$l=0$: 空词是约简的.

$l=1$: 词中只有一个元素, 因此不可能有 $a$ 和 $a^{-1}$ 相邻出现. 所以 $l=1$ 时, 词是约简的.

假设我们已经证明了长度为 $l-1$ 的每个词都有唯一的约简. 证明长度为 $l$ 的词也成立.

如果 $w$ 的长度为 $l$ 且已约简, 完毕.

如果不是, 则某处存在 $a{a}^{-1}$ 或 $a^{-1}a$. 可能有多个!

例如, 我们可以考虑 $w=a^{-1}a{a}^{-1}a{a}^{-1}a$, 长度为 $6$. 选取其中一个. $$\cdots \underline{a^{-1}a}\cdots$$可以通过以下方式得到 $w$ 的一个约简

(i)	在某个步骤消去 $\underline{a^{-1}a}$.
(ii)	从不消去 $\underline{a^{-1}a}$.

(ii) 仅在以下情况下发生In (6.2), cancelling $\underline{a^{-1}a}{a}^{-1}$ byorproduces the same word. Likewise for (6.2). So we can assume $\underline{a^{-1}a}$ is reduced at some point. (Any reduction achieved via (ii) can be achieved via (i).)

So we have a reduction \begin{aligned} w&=\cdots\underline{aa^{-1}}\cdots\underbrace{b^{-1}b}\cdots c^{-1}c\\ &\mathrel{\rotatebox[origin=c]{-90}{$\rightsquigarrow$}}\quad\text{Step one}\\ w_{1}&=\cdots\underline{aa^{-1}}\cdots\cdots\cdots\underbrace{c^{-1}c}\\ &\mathrel{\rotatebox[origin=c]{-90}{$\rightsquigarrow$}}\\ &~\vdots\\ &\mathrel{\rotatebox[origin=c]{-90}{$\rightsquigarrow$}}\quad\text{Step}~n\\ w_{n}&~\text{reduced} \end{aligned}Well, we get the same reduction if we cancel $a{a}^{-1}$ in step $1$, or in other step.

$\square$

6.3Definition of Free Groups

定义 6.3.1. Let $S$ be a set. Then the free group $F(S)$ on $S$ is $$(F(S),m)$$where

•	$F(S)$ is the set of reduced words in $\overline{S}=S\cup S^{\prime }$, where $S^{\prime }:=\{w^{-1}\mid w\in S\}$.
•	$m:F(S)\times F(S)\to F(S)$ sends $(w_1,w_2)$ to the reduction of $w_1{w}_2$.

例 6.3.2. Consider a set with one element $S=\{a\}$. A word in $\overline{S}$ looks like $$aaa{a}^{-1}a{a}^{-1}aa{a}^{-1}a$$If a word is reduced, it looks like $$\underset{n\text{times}}{\underbrace{aaaaa\cdots a}}$$or $$\underset{n\text{times}}{\underbrace{a^{-1}{a}^{-1}\cdots a^{-1}}}$$So $$\begin{array}{rl}\mathbb{Z}& \to F(S)\\ n& \mapsto \{\begin{array}{ll}\underset{n\text{times}}{\underbrace{a\cdots a}}& n>0\\ \underset{n\text{times}}{\underbrace{a^{-1}\cdots a^{-1}}}& n<0\\ \varnothing & n=0\end{array}\end{array}$$is a bijection. It is an isomorphism.

例 6.3.3. Consider a set with two elements $S=\{a,b\}$. $F(S)$ is free group on two generators. The elements look like $$\begin{array}{ll}l=0& \varnothing =:1\\ l=1& a,b,a^{-1},b^{-1}\\ l=2& aa,bb,ba,ab,a^{-1}{a}^{-1},b^{-1}{b}^{-1},a^{-1}{b}^{-1},b^{-1}{a}^{-1}\end{array}$$

命题 6.3.4. The inverse to $S_1\cdots S_n$ is $S_n^{-1}\cdots S_1^{-1}$.

证明. The inverse to $S_1\cdots S_n$ is $S_n^{-1}\cdots S_1^{-1}$, since \begin{array}{c} (S_{1}\cdots S_{n})(S_{n}^{-1}\cdots S_{1}^{-1})\\ \mathrel{\rotatebox[origin=c]{-90}{$\rightsquigarrow$}}\\ S_{1}\cdots S_{n-1}S_{n-1}^{-1}\cdots S_{1}^{-1}\\ \mathrel{\rotatebox[origin=c]{-90}{$\rightsquigarrow$}}\\ S_{1}\cdots S_{n-2}S_{n-2}^{-1}\cdots S_{1}^{-1}\\ \mathrel{\rotatebox[origin=c]{-90}{$\rightsquigarrow$}}\\ \vdots\\ \mathrel{\rotatebox[origin=c]{-90}{$\rightsquigarrow$}}\\ S_{1}S_{1}^{-1}\\ \mathrel{\rotatebox[origin=c]{-90}{$\rightsquigarrow$}}\\ \varnothing \end{array}

$\square$

6.4Equivalence Relations

定义 6.4.1. Let $X$ be a set. An equivalence relation on $X$ is a subset $$R\subset X\times X$$satisfying:

(1)	$(x,x)\in R$, $\forall x\in X$.
(2)	$(x,y)\in R$ $\Rightarrow$ $(y,x)\in R$.
(3)	$(x,y)\in R$ and $(y,z)\in R$ $\Rightarrow$ $(x,z)\in R$.

We will say $x\sim y$ if $(x,y)\in R$.

例 6.4.2. Let $G$ act on a set $X$. Say $x\sim y$ $\iff$ $y=gx$ for some $g\in G$. This is an equivalence relation, since

(1)	$x=1_{G}x$, so $x\sim x$.
(2)	$x\sim y$ $\Rightarrow$ $y=gx$ $\Rightarrow$ $x=g^{-1}y$ $\Rightarrow$ $y\sim x$ for some $g$.
(3)	$y\sim z$ $\Rightarrow$ $z=g^{\prime }z$ $\Rightarrow$ $z=g^{\prime }gy$ $\Rightarrow$ $z\sim x$.

Then $\forall x$, ${\mathcal{O}}_x$ is just the equivalence class of $x$. (i.e. ${\mathcal{O}}_x=\{y\mid y\sim x\}$.) And $X/G$ is the set of equivalence class.

Here is another example.

例 6.4.3. Let $S$ be a set and set $$\begin{array}{rl}{S}^{\prime }& =\{x^{-1}{\}}_{x\in S}\\ \overline{S}& =S\cup S^{\prime }\end{array}$$

6.5Existence of Unique Reduction

定理 6.5.1. Every $w\in \mathrm{Word}(\overline{S})$ has a unique reduction.

证明. Induction on length $l$.

$l=0$ obvious.

$l=1$ obvious.

Assume that $\forall w^{\prime }$ with length $⩽l-1$, the set $$\{\text{reduction of}{w}^{\prime }\}$$has only one element. We must prove this is true $\forall$ words $w$ of length $l$.

•	If $w$ is already reduced, then no other word can be obtained from $w$ by cancelling. Hence $$\{\text{reduction of}w\}\text{has only one element——}w\text{itself.}$$
•	Otherwise, $\exists$ an appearence of $$a{a}^{-1}\text{or}{a}^{-1}a$$somewhere in $w$.

Let’s fix a single such appearence, $$w=\cdots \underline{a{a}^{-1}}\cdots$$which we’ve underlined.

Let’s consider: $\text{ding}182$ is an equality, since if $\underline{a{a}^{-1}}$ is cancelled in step $N$, you’d get same reduction by first having cancelled $\underline{a{a}^{-1}}$, then performing step $1$ through $N-1$.

$\text{ding}183$ is either an equality or the set is empty, since NOT cancelling $\underline{a{a}^{-1}}$ means you had to cancel like $a^{-1}\cancel{a{a}^{-1}}$ or like $\cancel{a{a}^{-1}}a$ at some stage. $$\begin{array}{ll}\text{But}& \cdots a^{-1}\cancel{a{a}^{-1}}\cdots =\cdots \cancel{a^{-1}a}{a}^{-1}\cdots \\ \text{And}& \cdots \cancel{a{a}^{-1}}a\cdots =\cdots a\cancel{a^{-1}a}\cdots \end{array}$$

$\text{ding}182$ and $\text{ding}183$ tell us that every reduction of $w$ can be obtained by first cancelling $\underline{a{a}^{-1}}$. $$w^{\prime }=\cdots \underline{a{a}^{-1}}\cdots$$is a word of length $<l$!

Moreover, any reduction of $w$ obtained by first cancelling $\underline{a{a}^{-1}}$ is a reduction of $w^{\prime }$.

Hence $$\left\{\begin{array}{r}\text{reduction of}w\text{obtained}\\ \text{by first cancelling}\underline{a{a}^{-1}}\end{array}\right\}=\{\text{reduction of}{w}^{\prime }\}=\text{a set with one element.}$$

$\square$

例 6.5.2. If $S=\varnothing$, $\mathrm{Word}(S)$ is a set with one element——the empty word, i.e. the word of length zero.

例 6.5.3. If $S=\varnothing$, $\mathrm{Free}(S)=\{\text{reduced words in}\overline{S}=\varnothing \}=$the set containing the empty word. So $\mathrm{Free}(S)$ is a group with one element when $S=\varnothing$!

6.6Application of Free Groups

命题 6.6.1. Given a group $G$. Let $j:S\to G$ be a map of sets. It extends to a group homomorphism $F(S)\to G$.

证明. Let $s\in S$ be an element of the set, and $j(s)\in G$ its image in $G$. Let us denote by $\bar{j}:\overline{S}\to G$ the function sending $s\mapsto j(s)$ and $s^{-1}\mapsto j(s{)}^{-1}$. We then define a function$${\varphi }_j:\mathrm{Word}(\overline{S})\to G$$by sending any word $W=s_1\dots s_l$, with $s_i\in \overline{S}$, to the element$${\varphi }_j\left(s_1\right)\cdot {\varphi }_j\left(s_2\right)\cdot \cdots \cdot {\varphi }_j\left(s_l\right)$$We must prove this is well-defined on $F(S)$, and a homomorphism. Well, if $w$ is a reduction of $W$, it is obtained by canceling pairs of letters appearing next to their inverses. On the other hand, if any letter $s$ appears next to its inverse $s^{-1}$ inside $W$, the above string of multiplications in $G$ will also see an appearance of ${\varphi }_j(s)$ appearing next to ${\varphi }_j\left(s^{-1}\right)={\varphi }_j(s{)}^{-1}$. Hence if we cancel two inverse letters in the word $W$ to obtain a new word $w^{\prime }$, we see that ${\varphi }_j(W)={\varphi }_j\left(w^{\prime }\right)$. More explicitly, given a product of many elements in $G$, omitting an appearance of ${\varphi }_j(s){\varphi }_j(s{)}^{-1}$ (or of ${\varphi }_j(s{)}^{-1}{\varphi }_j(s))$ does not change the value of the multiplication:$$\begin{array}{rl}{\varphi }_j\left(s_1\right)\cdot \cdots \cdot {\varphi }_j(s){\varphi }_j(s{)}^{-1}\cdot \cdots \cdot {\varphi }_j\left(s_l\right)& ={\varphi }_j\left(s_1\right)\cdot \cdots \cdot 1_G\cdot \cdots \cdot {\varphi }_j\left(s_l\right)\\ & ={\varphi }_j\left(s_1\right)\cdot \cdots \cdot {\varphi }_j\left(s_l\right)\end{array}$$(and likewise for canceling the appearance of ${\varphi }_j(s{)}^{-1}{\varphi }_j(s)$). So if the words $w_i^{\prime }$ for $i=1,\dots ,I$ are the words one passes through on reducing $W$ to its reduction $w$, we have a string of equalities:$${\varphi }_j(W)={\varphi }_j\left(w_1^{\prime }\right)=\cdots ={\varphi }_j\left(w_I^{\prime }\right)={\varphi }_j(w).$$This shows that ${\varphi }_j$ is well-defined on $F(S)$. To show that ${\varphi }_j$ defines a homomorphism, let $W=w^{\prime }\cdot w^{\prime \prime }$ be a concatenation of words, and let $w$ be its reduction. We must prove that$${\varphi }_j(w)={\varphi }_j\left(w^{\prime }\right)\cdot {\varphi }_j\left(w^{\prime \prime }\right).$$By well-definedness, it suffices to show ${\varphi }_j(W)={\varphi }_j\left(w^{\prime }\right)\cdot {\varphi }_j\left(w^{\prime \prime }\right)$. This is obvious, since if$$w^{\prime }=s_1^{\prime }\cdots s_{l^{\prime }}^{\prime },w^{\prime \prime }=s_1^{\prime \prime }\cdots s_{l^{\prime \prime }}^{\prime \prime }$$then$$\begin{array}{rl}{\varphi }_j(W)& ={\varphi }_j\left(s_1^{\prime }\right)\cdot \cdots \cdot {\varphi }_j\left(s_{l^{\prime }}^{\prime }\right)\cdot {\varphi }_j\left(s_1^{\prime \prime }\right)\cdot \cdots \cdot {\varphi }_j\left(s_{l^{\prime \prime }}^{\prime \prime }\right)\\ & =\left({\varphi }_j\left(s_1^{\prime }\right)\cdot \cdots \cdot {\varphi }_j\left(s_{l^{\prime }}^{\prime }\right)\right)\cdot \left({\varphi }_j\left(s_1^{\prime \prime }\right)\cdot \cdots \cdot {\varphi }_j\left(s_{l^{\prime \prime }}^{\prime \prime }\right)\right)\\ & ={\varphi }_j\left(w^{\prime }\right)\cdot {\varphi }_j\left(w^{\prime \prime }\right)\end{array}$$

$\square$

命题 6.6.2. There is a bijection of sets$$\{\text{Group homomorphisms}F(S)\to G\}\cong \{\text{Set maps}S\to G\}.$$

证明. We above define a homomorphism ${\varphi }_j:F(S)\to G$ for any function $j:S\to G$. This defines a function$$\Phi :\{\text{Set maps}S\to G\}\to \{\text{Group homomorphisms}F(S)\to G\}$$given by $j\mapsto {\varphi }_j$. We define an inverse map $\Psi$ as follows: If $\varphi$ is a group homomorphism, it assigns a value to the reduced word $s$, for any $s\in S$. So we define $\Psi (\varphi ):={\psi }_{\varphi }$ to be the function sending $s$ to $\varphi (s)$. We must show that $\Psi \circ \Phi$ and $\Phi \circ \Psi$ are the identities. Well, given a homomorphism $\varphi :F(S)\to G$, let $w$ be the word$$w=s_1\dots s_l$$where the $s_i$ are whatever letters of $\overline{S}$ are in $w$. we know that$$\varphi (w)=\varphi \left(s_1\cdot \cdots \cdot s_l\right)=\varphi \left(s_1\right)\cdot \cdots \cdot \varphi \left(s_l\right)$$by the group homomorphism property, and the fact that every word is a product of one-letter words. So the value of $\varphi$ on one-letters words——i.e., its value on $S$——determines its value on all elements of $F(S)$. This shows that $\Phi \circ \Psi$ is the identity. On the other hand, we have defined $\Phi$ so that $\Phi (j)={\varphi }_j$ simply sends one-letter words to the value $j(s)$. Hence $\Psi \circ \Phi$ is also the identity.

$\square$

例 6.6.3. Let $S$ be a set and $G$ a group. For all functions $$S\to G$$$\exists$ a group homomorphism $$F(S)\to G$$When $S=\varnothing$, $\exists !$ function $$\varphi \to G$$What group homomorphism is $$F(\varphi )\to G?$$It sends the empty word to $1_G$.

命题 6.6.4. If $w_1$ and $w_2$ have the same reduction, then $w_1\sim w_2$ is an equivalence relation.

证明. $w_1\sim w_2$ is an equivalence relation, since

(1)	$w\sim w$ obviously: $\mathrm{reduction}(w)=\mathrm{reduction}(w)$.
(2)	$w_1\sim w_2$ $\Rightarrow$ $w_2\sim w_1$ obviously, since $$\begin{array}{rl}& \mathrm{reduction}(w_1)=\mathrm{reduction}(w_2)\\ \Rightarrow & \mathrm{reduction}(w_2)=\mathrm{reduction}(w_1).\end{array}$$
(3)	$w_1\sim w_2$, $w_2\sim w_3$ $\Rightarrow$ $w_1\sim w_3$ since $$\begin{array}{r}\mathrm{reduction}(w_1)=\mathrm{reduction}(w_2)\\ \mathrm{reduction}(w_2)=\mathrm{reduction}(w_3)\end{array}\Rightarrow \mathrm{reduction}(w_1)=\mathrm{reduction}(w_3)$$

(All follows from uniqueness of reduction and the fact that equality is an equivalence relation.)

$\square$

注 6.6.5. So if $w_1⇝w_2$ via cancellation, then $w_1\sim w_2$. (Not necessary conversely.)

命题 6.6.6. Let $F(S)$ be reduced words in $\overline{S}$. $\exists$ bijection $$F(S)\to \{\text{equivalence classes of words in}\mathrm{Word}(\overline{S})\}.$$

证明. Send $w\mapsto [w]$, i.e. send $w$ to its equivalence class.
Any equivalence class has a unique element of shortest length——the (common) reduction of any $w^{\prime }\in [w]$. This defines inverse map.

$\square$

命题 6.6.7. The operation $$\begin{array}{rl}\{\text{equiv class of words}\}\times \{\text{equiv class of words}\}& \stackrel{\text{concatenate}}{\to }\{\text{equiv class of words}\}\\ ([w_1],[w_2])& ⟼[w_1{w}_2]\end{array}$$is well-defined.

证明. Let $r_1$ and $r_2$ be reduction of $w_1^{\prime }$, $w_2^{\prime }$ respectively. Then note $$r_1{r}_2\text{can be obtained from}{w}_1^{\prime }{w}_2^{\prime }\text{via cancellations}.$$(Just apply cancellations to the $w_1^{\prime }$ part of the word, then to the $w_2^{\prime }$ part of the word.)

Hence for any $$w_1^{\prime }\in [w_1],w_2^{\prime }\in [w_2],$$we have $$w_1^{\prime }{w}_2^{\prime }\sim r_1{r}_2$$i.e. $$[w_1^{\prime }{w}_2^{\prime }]=[r_1{r}_2]$$So regardless of which representatives $w_1^{\prime }\in [w_1]$, $w_2^{\prime }\in [w_2]$ we choose, the equivalence class of $w_1^{\prime }{w}_2^{\prime }$ is unchanged.

$\square$

推论 6.6.8. The free group operation $$\begin{array}{rl}F(S)\times F(S)& \to F(S)\\ (r_1,r_2)& \mapsto \mathrm{reduction}(r_1{r}_2)\end{array}$$is associative.

证明.  

So we just need to show the operation $([r_1],[r_2])\mapsto [r_1{r}_2]$ is associative. Well,$$([r_1][r_2])[r_3]=[r_1{r}_2][r_3]=[(r_1{r}_2)r_3]=[r_1(r_2{r}_3)]=[r_1][r_2{r}_3]=[r_1]([r_2][r_3])$$where the third equality comes from the associativity of concatenating ordinary words.

$\square$