§ 6 自由群
定义一个群的一种方法是指定一组生成元(generator) 和生成元所满足的一组关系(relation) 。
问题 ：具有一组生成元但没有关系的群是什么样的？如果生成元集是S S S S S S
例 6.1 ⟨ g ⟩ = i m a g e ( Z → G ) n ↦ g n \begin{aligned}
\textbf{例 6.1}~\langle g\rangle=\mathrm{image}(\mathbb{Z}&\to G)\\
n&\mapsto g^{n}
\end{aligned} 例 6.1 ⟨ g ⟩ = image ( Z n → G ) ↦ g n
我们将要推广Z \mathbb{Z} Z Z \mathbb{Z} Z
∗ → g G ⇓ Z ⟶ G \begin{array}{rcl}
*&\xrightarrow{~g~}&G\\
&\Downarrow&\\
\mathbb{Z}&\longrightarrow&G
\end{array} ∗ Z g ⇓ ⟶ G G 对于任何集合之间的映射
我们将产生一个群同态
其中F ( S ) F(S) F ( S ) S S S
§ 6.1 词和字母
定义 6.1 设X X X 在X X X X X X 是X X X w w w w w w w w w 字母(letter) 。
等价地，一个词是：
X n 对于某个 n ⩾ 0 X^{n}\tag*{对于某个 $n\geqslant 0$} X n 对于某个 n ⩾ 0 的一个元素。
X 1 X 2 ⋯ X n − 1 X n X_{1}X_{2}\cdots X_{n-1}X_{n} X 1 X 2 ⋯ X n − 1 X n 其中每个X i ∈ X X_{i}\in X X i ∈ X n ⩾ 0 n\geqslant 0 n ⩾ 0
注 空词是没有字母的词。
我们令 W o r d ( X ) \mathrm{Word}(X) Word ( X ) X X X
例 6.2 如果 X = { a } X=\{a\} X = { a }
W o r d ( X ) = { ∅ , a , a a , a a a , … } \mathrm{Word}(X)=\{\varnothing,a,aa,aaa,\ldots\} Word ( X ) = { ∅ , a , aa , aaa , … } 如果 X = { a , b } X=\{a,b\} X = { a , b }
W o r d ( X ) = { ∅ , a , b , a b , b a , a a , b b , … } \mathrm{Word}(X)=\{\varnothing,a,b,ab,ba,aa,bb,\ldots\} Word ( X ) = { ∅ , a , b , ab , ba , aa , bb , … } 给定X X X
W o r d ( X ) × W o r d ( X ) → W o r d ( X ) ( w 1 , w 2 ) ↦ w 1 w 2 \begin{aligned}
\mathrm{Word}(X)\times\mathrm{Word}(X)&\to \mathrm{Word}(X)\\
(w_{1},w_{2})&\mapsto w_{1}w_{2}
\end{aligned} Word ( X ) × Word ( X ) ( w 1 , w 2 ) → Word ( X ) ↦ w 1 w 2 例 6.3
( b a , a b ) ↦ b a a b ( a b , b a ) ↦ a b b a \begin{aligned}
(ba,ab)&\mapsto baab\\
(ab,ba)&\mapsto abba
\end{aligned} ( ba , ab ) ( ab , ba ) ↦ baab ↦ abba 这显然是结合的，且空词看起来像是单位元素。但没有逆元！让我们修正这一点。
给定一个集合
S = { a , b , c } S=\{a,b,c\} S = { a , b , c } 令S ′ S^{\prime} S ′
S ′ = { a − 1 , b − 1 , c − 1 , … } S^{\prime}=\{a^{-1},b^{-1},c^{-1},\ldots\} S ′ = { a − 1 , b − 1 , c − 1 , … } （因此S S S S ′ S^{\prime} S ′
我们令
S ‾ = S ∪ S ′ = { a , a − 1 , b , b − 1 , … } \begin{aligned}
\overline{S}&=S\cup S^{\prime}\\
&=\{a,a^{-1},b,b^{-1},\ldots\}
\end{aligned} S = S ∪ S ′ = { a , a − 1 , b , b − 1 , … } 例 6.4 在 S ‾ \overline{S} S
w = b a b b − 1 a − 1 c − 1 c a . w=babb^{-1}a^{-1}c^{-1}ca. w = bab b − 1 a − 1 c − 1 c a . § 6.2 词的约化
定义 6.2 在S ‾ \overline{S} S a ∈ S a\in S a ∈ S
a a − 1 或 a − 1 a aa^{-1}~\text{或}~a^{-1}a a a − 1 或 a − 1 a 出现在该词中，则称其为未约化(unreduced) 词。如果一个词不是未约化的，则称其为约化(reduced) 的。
例 6.5
a a a b − 1 a − 1 b 是约化的 a c b c b − 1 b c − 1 a c b c b b − 1 c − 1 } 都是未约化的 \begin{aligned}
aaab^{-1}a^{-1}b~&\text{是约化的}\\
\left.\begin{aligned}
acbcb^{-1}bc^{-1}\\
acbcbb^{-1}c^{-1}
\end{aligned}\right\}&\text{都是未约化的}
\end{aligned} aaa b − 1 a − 1 b a c b c b − 1 b c − 1 a c b c b b − 1 c − 1 } 是约化的 都是未约化的 定义 6.3 如果从w w w a a − 1 aa^{-1} a a − 1 a − 1 a a^{-1}a a − 1 a w ′ w^{\prime} w ′ w ′ w^{\prime} w ′ w w w w ⇝ w ′ w\rightsquigarrow w^{\prime} w ⇝ w ′
例 6.6
空词是通过消去从b − 1 b b^{-1}b b − 1 b b b − 1 bb^{-1} b b − 1
a b ab ab
a b b − 1 b c − 1 c a b a c c − 1 b \begin{align*}
abb^{-1}b\tag*{可以移除$a\underline{bb^{-1}}b$或$ab\underline{b^{-1}b}$}\\
c^{-1}cab\\
acc^{-1}b
\end{align*} ab b − 1 b c − 1 c ab a c c − 1 b 可以移除 a b b − 1 b 或 ab b − 1 b 定义 6.4 如果w ′ w^{\prime} w ′ w w w
w ⇝ ⋯ ⇝ w ′ w\rightsquigarrow\cdots\rightsquigarrow w^{\prime} w ⇝ ⋯ ⇝ w ′ 且w ′ w^{\prime} w ′ w ′ w^{\prime} w ′ w w w 约简(reduction) 。
命题 6.1 如果w ′ w^{\prime} w ′ w ′ ′ w^{\prime\prime} w ′′ w w w
w ′ = w ′ ′ . w^{\prime}=w^{\prime\prime}. w ′ = w ′′ . 证明：对词w w w l l l w ⇝ u w\rightsquigarrow u w ⇝ u ⇒ \Rightarrow ⇒ l e n g t h ( u ) < l e n g t h ( w ) \mathrm{length}(u)<\mathrm{length}(w) length ( u ) < length ( w )
当l = 0 l=0 l = 0
当l = 1 l=1 l = 1 a a a a − 1 a^{-1} a − 1 l = 1 l=1 l = 1
假设我们已经证明了长度为l − 1 l-1 l − 1 l l l
如果w w w l l l
如果不是，则某处存在a a − 1 aa^{-1} a a − 1 a − 1 a a^{-1}a a − 1 a
例如，我们可以考虑w = a − 1 a a − 1 a a − 1 a w=a^{-1}aa^{-1}aa^{-1}a w = a − 1 a a − 1 a a − 1 a 6 6 6
⋯ a − 1 a ‾ ⋯ \cdots \underline{a^{-1}a}\cdots ⋯ a − 1 a ⋯ 可以通过以下方式得到w w w
(i) 在某个步骤消去 a − 1 a ‾ \underline{a^{-1}a} a − 1 a
(ii) 从不消去 a − 1 a ‾ \underline{a^{-1}a} a − 1 a
(ii) 仅在以下情况下发生
在(6.1)中, 通过a − 1 a ‾ a − 1 \underline{a^{-1}a}a^{-1} a − 1 a a − 1 a − 1 a ‾ \underline{a^{-1}a} a − 1 a
因此，我们有一个约简
w = ⋯ a a − 1 ‾ ⋯ b − 1 b ⏟ ⋯ c − 1 c w = \cdots \underline{aa^{-1}} \cdots \underbrace{b^{-1}b} \cdots c^{-1}c w = ⋯ a a − 1 ⋯ b − 1 b ⋯ c − 1 c ~~~~~~~~~ ⇝ \rightsquigarrow ⇝ 第1步
w 1 = ⋯ a a − 1 ‾ ⋯ ⋯ ⋯ c − 1 c ⏟ w_{1}= \cdots \underline{aa^{-1}} \cdots \cdots \cdots \underbrace{c^{-1}c} w 1 = ⋯ a a − 1 ⋯⋯⋯ c − 1 c ⇝ \rightsquigarrow ⇝
~~~~~~~~~ ⇝ \rightsquigarrow ⇝ 第n步
w n 约简 w_{n}~\text{约简} w n 约简 好吧，无论我们在第 1 步还是其他步骤消去 a a − 1 aa^{-1} a a − 1
§ 6.3 自由群的定义
定义 6.5 设S S S S S S 自由群 (free group) F ( S ) F(S) F ( S )
其中
F ( S ) F(S) F ( S ) S ‾ = S ∪ S ′ \overline{S}=S\cup S^{\prime} S = S ∪ S ′ S ′ : = { w − 1 ∣ w ∈ S } S^{\prime}:=\{w^{-1}\mid w\in S\} S ′ := { w − 1 ∣ w ∈ S } m : F ( S ) × F ( S ) → F ( S ) m:F(S)\times F(S)\to F(S) m : F ( S ) × F ( S ) → F ( S ) ( w 1 , w 2 ) (w_{1},w_{2}) ( w 1 , w 2 ) w 1 w 2 w_{1}w_{2} w 1 w 2
例 6.7 考虑一个只有一个元素的集合S = { a } S=\{a\} S = { a } S ‾ \overline{S} S
a a a a − 1 a a − 1 a a a − 1 a aaaa^{-1}aa^{-1}aaa^{-1}a aaa a − 1 a a − 1 aa a − 1 a 如果一个词是约简的，它看起来像
a a a a a ⋯ a ⏟ n 次 \underbrace{aaaaa\cdots a}_{n~\text{次}} n 次 aaaaa ⋯ a 或
a − 1 a − 1 ⋯ a − 1 ⏟ n 次 \underbrace{a^{-1}a^{-1}\cdots a^{-1}}_{n~\text{次}} n 次 a − 1 a − 1 ⋯ a − 1 因此
Z → F ( S ) n ↦ { a ⋯ a ⏟ n 次 n > 0 a − 1 ⋯ a − 1 ⏟ n 次 n < 0 ∅ n = 0 \begin{aligned}
\mathbb{Z}&\to F(S)\\
n&\mapsto\begin{cases}
\underbrace{a\cdots a}_{n~\text{次}}& n>0\\
\underbrace{a^{-1}\cdots a^{-1}}_{n~\text{次}}& n<0\\
\varnothing& n=0
\end{cases}
\end{aligned} Z n → F ( S ) ↦ ⎩ ⎨ ⎧ n 次 a ⋯ a n 次 a − 1 ⋯ a − 1 ∅ n > 0 n < 0 n = 0 是一个双射。它是一个同构。
例 6.8 考虑一个有两个元素的集合S = { a , b } S=\{a,b\} S = { a , b } F ( S ) F(S) F ( S )
l = 0 ∅ = : 1 l = 1 a , b , a − 1 , b − 1 l = 2 a a , b b , b a , a b , a − 1 a − 1 , b − 1 b − 1 , a − 1 b − 1 , b − 1 a − 1 \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} l = 0 l = 1 l = 2 ∅ =: 1 a , b , a − 1 , b − 1 aa , bb , ba , ab , a − 1 a − 1 , b − 1 b − 1 , a − 1 b − 1 , b − 1 a − 1 命题 6.2 S 1 ⋯ S n S_{1}\cdots S_{n} S 1 ⋯ S n S n − 1 ⋯ S 1 − 1 S_{n}^{-1}\cdots S_{1}^{-1} S n − 1 ⋯ S 1 − 1 S 1 ⋯ S n S_{1}\cdots S_{n} S 1 ⋯ S n S n − 1 ⋯ S 1 − 1 S_{n}^{-1}\cdots S_{1}^{-1} S n − 1 ⋯ S 1 − 1
( S 1 ⋯ S n ) ( S n − 1 ⋯ S 1 − 1 ) (S_{1}\cdots S_{n})(S_{n}^{-1}\cdots S_{1}^{-1}) ( S 1 ⋯ S n ) ( S n − 1 ⋯ S 1 − 1 ) ⇝ \rightsquigarrow ⇝
S 1 ⋯ S n − 1 S n − 1 − 1 ⋯ S 1 − 1 S_{1}\cdots S_{n-1}S_{n-1}^{-1}\cdots S_{1}^{-1} S 1 ⋯ S n − 1 S n − 1 − 1 ⋯ S 1 − 1 ⇝ \rightsquigarrow ⇝
S 1 ⋯ S n − 2 S n − 2 − 1 ⋯ S 1 − 1 S_{1}\cdots S_{n-2}S_{n-2}^{-1}\cdots S_{1}^{-1} S 1 ⋯ S n − 2 S n − 2 − 1 ⋯ S 1 − 1 ⇝ \rightsquigarrow ⇝
⇝ \rightsquigarrow ⇝
S 1 S 1 − 1 S_{1}S_{1}^{-1} S 1 S 1 − 1 ⇝ \rightsquigarrow ⇝
§ 6.4 等价关系
定义 6.6 设 X X X X X X 等价关系(equivalence relation) 是 X × X X\times X X × X
R ⊂ X × X R\subset X\times X R ⊂ X × X 满足：
(1) 对于所有 x ∈ X x\in X x ∈ X ( x , x ) ∈ R (x,x)\in R ( x , x ) ∈ R
(2) 如果 ( x , y ) ∈ R (x,y)\in R ( x , y ) ∈ R ( y , x ) ∈ R (y,x)\in R ( y , x ) ∈ R
(3) 如果 ( x , y ) ∈ R (x,y)\in R ( x , y ) ∈ R ( y , z ) ∈ R (y,z)\in R ( y , z ) ∈ R ( x , z ) ∈ R (x,z)\in R ( x , z ) ∈ R
我们记x ∼ y x\sim y x ∼ y ( x , y ) ∈ R (x,y)\in R ( x , y ) ∈ R
例 6.9 设 G G G X X X x ∼ y x\sim y x ∼ y y = g x y=gx y = gx g ∈ G g\in G g ∈ G
(1) x = 1 G x x=1_{G}x x = 1 G x x ∼ x x\sim x x ∼ x
(2) x ∼ y x\sim y x ∼ y ⇒ \Rightarrow ⇒ y = g x y=gx y = gx ⇒ \Rightarrow ⇒ x = g − 1 y x=g^{-1}y x = g − 1 y ⇒ \Rightarrow ⇒ y ∼ x y\sim x y ∼ x g g g
(3) y ∼ z y\sim z y ∼ z ⇒ \Rightarrow ⇒ z = g ′ y z=g^{\prime}y z = g ′ y z = g ′ g y z=g^{\prime}gy z = g ′ g y z ∼ x z\sim x z ∼ x
那么对于所有 x x x O x \mathcal{O}_{x} O x x x x O x = { y ∣ y ∼ x } \mathcal{O}_{x}=\{y\mid y\sim x\} O x = { y ∣ y ∼ x } X / G X/G X / G
这里有另一个例子。
例 6.10 设 S S S
S ′ = { x − 1 } x ∈ S S ‾ = S ∪ S ′ \begin{aligned}
S^{\prime}&=\{x^{-1}\}_{x\in S}\\
\overline{S}&=S\cup S^{\prime}
\end{aligned} S ′ S = { x − 1 } x ∈ S = S ∪ S ′ § 6.5 唯一约简的存在性
定理 6.3 每个 w ∈ W o r d ( S ‾ ) w\in \mathrm{Word}(\overline{S}) w ∈ Word ( S )
证明：对长度 l l l
l = 0 l=0 l = 0
l = 1 l=1 l = 1
假设对于长度 ⩽ l − 1 \leqslant l-1 ⩽ l − 1 w ′ w^{\prime} w ′
{ w ′ 的约简 } \{\text{$w^{\prime}$ 的约简}\} { w ′ 的约简 } 只有一个元素。我们必须证明对于长度为 l l l w w w
如果 w w w w w w
{ w 的约简 } 只有一个元素—— w 本身。 \{\text{$w$ 的约简}\}~\text{只有一个元素——}w~\text{本身。} { w 的约简 } 只有一个元素 —— w 本身。 a a − 1 或 a − 1 a aa^{-1}\quad \text{或}\quad a^{-1}a a a − 1 或 a − 1 a 的出现。
让我们固定这样一个出现，
w = ⋯ a a − 1 ‾ ⋯ w=\cdots\underline{aa^{-1}}\cdots w = ⋯ a a − 1 ⋯ 我们已将其下划线标记。
让我们考虑：
1 ◯ \textcircled{\small 1} 1 ◯ a a − 1 ‾ \underline{aa^{-1}} a a − 1 N N N a a − 1 ‾ \underline{aa^{-1}} a a − 1 1 1 1 N − 1 N-1 N − 1
2 ◯ \textcircled{\small 2} 2 ◯ a a − 1 ‾ \underline{aa^{-1}} a a − 1
1 ◯ \textcircled{\small 1} 1 ◯ 2 ◯ \textcircled{\small 2} 2 ◯ w w w a a − 1 ‾ \underline{aa^{-1}} a a − 1
w ′ = ⋯ a a − 1 ‾ ⋯ w^{\prime}=\cdots\underline{aa^{-1}}\cdots w ′ = ⋯ a a − 1 ⋯ 是一个长度小于 l l l
此外，通过首先消去 a a − 1 ‾ \underline{aa^{-1}} a a − 1 w w w w ′ w^{\prime} w ′
因此
{ 通过首先消去 a a − 1 ‾ 得到的 w 的约简 } = { w ′ 的约简 } = 一个只有一个元素的集合。 \left\{
\begin{aligned}
\text{通过首先消去}~\underline{aa^{-1}}\\
\text{得到的}~w~\text{的约简}
\end{aligned}
\right\}=\{\text{$w^{\prime}$ 的约简}\}=\text{一个只有一个元素的集合。} { 通过首先消去 a a − 1 得到的 w 的约简 } = { w ′ 的约简 } = 一个只有一个元素的集合。 例 6.11 如果 S = ∅ S=\varnothing S = ∅ W o r d ( S ) \mathrm{Word}(S) Word ( S )
例 6.12 如果 S = ∅ S=\varnothing S = ∅ F r e e ( S ) = { 在 S ‾ = ∅ 中的约简词 } \mathrm{Free}(S)=\{\text{在}~\overline{S}=\varnothing~\text{中的约简词}\} Free ( S ) = { 在 S = ∅ 中的约简词 } S = ∅ S=\varnothing S = ∅ F r e e ( S ) \mathrm{Free}(S) Free ( S )
§ 6.6 自由群的应用
命题 6.4 给定一个群 G G G j : S → G j:S\to G j : S → G F ( S ) → G F(S)\to G F ( S ) → G
证明：设 s ∈ S s \in S s ∈ S j ( s ) ∈ G j(s) \in G j ( s ) ∈ G G G G j ˉ : S ‾ → G \bar{j}: \overline{S} \rightarrow G j ˉ : S → G s ↦ j ( s ) s \mapsto j(s) s ↦ j ( s ) s − 1 ↦ j ( s ) − 1 s^{-1} \mapsto j(s)^{-1} s − 1 ↦ j ( s ) − 1
ϕ j : Word ( S ‾ ) → G \phi_j: \operatorname{Word}(\overline{S}) \rightarrow G ϕ j : Word ( S ) → G 通过将任何词 W = s 1 … s l W=s_1 \ldots s_l W = s 1 … s l s i ∈ S ‾ s_i \in \overline{S} s i ∈ S
ϕ j ( s 1 ) ⋅ ϕ j ( s 2 ) ⋅ … ⋅ ϕ j ( s l ) 。 \phi_j\left(s_1\right) \cdot \phi_j\left(s_2\right) \cdot \ldots \cdot \phi_j\left(s_l\right)。 ϕ j ( s 1 ) ⋅ ϕ j ( s 2 ) ⋅ … ⋅ ϕ j ( s l ) 。 我们必须证明这个定义在 F ( S ) F(S) F ( S ) w w w W W W W W W s s s s − 1 s^{-1} s − 1 G G G ϕ j ( s ) \phi_j(s) ϕ j ( s ) ϕ j ( s − 1 ) = ϕ j ( s ) − 1 \phi_j(s^{-1})=\phi_j(s)^{-1} ϕ j ( s − 1 ) = ϕ j ( s ) − 1 W W W w ′ w^{\prime} w ′ ϕ j ( W ) = ϕ j ( w ′ ) \phi_j(W)=\phi_j(w^{\prime}) ϕ j ( W ) = ϕ j ( w ′ ) G G G ϕ j ( s ) ϕ j ( s ) − 1 \phi_j(s) \phi_j(s)^{-1} ϕ j ( s ) ϕ j ( s ) − 1 ϕ j ( s ) − 1 ϕ j ( s ) \phi_j(s)^{-1} \phi_j(s) ϕ j ( s ) − 1 ϕ j ( s )
ϕ j ( s 1 ) ⋅ ⋯ ⋅ ϕ j ( s ) ϕ j ( s ) − 1 ⋅ ⋯ ⋅ ϕ j ( s l ) = ϕ j ( s 1 ) ⋅ ⋯ ⋅ 1 G ⋅ ⋯ ⋅ ϕ j ( s l ) = ϕ j ( s 1 ) ⋅ ⋯ ⋅ ϕ j ( s l ) \begin{aligned}
\phi_j\left(s_1\right) \cdot\cdots \cdot\phi_j(s) \phi_j(s)^{-1}\cdot \cdots \cdot \phi_j\left(s_l\right)&=\phi_j\left(s_1\right) \cdot \cdots \cdot 1_G \cdot \cdots \cdot \phi_j\left(s_l\right)\\
&=\phi_j\left(s_1\right) \cdot \cdots \cdot \phi_j\left(s_l\right)
\end{aligned} ϕ j ( s 1 ) ⋅ ⋯ ⋅ ϕ j ( s ) ϕ j ( s ) − 1 ⋅ ⋯ ⋅ ϕ j ( s l ) = ϕ j ( s 1 ) ⋅ ⋯ ⋅ 1 G ⋅ ⋯ ⋅ ϕ j ( s l ) = ϕ j ( s 1 ) ⋅ ⋯ ⋅ ϕ j ( s l ) （同样适用于取消 ϕ j ( s ) − 1 ϕ j ( s ) \phi_j(s)^{-1} \phi_j(s) ϕ j ( s ) − 1 ϕ j ( s ) w i ′ w_i^{\prime} w i ′ i = 1 , … , I i=1, \ldots, I i = 1 , … , I W W W w w w
ϕ j ( W ) = ϕ j ( w 1 ′ ) = ⋯ = ϕ j ( w I ′ ) = ϕ j ( w ) 。 \phi_j(W)=\phi_j\left(w_1^{\prime}\right)=\cdots=\phi_j\left(w_I^{\prime}\right)=\phi_j(w)。 ϕ j ( W ) = ϕ j ( w 1 ′ ) = ⋯ = ϕ j ( w I ′ ) = ϕ j ( w ) 。 这表明 ϕ j \phi_j ϕ j F ( S ) F(S) F ( S ) ϕ j \phi_j ϕ j W = w ′ ⋅ w ′ ′ W=w^{\prime} \cdot w^{\prime \prime} W = w ′ ⋅ w ′′ w w w
ϕ j ( w ) = ϕ j ( w ′ ) ⋅ ϕ j ( w ′ ′ ) 。 \phi_j(w)=\phi_j\left(w^{\prime}\right) \cdot \phi_j\left(w^{\prime \prime}\right)。 ϕ j ( w ) = ϕ j ( w ′ ) ⋅ ϕ j ( w ′′ ) 。 通过良定义性，只需证明 ϕ j ( W ) = ϕ j ( w ′ ) ⋅ ϕ j ( w ′ ′ ) \phi_j(W)=\phi_j\left(w^{\prime}\right) \cdot \phi_j\left(w^{\prime \prime}\right) ϕ j ( W ) = ϕ j ( w ′ ) ⋅ ϕ j ( w ′′ )
w ′ = s 1 ′ ⋯ s l ′ ′ , w ′ ′ = s 1 ′ ′ ⋯ s l ′ ′ ′ ′ w^{\prime}=s_1^{\prime} \cdots s_{l^{\prime}}^{\prime}, \quad w^{\prime \prime}=s_1^{\prime \prime} \cdots s_{l^{\prime \prime}}^{\prime \prime} w ′ = s 1 ′ ⋯ s l ′ ′ , w ′′ = s 1 ′′ ⋯ s l ′′ ′′ 那么
ϕ j ( W ) = ϕ j ( s 1 ′ ) ⋅ ⋯ ⋅ ϕ j ( s l ′ ′ ) ⋅ ϕ j ( s 1 ′ ′ ) ⋅ ⋯ ⋅ ϕ j ( s l ′ ′ ′ ′ ) = ( ϕ j ( s 1 ′ ) ⋅ ⋯ ⋅ ϕ j ( s l ′ ′ ) ) ⋅ ( ϕ j ( s 1 ′ ′ ) ⋅ ⋯ ⋅ ϕ j ( s l ′ ′ ′ ′ ) ) = ϕ j ( w ′ ) ⋅ ϕ j ( w ′ ′ ) . \begin{aligned}
\phi_j(W) & =\phi_j\left(s_1^{\prime}\right) \cdot \cdots \cdot\phi_j\left(s_{l^{\prime}}^{\prime}\right) \cdot \phi_j\left(s_1^{\prime \prime}\right) \cdot \cdots \cdot \phi_j\left(s_{l^{\prime \prime}}^{\prime \prime}\right) \\
& =\left(\phi_j\left(s_1^{\prime}\right) \cdot \cdots \cdot \phi_j\left(s_{l^{\prime}}^{\prime}\right)\right) \cdot\left(\phi_j\left(s_1^{\prime \prime}\right) \cdot \cdots \cdot \phi_j\left(s_{l^{\prime \prime}}^{\prime \prime}\right)\right) \\
& =\phi_j\left(w^{\prime}\right) \cdot \phi_j\left(w^{\prime \prime}\right).
\end{aligned} ϕ j ( W ) = ϕ j ( s 1 ′ ) ⋅ ⋯ ⋅ ϕ j ( s l ′ ′ ) ⋅ ϕ j ( s 1 ′′ ) ⋅ ⋯ ⋅ ϕ j ( s l ′′ ′′ ) = ( ϕ j ( s 1 ′ ) ⋅ ⋯ ⋅ ϕ j ( s l ′ ′ ) ) ⋅ ( ϕ j ( s 1 ′′ ) ⋅ ⋯ ⋅ ϕ j ( s l ′′ ′′ ) ) = ϕ j ( w ′ ) ⋅ ϕ j ( w ′′ ) . 命题 6.5 集合之间存在一个双射
{ 群同态 F ( S ) → G } ≅ { 集合映射 S → G } 。 \{\text{群同态}~F(S) \rightarrow G\} \cong\{\text{集合映射}~S \rightarrow G\}。 { 群同态 F ( S ) → G } ≅ { 集合映射 S → G } 。 证明：我们在上面定义了对于任意函数 j : S → G j: S \rightarrow G j : S → G ϕ j : F ( S ) → G \phi_j: F(S) \rightarrow G ϕ j : F ( S ) → G
Φ : { 集合映射 S → G } → { 群同态 F ( S ) → G } \Phi:\{\text{集合映射}~S \rightarrow G\} \rightarrow\{\text{群同态}~F(S) \rightarrow G\} Φ : { 集合映射 S → G } → { 群同态 F ( S ) → G } 由 j ↦ ϕ j j \mapsto \phi_j j ↦ ϕ j Ψ \Psi Ψ ϕ \phi ϕ s ∈ S s \in S s ∈ S Ψ ( ϕ ) : = ψ ϕ \Psi(\phi):=\psi_\phi Ψ ( ϕ ) := ψ ϕ s s s ϕ ( s ) \phi(s) ϕ ( s ) Ψ ∘ Φ \Psi \circ \Phi Ψ ∘ Φ Φ ∘ Ψ \Phi \circ \Psi Φ ∘ Ψ ϕ : F ( S ) → G \phi: F(S) \rightarrow G ϕ : F ( S ) → G w w w
w = s 1 … s l ， w=s_1 \ldots s_l， w = s 1 … s l ， 其中 s i s_i s i w w w S ‾ \overline{S} S
ϕ ( w ) = ϕ ( s 1 ⋅ ⋯ ⋅ s l ) = ϕ ( s 1 ) ⋅ ⋯ ⋅ ϕ ( s l ) 。 \phi(w)=\phi\left(s_1 \cdot \cdots \cdot s_l\right)=\phi\left(s_1\right) \cdot \cdots \cdot \phi\left(s_l\right)。 ϕ ( w ) = ϕ ( s 1 ⋅ ⋯ ⋅ s l ) = ϕ ( s 1 ) ⋅ ⋯ ⋅ ϕ ( s l ) 。 因此，ϕ \phi ϕ S S S F ( S ) F(S) F ( S ) Φ ∘ Ψ \Phi \circ \Psi Φ ∘ Ψ Φ \Phi Φ Φ ( j ) = ϕ j \Phi(j)=\phi_j Φ ( j ) = ϕ j j ( s ) j(s) j ( s ) Ψ ∘ Φ \Psi \circ \Phi Ψ ∘ Φ
例 6.13 设 S S S G G G
都存在一个群同态
当 S = ∅ S=\varnothing S = ∅
那么
是什么群同态？
它将空字映射到 1 G 1_{G} 1 G
命题 6.6 如果 w 1 w_{1} w 1 w 2 w_{2} w 2 w 1 ∼ w 2 w_{1}\sim w_{2} w 1 ∼ w 2
证明：w 1 ∼ w 2 w_{1}\sim w_{2} w 1 ∼ w 2
(1) w ∼ w w\sim w w ∼ w r e d u c t i o n ( w ) = r e d u c t i o n ( w ) \mathrm{reduction}(w)=\mathrm{reduction}(w) reduction ( w ) = reduction ( w )
(2) w 1 ∼ w 2 w_{1}\sim w_{2} w 1 ∼ w 2 ⇒ \Rightarrow ⇒ w 2 ∼ w 1 w_{2}\sim w_{1} w 2 ∼ w 1
r e d u c t i o n ( w 1 ) = r e d u c t i o n ( w 2 ) ⇒ r e d u c t i o n ( w 2 ) = r e d u c t i o n ( w 1 ) 。 \begin{aligned}
&\mathrm{reduction}(w_{1})=\mathrm{reduction}(w_{2})\\
\Rightarrow&\mathrm{reduction}(w_{2})=\mathrm{reduction}(w_{1})。
\end{aligned} ⇒ reduction ( w 1 ) = reduction ( w 2 ) reduction ( w 2 ) = reduction ( w 1 ) 。 (3) w 1 ∼ w 2 w_{1}\sim w_{2} w 1 ∼ w 2 w 2 ∼ w 3 w_{2}\sim w_{3} w 2 ∼ w 3 ⇒ \Rightarrow ⇒ w 1 ∼ w 3 w_{1}\sim w_{3} w 1 ∼ w 3
r e d u c t i o n ( w 1 ) = r e d u c t i o n ( w 2 ) r e d u c t i o n ( w 2 ) = r e d u c t i o n ( w 3 ) ⇒ r e d u c t i o n ( w 1 ) = r e d u c t i o n ( w 3 ) 。 \begin{aligned}
\mathrm{reduction}(w_{1})=\mathrm{reduction}(w_{2})\\
\mathrm{reduction}(w_{2})=\mathrm{reduction}(w_{3})
\end{aligned}\Rightarrow \mathrm{reduction}(w_{1})=\mathrm{reduction}(w_{3})。 reduction ( w 1 ) = reduction ( w 2 ) reduction ( w 2 ) = reduction ( w 3 ) ⇒ reduction ( w 1 ) = reduction ( w 3 ) 。 （所有这些都来源于约简的唯一性和等式是一个等价关系的事实。）
注 因此，如果 w 1 ⇝ w 2 w_{1}\rightsquigarrow w_{2} w 1 ⇝ w 2 w 1 ∼ w 2 w_{1}\sim w_{2} w 1 ∼ w 2
命题 6.7 设 F ( S ) F(S) F ( S ) S ‾ \overline{S} S
F ( S ) → { 在 W o r d ( S ‾ ) 中的词的等价类 } . F(S)\to \{\text{在}~\mathrm{Word}(\overline{S})~\text{中的词的等价类}\}. F ( S ) → { 在 Word ( S ) 中的词的等价类 } . 证明：将 w ↦ [ w ] w\mapsto [w] w ↦ [ w ] w w w
任何等价类都有唯一的最短长度的元素——即任意 w ′ ∈ [ w ] w^{\prime}\in [w] w ′ ∈ [ w ]
命题 6.8 操作
{ 词的等价类 } × { 词的等价类 } → 连接 { 词的等价类 } ( [ w 1 ] , [ w 2 ] ) ⟼ [ w 1 w 2 ] \begin{aligned}
\{\text{词的等价类}\}\times\{\text{词的等价类}\}&\xrightarrow{\text{连接}}\{\text{词的等价类}\}\\
([w_{1}],[w_{2}])&\longmapsto [w_{1}w_{2}]
\end{aligned} { 词的等价类 } × { 词的等价类 } ([ w 1 ] , [ w 2 ]) 连接 { 词的等价类 } ⟼ [ w 1 w 2 ] 是良定义的。
证明：设 r 1 r_{1} r 1 r 2 r_{2} r 2 w 1 ′ w_{1}^{\prime} w 1 ′ w 2 ′ w_{2}^{\prime} w 2 ′
r 1 r 2 可以通过取消从 w 1 ′ w 2 ′ 中得到 . r_{1}r_{2}~\text{可以通过取消从}~w_{1}^{\prime}w_{2}^{\prime}~\text{中得到}. r 1 r 2 可以通过取消从 w 1 ′ w 2 ′ 中得到 . （只需对词的 w 1 ′ w_{1}^{\prime} w 1 ′ w 2 ′ w_{2}^{\prime} w 2 ′
因此，对于任何
w 1 ′ ∈ [ w 1 ] , w 2 ′ ∈ [ w 2 ] ， w_{1}^{\prime}\in [w_{1}], w_{2}^{\prime}\in [w_{2}]， w 1 ′ ∈ [ w 1 ] , w 2 ′ ∈ [ w 2 ] ， 我们有
w 1 ′ w 2 ′ ∼ r 1 r 2 w_{1}^{\prime}w_{2}^{\prime}\sim r_{1}r_{2} w 1 ′ w 2 ′ ∼ r 1 r 2 即
[ w 1 ′ w 2 ′ ] = [ r 1 r 2 ] 。 [w_{1}^{\prime}w_{2}^{\prime}]=[r_{1}r_{2}]。 [ w 1 ′ w 2 ′ ] = [ r 1 r 2 ] 。 所以无论我们选择哪个代表 w 1 ′ ∈ [ w 1 ] w_{1}^{\prime}\in [w_{1}] w 1 ′ ∈ [ w 1 ] w 2 ′ ∈ [ w 2 ] w_{2}^{\prime}\in [w_{2}] w 2 ′ ∈ [ w 2 ] w 1 ′ w 2 ′ w_{1}^{\prime}w_{2}^{\prime} w 1 ′ w 2 ′
推论 6.9 自由群操作
F ( S ) × F ( S ) → F ( S ) ( r 1 , r 2 ) ↦ r e d u c t i o n ( r 1 r 2 ) \begin{aligned}
F(S)\times F(S) &\to F(S)\\
(r_{1},r_{2})&\mapsto \mathrm{reduction}(r_{1}r_{2})
\end{aligned} F ( S ) × F ( S ) ( r 1 , r 2 ) → F ( S ) ↦ reduction ( r 1 r 2 ) 是结合的。
证明：
因此，我们只需要证明操作 ( [ r 1 ] , [ r 2 ] ) ↦ [ r 1 r 2 ] ([r_{1}],[r_{2}])\mapsto [r_{1}r_{2}] ([ r 1 ] , [ r 2 ]) ↦ [ r 1 r 2 ]
( [ 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 ] ) ， ([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}])， ([ 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 ]) ， 其中第三个等号来自于普通词连接的结合性。
