离散数学及其应用-第2版 课件 第11章 代数系统

第11章代数系统1离散数学及其应用代数系统代数系统由集合和定义在集合上的运算构成，计算科学的研究也离不开抽象代数的应用。代数系统在自动机理论和形式语言、编码理论、软件理论等方面有着重要的应用。2第11章代数系统11.1代数系统的概念和性质11.2代数系统的同态和同构11.3半群11.4群11.5循环群和置换群11.6环和域311.1代数系统的概念和性质11.1.1二元运算及其性质定义11.1.1设A为集合，函数f:A

A

A称为A上的一个二元代数运算，简称二元运算。

由定义可知，A上的二元运算是一种特殊的函数，必须具有确定性和封闭性的特征，即A中元素的运算结果是唯一确定的且仍在A中。4二元运算例11.1.11）加法、乘法运算是正整数集上的二元运算，减法和除法不是。2）加法、减法、乘法运算是有理数集、实数集上的二元运算，除法不是。3）乘法和除法运算是非零实数集上的二元运算，而加法和减法运算不是。4）两个集合的并运算和交运算都是集合A的幂集P(A)上的二元运算。5）所有3阶实矩阵的全体组成的集合M对于矩阵的加法、减法、乘法都是M上的二元运算。5二元运算算符常用

、。、

、

、

等表示二元运算,称为算符。例：设f:A

A

A是A上的一个二元运算，对任意的x、y

A，如果f(<x,y>)=z,可用算符

简记为x

y=z，用前缀表示法可写成

(x,y)=z。这些算符除特别说明外，泛指抽象意义上的运算。6例题例11.1.2（1） 设M是所有n阶布尔矩阵的集合。对于A=,B=

M，定义A*B=,其中(i,j=1,…,n),则*运算为二元运算。（2） 设Z为整数集，对于任意a,b

Z，定义a*b=max{a,b},则*运算为二元运算。7二元运算的性质定义11.1.2设

是集合A上的二元运算，如果对于任意的x,y

A，都有

x

y=y

x，则称

运算满足交换律。

整数集Z上的加法运算和乘法运算满足交换律，对任意的x,y

Z，都有x+y=y+x和x

y=y

x成立，而减法运算不满足交换律。8二元运算的性质定义11.1.3设

是集合A上的二元运算，如果存在a

A，使得a

a=a，则称a是A中关于

运算的幂等元。如果对于任意的x

A，都有x

x=x，则称

运算满足幂等律。

整数集Z上，0+0=0，所以0是“+”运算的幂等元；对任意的x

Z，x+x

x，除非x=0，所以整数集上的加法运算不满足幂等律。

集合的幂集上的“

”和“

”运算满足幂等律。9二元运算的性质定义11.1.4设

是集合A上的二元运算，如果对于任意的x,y,z

A，都有x

(y

z)=(x

y)

z，则称

运算满足结合律。

整数集Z上的普通加法运算和普通乘法运算满足结合律，对任意的x,y,z

Z，都有(x+y)+z=x+(y+z)和(x

y)

z=x

(y

z)成立，而减法运算不满足结合律。

集合的“

”和“

”运算满足结合律。10二元运算的性质定义11.1.5设

是集合A上的二元运算，若存在a

A,对于任意的x,y

A，如果a*x=a*y，那么x=y，则称a在A中关于*运算是左可消去元。类似地，若存在a

A，对于任意的x,y

A，如果x*a=y*a，那么x=y，则称a在A中关于*运算是右可消去元。如果a既是左可消去元，又是右可消去元，则称a是A的可消去元。若A上的所有元素都是关于*运算的可消去元，则称*运算满足消去律。整数集Z上的普通加法运算满足消去律，普通乘法运算不满足消去律。11二元运算的性质定义11.1.6设*、

是集合A上的二元运算，如果对于任意的x,y,z

A，都有x*(y

z)=(x*y)

(x*z))，则称*运算对

运算左可分配。如果对于任意的x,y,z

