第九章 半群与群(Semigroups and Groups)

第九章 半群与群（Semigroups and Groups）

本章讨论含一个二元运算的特殊的代数系统――半群与群。群论近世代数中发展最早、内容最丰富、应用最广泛的部分，也是建立其他代数系统的基础。群论在自动机政论、形式语言，语法分析快速加法器设计、纠错码制定等方面均有卓有成效的应用。

2－1 半群与含幺半群

定义2－1.1 满足结合律的代数系统U=称为半群。 例2－1.1 ,,<2I+,+>和<2I+,×>都是半群。 例2－1.2 和都是半群。

例2－1.3 和都是半群。

定义2－1.2 含幺元e的半群U=称为含幺半群，常记作U=。在例2－1.1～例2－1.3中，除<2I+,+>和<2I+,×>外都是含幺半群。

例2－1.4 设S是任意非空集合，则和都是含幺半群。

例2－1.5 在形式语言中，我们常称非空有限字符集合为字母表。字母表中字符的n重序元称为字符串，由m个字符所组成的字符串称为长度为m的字符串。长度为0的字符串称为空串，用 来表示。如对V={a,b}, =aa和β=ab都是长度为2的字符串；γ=aab和δ=bab都是长度为3的字符串。我们用*来表示两个字符串的邻接运算，如,α*δ=aabab,α*γ=aaaab。

设用V*表示字母表V的所有有限长度字符串的集合，而用V+表示V*-{ }，则显然是半群，是含幺半群。

定义2－1.3 对运算满足交换律的半群（含幺半群）称为交换半群（交换含幺半群）。 在例2－1.1～例2－1.3中，除外都是交换半群，除，<2I+,+>和<2I+,×>外都是交换含幺半群。

例2－1.4的含幺半群也都是交换含幺半群。 定义2－1.4 设是半群（含幺半群），若S中存在一个元素g，可将S中任意元素a表示成a=gnn?I+,(n?N)，则称是循环半群（循环含幺半群）,g就称为是它的生成元。此时，常将记作。

注意在含幺半群中，我们规定任意元素的零次幂为幺元。 例2－1.6 <2I+,+>=<2>是循环半群。 例2－1.7 <{i,-1,-i,1},×>==<-i>,=和<{1,2,3,4},×5>=<2>=<3>都是循环含幺半群。

可见循环半群（循环含幺半群）的生成元不一定是唯一的，但它们一定是可交换的。 定理2－1.1 两个半群（含幺半群）的积代数是半群（含幺半群）。 证明 设和是两个半群，其积代数为。对S×T中任意三个元素和，因为( )

=<(s1*s2)*s3,(t1 t2) t3>== ( )故是半群。

设和是两个含幺半群，共中幺元分别为es和eT，则显然是半群的幺元,故是含幺半群。 ★

很明显，可交换半群（含幺半群）的积代数也是可交换的。

2－2 子半群与子含幺半群

子含幺半群的概念是子代数系统概念在（含幺）半群这种代数系统中的具体体现。 定义2－2.1 设是半群，T是S 的非空子集，若T对*封闭，则称是半群的子半群。

定义2－2.2 设是含幺半群，T是S的非空子集，若T对*封闭，且e?T，则称是含幺半群的子含幺半群。

易知子半群必是半群；子含幺半群必是含幺半群。

例2－2.1 对任意正整数m，是半群的子半群。

例2－2.2 设集合S={e,0,1}，若在S中规定二元运算*（见表2－2.1），

* e 0 1 e e 0 1 0 0 0 0 1 1 0 1 表2－2.1

则是含幺半群，从运算表可看出<{0,1},*>不是的子含幺半群。

定理2－2.1 设T是可交换含幺半群的等幂元构成的集合，则是的子含幺半群。

证明 因e2=e，故e?T，即T非空。又对T中任意元素a和b，因 (a*b)2=(a*b)*(a*b)=a*(b*a)*b=a*(a*b)*b=(a*a)*(b*b)=a2*b2=a*b 故a*b?T。这就证明了是的子含幺半群。 ★

2－3 半群与含幺半群的同态和同构

本节中，将把代数系统运用的同态与同构的概念应用于半群（含幺半群），有关定义与性质，几乎是代数系统部分的平行照搬。

定义2-3.1 设U=和V=是两个半群。若存在映射（满射，单射，双射）f: S→T，对S中任意元素a和b，有

f(a*b)=f(a) f(b)

则称f是U到V的一个半群同态（满同态，单同态，同构）映射或简称同态（满同态，单同态，同构）。

