离散数学之代数系统篇

第三篇代数系统篇

第34章代数结构

本章将从引入一般代数系统出发，研究如群、环、域等这样一些代数系统，

而这些代数系统中的运算所具有的性质确定了这些代数系统的数学结构。

§3-1-1代数系统的概念

在计算机科学中，常用代数系统去描述机器可计算函数，研究运算的复杂性，

分析程序设计语言的语义等。

由非空集合和该集合上的一个或多个运算所组合的系统，常称为代数系统，有

时简称为代数。在研究代数系统之前，首先考察一个非空集合上运算的概念，如

将有理数集合Q上的每一个数a的映射成它的整数部分［«］；或者将Q上的每一

个数a映射成它的相反数-a,这两个映射可以称为集合Q上的一元运算；而在集

合Q上，对任意两个数所进行的普通加法和乘法都是集合Q上的二元运算，也可以

看作是将Q中的每两个数映射成一个数；至于对集合Q上的任意三个数打，必，冷，

代数式打2+小，心2和X1+X2+X3分别给出了Q上的两个三元运算，它们分别将Q中

三个数映射成Q中的一个数。上述这些例子有一个共同的特征，那就是其运算的结

果都是在原来的集合中，我们称那些具有这种特征的运算是封闭的，简称闭运算。

相反地，没有这种特征的运算就是不封闭的。

很容易举出不封闭运算的例子，设N是自然数集，Z是整数集，普通的减法是

NxN到Z的运算，但因为两个自然数相减可以不是自然数，所以减法运算不是自然

数集N上的闭运算。

定义3-L1.1设A和B都是非空集合，n是一个正整数，若是A"到B的一个映

射，则称是A到B的一个〃元运算。当B=A时，称是A上的"元运算（”-aryoperation）,

简称A上的运算。并称该〃元运算在A上是封闭的。

例3-LL1（1）求一个数的倒数是非零实数集R*上的一元运算。

（2）非零实数集R"上的乘法和除法都是R*上的二元运算，而加法和减法不是。

（3）S是一非空集合，5$是S到S上的所有函数的集合，则复合运算。是SS上的

二元运算。

（4）空间直角坐标系中求点（x,y,z）的坐标在x轴上的投影可以看作实

数集R上的三元运算/1（X,y,z）=x,因为参加运算的是有序的3个实数，而结果也

是实数。

通常用等。，・，*,……等表示二元运算，称为算符。若/:SXS-S是集合

S上的二元运算，对任意x,yS,如果x与y运算的结果是z,即/(x，y)=z,可利用

运算。简记为，xoy=zo

类似于二元运算，也可以使用算符来表示〃元运算。如〃元运算

fCa/,如…，%)=6可简记为

o(41，42，........，a〃)=b

n=\时。(«|)=b是一元运算

〃=2时-O(田，。2)=b是二兀运算

"=3时o(4|,a2,a3)=b是二兀运算

这些相当于前缀表示法，但对于二元运算用得较多的还是四。"2=。，以下所

涉及的n元运算主要是一元运算和二元运算。

若集合X={xi，也，……，X"}是有限集，X上的一元运算和二元运算也可用

运算表给出。表3-1-1.1和3-1-12分别是一元运算和二元运算的一般形式。

表3-1-1.1表3-1-1.2

SiO(Si)os.S2…”Sn

Si。⑸)s,S1OS1S1OS2-SQSn

ssS2OS1

2o(S2)2S2OS21S2°Sn

例

3-1-1.2

SnOSi

Sn。⑸)S„S„oS2-Sn°Sn

设集合s