A，都有(y

z)*x=(y*x)

(z*x))，则称*运算对

运算右可分配。如果*运算对

运算既左可分配，又右可分配，则称*运算对

运算满足分配律。整数集上的普通乘法对加法满足分配律，加法对乘法不满足分配律。集合上的并运算对交运算满足分配律，交运算对并运算也满足分配律。12二元运算的性质定义11.1.7设*、

是集合A上的二元运算，如果*和都可交换，并且对于任意的x,y

A，都有x*(y

z)=x和x

(x*y)=x，则称*运算对

运算满足吸收律。整数集上的普通乘法对加法，加法对乘法都不满足吸收律。集合上的并运算对交运算，交运算对并运算满足吸收律。13例题例11.1.4设

是集合A上的二元运算，其运算表如下：运算

满足结合律、交换律、消去律、幂等律吗？为什么？解：不满足结合律、交换律、消去律

满足幂等律14

a1a2a3a4

a1a2a3a4

a1a2a3a4

a2a2a1a2a3a1a3a4a4a3a4a411.1.2.代数系统和子系统代数系统定义11.1.8设A是非空集合，

1、

2、…

m是定义在A上的各种运算，称集合A和定义在A上的各种运算

1、

2、…

m组成的系统为代数系统，记为<A,

1、

2、…

m>.

由定义可知,代数系统包括非空集合A，称为代数系统的载体，以及A上的运算，这些运算可以是一元运算、二元运算或多元运算，并且要求这些运算关于A满足封闭性。

15例题例11.1.5（1）对于设R表示实数集R，<R,+>，<R，

>和<R，+，

>都是代数系统，其中“+”、“

”分别为实数R上的普通加法、乘法运算。（2）对于集合A的幂集P(A)，<P(A),∪>，<P(A),∩>和<P(A),∪,∩,~>都是代数系统，其中“∪”、“∩”、“~”是集合的并、交、补运算。（3）设Zn={0，1，2，…，n-1},<Zn,+n>和<Zn,

n>都是代数系统，其中+n和

n分别表示模n加法和模n乘法，即x+n

y=(x+y)modn,x

n

y=(xy)modn.（4）对于全体n

n实数矩阵组成的集合M，<M,○>是代数系统，其中“○”为矩阵乘运算。16子代数系统定义11.1.9 设<A,

1、

2、…

m>是代数系统，,如果B

A，且B

，运算

1、

2、…

m对B封闭．则称<B,

1、

2、…

m>也是一个代数系统，称为代数系统<A,

1、

2、…

m>的子代数系统，或子代数（subalgebra）。如果B

A，则称<B,

1、

2、…

m>是<A,

1、

2、…

m>的真子代数。对任何代数系统A，它的子代数一定存在，因为任何代数系统都是它自身的子代数。17例题例11.1.6对<R，＋>而言，<N，+>为其真子代数，+是普通加法运算。<N，−>，不是<R，−>的子代数，因为普通减法“−”对自然数集合N不满足封闭性。

子代数是抽象代数中的一个重要概念。当原来代数系统的运算满足某些运算律，在它的子代数中也满足相同的运算律，也就是子代数和原来的代数系统是同种的代数系统。因此，可以通过研究子代数的结构和性质，得到原代数系统的某些性质。1811.1.3代数系统的性质

一些代数系统所规定的运算中，有些元素呈现出与其他元素很不同的性质，称这些有特殊性质的元素为特异元素，这些特异元素又称为代数系统的代数常数。特异元素的存在反映了代数系统的一些性质，。19幺元（单位元）定义11.1.10设<A,

>是代数系统，

是A上的二元运算，

如果存在el

A

，对任意元素x

S满足

el

x=x

，则称el为A中关于

运算的左幺元，或称左单位元。

如果存在

er

A，对任意元素x

S满足x

er=x，则称er为A中关于

运算的右幺元，或称右单位元。

如果存在

e

A，对任意元素x

S满足x

e

=e

x=x，则称e为A中关于