特别U到U（上）的同态（同构）f称为U的自同态（自同构）。 定义2－3.2 若半群U=到V=存在一个满同态（同构），则称U同态（同构）于V,记作U～V(U?V)。

定义2－3.3 设U=和V=是两个含幺半群。若存在映射（满射，单射，双射）f: S?T，对S中任意元素a和b，有 f(a*b)=f(a) f(b) f(es)=eT

则称f是U到V的一个含幺半群同态（满同态，单同态，同构）映射或简称同态（满同态，单同态，同构）。

特别U到U（上）的同态（同构）f称为U的自同态（自同构）。

定义2－3.4 若含幺半群U=到V=存在一个满同态（同构），则称U同态（同构）于V，记作U～V(U?V)。

例2－3.1 我们已知例2－1.1中的U=是半群（也是含幺半群）。易知N到S的映射

是半群U到V的同态。但不是含幺半群U到V的同态。

例2－3.2 对半群（含幺半群）U＝和V＝,N到M4的映射

f: a?〔a(mod 4)〕

即是半群U到V的同态，也是含幺半群U到V的同态。

2－4 群

对子群再附加一些性质就可成为群。 群是代数“系统中研究得比较完美的一类，目前已有许多群的专著。在计算机科学中，群在快速加法器设计和纠错码理论等方面有广泛应用。

定义2－4.1 每个元素都有逆元的含幺半群U＝称为群。若群还满足交换律，则称为交换群或阿贝尔群。

也就是说，设U=是代数系统，若满足： 1） 对G中任意元素a,b和c，有

(a*b)*c=a*(b*c)

2） 在G中存在元素e，对G中任意元素a，使 c*a=a*e=a

3） 对G中任意元素a，在G中存在元素a-1，使 a-1*a=a*a-1=e 则称U=(G,*)为群。若还满足

4） 对G中任意元素a和b，有 a*b=b*a 则称U=为交换群或阿贝尔群。

由定义2－4.1，定理1－1.1和定理1－1.4知群中的幺元和每个元素的逆元都是唯一的。且对群中任意元素a1,a2,?,am必有

。由定理1－1.3知除单个元素构成的群外，群无零元。还应注意，含幺半群中的等幂元不一定是唯一的，但群中的等幂元却一定是唯一的，即只有幺元一个。

例2－4.1 ,,,,,和都是交换群。 例2－4.2 和都是交换群，其中R[x]表示所有实系数多项式的集合。 显然，由定义2－4.1知，给空集合G，和其上的二元运算A，能构成群的判定过程如下：

（1） 验证*运算的封闭性 （2） 验证*运算的可结合性

（3） 验证题?e?G,?x?G有e*x=x*e=x （4） 验证?x?G,?x-1?G使x*x-1=x-1*x=e

上述四个步骤中至少一个步骤的验证不成立,都不是群。

定理2－4.1 半群是群的充要条件为存在左（右）幺元e1(er)，且每个元素对此左（右）幺元具有左（右）逆元。

证明 必要性是很明显的。 充分性，只证“左”的情况（“右”的情况完全类似），对G中任意元素a，设其左逆元为则因在此式两边左“乘” 的左逆元，可得即 也是a的右逆元。又因

即e1也是右幺元。故由定理1-1.1和定理1-1.4知e1=e， 可见是群。 ★

这个定理说明群定义中的条件可以削弱。

定理2－4.2 代数系统是群的充要条件为 1)对G中任意元素a,b和c，有

(a*b)*c=a*(b*c)

2）对G中任意元素a和b，方程a*x=b和y*a=b都有解。

证明 必要怀是很明显的。实际上，x=a-1*b和y=b*a-1就是2）中方

程的（唯一）解。

充分性：对G中任意元素a和b，设方程b*x=a的解为 d，方程y*b=b

的解为e，则有e*a=e*(b*d)=(e*b)*d=b*d=a，即e是左幺元。又方程y*a=e的解是a的左逆元。故由定理2－4.1知是群。 ★

定理2－4.3 若是群，则对*满足消去律。

证明 设a*b=a*c或b*a=c*a，则在等式两边左“乘”或右“乘” a-

1

即得b=c。 ★ 定理2－4.4 有限半群是群的充要条件为对*满足消去律。 证明 必要性由定理2－4.3即得。

充分性：由于有限半群满足消去律，可见其运算表中的每行（列）

都是G中元素的不同排列，故对G中任意元素a和b，方程a*x=b和y*a=b都有解。由定理2-4.2即知是群。 ★

