离散数学课件(第5章).ppt

离散数学教案,计算机科学与技术学院课程学时：64主 讲：宋 成,河南理工大学电子教案,本篇用代数方法来研究数学结构，故又叫代数结构，它将用抽象的方法来研究集合上的关系和运算。代数的概念和方法已经渗透到计算机科学的许多分支中，它对程序理论，数据结构，编码理论的研究和逻辑电路的设计已具有理论和实践的指导意义 本篇讨论一些典型的代数系统及其性质。,第三篇：代数系统,第五章：代数结构,5.1 代数系统的引入5.2 运算及其性质5.3 半群5.4 群与子群5.5 阿贝尔群和循环群5.6*陪集与拉格朗日定理 5.7 同态与同构5.8 环与域,第五章：代数结构,教学目的及要求：深刻理解和掌握代数系统的基本概念和运算教学类容：代数系统的引入、运算及性质、半群、群与子群、阿贝尔群和循环群、陪集与拉格朗日定理、同态与同构、环和域。教学重点：群、环、域的概念及运算，同态和同构。教学难点：同态与同构 的概念。,第五章：代数结构,5.1 代数系统的引入1、运算【定义5.1.1】设A是非空集合，一个从An到B的映射,称为集合A上的n元运算。简称为n元运算。如果B A，则称该n元运算是封闭的。在定义5.1中，当n=1时，f称为集合A上的一元运算；当n=2时，f称为集合A上的二元运算。在讨论抽象运算时，“运算”常记为“*”、“”等。设*是二元运算，如果a与b运算得到c，记作a*b=c；若*是一元运算，a的运算结果记作*a或*(a)。,第五章：代数结构,设A=1,a,，其中，a是非零实数。f定义为：aA，f(a)=。容易看出f是A上的一元运算。又如，f：m,nN，f(m,n)=mn，f是自然数集合N上的二元运算，它就是普通加法运算。普通减法也是自然数集合N上的二元运算，但是它不是封闭的，因为两个自然数相减可能得到负数，而负数不是自然数。所以普通的减法不是自然数集合N上封闭的二元运算。通过以上讨论可以看出，一个运算是否为集合A上的封闭运算必须满足以下两点：A中任何元素都可以进行这种运算，且运算的结果是惟一的。A中任何元素的运算结果都属于A。A中任何元素的运算结果都属于A通常称为运算在A是封闭的。,【例5.1】设N为自然数集合，*和是NN到N映射，规定为：m,nN，mn=minm,n mn=maxm,n则和是N上的二元封闭运算。【例5.2】设Nk=0,1,k-1。Nk上的二元运算+k定义为：对于Nk中的任意两个元素i和j，有 称二元运算+k为模k加法。,第五章：代数结构,第五章：代数结构,第五章：代数结构,2.运算的表示 表示运算的方法通常有两种：解析公式和运算表。解析公式是指用运算符号和运算对象组成的表达式。如 f(a)=，,运算表是指运算对象和运算结果构成的二维表。经常使用运算表来定义有限集合上的二元运算，特别当有限集合上的二元运算不能用表达式简明地表示时，借助于运算表来定义二元运算会带来方便。另外，运算表还便于对二元运算的某些性质进行讨论，更形象地了解二元运算的有关特征。设N4=0,1,2,3，N4上的模4加法4可以用运算表表示，它的运算表如表5.1所示。N4上的模4乘法4也可以用运算表表示，它的运算表如表5.2所示。,第五章：代数结构,3 代数系统【定义5.1.2】一个非空集合A连同若干个定义在该集合上的运算1,2,k所组成的系统称为一个代数系统，记作。根据定义，一个代数系统需要满足下面两个条件：有一个非空集合A。有一些定义在集合A上的运算。集合和定义在集合A上的运算是一个代数系统的两个要素，缺一不可。【例5.3】设B是一个集合，A=P(B)是A幂集合。集合的求补运算是A上的一元运算，集合的并和交运算是A上的是二元运算。于是构成一个代数系统，该代数系常称为集合代数。【例5.4】设R-0是全体非零实数集合，*是R-0上二元运算，定义为：a,b R-0，a*b=b。则是代数系统。,第五章：代数结构,5.2二元运算的性质 5.2.1运算的基本性质 1.交换律【定义5.2.1】设*是非空集合A上的二元运算，如果对于任意的a,bA，有ab=ba，则称二元运算在A上是可交换的，也称二元运算*在A上满足交换律。例如，设R为实数集合，对于任意的a,bR，规定 ab=(ab)2 ab=a2+b2 ab=a+bab则运算、和都是可交换的。2.结合律【定义5.2.2】设*是非空集合A上的二元运算，如果对于任意的a,b,cA，有(a*b)*c=a*(b*c)，则称二元运算*在A上是可结合的，也称二元运算在A上满足结合律,第五章：代数结构,实数集合上的普通加法和乘法是二元运算，满足结合律；矩阵的加法和乘法也是二元运算，也满足结合律。【例5.5】设*是非空集合A上的二元运算，定义为：a,bA，ab=b。证明运算*是可结合的。证明：对于任意的a,b,cA，有(ab)c=c，而a(bc)=ac=c，故有(ab)c=a(bc)，即运算是可结合的。当二元运算*在A上适合结合律时，在只有该运算符的表达式中，表示运算顺序的括号常被省略。所以将(x*y)*z=x*(y*z)常写成x*y*z。这样，可以令,第五章：代数结构,当运算*满足结合律时，an的也可以递归定义如下：a1=a an+1=ana 由此利用数学归纳法，不难证明下列的公式：aman=am+n(am)n=amn 3.分配律【定义5.2.3】设*和是非空集合A上的两个二元运算，如果对于任意a,b,cA，有a*(bc)=(a*b)(a*c)(左分配律)(bc)*a=(b*a)(c*a)(右分配律)则称运算*对运算是可分配的。也称运算*对运算满足分配律。,第五章：代数结构,【例5.6】设A=0,1，*和都是A上的二元运算，定义为：00=1*1=0，0*1=1*0=1 00=01=10=0，11=1 则容易验证对于运算*是可分配的，但*对于运算是不可分配的。如1*(01)=10=(1*0)(1*1)【定理5.2.1】设*和是非空集合A上的两个二元运算，*是可交换的。如果*对于运算满足左分配律或右分配律，则运算*对于运算是可分配的。证明：设*对于运算满足左分配律，且是可交换的，则对于任意a,b,cA，有(bc)a=a(bc)=(ab)(ac)=(ba)(ca)即(bc)a=(ba)(ca)故对于运算是可分配的。同理可证另一半。,第五章：代数结构,4.吸收律【定义5.2.4】设*和是非空集合A上的两个可交换的二元运算，如果对于任意a,bA，有 a*(ab)=a；a(a*b)=a则称运算和运算满足吸收律。【例5.7】设N为自然数集合，*和是集合N上的二元运算，定义为：aN，bN a*b=max(a,b)，ab=min(a,b)验证运算*和适合吸收律。解：aN，bN 若ab，a*(ab)=a*min(a,b)=a*b=max(a,b)=a 若ab，a*(ab)=a*min(a,b)=a*a=max(a,a)=a 若ab，a*(ab)=a*min(a,b)=a*a=max(a,a)=a 即 a*(ab)=a 同理可证a(a*b)=a 因此运算*和适合吸收律。,第五章：代数结构,5.幂等律【定义5.2.5】设*是非空集合A上的二元运算，如果对于任意的aA，有aa=a，则称运算*是幂等的或运算满足幂等律。如果A的某个元素a满足aa=a，则称a为运算*的幂等元。易见，集合的并、交运算满足幂等律，每一个集合都是幂等元。由定义不难证明下面定理。【定理5.2.2】设是非空集合A上的二元运算，a为运算的幂等元，对任意的正整数n，则an=a。5.2.2特殊元素 1.幺元【定义5.2.6】设是定义在集合A上的二元运算，如果有一个elA，对于任意的aA，有el a=a，则称el为A中关于运算的左单位元或左幺元；如果有一个erA，对于任意的aA，有a er=a，则称er为A中关于运算的右单位元或右幺元；如果在A中有一个元素，它既是左单位元又是右单位元，则称为A中关于运算的单位元或幺元。,第五章：代数结构,【定理5.2.3】设是定义在集合A上的二元运算，el为A中关于运算的左幺元，er为A中关于运算的右幺元，则el=er=e，且A中的幺元是惟一的。证明：因为el和er分别是A中关于运算的左幺元和右幺元，所以el=el er=er=e设另一幺元e1A，则e1=e1 e=e 2.零元【定义5.2.7】设是集合A上的二元运算，如果有一个lA，对于任意的aA都有l a=l，则称l为A中关于运算的左零元；如果有一个rA，对于任意的aA，都有a r=r，则称r为A中关于运算的右零元；如果A中有一个元素A，它既是左零元又是右零元，则称为A中关于运算的零元。,第五章：代数结构,【定理5.2.4】设是集合A上的二元运算，l为A中关于运算的左零元，r为A中关于运算的右零元，则l=r=，且A中的零元是惟一的。证明：因为l和r分别是A中关于运算的左零元和右零元，所以l=lr=r=设另一零元1A，则1=1=【定理5.2.5】设是集合A上的二元运算，集合A中元素的个数大于1。如果A中存在幺元e和零元，则e。证明：用反证法。设e=，那么对于任意的aA，必有 a=ea=a=，于是A中的所有元素都是零元，与A中至少有两个元素矛盾。,第五章：代数结构,3.逆元【定义5.2.8】设是集合A上的二元运算，e为A中关于运算的幺元。如果对于A中的元素a存在着A中的某个元素b，使得ba=e，那么称b为a的左逆元；如果存在A中的某个元素b，使得ab=e，那么称b为a的右逆元；如果存在着A中的某个元素b，它既是a的左逆元又是a的右逆元，那么称b为a的逆元。a的逆元记为a1。如果aA存在逆元a1A，那么称a为可逆元。一般地说，一个元素的左逆元不一定等于该元素的右逆元。一个元素可以有左逆元而没有右逆元，同样可以有右逆元而没有左逆元。甚至一个元素的左逆元或者右逆元还可以不是惟一的。【定理5.2.6】设为A中的一个二元运算，A中存在幺元e且每个元素都有左逆元。如果是可结合的运算，则在A中任何元素的左逆元必定是该元素的右逆元，且每个元素的逆元是惟一的。,第五章：代数结构,证明：设a,b,cA，b是a的左逆元，c是b的左逆元。于是(ba)b=eb=b，所以 e=cb=c(ba)b)=(c(ba)b=(cb)a)b=(ea)b=ab因此，b也是a的右逆元。设元素a有两个逆元b和d，那么b=be=b(ad)=(ba)d=ed=d故a的逆元是惟一的。4.消去律【定义5.2.9】设是集合A上的二元运算，为A中关于运算的零元，a,b,cA，a。如果 若ab=ac，便有b=c，则称运算满足左消去律，称a为运算的左可消元。若ba=ca，便有b=c，则称运算满足右消去律，称a为运算的右可消元。,第五章：代数结构,若运算既满足左消去律又满足右消去律，则称运算满足消去律，称a为运算的可消元。注意可消元a不能是零元。【定理5.2.7】设是A中可结合的二元运算，如果a的逆存在且a，则a为关于的可消元。证明：设b,cA，且有ab=ac或ba=ca。由于为可结合的二元运算、a的逆存在且a，则a 1(a b)=(a 1 a)b=e b=ba 1(a c)=(a 1 a)c=e c=c而 a 1(a b)=a 1(a c)于是b=c，同理由ba=ca，得b=c，故a为关于的可消元。,第五章：代数结构,【例5.8】实数集R上的下列二元运算是否满足结合律和交换律？ab=a+bab ab=(a+b)解：因为a,b,cR，有(ab)c=(a+b-ab)c=(a+b-ab)+c-(a+b-ab)c=a+b+c-ab-ac-bc+abc又 a(bc)=a(b+c-bc)=a+b+c-bc-a(b+c-bc)=a+b+c-ab-ac-bc+abc所以(ab)c=a(bc)因此运算满足结合律。又 ab=a+bab=b+aba=ba 所以运算满足交换律。因为a,b,cR，有(ab)c=(a+b)c=(a+b)+c)=(a+b+2c),第五章：代数结构,a(bc)=a(b+c)=(a+(b+c)=(2a+b+c)在一般情况下(a+b+2c)(2a+b+c)所以运算不满足结合律。而ab=(a+b)=(b+a)=ba所以运算满足交换律。【例5.9】在例5.8中，运算*是否有单位元，零元和幂等元？若有单位元，哪些元素有逆元？解：运算的定义为：ab=a+bab 若e是单位元，则对任意元素aR，有ae=ea=a，由于元素是可交换的，仅考虑ea=a，即ea=e+aea=a，于是eea=0，即e(1a)=0。由于a是任意的，要使上式成立，只有e=0。因此0是运算的单位元。,第五章：代数结构,若是零元，则对任意元素aR，有a=a=。仅考虑a=，即a=+aa=，于是aa=0，即a(1)=0。由于a是任意的，要使上式成立，只有=1。因此1是运算的零元。若aR是幂等元，则应有aa=a，即a+aa2=a。于是aaa=0，即a(1a)=0。要使上式成立，只有a=0或a=1。因此0或1是运算的幂等元。设b是a的逆元，则应有ab=a+bab=0(的单位元)，于是b=，因此对于R中的任何元素a(只要a1)均有逆元，其逆元是。,第五章：代数结构,5.3 半群【定义5.3.1】一个代数系统，其中S是非空集合，*是S上的一个二元运算，如果运算*是封闭的，则称代数系统为广群。【定义5.3.2】设是代数系统，*是S上的二元运算，如果*满足结合律，则称代数系统为半群。【例如】代数系统、R，、和都是半群。半群是一个非空集合和一个定义在其上的可结合二元运算组成的代数系统。设是半群，如果运算*又满足交换律，则称半群为可换半群。若S为有限集合，则半群称为有限半群。【定理5.3.1】设是半群，*是S上的二元运算，BS，如果*在B上是封闭的，则B，*也是半群。,第五章：代数结构,证明：因为*在B上是封闭的，所以*是B上的二元运算。B,*是代数系统。a,b,cB，由于BS，所以a,b,cS，又由于S,*是半群，所以(a*b)*c=a*(b*c)，故B,*是半群。【定义5.3.3】定理中的半群B,*叫做半群S,*的子半群。例如，因为QR且乘法在有理数集上是封闭的，由定理5.3.1和定义，Q,是R,的子半群，所以Q,是半群。类似的可以证明N,、0,1,和(0,1),是半群。【定理5.3.2】设S,*是半群，S是有限集，则必有aS，使得a*a=a 证明：bS，由*在S上的封闭性知：b2=b*bS b3=b2*bS,第五章：代数结构,因为S是有限集，所以必有ij使 bi=bj 令p=ji，则p=ji1，而j=p i bi=bj=bp+i=bp*bi 于是下式成立：bq=bp*bq qi 因为p=ji1，总可以找到k1，使得kpi 对于S中的元素bkp，就有 bkp=bp*bkp=bp*(bp*bkp)=b2p*bkp=b2p*(bp*bkp)=bkp*bkp 令a=bkp，a*a=a,第五章：代数结构,设I是正整数集合，是I上的普通加法，加法在正整数集合I上封闭且适合结合律。所以I,是半群。但因I是无限集，所以I中没有幂等元。【】设R是实数集，定义R上的二元运算*为：x,yR，x*y=x|y|其中x|y|为实数x与实数y的绝对值的乘法运算，证明是一个半群。证明：显然，x,yR，则x|y|R，故运算*在R上封闭。接下来只需验证*满足结合律。x,y,zR，有(xy)z=(xy)|z|=(x|y|)|z|=x|y|z|x(yz)=x|yz|=x|y|z|=x|y|z|所以，(xy)z=x(yz)，故是一个半群。【定义5.3.4】设G,*是半群，如果运算*的单位元eG，则称半群G,*为含幺半群或独异点。,第五章：代数结构,若G,*为独异点，且*是可交换的，则称G,*为可换的独异点。例如，设A是任一集合，P(A)是A的幂集合。集合并运算在P(A)上是封闭的，并运算的单位元P(A)，所以半群是独异点；交运算在P(A)上也是封闭的，交运算的单位元AP(A)，所以半群也是独异点。显然，并运算和交运算满足交换律。所以，它们都是可交换独异点。【定理5.3.3】设G,*是可交换的独异点，H为其所有幂等元的集合，则H,*为独异点。证明：a,bH，于是a*a=a，b*b=b。由*是可交换的，从而(a*b)*(a*b)=(a*b)*(b*a)=a*(b*b)*a=a*(b*a)=(a*a)*b=a*b于是a*bH，即*在H上封闭，显然HG，根据定理5.3.1，H,*是半群。因e*e=e，故eH。所以H,*为独异点。,第五章：代数结构,【定理5.3.4】设G,*是独异点，则在*的运算表中任何两行两列都不相同。证明：先证明任何两列不相同。设运算*的单位元是eG，xG，yG，xy 因为e*x=x，e*y=y，所以e*xe*y，这说明e所在行的元素是两两互不相同的且都是G的元素。故在*的运算表中任何两列是不相同的，至少e所在行互不相同。类似地可证任何两行是不相同的。【定理5.3.5】设是独异点，a,bG且a,b均有逆元，则,第五章：代数结构,(a1)1=a a*b有逆元，且(a*b)1=b1*a1证明：因a*a1=a1*a=e，故(a1)1=a 因(a*b)*(b1*a1)=(a*(b*b1)*a1=a*e*a1=a*a1=e,又(b1*a1)*(a*b)=(b1*a1)*(a*b)=b1*(a1*a)*b=b1*e*b=b1*b=e故(a*b)1=b1*a1,【定义5.3.5】设是半群，如果它的每个元素均为G的某元素a的某一方幂，则称半群为由a所生成的循环半群，而a称为半群的生成元素，并记(a)。【定理5.3.6】一个循环半群一定是可换半群。,第五章：代数结构,证明：设为由a所生成的循环半群，x,yG，则x=am，y=an，于是x*y=am*an=am+n=an+m=an*am=y*x即是可换半群。,5.4 群与子群 1、群,第五章：代数结构,【定义5.4.1】设G,*是代数系统，其中，G是非空集合，*是G上二元运算。如果 运算*在G上是可结合的。运算*的单位元eG。xG，有x1G。则称G,*为群。有时也可将群G,*简称为群G。根据定义，广群是一个非空集合和一个定义在非空集合的二元运算组成；半群是一个具有结合运算的广群；独异点是具有幺元的半群；群是每个元素都有逆元的独异点。,普通加法在I上是封闭的和可结合的，在I中有关于加法的单位元0，xI，有x1xI，所以I,是群。该群叫做整数加法群。,第五章：代数结构,乘法在Q-0上也是封闭的和可结合的，在Q-0中有关于乘法的单位元1，xQ-0，有x1 Q-0，所以Q-0,是群。用同样的办法可以证明R,是群，其中0是单位元，xR，x1xR。群R,叫做实数加法群；但R,不是群，因为对普通乘法，0的逆元是不存在的；而R-0,是群，其中1是单位元，xR-0，有x1=R-0。【例】设Ge,a,b,c，表5.3给出了*的运算表。证明G,*是群。,证明：由表5.3可以看出，*运算是封闭的和可结合的，在G中有关于*的单位元e。G中每个元素都是自己的逆元，即e1=e，a1=a，b1=b，c1=c。所以G,*是群。,第五章：代数结构,中的群G,*叫做Klein 四元群，简称四元群。Klein 四元群有以下4个特点：,e为G中的单位元。*运算是可交换的。G中每个元素的逆元都是自己。a,b,c三个元素中任何两个元素的*运算结果都等于第三个元素。由于群G中有幺元且每一个元素都有逆元，所以可以定义G中元素的0次幂和负整数次幂。定义x0=e，xG，nI+，定义xn(x1)n,【定义5.4.2】设是群，如果G是有限集，则称为有限群，如果G是无限集，则称为无限群。基数|G|称为群的阶数，简称群G的阶。【定理5.4.1】群中不可能有零元。证明：当群的阶为1时，惟一元素为幺元。设|G|1且群有零元。那么对群中任何元素xG，都有x=x=e，所以，零元就不存在逆元，这与是群相矛盾。,【定理5.4.2】设是群，对于a,bG，必存在惟一的xG，使得ax=b。证明：设a的逆元是a1，令x=a 1b，则 ax=a(a 1b)=(aa 1)b=eb=b若另有一解x1，满足ax1=b，则a 1(ax1)=a 1b 即x1=a 1b=x。,第五章：代数结构,【定理5.4.3】设是群，对于任意的a,b,cG，如果有ab=ac或者ba=ca，则必有b=c。证明：设ab=ac，且a的逆元是a 1，则有 a 1(ab)=a 1(ac)(a 1a)b=(a 1a)c即eb=ec，故b=c；当ba=ca时，同样可证得b=c。“对于任意的a,b,cG，如果有ab=ac或者ba=ca，则必有b=c。”即消去律。所以，定理可理解为：群中满足消去律。,第五章：代数结构,【定理5.4.4】在群中，除幺元e外，不可能有别的幂等元。证明：因为ee=e，所以e是幂等元。设aG且aa=a，则有a=ea=(a 1a)a=a 1(aa)=a 1a=e 即a=e。,2、子群【定义5.4.3】设是群，H是G的非空子集，如果也构成群，则称是的子群。由子群的定义可以看出，如果H是G的非空子集，考察H,*是否是群G,*的子群，应当验证：运算*在H上封闭。群G中的幺元eH。xH，有x1H【定理5.4.5】设是一个群，是的子群，则中的幺元e必定也是中的幺元。证明：设中的幺元为e1，对于任意aHG，有e1*a=a=e*a由消去律得e1=e。,第五章：代数结构,如果G,*是群，其中e单位元。e和G都是G的非空子集，e,*和G,*也都构成群，它们是G,*的子群，这是两个特殊的子群。【定义5.4.4】设G,*是群，e,*和G,*是G,*的子群，称为群G,*的平凡子群。子群的判定 用定义证明H,*是群G,*的子群，要验证三个条件。下面的定理说明，在有限群中，只需验证一个条件也能证明H,*是群G,*的子群。【定理5.4.6】设G,*是群，A是G的非空子集，如果A是一个有限集，只要运算*在A上封闭，则是G,*的子群。证明：G,*是群，则G,*是半群，由定理5.3.1知A,*是半群。以下证明A中有幺元e且A中每一个元素都有逆元。证明A中有幺元e。,第五章：代数结构,bA，因为运算*在A上封闭，所以 b2=b*bA b3=b2*bA 由于A是有限集，所以必存在正整数i和j，不妨设ij，使得bi=bj 从而有 bi=bi*bji和bi=bji*bi 根据群中的消去律得bji=e，即bji是群G,*的幺元。且这个幺元也在G的非空子集A中。证明S中每一个元素都有逆元。如果ji1，那么bji=b*bji1和bji=bji1*b，即bji1是b的逆元，b1=bji1且bji1A。如果ji=1，b=bji，那么b是幺元。所以b1=b。【例5.4.2】求群的所有非平凡子群。,第五章：代数结构,解:作N6=0,1,2,3,4,5上模6加法6的运算表，如表5.4所示。取N6的子集S1=0,2,4和S2=0,3，它们的运算表是表5.5和表5.6。从表中可以看出,模6加法6在S1和S2上封闭。所以和是群的子群。,第五章：代数结构,【定理5.4.7】设G,*是群，H是G的非空子集，如果对于H中的任意两元素a和b有a*b 1H，则是G,*的子群。证明：首先证明G中的幺元e也是H中的幺元。任取H中的元素a，因为aHG，所以e=a*a 1H且a*e=e*a=a，即e是H中的幺元。其次证明在H中的每一元素都有逆。对任意aH，因为eH，所以e*a 1H，即a 1H。最后证明*在H上封闭。对任意的a,bH，由上可知b 1H，而b=(b 1)1，所以a*b=a*(b 1)1H。因此，H,*是G,*的子群。元素的阶及其性质【定义5.4.5】设G,*是群，a是G中的元素。如果存在正整数n，使得an=e，则称元素a为有限阶元素，满足上述条件的最小正整数n称为元素a的阶数，记为|a|=n；如果不存在这样的正整数n，则称a为无限阶元素。,第五章：代数结构,显然，幺元e的阶数为1。【定理5.4.8】如果群G,*的一个元素a的阶是r，则ak=e当且仅当k是r的倍数。证明：设ak=e，下证k是r的倍数。设 k=tr+q(0qr)，e=ak=atr+q=atr*aq=(ar)t*aq=(e)t*aq=e*aq=aq，但是r是使得 ar=e的最小的正整数，故q=0，即k=tr。设k是r的倍数，即k=tr，下证ak=e ak=atr=(ar)t=et=e。【定理5.4.9】群中任何元素和它的逆元的阶数相同。证明：设a是群中任意元素，a的阶数为n，即an=e(e为群的幺元)。而(a1)n=(an)1=e1=e。所以a1为有限阶元素。设a1的阶数为m，mn。因为am=(am)1)1=(a1)m)1=e1=e。这与a的阶数为n相矛盾。所以a1的阶数为n。,第五章：代数结构,【定理5.4.10】设G,*是n阶群，a是G中的任意元素，|a|=k，则kn。证明：因为|G|=n，在n1个元素a，a2，an，an1中至少有两个相同。设ai=aj，1ijn1。aji=aj*ai=ai*ai=e，1jin。由定理5.4.8，kjin。所以kn。【定理5.4.11】设G,*是群,aG，|a|=k，令S=a,a2,ak，则S,*是G,*的子群。证明：aiS，ajS，当ijk时，ai*aj=aijS 当ijk时，ai*aj=ak*aijk=e*aijk=aijkS 所以*在S上封闭。根据定理，S,*是G,*的子群。,第五章：代数结构,5.5 阿贝尔群和循环群 1.阿贝尔群【定义5.5.1】是群，如果二元运算*是可交换的，则称该群为阿贝尔(Abel)群，或称可交换群。整数加法群I,中的加法运算是可交换的，所以，整数加法群是阿贝尔群，群R-0,中的乘法运算也是可交换的，所以，R-0,也是阿贝尔群。【定理5.5.1】设是群，则是阿贝尔群的充要条件是对任意的a,bG,有(a*b)*(a*b)=(a*a)*(b*b)证明：设是阿贝尔群，下证对任意的a,bG,有(a*b)*(a*b)=(a*a)*(b*b),第五章：代数结构,对任意的a,bG，有a*b=b*a，因此，(a*b)*(a*b)=a*(b*a)*b=a*(a*b)*b=(a*a)*(b*b)即(a*b)*(a*b)=(a*a)*(b*b)设对任意a,bG，有(a*b)*(a*b)=(a*a)*(b*b)，下证是阿贝尔群。ab=e*(a*b)*e=(a 1*a)*(a*b)*(b*b 1)=a 1(a(a*b)*b)*b 1=a 1*(a*a)*(b*b)*b 1=a1(a*b)*(a*b)*b1=(a 1a)*(b*a)*(b*b 1)=e*(b*a)*e=b*a 即得a*b=b*a，因此群是阿贝尔群。,第五章：代数结构,2.循环群【定义5.5.2】设G,*为群，若在G中存在一个元素a，使得G中的任意元素都由a的幂表示，则称群G,*为循环群，并记(a)。元素a称为循环群G的生成元。设G,*为循环群，元素a为循环群G的生成元。若元素a为有限阶元素，元素a的阶数|a|=r称为a的周期，若a为无限阶元素，则称a的周期为无限的。【例5.5.1】证明代数系统是循环群。证明：前面已经说明是群，0是单位元。0的逆元是0，xN6且x0，x1=6x。考察1N6 11=1 12=161=2 13=1261=261=3 14=1361=361=4,第五章：代数结构,15=1461=461=5 16=1561=561=0 由此可见，元素1是群的生成元，N6=(1)，是循环群。可以验证5也是群的生成元。【例5.5.2】证明整数加法群I,是循环群。证明：前面已证I,是群，0是单位元。考察1I 10=0 11=1 12=11=2 13=121=3 11=1 12=(11)2=(1)(1)=2 1n=n,第五章：代数结构,由此可见，元素1是群I,的生成元，I=(1)，I,是循环群。可以验证1也是群I,的生成元。设G,*是群,aG，|a|=k，令S=a,a2,ak，根据定理5.4.11，S,*是G,*的子群显然G,*的子群S,*是循环群，它的生成元是a，S=(a)【定理5.5.2】任何循环群必定是阿贝尔群。证明：设G,*是循环群，它的生成元是a，那么对于任意的x,yG，必有r,sI，使得x=ar,y=as而且x*y=ar*as=ar+s=sr*ar=y*x因此G,*是阿贝尔群。【定理5.5.3】设G,*是无限循环群，a是生成元，则a也是无限阶元素。证明：设a为有限阶元，|a|=n，令S=a,a2,an，an=e，amG，m=nqs，q,s是整数且0sn，am=anqs=(a n)q*as=(e)q*as=e*as=asS，GS，矛盾。所以a是无限阶的。,第五章：代数结构,整数加法群I,是无限循环群，其生成元是1或1，它们是无限阶元。对于有限循环群，有下面的定理。【定理5.5.4】设G,*是n阶循环群，a是生成元，则a的阶数也是n。证明：用反证法，设生成元a的阶数为k，kn，由定理知kn，由于ak=e，ak1=ak*a=e*a=a，ak2=ak*a2=e*a2=a2，所以a的幂只能是G中的k个元素a,a2,a3,ak，而不能表示G中的所有元素，与a是G的生成元相矛盾。在例中，群是6阶循环群，其生成元1和5，16=0，56=0，它们都是6阶元。【定理5.5.5】设G,*是n阶循环群，e是单位元，a是生成元。则G=a,a2,an。证明：令S=a,a2,an。aiS，因为a是G的元素，*在G上封闭，所以aiG，从而SG,第五章：代数结构,以下证明S中的元素是两两互不相同的。假设ai=aj，其中1ijn。于是ai=aj=ai*aji，1jin，即ai*e=ai*aji，有消去律得aji=e，这与a的阶数是n矛盾。所以S中的元素是两两互不相同的。故|G|=|S|=n，G=S=a,a2,an。在例5.5.1中，群是6阶循环群，其生成元是1和5，N6=1,12,13,14,15,16=5,52,53,54,55,56=0,1,2,3,4,5【定理5.5.6】设G,*是n阶循环群，a是G的元素，如果a的阶数是n，则a是群G,*的一个生成元。证明：令S=a,a2,an。由定理5.5.5的证明过程知S=G。所以xG，aiS，使x=ai，根据定义5.5.2，a是群G,*的一个生成元。】设G,*是无限循环群，a是生成元则群G,*的生成元只有a和a1两个。证明：根据定义5.5.2，G=(a)=ak|kI，akG，ak=(a1)k，即G中的任何元素都可以表示成a1的整数次幂，所以a1是生成元。,第五章：代数结构,再证G中只有a和a1两个生成元。假设b也是群G,*的生成元。即G=(b)=bk|kI，aG=(b)，tI使得a=bt，又由于bG=(a)，sI使b=as，从而得到a=bt=(as)t=ast，e=a*a1=ast*a1=ast1，因为a是无限循环群的生成元，所以st1=0，st=1，从而推出s=t=1或s=t=1，即b=a或b=a1。所以G中只有a和a1两个生成元。下面介绍循环群的子群的性质。【定理5.5.8】设G,*是循环群，a是生成元如果H,*是G,*的子群。则H,*也是循环群。证明：若H,*是G,*的平凡子群，则H=G或H=e。当H=G时，显然H,*是循环群；当H=e时，e是生成元。所以H,*是循环群。若H,*不是G,*的平凡子群。由于H不空，akH，k0(即ake)，(ak)1H。从而H含有a的某些正整数次幂，令A=k|akHk1kI，则A不空，从而有最小者，设,第五章：代数结构,最小者为r。以下证明ar是子群H,*的生成元。amH，如果r不能整除m，则m=rqs，q是整数，0sr，am=a rqs=(a r)q*as，as=(a r)q)1*amH，sA。但sr，这与r是A中最小者矛盾。此矛盾表明，amH，r能整除m，即am=arq=(ar)q，所以a r是子群H,*的生成元，H,*也是循环群。,第五章：代数结构,5.6陪集和拉格朗日定理【定义5.6.1】设是群的子群，a是G中任意一个元素，则称集合Ha=h*a|hH(aH=a*h|hH)为由a确定的子群H,*在群G,*中的右(左)陪集，简称为H关于a的右(左)陪集，a叫做右(左)陪集Ha(aH)的代表元。,【例】设G,*是Klein四元群，其中，G=e,a,b,c，二元运算*的运算表如表5.3所示。令H=e,a，H,*是G,*子群。试求子群H,*在群G,*中的左陪集eH,aH,bH,cH和右陪集He,Ha,Hb,Hc 解：eH=e*e,e*a=e,a=H aH=a*e,a*a=a,e=eH=H bH=b*e,b*a=b,c cH=c*e,c*a=c,b=bH He=e*e,a*e=e,a=H Ha=e*a,a*a=a,e=He=H Hb=e*b,a*b=b,c Hc=e*c,a*c=c,b=Hb 以下讨论右陪集的性质：【定理5.6.1】设H,*是群G,*的子群，H的右陪集具有下述性质：,第五章：代数结构,aHa，H=He。Ha与H的基数相同。xHa，都有Hx=Ha。这一性质表明Ha的代表元可在Ha中任意选取。Ha=Hb的充分必要条件是a*b 1H。对于H的任意两个右陪集Ha,Hb，则Ha=Hb或HaHb=证明：因为a=e*ah*a|hH，所以aHa。又He=h*e|hH=h|hH=H，所以He=H。h1,h2H，且h1h2，则h1*ah2*a，否则，按消去律h1=h2。设f：HHa，f(h)=h*a。可以证明f是H到Ha的双射。故Ha与H的基数相同，即|Ha|=|H|。xHa，令x=h1*a，h1H。于是h*xHx，则有h*x=h*(h1*a)=(h*h1)*a，由于H是子群，所以h*h1H。于是(h*h1)*aHa，即h*xHa。HxHa。同样可证HaHx，这就证明了Hx=Ha。,第五章：代数结构,充分性。若a*b 1H，则存在h1H，使得a*b1=h1，于是有a=h1*bHb。由得Ha=Hb。必要性。若Ha=Hb，由得aHa=Hb，于是存在hH，使得a=h*b。故a*b 1H。若xHaHb，xHa且xHb，则h1,h2H，使x=h1*a=h2*b；于是a*b 1=h11*h2H。由得Ha=Hb。这就证明了对于H的任意两个右陪集Ha,Hb，则Ha=Hb或HaHb=。【定理5.6.2】设是有限群，是的子群，则G可以表示成两两不相交的右陪集的并。即存在一个正整数m，使得G=Ha1Ha2Ham，其中，HaiHaj=，ij，i,j=1,2,m。证明：因为是有限群，所以在中的右陪集个数有限。设所有不同的右陪集为Ha1,Ha2,Ham，共m个。xG，则有xHxHa1Ha2Ham，故GHa1Ha2Ham,第五章：代数结构,又显然 Ha1Ha2HamG所以 G=Ha1Ha2Ham 由定理5.6.1的得Ha1,Ha2,Ham是两两不相交的。例如，设G,*是Klein四元群，其中，G=e,a,b,c。令H=e,a，H,*是G,*子群。子群H,*在群G,*中的右陪集有两个：He=Ha=e,a，Hb=Hc=b,c。G=e,a,b,c=e,ab,c=HeHb，而e,ab,c=。当是无限群时，对于的子群仍可以考虑它的全部不同的右陪集的集合，设为Hxi|xiG，它可以是有限的或无限的。类似定理5.6.2有 G=Hx1Hx2Hxm其中，HxiHxj=，ij，i,j=1,2,m,以上是右陪集的一些性质。左陪集也有类似性质，限于篇幅这里就不赘述了，由同学们总结。,第五章：代数结构,一般地说，对于群G,*的子群H,*不能保证aH=Ha，但对某些子群H,*有aH=Ha。称这些子群为正规子群。尽管H,*在G,*中的左陪集和右陪集是不一定相等的，但是，可以证明H,*在G,*中的左陪集数和右陪集数是相等的。今后不再区分左陪集数和右陪集数，统称为H,*在G,*中的陪集数，记为|G:H|【定理5.6.3】(Lagrange定理)设G,*是有限群，H,*是G,*的子群。则|H|是|G|的因子。证明：设H,*在G,*中的陪集数|G:H|=r，并设全部不同的右陪集为Ha1,Ha2,Har。由定理5.6.2知，它们两两不相交的且G=Ha1Ha2Har于是|G|=|Ha1|+|Ha2|+|Har|=|H|+|H|+|H|=r|H|即|G|=r|