运算的幺元，或称单位元。

显然，幺元e既是左幺元又是右幺元。20例题（1）<R，+>中的数零0,<P(A),∪>中的

,以及<P(A),∩>中的集合A,分别是这三个代数系统的关于“+”，“∪”，“∩”运算的幺元，因为对任意x

R，x+0=0+x=x或S

ρ(A)),S∪

=

∪S=S,S∩A=A∩S=S21例题（2）设Zn={0，1，2，…，n-1},+n和

n分别表示模n加法和模n乘法，即x+ny=(x+y)modn,x

ny=(xy)modn。在<Zn,+n>中0是幺元，<Zn,

n>中1是幺元，因为对任意x

Zn，x+n0=0+n

x=x,x

n1=1

n

x=x（3）设A={a，b，c},A上运算*由运算表给出，那么a，c都是<A,*>的左幺元，它没有右幺元和幺元。注意，左幺元、右幺元，幺元未必总是存在。22

abcabcabccababc代数系统的性质定理11.1.1.设<A,

>是代数系统，

是A上的二元运算，el和er为A中关于

运算的左幺元和右幺元。如果<A，

>有关于

运算的幺元e，则幺元是唯一的，而且er=el=e。证：设<A，

>有幺元e和e

,那么

e=e

e=e

故幺元是唯一的。设er，el

为<A，

>的左、右幺元,那么

er=el

er=el

因此er(el)即幺元e，即er=el=e。23零元定义11.1.11设<A,

>是代数系统，

是A上的二元运算，

如果存在θl

A

，对任意元素x

A满足θl

x=θl

，则称θl为A中关于

运算的左零元。

如果存在

θr

A，对任意元素x

A满足x

θr=θr，则称θr为A中关于

运算的右零元。

如果存在

θ

A，对任意元素x

A满足x

θ

=θ

x=θ，则称θ为A中关于

运算的零元。

显然，零元θ既是左零元又是右零元。24例题（1）<R，

>（

为普通乘法运算）中的数0，<P(A),∪>中的集合A，<P(A),∩>中的

，分别是这三个代数系统的关于运算“

”,“∪”，“∩”的零元．（2）设Zn={0，1，2，…，n-1},+n和

n分别表示模n加法和模n乘法，即x+ny=(x+y)modn,x

ny=(xy)modn。在<Zn,+n

>中不存在零元，<Zn,

n>中0是零元。25零元定理11.1.2设<A,

>是代数系统，

是A上的二元运算，θl和θr为A中关于

运算的左零元和右零元。如果<A，

>有关于

运算的零元θ，则零元是唯一的，而且θr=θl=θ。26逆元定义11.1.12 设<A,*>是代数系统，*是A上的二元运算，e是A中关于*运算的幺元，对于一个元素a，b

A，（1） 如果a*b=e，则称a是b的左逆元，b是a的右逆元。（2） 如果a*b=b*a=e，则称a可逆，b是a的一个逆元，或称b可逆，a是b的一个逆元.根据上述定义可知：a的逆元既是左逆元，又是右逆元。对于幺元e，有e*e=e*e=e,所以幺元的逆元就是它自身。通常a的逆元记为a-1。但当运算是普通加法运算“+”时，a的逆元可记为−a。27例题（1）代数系统<M,

>，其中M为所有阶方阵组成的集合，“

”为普通矩阵的乘法运算，则阶单位矩阵为幺元，只有所有可逆矩阵有逆元，不可逆矩阵都没有逆元。（2）代数系统<Z，+，

>,其中Z为整数集，“+”为普通加法运算，“

”为普通乘法运算，Z的每个元素x对加法运算均有逆元-x，但除1以外的数对乘法运算都没有逆元。（3）代数系统<Q，+，

>，其中Q为有理数集，“+”为普通加法运算，“

”为普通乘法运算，Q中每个元素x,对加法运算，Q中每个元素x，都有逆元-x，。对乘法运算，0无逆元，除0以外的每个元素x对乘法运算都有逆元x-1=1/x。28逆元定理11.1.3设<A,*>是代数系统，*是A上的二元运算，*满足结合律，e为A中关于*运算的幺元。对于a