={0,1},给出S的幕集(P(S)上求补运算〜和求对称差运算的运算表，其中

全集是S

解所求运算表如表3-1-L3和表3-1-1.4所示。

表3-1-1.3表3-1-1.4

Si〜(Si){0){1}{0,1}

{0.1}{0){1}{0,1}

{0}{1}{0}{0){0,1}{1}

{1}{0}{1}{1}{0,1}{0}

{011}{0,1}{011}{1}{0}

定义3-1-1.2一个非空集合A连同若干个定义在该集合上的运算力，

力，...，1A所组成的系统称为一个代数系统(algbraicsystem)。记作VA,力，

于2,...，°

如果对集合S,由S的嘉集(P(S)以及该幕集上的运算“U”、"C

组成一个代数系统〈①(S),u,n,〜＞，S|£＜?(s),Si的补集〜s尸s-Si也

常记为1O又如整数集Z以及Z上的普通加法“+”组成一个系统＜Z,+＞o值

得注意的是，虽然代数系统有许多不同的形式，但它们可能有一些共同的运算。

例如，考察上述代数系统VZ,+＞。很明显，在这个代数系统中，关于加法

运算，具有以下二个运算规律，即对于任意的无，y,ZWZ,有

⑴x+y=y+x佼换律)

(2)(x+y)+z=x+(y+z)(结合律)

又如，设S是集合，。(S)是S的基集，则代数系统(＜?(S),U＞和〈7

(S),。＞中的口、。都适合交换律，结合律，即他们与＜Z,+＞有类似的运

算性质。

§3-1-2代数系统的运算及其性质

对给定的集合，我们可以相当任意地在这个集合上规定运算使它成为代数系

统。但我们所研究的是其运算有某些性质的代数系统。在前面考察几个具体的代

数系统时一，已经涉及到我们所熟悉的运算的某些性质。这一节，主要讨论一般二

元运算的一些性质。

定义3-1-2.1设是定义在集合S上的二元运算，如果对于任意的x,yCS,

都有则称二元运算是可交换的或称运算满足交换率(commutativelaw)。

例3-1-2.1设Z是整数集，△,☆分别是Z上的二元运算，其定义为，对

任意的a,6GZ,a/\b—ab—a-h,3b=ab—a+b,问Z上的运算/\,☆

分别是否可交换？

解：因为a/\b=ab—a—b-ba-b—a=bAa对Z中任意元素a,b成

立，所以运算△是可以交换的。

又因为对Z中的数0,1,Oiirl=0X1-0+1=1,1☆0=lX0—1+0=-1,

所以，O+lWl+O,从而运算☆是不可交换的。

定义3-1-2.2设*是定义在集合S上的二元运算，如果对于S上中的任意

元素x,y,z都T,(x*y)*z=x*(y*z)，则称二元运算*是可以结合的或称

运算*满足结合律(associativelaw)。

例3-1-2.2设Q是有理数集合，。，*分别是Q上的二元运算，其定义为，

对于任意的a,bGQ,aob=a,aoh=a—2h,证明运算。是可结合的并说明

运算*不满足结合律。

证明：因为对任意的mb,c-GQ,

(aOb')oc=aoc=a

ao(hoc)=aoh=a

所以Caob)oc=ao(boc),即得运算。是可以结合的。

又因为对Q中的元0,1

(0*0)*1=0*1=0—2=2

0*(0*1)=0*(—2)=0—2X(—2)=4

所以，(0*0)*120*(0*1),从而运算*不满足结合律。

对于满足结合律的二元运算，在-一个只有该种运算的表达式中，可以去掉标

记运算顺序的括号。例如，实数集上的加法运算是可结合的，所以表达式Q+y)

+可简写为x+y+"+v。

若VS,。＞是代数系统，其中。是S上的二元运算且满足结合律，〃是正整

数，a@S,那么，aoaoa...oa是S中的~■个元素，称其为a的〃次幕，

记为a"。

关于a的累，用数学归纳法不难证明以下公式

a八机o—an=a4机+〃(za/n)xn=a_mn

其中机，〃为正整数。

定义3-1-2.3设。，*是定义在集合S上的两个二元运算，如果对于任意

的x,y,z《S,都有xo(y*z)=(xoy)*(xoz)

(y*z)ox=(yox)*(zox)

则称运算。对运算*是可分配的，也称。对运算*满足(适合)分配律(distributive

law)。

例3-1-2.3设集合A={0,1},在A上定义两个二元运算。和*如表3-1-2.1

和表3-1-2.2所示。试问运算*对运算。和运算。对运算*分别是否是可分配的？

表3-1-2.1表3-1-2.2

［表3-122

O0*01

_____0_01000

110101

解：容易

验证运算*对运算。是可分配的，但运算。对运算*是不满足分配律的。因

1O(0*1)=101=1而(1。0)*(1O1)=1*0=0

所以，。对*不满足分配律。

定义3-1-2.4设。和*是集合S上的两个可交换的二元运算，如果对任意

x,yS的都有x*(尤。y)=xxo(x*y)=x

则称运算。和*满足吸收律(absorptivelaw)。

例3-1-2.4设(P(S)是集合S上的塞集，集合的并“”和交“”是

①(S)上的两个二元运算，验证运算和运算满足吸收律。

解：对任意A,B0(S),由集合相等及和的定义可得

A(AB)=AA(AB)=A

因此，和满足吸收律。

定义3-1-2.5设*是集合S上的二元运算，如果对于任意的xS,都有x

*x=x,则称运算*是等塞的，或称运算*满足基等律(ildempotentlaw)。

例3-1-2.5设Z是整数集，在Z上定义两个二元运算。和*,

对于任意x,yZ,xoy=max(x,y)；x*y=min(x,y)

验证运算*和。都是幕等的

解：对于任意的xZ,有

xox=max(x,x)=x；x*x=min(x,x)=x

因此运算*和运算。都是等事的。

定义3-1-2.6设。是定义在集合S上的一个二元运算，如果有一个元素，

使得对于任意元素xS都有则称e为S中关于运算。的左幺元(leftidentiy)；女果有

一个元素，使对于任意的元都有，则称为S中关于运算。的右幺元(rightidentity)；

如果S中有一个元素e,它既是左幺元又是右幺元，则称e是S中关于运算。的

幺元(identity)。

在整数集Z中加法的幺元是0,乘法的幺元是1；设S是集合，在S的事集

①(S)中，运算的幺元是①，运算的幺元是S。

对给定的集合和运算，有些存在幺元，有些不存在幺元。

例如，R*是非零的实数的集合，。是R*上如下定义的二元运算，对任意的元

素a,bR*,aob=b则R*中不存右幺元；但对任意的aR*对所有的/求*都有

aoh=b

所以，R"的任一元素a都是运算。的左幺元，R*中的运算。有无穷多左幺元,

没有右幺元和幺元。

又如，在偶数集合中，普通乘法运算没有左幺元，右幺元和幺元。

定理3-1-2.1设*是定义在集合S上的二元运算，和分别是S中关于运算

*的左幺兀和右幺兀，则有e=e=e

月.e为S上关于运算*的唯一的幺元。

证明：因为和分别是S中关于运算*的左幺元和右幺元，所以

把e=e记为e,假设S中存在ei，则有e=e*e=e

所以，e是S中关于运算*的唯一幺元。

定义3-1-2.7设*是定义在集合S上的一个二元运算，如果有一个元S,

使得对于任意的元素xA都有*m，则称为S中关于运算*的左零元；如果有一

元素S,对于任意的元素xS都有x*=,则称为S中关于运算*的右零元；如果

S中有一元素，它既是左零元又是右零元，则称为S中关于运算*的零元

(zero.element)o

例如，整数集Z上普通乘法的零元是0,加法没有零元；S是集合，在S的

事集0(S)中，运算的零元是S,运算的零元是①，在非零的实数集R*上定义运算

*，使对于任意的元素。,〃R*,有a*b=a

那么，R*的任何元素都是运算*的左零元，而R"中运算*没有右零元，也

没有零元。

定理3-1-2.2设是集合S上的二元运算，和分别是S中运算。左零元和右

零元，则有==且是S上关于运算。的唯一的零元。

这个定理的证明与定理3-1-2.1类似。

定理3-1-2.3设VS,*＞是一个代数系统，其中*是S上的一个二元运

算，且集合S中的元素个数大于1,若这个代数系统中存在幺元e和零元，则e。

证明：(用反证法)若e=,那么对于任意的xS,必有x=e*x=*x==e,

于是S中所有元素都是相同的，即S中只有一个元素，这与S中元素大于1矛

盾。所以，e。

定义3-1-2.8设VS,*＞是代数系统，其中*是S上的二元运算，eS是S

中运算*的幺元。对于S中任一元素x,如果有S中元素y使y*x=e,则称y

为x的左逆元；若有S中元素y使x*y=e,则称y为x的右逆元；如果有S

中的元素y,它既是x的左逆元，又是x右逆元，则称y是x的逆元(inverse)»

例如，自然数集关于加法运算有幺元0且只有0有逆元，0的逆元是0,其

它的自然数都没有加法逆元。设Z是整数集合，则Z中乘法幺元为1,且只有一

1和1有逆元，分别是一1和1；Z中加法的幺元是0,关于加法，对任何整数x,

x的逆元是它的相反数一X,因为(-x)+x=0=x+(—X)O

例3-1-2.6设集合A={a,a,a,a,a,a},定义在A上的一-个二元运算*如表

3-1-2.3所示，试指出代数系统VA,*＞中各元素的左、右逆元的情况

表3-123

解：由表可知，a是幺元，a的逆元是a,a的左逆元和右逆元都是a,即a

和a互为逆元；a的左逆元是念，而右逆元是a，a有两个右逆元a和a,a有左

逆元a,但a没有右逆元。

一般地，对给定的集合和其上的一个二元运算来说，左逆元、右逆元、逆元

和幺元、零元不同，如果幺元和零元存在，一定是唯一的，而左逆元、右逆元、

逆元是与集合中某个元素相关的，一个元素的左逆元不一定是右逆元，一个元素

的左(右)逆元可以不止一个，但一个元素若有逆元则是唯一的。

定理3-1-2.4设〈S,*〉是一个代数系统，其中*是定义在S上的一个

可结合的二元运算，e是该运算的幺元，对于x《S,如果存在左逆元”和右元素

和右元素孙，则有

yi=yr=y

月.y是x的唯一的逆元。

证明：y=y*e=y*(x*y)=(y*x)*y=e*y=y令y=y=y,则y是x

的逆元，假设也是x的逆元，

则有yi1*e=y\*(x*y)=(y\*x)*y=e*y=y

所以，y是x的唯一的逆元。

由这个定理可知，对于可结合的二元运算来说，元素x的逆元如果存在则是

唯一的，通常把x的唯一的逆元记为

例如，若N和Z分别表示自然数集和整数集，x为普通乘法，则代数系统＜

N,x＞中只有幺元1有逆元，＜Z,x＞中只有-1和1有逆元，若十为普通的

加法，则代数系统

＜Z,+＞中所有元素都有逆元。

例3-1-2.7对于代数系统＜NQ+后〉，其中k是正整数，N={O,1,…,hl},

+是定义在N上的模々加法运算，定义如下：对任意的x,yGN,

x+y,若x+y＜k;

%+*y=〈...

x+y-k,若x+y＞/:.

试问是否每个元素都有逆元？

解：容易验证，+是一个可结合的二元运算，N中关于运算+的幺元是0,

N中每个元素都有唯一的逆元，即0的逆元是0,每个非零元x的逆元是k-X。

定理3-1-2.5设VS,*＞是代数系统，其中*是S上可结合的二元运算，

S有单位元e,若S中的每个元有右逆元，则这个右逆元也是左逆元，从而是该

元唯一的逆元。

证明：对任一元素a£S,由条件可设b,cGS,b是。的右逆元，c是b

的右逆元。

因为6*(a*b)=b*e=b,所以

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

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

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

=b*(a*e)=h*a

因此，b也是。的左逆元

从而由定理3-1-24知，匕是a的唯一逆元，由“GS的任意性知定理成立。

若vs,。＞是代数系统，其中。是有限非空集合S上的二元运算，那么该运

算的部分性质可以从运算表直接看出，例如

1.当且仅当运算表中每个元素都属于S中，运算。具有封闭性。

2.当且仅当运算表关于主对角线对称时，运算。具有可交换性。

3.当且仅当运算表的主对角线上的元素与它所在行(列)的表头相同时，

运算。具有幕等性。

4.S关于运算。有幺元e,当且仅当表头e所在的列与左边一列相同且表中

左边一列e所在的行与表头一行相同。

5.S关于运算。有零元。，当且仅当表头9所在的列和表中左边一列0所在

的行都是。。

6.设S关于运算。有幺元，当且仅当位于a所在的行与人所在的列交叉点

上的元素以及b所在的行与«所在的列交叉点上的元素都是幺元时，。与6互逆

0

代数系统＜S,。〉中一个元素是否有左逆元或右逆元也可从运算表中观察出

来，但运算是否满足结合律在运算表上一般不易直接观察出来。

§3-1-3半群与含幺半群

半群及含幺元群是特殊的代数系统，在计算机科学领域中，如形式语言，自

动机理论等方面，它们已得到了卓有成效的应用。

定义3-1-3.1设＜S,*＞是一个代数系统，*是5上的一个二元运算，

如果运算*是可结合的，即对任意的WS,都有(x*y)*z=x*(y*z),则

称代数系统VS,*＞为半群(semigroup)。

半群中的二元运算也叫乘法，运算的结果也叫积。

由定义易得，＜N,+＞,＜N,x＞是半群，其中N是自然数集，“+”，“x”

分别是普通的加法和乘法。A是任一集合，①(A)是A的基集，则〈①(A),U＞,

＜＜P(A),都是半群。

例3-1-3.1设5=仅/1},5上的一个二元运算的定义如表3-1-3.1所示，

验证＜S,＞是半群。

表3-1-3.1

oabc

aabc

babc

解：由表cabC3-1-3.1知运算。

在S上是封闭的而且对任意打,无2

es有"所以＜S,O＞是代数系统，且a,。,C都是左幺元，

从而对任意的x,y,zGS都有xo(yoz)=xoz=z=yoz=(xoy)。工因此，

运算。是可结合的，是半群。

例3-1-3.2设k是一个非负整数，集合定义为&={xlx是整数且X2。，

那么,VSk,+＞是半群，其中+是普通的加法运算。

解：因为上是非负整数，易知运算+在也上是封闭的，而且普通加法运算

是可结合的，所以＜1,+＞是半群。

易知，代数系统VZ,—＞,VR-{0},/＞都不是半群,这里“一”和“/”分

别是普通的减法和除法。

定理3-1-3.1设VS,*＞是半群，B是S的非空子集，且二元运算*在B

上封闭的，即对任意的a/WB有a*6B。那么，＜B,*＞也是半群。通常称＜B,*

＞是＜5,*＞的子半群(sub-semigroup)

证明：因为运算*在S上是可以结合的，而B是S的非空子集且*在B是

上的封闭的，所以*在B上也是可结合的，因此，VB,*＞是半群。

例3-1-2.3设•表示普通的乘法运算，那么V{—1,1},・＞,＜[-1,1],

•＞和

＜2,・＞都是半群＜R,・＞的子半群。

解：首先，运算•在R上是封闭的，且是可结合的，所以＜1＜,・＞是半群。

其次，运算•在{-1,1},[—1,1]和Z上都是封闭的，{-1,1}」—1,1]和Z都是

R的非空子集，由定理3-1-3.1可知＜{-1,1},・＞、＜[-1,1],・＞和＜Z,

・＞都是＜R,・＞的子半群。

定义3-1-3.2半群VS,。＞中的任一元素a的方幕。定义为

a=a,a=aoa(M是大于等于1的整数)

可以证明，对于任意的aS和任意正整数机,〃都有

aoa=a

(a)=a

若a=a，则称a为基等元素(idempotentelement)o

定理3T-3.2设VS,*＞是半群，若S是一有限集，则S中有基等元。

证明：因为＜S,*＞是半群，对于任意yS的由运算*的封闭性可知,y=y*yS,

y=y*y=y*yS,因为S是有限集，所以必定存在正整数i,/使得且y=y

记机=j-i,则有y=y*y从而对任意〃＞i,

y=y*y=y*yy=y*y因为，〃2，1,所以总可以找至此＞1,

使得女机2i对于S中的元素y,

就有y=y*y=y*y*y

==y*(y*y)=•••=y^yo

所以a=y是S中的基等兀。

定义3T-3.3若半群＜S,。〉的运算。满足交换律，则称＜S,。〉是一个可

交换半群。

在可交换半群VS,。》中，有3。。)=。昉其中〃是正整数，a,bS。