我们知道，在半群（含幺半群）中可定义元素的正整数（非负整数）

次幂的概念，且相应的指数律成立。而在群中则可定义元素的整数次幂的概念。

定义2－4.2 设是幺元为e的群，则对G中任意元素a和任意 正整数m，可规定

a=e 0利用数学归纳法，易证对群中任意元素的整数次幂，其指数律也成立。 定义2－4.3 设是群，其幺元为e，则称

为群的阶。

而称

为群中元素a的阶。 定义2－4.4 n阶有限集合S={a1,a2,?,an}到S的双射P称为S的n次置换，常记作 其中P(ak)=aik,k=1,2,?，n。置换中列的次序显然无关紧要。置换中两行逆序的和若是偶（奇）数，则称这种置换为偶（奇）置换。

对n次置换Pi和Pj，规定Pi◇Pj=Pj○Pi，其中○是映射的合成。如设

则

Pi◇Pj= 可以证明

偶置换◇偶置换=偶置换 偶置换◇奇置换=奇置换 奇置换◇偶置换=奇置换 奇置换◇奇置换=偶置换

对二元运算◇，我们将某些n次置换的集合构成的群称为n次置换群。特别，将所有n次置换的集合（其元素共n!个）构成的群称为n次对称群，记作;将所有n次偶置换的集合（其元素共个）构成的群称为n次交代群，记作，这两个结论请读者自行证之。

例2－4.3 设S={1,2,3}，则所有3次置换为

运算表为

◇ P1 P2 P3 P4 P5 P6 P1 P1 P2 P3 P4 P5 P6 P2 P2 P1 P5 P6 P3 P4 P3 P3 P6 P1 P5 P4 P2 P4 P4 P5 P6 P1 P2 P3 P5 P5 P4 P2 P3 P6 P1 P6 P6 P3 P4 P2 P1 P5

表2－4.1

可见<{P1,P2},◇>,<{P1,P3},◇>和<{P1,P4},◇>等都是3次置换群。 是3次对称群，其中S3={P1,P2,P3,P4,P5,P6}。是3次交代群，其中A3={P1,P5,P6}。 定义2－4.5 设是群，若G中存在一个元素g，可将G中任意元素a表示成a=gn，n?I，则称是循环群，g就称为是它的生成元，此时，常将记作。 定理2－4.5 设=是循环群。

1） 若?G?=n，则G={g0,g1,g2,?,gn-1}。

2） 若?G?=∞，则G={?,g-2,g-1,g0,g1,g2,?}。证明 对于1），有

12n-1

a) g,g,?,g都不等幺元e：

用反证法。若gm=e,0﹤m﹤n,则对于G中 任意元素gk。可设k=qm+r 0﹤r﹤m，故必有

gk=gqm+r=(gm)q*gr=eq*gr=gr

可见G中至多有m个元素，这与|G|=n矛盾。

b) g1,g2,?,gn-1,gn都互不相等；

用反证法。若gi=gj 1﹤i﹤j﹤n，则有gj-i=e 0﹤j-i﹤n，这与a)的结论矛盾。 故由a),b)的结论和|G|=n，得gn=g0=e，即1）的结论成立。 对于2），显然?g-2,g-1,g0,g1,g2,?也都互不相等，因而2）的结论成立。 可见n阶有限循环群生成元的阶为n，而无限循环群生成元的阶为∞。 ★ 定理 2－4.6 两个群的积代数是群。 证明 设和是两个群，其幺元分别为eG和eH，其积代数为，由定理2－1.1知是含幺半群，其幺元为。又G×H中任意元素有逆元，故是群。 ★

实际上，可以定义两个以上群的积代数，产生更高阶的群的积代数，本文从略。

2－5 子群与陪集

子群在群论中的地位，与子半群机子含幺半群在半群中的地位相似。

定义2－5.1 设是群，e是其幺元，S是G的非空子集，若对S中任意元素a和b，有

1) a*b?S

-1

2) a?S 3) e?S

则称是群的子群。

可见子群必是群，且其幺元与原群幺元一致。 <{e},*>和都是群的子群，这种子群常称为平凡子群。非平凡子群称为真子群。

i

设a是群中的任意元素，H={a|i?I}，则也是群的一个子群，称为由元素a生成的子群。

还应注意，定义2－5.1中的条件3）实际上是多余的。这是因为S是非空集合，故必存在元素d，从而由条件1）和2）可得出e=d*d-1?S。

例2－5.1 不是群的子群，因为它们的二元运算不同。