A，如果存在左逆元bl和右逆元br，则bl=br=b，b是逆元，而且是关于*运算的唯一逆元。证：如果存在左逆元bl和右逆元br，则有bl*a=e和a*br=e因为*满足结合律，所以有bl=bl*e=bl*a*br=(bl*a)*br=e*br=br即bl*a=e=a*br=a*bl，所以bl=br=b。再证逆元是唯一的。对于a*A，存在逆元，假设b和b

都是a的逆元，则有：

a*b=b*a=e，

a*b

=b

*a=e由于*满足结合律，所以有

b=e*b=(b

*a)*b=b

*(a*b)=b

*e=b

，即a的逆元是唯一的。29逆元定理11.1.4 <A,*>是代数系统，*运算满足结合律,对于a

A，a有逆元，那么a是可消去元。证设a的逆元为a-1,那么由a*x=a*y可得

a-1*(a*x)=a-1*(a*y)由于*运算满足结合律，所以有(

a-1*a)*x=(a-1*a)*y

,即e*x=e*y,可推得x=y。因此，a是可消去元。注意：当a是可消去元时，a不一定是可逆的。例如<N,+>中，任一非零元素a均是可消去元，但a无逆元。3011.1.4代数系统的分类定义11.1.13 设<A,

1、

2、…

m>和<B,

1、

2、…

k>是两个代数系统，如果k=m，对应的运算

i

和*i都是ki元运算，i=1,2,…,k，而且两个代数系统的代数常数也相同，则称这两个代数同类型。例如代数系统<R，+，

>和<P(A),∪,∩>是同类型的，它们都含有两个二元运算。31代数系统的分类定义11.1.14设<A,

1、

2、…

m>和<B,

1、

2、…

m>是两个同类型的代数系统，对应的运算

i

和*i

所规定的运算性质也相同，i=1,2,…,k，则称这两个代数同种。例如定义代数系统时规定：第一个二元运算满足结合律和交换律，第二个二元运算满足结合律，第二个二元运算对第一个二元运算满足分配律，代数系统<R，+，

>和<P(A),∪,∩>是同种的。如果还规定第一个二元运算有幺元，而且每个元素都有逆元，那么代数系统<R，+，

>和<P(A),∪,∩>不是同种的，因为不是P（A）的元素对∪都可逆。3211.2代数系统的同态和同构定义11.2.1设<A,*>及<B,·>均为同类型的代数系统，f是A到B的映射，对任意的a,b

A，有f（a*b）＝f（a）·f（b），则称函数f:A→B是从<A,*>到<B,·>的同态映射，或同态（homomorphism）。当同态f为单射时，又称为单一同态；当f为满射时，又称为满同态；当f为双射时，又称为同构映射，或同构（isomorphism）。当两个代数系统间存在同态（或同构）映射时，也称这两个代数系统同态（或同构）。当f为<A,*>到<A,*>的同态（同构）时,称f为A的自同态（自同构）。通常用<A,*>∽<B,·>表示<A,*>与<B,·>同态，用<A,*>≌<B,·>表示<A,*>与<B,·>同构。33例题（1）设f:R→R为f（x）=2x（R为实数集）那么,f为<R,+>到<R,·>的同态。因为对任意实数x，y，有

f（x+y）＝2x+y

=2x·2x=f（x）·f（y）由f的定义还可知f为单一同态。（2）设f:Z→E为f(x)=2x,其中Z为整数集，E为偶整数集。因为对任意实数x，y，

f（x+y）＝2（x+y）=2x+2y=f（x）+f（y）而且f是双射函数，可知f为<Z,+>与<E,+>的同构映射。（3）设g:R→R为g(x)=kx（k为常实数），那么g为<R,+>到<R,+>的自同态，因为对任何实数x，y，