定义3-1-3.4含有幺元的半群称为含幺半群或独异点(monoid)。

例如，代数系统＜R,・＞是含幺半群，其中R是实数集，•是普通乘法，这

是因为

＜1^,・＞是半群，且1是R关于运算•的幺元。

另外代数系统〈｛-1，1｝，*＞,＜[-1,1J,•＞,和＜Z,・＞都是具有幺

元1的半群。因此它们都是含幺半群。

设集合A=｛1,2,3，…｝则VA,+＞是半群但不含幺元。所以它不是含

幺半群。

例3-1-3.4设£是非空有限字母表，£*是£中的有限个字母组成的符号串

的集合，符号串中字母的个数“叫做这个符号串的长度，当加=0是用符号人表

示，叫做空串。在X*上定义连接运算贝2=。如若=5£乂1,=GROUP,

=SEMIGROUPo

代数系统〈£*,。〉是含幺半群，且幺元是A。

定理3-1-3.3设S是至少有两个元的有限集且VS,*＞是一个含幺半群，

则在关于运算*的运算表中任何两行或两列都是不相同的。

证明：设S中的关于运算*的幺元是e。因为对于任意a,bS的且ah是，

总有

e-ab-e^ba^e-ab-b*e

所以在运算*表中不可能有两行和两列是相同的。

定理3-1-3.4设是含幺半群，对于任意的，当均有逆元时，有

(1)

(2)有逆元，且。

证明：(1)因是的逆元，所以，从而由逆元的定义及唯一性得。

(2)因为

同理可证

所以，由逆元的定义及唯一性得。

例3-1-3.5设是整数集合，是任意正整数，是由模的同余类组成的集合，

在上分别定义两个二元运算+,”和X,”如下：

对任意的

试证明时，在这两个二元运算的运算表中任何两行或两列都不相同。

证明：考察非空集合上二元运算和x,”，

(1)由运算+,”和X,”的定义易得，运算+,“和X,”在上都是封闭的且都是可结

合的，所以，，都是半群。

(2)因，所以是中的幺元；因为，所以是中的幺元。

由上知，代数系统，都是含幺半群。从而由定理3-1-3.3知，中的两个运算,

的运算表的任何两行或两列都是不相同的。

下面表3-1-3.2和表3-1-3.3分别给出时，和的运算表，在这两个运

算表中没有两行或两列时相同的。

表3-1-3.2

4-,rmrnr?im

roiroirn⑵Hl

rnni⑵Hlroi

⑵⑵F31roirn

「31mmirn⑵

表3-1-3.3

Xiroirnr?iRI

101101roiroi101

mroirn⑵「31

F21roi⑵rm⑵

mroini171「11定

义

3-1-3.5设是含幺半群的子半群，且的幺元，则称为的子含幺半群（submonoid）。

由定义可得，子含幺半群也是含幺半群。

例3-1-3.6代数系统，中运算“”如表3-1-3.4所示。

易得是含幺半群且幺元为0;是的子半群且有幺元表3-1-3.4

1,从而是含幺半群，但不是的子含幺半群。

V01

证明：设是可换含幺半群且幺元为，，因为所以又001

因为对任意，有111

所以从而运算在上是封闭的，故是的子含幺半群。

如是含幺半群，中所有幕等元的集合为，所以是的子含幺半群。

§3-1-4群与子群

群是一种较为简单的代数系统，只有一个二元运算。当然这一运算还应满足

一定的条件。正是由于这些条件使我们能够利用这种运算系统去描述事物的对称

性和其他特性。群的理论在数学和包括计算机科学在内的其他学科的许多分支中

发挥了重要的作用，本节主要介绍群与子群的一些基本知识。

定义3-1-4.1设是一个代数系统，其中是非空集合，是上的一个二元运算,

如果

（1）运算。是封闭的；

（2）运算。是可结合的；

（3）中有幺元；

（4）对每个元素，中存在的逆元；

则称是一个群（Group）或简称是群。

由定义可得群一定是含幺半群，反之不一定成立。

例3-1-4.1若集合，定义二元运算。为，则是半群。事实上，由运算。的定

义可得，适合群定义的条件(1),(2),又是的幺元，的逆元是，所以是群。

例3-1-4.2有理数集关于普通加法构成群，幺元是，，的逆元是；类似地

若是整数集，则是群；但是只含幺元的半群而不是群。

例3-1-4.3设，二元运算“。”由表3-1-4.1给出，则是一个群。

表3-1-4.1

Oabc

aabc

bbca

ccab

事实上，运算在上是封闭的，是单位元，，但结合律是否成立不易从表上看

出，验证适合结合律比较麻烦，需要验证33=27次。但是，由于第一行、第一列

分别与表头的行列相同，故有，对任意的成立。这样，验证结合律的三个元中只

要出现，则必然是可结合的。因此，我们只要对不包含的任意三个元验证可结合

性即可，因而只需验证23=8次。这里，我们只验证一个，其余留作练习。

因此，是一个群。

定义3T-4.2设是一个群，如果是有限集，则称是有限群(finitegroup),中

的元素个数称为的阶(order)记为，如果是无限集，则称为无限群(infinitegroup),

也称的阶为无限。

如上面例3-1-4.1和例3-1-4.3中的群都是有限群，阶数分别为1和3,例

3-1-4.2中的群和都是无限群。

下面是群的一些基本性质

定理3-H4.1在群中，个元素的连乘积，经任意加括号计算所得的结果相

同。

证明：我们证明任意加括号得到的乘积都等于从左到右依次加括号计算所

得的结果，即等于

采用数学归纳法，当时，定理显然成立。现在假设对小于或等于个元素的连

乘积定理成立，则对个元素的连乘，，对任意加括号，不妨设最后时将与相乘，

下面对分三种情况讨论。

（1）,这时按归纳假设有

（2）,这时利用结合律和归纳假设可得

P=（«i。…。4T）°（氏。4+1）

=（（«i。…。*）。4）。4+1

=（•••（（«!°a2）oa3）--oak）ak+l

（3）这时用归纳假设，再对p的表达式用结合律和归纳假设，我们有

由数学归纳法原理知定理成立。

由这个定理知，在群中个元的连乘任意加括号进行计算所得最后结果是一样

的，故可以将其简记为而不致误解。特别当时可表示为。

由定理3-24.1的证明知，这个定理的结论在半群中成立。

与定理3-1-3.5类似，我们有以下结论

定理3-1-4.2设是群，则中任意个元有，对群中任一元素，我们约定

为正整数

我们容易得到以下结果

定理3-1-4.3若是群，则对任一元素和任意整数有

（1）

（2）

定理3-1-4.4在群中成立消去律，即对，

（1）若,则，

（2）若，则。

证明：（1）因为是群，，所以，存在的逆元，用从左边乘两边，可得

所以

（2）的证明与（1）类似。

定理3-1-4.5设是一个群，则对任意的有

（1）存在唯一的元素，使；

（2）存在唯一的元素，使。

证明：因为，所以至少有一个是满足。若是中另一个满足方程的元素，

则。由定理3-14.4知。因此，是中唯一满的元素。

（2）与（1）同理可证。

定理3-1-4.6是群，，则是幕等元当且仅当是的幺元。

证明：因为，所以是的事等元。

现设，，若，贝IJ

与矛盾。

由定理3-14.4知，有限群的运算表中，设有两行（或两列）是相同的。为

进一步考察群的运算表的性质，下面引进置换的概念。

定义3-1-4.3设是一个非空集合，从到的一个双射称为的一个置换

（permutation）。

例如对集合，是到的一个映射使得，，，，，则是到的一个双射从而是的一个

置换。也可用下表表示，

即表中上一行为按任何次序写出集合中的全部元素，而在下一行写出上一行

相应元素的象。

定理3-1-4.7有限群的运算表中的每一行或每一列都可由中的元素经一

个置换得到。

证明：设有限群，由的运算表的构造知，表中的第行元素为，，…，，且集

合是的子集，因为中消去律成立，所以当时，，从而。

作到的映射，。则是的一个置换，所以的运算表中的第行可由的元素通过置

换得到。对列的情形类似可证。

现在介绍子群。

定义3-1-4.4设是一个群，是的非空子集，如果也构成群，则称是的子群

（subgroup）o

定理3-1-4.8设是群的子群，则的幺元就是的幺元，中任意元在中的逆元

就是在中的逆元。

证明：设和分别是和的幺元，为在中逆元，则

又因为对任意，有

设是群，是的幺元，由子群的定义可得，都是的子群，称为的平凡子群(trivil

subgroup)e若是的子群且，，则称为的真子群(propersubgroup)。

例3-1-4.4是整数加群，，证明是的一个子群。

证明：因为，所以；

(1)对于任意的，可设，，，，，所以，即在上是封闭的；

(2)运算在上可结合，从而在上可结合；

(3)的幺元0在中也是的幺元；

(4)对与任意，有，，而

所以，使，是在中的逆元，所以是群，从而是的子群。

实际上，群的非空子集构成子群的条件可以简化如下。

定理3-1-4.9设是群，是的非空子集，则关于运算是的子群的充分必要

条件是：

(2)对任意的，有；

(2)对任意的，有。

证明：必要性显然成立。

充分性条件(1)说明运算在上是封闭的；由于中的运算是可结合的，所

以中运算是可结合的；对任意，由条件(2)知，，再由条件(1),易得是的单位

元，是在中的逆元，所以是群，从而是的子群。

定理3T-4.10设是一个群，是的非空子集，则关于运算是的子群的充分

必要条件是：对任意的有。

证明：必要性易得

充分性任取，由条件，即，又因为，所以，这说明，若，贝I」，由条件可得

根据定理3-148,是的子群。

定理3T-4.11设是一个群，是的一个有限非空子集，则关于运算是群的

子群的充分必要条件是：对任意的有。

证明：必要性由子群的定义可得

充分性设是中的任一元素，由条件，，…，因为是有限集，所以必存在正

整数和，使，，不妨设，则这说明是中的幺元，这个幺元也在子集中。

如果，那幺由知是的逆元且。如果，那么由知就是幺元且的逆元就是。总之

对任意元素，有。所以由定理3-1-4.9知是的子群。

例3-1-4.5设是群，，求证是的一个子群。

证明：设是群的幺元，贝IJ,又对任意的和任意的，有，，所以，从而。故。

由定理3-1-4.10知，是群的子群。这个子群称为群的中心。

例3-1-4.6设和都是群的子群，试证也是的子群。

证明：设是群的幺元，则因，都是的子群，所以，，从而。对任意的，有

.且，由，都是的子群，得且，所以，故是群的子群。

例3-1-4.7设是群，是的一个固定元，，则是的子群。

事实上，得幺元，对中的任意元和，由定理3-1-4.10知是的子群。

§3-1-5交换群与循环群置换群

这一节讨论几种具体的群，这种讨论不但能加深我们对群的认识，而且这几

种群本身在理论上和应用上都是非常重要的。

定义3-1-5.1如果群中的运算。是可交换的，则称该群为交换群

(commutativegroup),或称为阿贝尔(Abel)群。

例如，，，，都是交换群。

例3-1-5.1设集合，在上定义一个双射函数：，，，，并构造符合函数：对，

若用表示上的恒等映射，即，则有，设并构造集合。求证，是一个交换群。

证明：上的运算的运算表由表3-1-5］给出。可见上的运算是封闭的，由

的定义可得，运算是可结合的。是的幺元，

表3-1-5.1

O01a2a3

QO

00123

QQOGQ

11230

OaOOo

2231

QQQQ

33()12

QCTaoQ

的逆元是自身，和互为逆元，的逆元是它自身。由表3-I-5.1的对称性知,

上的运算是可交换的，所以是一个交换群。

例3-1-5.3设是一个大于1的整数，为所有阶非奇(满秧)矩阵的集合，

表示矩阵的乘法，则是一个不可交换群。

事实上，任意两个阶非奇矩阵相乘后还是一个阶非奇矩阵，所以上的运算是

封闭的；矩阵的乘法运算是可结合的；〃阶单位矩阵是中的幺元；任意一个非奇

的阶矩阵有唯一的阶逆矩阵也是非奇的且，但中的运算不是可换的，因此是一个

群，但不是交换群。

定理3-1-5.1设是一个群，则是交换群的充分必要条件是，对任意的，有

证明：必要性设是交换群，则对任意的有

因此

充分性若对任意，

则

所以即得

因此，群是交换群。

例3-1-5.2设是群，是的幺元，若对任意，都有，则是交换群。

证明：对任意的，由条件，所以，，，又所，从而，故是交换群。

定义3-1-5.2设是群，若中存在一个元素，使得中任意元素都是的暴，

即对任意的都有整数使，则称为循环群(cyclicgroup),元素称为循环群的生成元

(generator)o

例3-1-5.3是由1生成的无限阶循环群。

例3-1-5.4设是整数集，是一正整数，是由模的剩余类组成的集合，上

的二元运算定义为：对，

则是以山为生成元的循环群。

证明：由例3-1-3.5知，是含幺半群，幺元为［0］,又中，［0］的逆元是，

时:的逆元是，所以是群，又任意，有，所以是以［1］为生成元的循环群。称为

模的剩余类加群。

定理3-1-5.2任何一个循环群都是交换群。

证明：设是一个循环群，是它的一个生成元，那幺，对任意，必有使得，，

所以因此，是一个交换群。

对于有限循环群，有下面的结论。

定理3-1-5.3设是一个由元素生成的循环群且是有限群，如果的阶是，

即，则且其中是的幺元，是使的最小正整数（称为元素的阶）。

证明：因为是有限群，，所以，存在正整数s使，假设对某个正整数使，

那幺，由于是一个生成的循环群，所以中任何元素都能写成的形式。又，其中且。

这样就有，所以中每个元素都能写成的形式，这样中最多有个不同的元素，与

且矛盾，所以是不可能的。

下面证明是互不相同的，用反证法，若其中，就有且上面已经证明这是不可

能的。所以，是互不相同的，又，所以，，因为，，所以。

例3-1-5.5在模4的剩余类加群中，试说明［1］和⑶都是生成元。

解：因为，

所以山是循环群的生成元。

又因为

所以，［3］也是循环群的生成元。

从例3-1-5.5知，一个循环群的生成元可以不是唯一的。

下面讨论另一类重要的群一一置换群。

对于一个具有个元素的集合，将上所有个不同的置换所组成的集合记为。

定义3-1-5.3设，上的二元运算和使对，和都表示对的元素先作置换接

着再作置换所得到的置换。二元运算和分别称为左复合和右复合。

例3-1-5.6设，中的元素

则

因为都是上的双射变换，所以它们都有逆变换并II是置换。如的逆置换

易得是使中每个元素映射到自身的置换。

为确定起见，我们在下面只对左复合进行讨论。

定理3-1-5.4是一个群，其中是置换的左复合运算。

证明：首先证二元运算在上是封闭的，对任意的，若，，则因都是上的

双射变换，所以

从而

因而是上的单射。

对，因是上的双射变换，所以存在使，又是上的双射变换，所以存在使，从

而，即得是上的满射变换。故。

其次证明二元运算在上是可结合的且有幺元。

于，，记，，。

则,由于,

所以，，

同样地，由于，

所以，，

因此，

如果将S中的每个元素映射成它自身的变换，记为，则是双射变换，所以，

且对于任一个元素，都有，因此S"中存在幺元，称它为置换(identicalpermutation)。

最后，对于任意的，因为b是S上的双射变换，因此它有逆变换且也是S

上的双射变换，所以，由于，。将映射成当且仅当将y映射成为x,所以，是。

在〈中的逆元，故(是群。

定义3T-5.4的任何一个子群，称为集合S上的一个置换群(permutation

group)特别地，置换群称为n次对称群(symetricgroup)。

例3-1-5.7设写出S的对称群以及S上的其它置换群，并指出它们是否是

循环群？是否是交换群？

解：S的对称群为，

其中如图3-1-5.1所示，S3上左复合运算。如表3-1-52所示。

由表3-1-5.2可见，S3上的二元运算。不是可交换的，如

所以不是交换群，更不是循环群；容易得到S上的换群还有，，，，，它们都是

循环群，从而都是交换群。

表3-1-5.2

O

rrrr.c、r、rr.c「

rrr.f\■f\cf\、f\»f\=

rr.f\<t\t\Cf\1f\c，\

fTc<"、c<、•t'I\r<、1I\c

ECcCvfTiCcfTnCi

rr,f\4r\\C/\1f\，t\

rx「

§3-1-6陪集与拉格朗日定理

我们已经讨论了利用集合上的等价关系对集合进行划分（分解），本节研究

利用子群来对群进行划分（分解），从而研究群的一些性质。

我们从推广＜Z,+＞中“模相同余”的概念开始，易知，对a,bZ,,因此在

群中，，推广到一般的群，我们有

定义3-1-6.1设是群的子群，。，bG如果，则称。与。有二元关系RL（模

H左同余）。

即。

定理3T-6.1设vH,。＞是群＜G,。＞的子群，

则（1）RL是G上的一个等价关系；

（2）对任意其中是a所在的等价类，称为H的左陪集（leftcoset）；

（3）=（即aH与H之间存在双射

证明：（1）设a,b,cG,因为G的幺元eH,使a=a