g（x+y）=k（x+y）＝kx+ky=g（x）+g（y）并且在k0时，g为自同构。34例题35例11.2.2证明代数结构<N,+>与<N,·>不同构。

证

反证法。设<N,+>与<N,·>同构，f为任一同构映射。

不失一般性，设有n，n≥2，f(n)为一质数p

。于是

p=f（n）=f(n+0)=f(n)·f(0)

（11.1）

p=f（n）=f(n−1+1)=f(n−1)·f(1)（11.2）据式（11.1）,f（n）=1或f（0）=1；据式（11.2），f（n−1）=1或f（1）=1。总之，至少在两处f的值为1，这与f为同构映射（双射）冲突．因此<N,+>与<N,·>不同构。同态的性质定理11.2.1

设f为代数系统<A,

>到<B,·>的满同态，则若运算

可结合，则运算·也可结合。若运算

可交换，则运算·也可交换。若<A,

>有幺元e、零元θ和幂等元a，则f(e)、f(θ)和f(a)分别是<B,·>的幺元、零元和幂等元。若x-1是x在<A,

>上的逆元，则f(x-1)是f(x)在<B,·>上的逆元。36证明（1)证明：（1）对任意x,y,z

B，因为是满射，所以存在a,b,c

A，使得f(a)=x，f(b)=y，f(c)=z，由于运算

可结合，则有(a

b)

c=a

(b

c),因而有（x·y）·z=(f(a)·f(b))·f(c)=(f(a

b))

f(c)=f((a

b)

c)=f(a

(b

c))=f(a)·(f(b)·f(c))=x·（y·z）所以，运算·满足结合律。（2）证明方法类似（1），略。37证明（2）（3）对任意x，存在a

A，使得f(a)=x，若<A,

>有幺元e，则有e

a=a

e=a,因而有f(e)

·f(a)=f(e

a)

=f(a

e)=f(a)·f(e)=f(a),即f(e)·x=x·f(e)=x,所以f(e)是<B,·>的幺元。类似地可以证明，f(θ)和f(a)分别是<B,·>的零元和幂等元。（4）设<A,

>的幺元为e，根据（3）f(e)是<B,·>的幺元。因而有f(x-1)·f(x)=f(x-1

x)=f(e)f(x)·f(x-1)=f(x

x-1)=f(e)所以，f(x-1)是f(x)在<B,·>上的逆元。38同态像定义11.2.2

设f为代数系统<A,

>到<B,·>的同态映射，那么称f（A）为同态象（image

under

homomorphism），其中f(A)={f(x)|x

A}。定理11.2.2

设f为代数系统<A,

>到<B,·>的同态，那么同态象f（A）与·构成<B,·>的一个子代数<f（A）,·>。证只要证f（A）非空，且对运算·封闭．因为A为非空集合，所以f（A）是B的非空子集是显然的。设a，b为f（A）中任意两个元素，则存在x,y

A,使得f（x）=a,f（y）=b．那么

x·y=f（a）·f（b）=f（a

b）

f（A）故f（A）对运算·封闭，<f（A）,·>为<B,·>的子代数。3911.3半群定义11.3.1在代数系统<S，

>中，如果二元运算

满足结合律，则称代数系统<S，

>为半群（semigroups）。当半群<S，

>含有关于

运算的幺元e，则称它为含幺半群，或独异点（monoid）．独异点有时记做<S，

，e>。例如<Z，＋>，<N，＋>，<R，＋>都是半群，+是普通加法，因为+运算满足结合律。它们都含有关于+运算的幺元，也是独异点．40例题

例11.3.1设Zn={0，1，2，…，n-1},

n为模n乘法运算，即x

n

y=xy（mod

n）.证明：<Zn，

n>为含幺半群。

根据定义，代数系统是半群的充分必要条件是其上的运算是封闭的和可结合的。因此这里需要证明运算

n在Zn上是封闭的，可结合的，且幺元存在。41证明证明：（1）

x,y

Zn，令k=x

n

y=xy（mod

n）,则有0

k

n-1,即k

Zn，封闭性成立。（2）

x,y,z

Zn，假设u=x

n

y,v=y

n

z,有xy-u和yz-v都能被n整除，因而有uz-xv=x(yz-v)-(xy-u)z故uz-xv能被n整除，所以，u

nz=x

nv，即(x

n

y)

n

z=x

n(y

n

z)结合律成立。（3）

x

Zn，有x

n1=1

n

x=x1是幺元。所以<Zn，

n>为含幺半群。42半群定义11.3.2设代数系统<S，

>为半群，如果二元运算

满足交换律，则称代数系统<S，

>为可交换半群（semigroups）。当它含有关于

运算的幺元e，则称为可交换含么半群，或可交换独异点（monoid）。43例题设S是一个集合，P(S)是S的幂集，试证明：代数系统<P(S),∪>和<P(S),∩>都是可交换的含幺半群。证明：集合的“∪”,“∩”运算是可交换和可结合的，所以代数系统<P(S),∪>和<P(S),∩>都是可交换的半群。因为对任意集合A

P(S)，都有A∪

=A=

∪A，A∩S=A=S∩A，所以

是<P(S),∪>的幺元，S是<P(S),∩>的幺元。因此，代数系统<P(S),∪>和<P(S),∩>都是可交换的含幺半群。44定理11.3.1设<S，

>为一半群,若对于任意A

S，且A

，运算

对A封闭，则<A，

>是半群，称为<S，

>的子半群．若<S，

>为独异点，幺元e

A，则<A，

，e>是独异点,称为<S，

,e>的子独异点．

半群<S，

>的任一子代数都是半群，独异点<S，

，e>的子代数含有么元e，则它必为一独异点．证明较简单，不赘述．45半群及独异点的性质半群在半群<S，

>中，因为*运算满足结合律，对于元素a

S，可以定义a的幂：显然an

S。如果<S，

>存在幺元，设幺元为e，则增加规定容易证明，对

m,n

N，幂运算满足如下规则：46例题

例11.3.1设<S，

>是半群，对于元素a

S，由a的正整数幂构成的集合M={an|

n

Z+}，证明<M，

>是<S，

>的子半群。证明：因为a=a1

M,所以M是非空集合。根据元素的幂的定义，对于

n

Z+,an

S所以M是S的非空子集。对于其中，则因而故*运算对M是封闭的。所以<M，*>是<S，*>的子半群。47循环半群定义11.3.3若<S，

>是半群，如果存在一个元素a

S，使得对任意的x

S，有x=an,

其中n

Z+，则称<S，

>是循环半群，并称a为该循环半群的一个生成元，M={a|a

S

a是S的生成元}称为该循环半群的生成集。如果知道循环半群<S，

>的生成元a，则S中的所有元素都可以用a的幂表示，即S={a1,a2,…an,…}，所以，可记循环半群<S，

>为<<a>，

>。48例题判断<N，+>是否是一个循环含幺半群？解因为存在元素1

N，对任意的n

N，有n=（n-1）+1=1+1+1+…+1=1n，对幺元0，有0=10，因而1是生成元，所以<N，+>是一个循环含幺半群。4911.4群定义11.4.1设<G，

>为二元代数系统，如果

运算是可结合的二元运算，存在幺元e

G，对任意x

G，都有x的逆元x-1，则称二元代数系统<G，

>为群（groups）。

根据定义，群是含幺半群，而且每个元素都是可逆的．通常用字母G表示群。5011.4群定义11.4.2在群<G，

>中，

（1）若

运算满足交换律，则称G为交换群或阿贝尔群（Abel

group）．

（2）G为有限集时，称G为有限群（finite

group）,此时G的元素个数也称G的阶（order）；否则，称G为无限群（infinite

group）．（3）只含幺元的群称为平凡群。51例题11.4.152例题11.4.253

设Zn={0，1，2，…，n-1},+n为模n加法运算，即x+n

y

=x+y（mod

n）.证明：<Zn，+n>为一阿贝尔群。证明：需要证明+n运算在Zn上是封闭的，满足结合律和交换律，幺元存在，G中每个元素的逆元都存在。（1）

x,y

Zn，令k=x+n

y=xy（mod

n）,则有0

k

n-1,即k

Zn，封闭性成立。（2）

x,y,z

Zn，假设p=x+n

y,q=y+n

z,有x+y-p和y+z-q都能被n整除，因而有(p+z)-(x+q)=(y+z-q)-(x+y-p)，故(p+z)-(x+q)能被n整除，所以，p+nz=x+nq，即

(x+n

y)+n

z=x+n(y+n

z)，所以结合律成立。（3）

x

Zn，有x+n0=0+n

x=x，所以0是幺元。

(4)

x

Zn，如果x

0有x+n(n-x)=0=(n-x)+n

x,即x的逆元是n-x；如果

x=0,x+n0=0+n

x=0。所以，Zn中的所有元素都是可逆的。（5）+n运算在Zn上显然满足交换律。因此，<Zn，+n>为一阿贝尔群。

元素的幂定义11.4.3 设<G，*>为群，对任意a

G，可以定义a的幂：

幂指数n在群中可以取负整数，例如在群<Z,+>中，有2-2=（2-1）2=(-2)+(-2)=-454元素的阶定义11.4.4设<G，

>为群，a

G，如果an=e,且n为满足此式的最小正整数，则称a

的阶(order)为n，或称a

为n阶元，若这样的正整数n不存在时,称a有无限阶，或称a

为无限阶元。55例题例11.4.4

(1) 群<Z,+>的幺元为0，01=0，所以0是1阶元，对于任意非0整数a,an=a+a+…+a=na

0，a是无限阶元，所以除0外的其它整数都是无限阶元。(2) 在群<Z4,+4>中，22=2+2（mod4）=0，所以2的阶是2，可以求得：1的阶是4，3的阶是4，0的阶是1。例11.4.5 计算群<G，

>中元素的阶，G={1，-1，i，-i}，

是普通乘法。解1的阶为1，-1的阶为2，i，-i的阶都为4。56注意(1)幺元的阶为1，而且只有幺元的阶为1；(2)元素的阶总是正整数，0和负数不能作为元素的阶；(3)a为n阶元实际上是要同时满足下面两个条件：

1）存在正整数n,使得；

2）对于任何对群<G，*>的任意元素a，及任何整数m，n,有以下两式成立：

（1）am

an

=am+n

（2）(am)

n

=amn57群的性质定理11.4.1 设<G，*>为群，有设<G，

>为群，有（1）对

a

G，(a-1)-1＝a（2）G的所有元素都是可消去的．

（3）幺元是G的唯一的等幂元素.

（4）对

a,b

G，

（5）当G

{e}时,G无零元．（6）对

a,b

G，关于x的方程a

x＝b，x

a＝b都有唯一解．（7）群<G，

>的运算表中任意一行（列）都没有两个相同的元素。

58子群定义11.4.5设<G，

>为群，如果<H，

>为<G，

>的子代数，且<H，

>为一群，则称<H，

>为<G，

>的子群(subgroups)。若H

G，称<H，

>为<G，

>的真子群。根据定义，<{e}，

>和<G，

>均为<G，

>的子群，称为<G，

>的平凡子群。<G，

>的其它子群则称为非平凡子群或真子群。59例题（l）<{0,3}

,+6>和<{0,2,4}

,+6>是群<Z6,+6>的真子群。

（2）<nZ,+>是<Z,+>的子群，n是自然数，当n≠1时是真子群。

对于群<G，

>，若H是G的非空子集，可以根据定义判断H是否是子群，除此之外，还可以由以下的定理判断子群．60定理11.4.2设<G，

>为群，H是G的非空子集，那么<H，

>为<G，

>的子群的充分必要条件是

（l）若a，b

H

，则a

b

H

．

（2）若a

H，则a-1

H．

证明先证必要性．若<H，

>为<G，

>的子群，

对H满足封闭性，H中的每个元素都可逆，所以（1）（2）显然成立。再证充分性.事实上满足条件（1），（2）便可知

对H满足封闭性，H中的每个元素都可逆。因为H是G的子集，

在G上满足结合律，

在H上也满足结合律。最后只需证明G的幺元e

H。若a

H，根据条件（2），a-1

H．再由条件（1）有a

a-1

H，而a

a-1=e为G的幺元，所以e

H。因而，<H，

>为<G，

>的子群。61定理11.4.362设<G，

>为群，H是G的非空子集，那么<H，>为<G，>的子群的充分必要条件是：对a，b

H

，都有a

b-1

H

．证明充分性：即证如果对a，b

H

，都有a

b-1

H，则<H，>为<G，>的子群。对a

H

，根据给定条件，有a

a-1

H，即幺元e=a

a-1

H。由e,a

H，则有e

a-1

H，因而a-1

H。对a，b

H，知b-1

H，根据给定条件，有a

(b-1)-1

H，即a

b

H。满足定理11.4.2的两个条件，<H，>为<G，>的子群。必要性：如果<H，>为<G，>的子群，根据定理11.4.2条件（2），则对a，bH，有b-1H，再根据条件（1）,有ab-1H。例题63例题例11.4.7设<G，

>是一个群，对任意的a

G，令S={an|n

Z，Z是整数集}，证明<S，

>是<G，

>的子群。证明

因为a

S，所以S是G的非空子集。对

x,y

S，则存在n,m

Z，则由n,m

Z，有n-m

Z，所以an-m

S，由定理11.4.3可知<S，

>是<G，

>的子群。6411.5循环群和置换群循环群定义11.5.1如果<G，

>为群，且G中存在元素g

G，使得对

a

G，都有a=gi

（i

Z,Z为整数集合），则称<G，

>为循环群(cyclic

group)，记做G=<g>，并称g为循环群G的生成元（generater），G的所有生成元的集合称为G的生成集。

根据循环群的定义，判断一个群是否是循环群，需要说明其生成元存在。65例题66循环群67定理68循环群的子群定理11.5.3对于循环群G=<g>，（1）循环群G的子群都是循环群．（2）若G=<g>是一个n阶循环群，则由n的一切因子d都可对应产生一个且仅一个d阶子群<gn/d>.69证明证明（1）设<G，

>为g生成的循环群，<H，

>为其子群．当然，H中元素均可表示为gr．

若H＝{e},显然H为循环群．

若H

{e}，那么H中有gi(i

0)．由于H为子群，H中必还有g-i.因此，不失一般性，可设i为正整数，并且它是H中元素的最小正整数指数．现证明H为gi生成的循环群．

设gj为H中任一元素．令j＝mi+r，其中m为i除j的商，r为剩余，0≤r＜i．于是

gj

=gmi+r＝gmi

gr

gr=g-mi

gj由于gj,g-mi

H，（因gmi

H），故gr

H，根据i的最小性，r＝0，从而gj

=gmi=(gi)m，

H为循环群．

（2）的证明略。70置换群定义11.5.2设S为有限集合，|S|=n,S上的任何双射函数

：S

S，称为S上的一个n元置换．假设S={a1，a2，…，an}时，S上的n元置换

可表示为：71例题72一般地，S={a1，a2，…，an}时，S上有

n!个置换．

置换的复合运算定义11.5.3 设

1和

2是二个n元置换，

1和

2的复合

1o

2也是n元置换。例如上例中，

将n个元素的集合S上的置换全体记为Sn，对于置换的复合运算而言，n元置换的复合运算对Sn是封闭的，复合运算是可结合的，S上置换的全体中有幺元：恒等函数，又称幺置换，且每一置换都有逆置换，因此<Sn,○>是一个群。73置换群定义11.5.4将n个元素的集合S上的全体置换记为Sn，那么称群<Sn,○>为S上的n次对称群（symmetric

group