离散数学第.ppt

Click to edit Master title style,Click to edit Master text styles,Second level,Third level,Fourth level,Fifth level,*,*,单击此处编辑母版标题样式,*,*,半群、独异点与群的定义,定义,10.1,(1),设,V,=,是代数系统，为二元运算，如果运算是可,结合的，则称,V,为半群,.,(2),设,V,=,是半群，若,e,S,是关于运算的单位元，则称,V,是含幺半群，也叫做独异点,.,有时也将独异点,V,记作,V,=.,(3),设,V,=,是独异点，,e,S,关于运算的单位元，若,a,S,，,a,1,S,，则称,V,是群,.,通常将群记作,G,.,1,实例,例1,(1),都是半群，+是普通加,法.这些半群中除外都是独异点,(2)设,n,是大于1的正整数，和都是半,群，也都是独异点，其中+和分别表示矩阵加法和矩阵,乘法,(3)为半群，也是独异点，其中,为集合对称差运算,(4)为半群，也是独异点，其中Z,n,=0,1,n,1，,为模,n,加法,(5)为半群，也是独异点，其中,为函数的复合运算,(6)为半群，其中,R,*为非零实数集合，,运算定义如,下：,x,y,R,*,x,y,=,y,2,例,2,设,G,=,e,a,b,c,，,G,上的运算由下表给出，称为,Klein,四元群,e a b c,e,a,b,c,e a b c,a e c b,b c e a,c b a e,实例,特征：,1.,满足交换律,2.,每个元素都是自己的逆元,3.,a,b,c,中任何两个元素运算结,果都等于剩下的第三个元素,3,有关群的术语,定义,10.2 (1),若群,G,是有穷集，则称,G,是有限群，否则称为无,限群,.,群,G,的基数称为群,G,的阶，有限群,G,的阶记作,|,G,|.,(2),只含单位元的群称为平凡群,.,(3),若群,G,中的二元运算是可交换的，则称,G,为交换群或阿贝,尔,(Abel),群,.,实例：,和,是无限群，,是有限群，也是,n,阶群,.,Klein,四元群是,4,阶群,.,是平凡群,.,上述群都是交换群，,n,阶,(,n,2),实可逆矩阵集合关于矩阵乘法,构成的群是非交换群,.,4,这就推出akG，ak=(ar)uk，即G.,通常称+运算为环中的加法，运算为环中的乘法.,中，由2生成的子群=0,2,4,由于|G|=6,|b|=6,所以 b 为生成元.,若ae，令S=a,a2,，则SH.,=1，即 b=a 或 b=a1,C=a|aGxG(ax=xa)，,G=Ha1Ha2Har|G|=|Ha1|+|Ha2|+|Har|,(1 2 3)(2 3)(1 2)(1 3)(1 3 2)(1),=a(x1b)1=a(bx1)1=a(xb1),baR R ab1H Ha=Hb bHa,h(hHab1=h)ab1H,因此 xy1属于H.,(1)若环中乘法 适合交换律，则称R是交换环,G=ak|kZ,定义,10.3,设,G,是群，,a,G,，,n,Z,，则,a,的,n,次幂,.,群中元素的幂,群中元素可以定义负整数次幂,.,在,中有 ,2,3,=(2,1,),3,=1,3,=1,1,1=0,在,中有,(,2),3,=2,3,=2+2+2=6,5,元素的阶,定义,10.4,设,G,是群，,a,G,，使得等式,a,k,=,e,成立的最小正整数,k,称为,a,的阶，记作,|,a,|=,k,，称,a,为,k,阶元,.,若不存在这样的正,整数,k,，则称,a,为无限阶元,.,例如，在,中，,2,和,4,是,3,阶元，,3,是,2,阶元，,1,和,5,是,6,阶元，,0,是,1,阶元,.,在,中，,0,是,1,阶元，其它整数的阶都不存在,.,6,群的性质：幂运算规则,定理,10.1,设,G,为群，则,G,中的幂运算满足：,(1),a,G,，,(,a,1,),1,=,a,(2),a,b,G,，,(,ab,),1,=,b,1,a,1,(3),a,G,，,a,n,a,m,=,a,n,+,m,，,n,m,Z,(4),a,G,，,(,a,n,),m,=,a,nm,，,n,m,Z,(5),若,G,为交换群，则,(,ab,),n,=,a,n,b,n,.,证,(1)(,a,1,),1,是,a,1,的逆元，,a,也是,a,1,的逆元,.,根据逆元唯一,性，等式得证,.,(2)(,b,1,a,1,)(,ab,)=,b,1,(,a,1,a,),b,=,b,1,b,=,e,同理,(,ab,)(,b,1,a,1,)=,e,，,故,b,1,a,1,是,ab,的逆元,.,根据逆元的唯一性等式得证,.,7,群的性质：方程存在惟一解,定理,10.2,G,为群，,a,b,G,，方程,ax,=,b,和,ya,=,b,在,G,中有解且,仅有惟一解,.,例,3,设群,G,=,，其中,为对称差,.,解下列群方程：,a,X,=,，,Y,a,b,=,b,解,X,=,a,1,=,a,=,a,，,Y,=,b,a,b,1,=,b,a,b,=,a,证,a,1,b,代入方程左边的,x,得,a,(,a,1,b,)=(,aa,1,),b,=,eb,=,b,所以,a,1,b,是该方程的解,.,下面证明惟一性,.,假设,c,是方程,ax,=,b,的解，必有,ac,=,b,，从而有,c,=,ec,=(,a,1,a,),c,=,a,1,(,ac,)=,a,1,b,同理可证,ba,1,是方程,ya,=,b,的惟一解,.,8,群的性质：消去律,定理,10.3,G,为群，则,G,中适合消去律，即对任意,a,b,c,G,有,(1),若,ab,=,ac,，则,b,=,c,.,(2),若,ba,=,ca,，则,b,=,c,.,证明略,例,4,设,G,=,a,1,a,2,a,n,是,n,阶群，令,a,i,G,=,a,i,a,j,|,j,=1,2,n,证明,a,i,G,=,G,.,证 由群中运算的封闭性有,a,i,G,G,.,假设,a,i,G,G,，即,|,a,i,G,|,n,.,必有,a,j,a,k,G,使得,a,i,a,j,=,a,i,a,k,（,j,k,）,由消去律得,a,j,=,a,k,与,|,G,|=,n,矛盾,.,9,群的性质：元素的阶,证,(1),充分性,.,由于,r,|,k,，必存在整数,m,使得,k,=,mr,，所以有 ,a,k,=,a,mr,=(,a,r,),m,=,e,m,=,e,.,必要性,.,根据除法，存在整数,m,和,i,使得 ,k,=,mr,+,i,0,i,r,1,从而有,e,=,a,k,=,a,mr,+,i,=(,a,r,),m,a,i,=,ea,i,=,a,i,因为,|,a,|=,r,，必有,i,=0.,这就证明了,r,|,k,.,(2),由,(,a,1,),r,=(,ar,),1,=,e,1,=,e,可知,a,1,的阶存在,.,令,|,a,1,|=,t,，根据上面的证明有,t,|,r,.,a,又是,a,1,的逆元，所以,r,|,t,.,从而证明了,r,=,t,，即,|,a,1,|=|,a,|,定理,10.4,G,为群，,a,G,且,|,a,|=,r,.,设,k,是整数，则,(1),a,k,=,e,当且仅当,r,|,k,(2)|,a,1,|=|,a,|,10,实例,例,5,设,G,是群，,a,b,G,是有限阶元,.,证明,(1)|,b,1,ab,|=|,a,|(2)|,ab,|=|,ba,|,证,(1),设,|,a,|=,r,，,|,b,1,ab|,=,t,，则有,从而有,t,|,r,.,另一方面，由,a,=(,b,1,),1,(,b,1,ab,),b,1,可知,r,|,t,.,从而,有,|,b,1,ab,|=|,a,|.,11,实例,(2),设,|,ab,|=,r,，,|,ba,|=,t,，则有,由消去律得,(,ab,),t,=,e,，从而可知，,r,|,t,.,同理可证,t,|,r,.,因此,|,ab,|=|,ba,|.,12,10.2,子群与群的陪集分解,定义,10.5,设,G,是群，,H,是,G,的非空子集，,(1),如果,H,关于,G,中的运算构成群，则称,H,是,G,的子群,记作,H,G,.,(2),若,H,是,G,的子群，且,H,G,，则称,H,是,G,的真子群，记作,H,G,.,例如,n,Z(,n,是自然数,),是整数加群,的子群,.,当,n,1,时,n,Z,是,Z,的真子群,.,对任何群,G,都存在子群,.,G,和,e,都是,G,的子群，称为,G,的平凡,子群,.,13,子群判定定理,1,定理,10.5,（判定定理一）,设,G,为群，,H,是,G,的非空子集，则,H,是,G,的子群当且仅当,(1),a,b,H,有,ab,H,(2),a,H,有,a,1,H,.,证 必要性是显然的,.,为证明充分性，只需证明,e,H,.,因为,H,非空，存在,a,H,.,由条件,(2),知,a,1,H,，根据条件,(1),aa,1,H,，即,e,H,.,14,子群判定定理,2,定理,10.6,（判定定理二）,设,G,为群，,H,是,G,的非空子集,.,H,是,G,的子群当且仅当,a,b,H,有,ab,1,H,.,证 必要性显然,.,只证充分性,.,因为,H,非空，必存在,a,H,.,根据给定条件得,aa,1,H,，即,e,H,.,任取,a,H,由,e,a,H,得,ea,1,H,，即,a,1,H,.,任取,a,b,H,，知,b,1,H,.,再利用给定条件得,a,(,b,1,),1,H,，即,ab,H,.,综合上述，可知,H,是,G,的子群,.,15,子群判定定理,3,定理,10.7,（判定定理三）,设,G,为群，,H,是,G,的非空有穷子集，则,H,是,G,的子群当且仅当,a,b,H,有,ab,H,.,证 必要性显然,.,为证充分性，只需证明,a,H,有,a,1,H,.,任取,a,H,若,a,=,e,则,a,1,=,e,H,.,若,a,e,，令,S,=,a,a,2,，则,S,H,.,由于,H,是有穷集，必有,a,i,=,a,j,（,i,1,，由此得,a,j,i,1,a,=,e,和,a a,j,i,1,=,e,从而证明了,a,1,=,a,j,i,1,H,.,16,典型子群的实例,:,生成子群,定义,10.6,设,G,为群，,a,G,，令,H,=,a,k,|,k,Z,，,则,H,是,G,的子群，称为由,a,生成的子群，记作,.,证 首先由,a,知道,.,任取,a,m,a,l,，则 ,a,m,(,a,l,),1,=,a,m,a,l,=,a,m,l,根据判定定理二可知,G,.,实例：,例如整数加群，由,2,生成的子群是,=2,k,|,k,Z=2Z,中，由,2,生成的子群,=0,2,4,Klein,四元群,G,=,e,a,b,c,的所有生成子群是：,=,e,=,e,a,=,e,b,=,e,c,.,17,典型子群的实例,:,中心,C,定义,10.7,设,G,为群,令,C,=,a,|,a,G,x,G,(,ax,=,xa,),，,则,C,是,G,的子群，称为,G,的中心,.,证,e,C,.,C,是,G,的非空子集,.,任取,a,b,C,，只需证明,ab,1,与,G,中所有的元素都可交换,.,x,G,，有,(,ab,1,),x,=,ab,1,x,=,ab,1,(,x,1,),1,=,a,(,x,1,b,),1,=,a,(,bx,1,),1,=,a,(,xb,1,),=(,ax,1,),b,1,=(,xa,),b,1,=,x,(,ab,1,),由判定定理二可知,C,G,.,对于阿贝尔群,G,，因为,G,中所有的元素互相都可交换，,G,的中,心就等于,G,.,但是对某些非交换群,G,，它的中心是,e,.,18,典型子群的实例,:,子群的交,例,6,设,G,是群，,H,K,是,G,的子群,.,证明,(1),H,K,也是,G,的子群,(2),H,K,是,G,的子群当且仅当,H,K,或,K,H,证,(1),由,e,H,K,知,H,K,非空,.,任取,a,b,H,K,，则,a,H,a,K,b,H,b,K,.,必有,ab,1,H,和,ab,1,K,，从而,ab,1,H,K,.,因此,H,K,G,.,(2),充分性显然，只证必要性,.,用反证法,.,假设,H,K,且,K,H,，那么存在,h,和,k,使得 ,h,H,h,K,k,K,k,H,推出,hk,H,.,否则由,h,1,H,得,k,=,h,1,(,hk,),H,，与假设矛盾,.,同理可证,hk,K,.,从而得到,hk,H,K,.,与,H,K,是子群矛盾,.,19,图,1,定义,10.8,设,G,为群,令,L,(,G,)=,H,|,H,是,G,的子群,则偏序集,称为,G,的子群格,子群格,实例：,Klein,四元群的子群格如下：,20,陪集定义与实例,定义,10.9,设,H,是,G,的子群，,a,G,.,令,Ha,=,ha,|,h,H,称,Ha,是子群,H,在,G,中的右陪集,.,称,a,为,Ha,的代表元素,.,例,7 (1),设,G,=,e,a,b,c,是,Klein,四元群，,H,=,是,G,的子群,.,H,所有的右陪集是：,He,=,e,a,=,H,Ha,=,a,e,=,H,Hb,=,b,c,Hc,=,c,b,不同的右陪集只有两个，即,H,和,b,c,.,21,实例,(2),设,A,=1,2,3,，,f,1,f,2,f,6,是,A,上的双射函数,.,其中,f,1,=,，,f,2,=,f,3,=,，,f,4,=,f,5,=,，,f,6,=,令,G,=,f,1,f,2,f,6,，则,G,关于函数的复合运算构成群,.,考虑,G,的子群,H,=,f,1,f,2,.,做出,H,的全体右陪集如下：,Hf,1,=,f,1,f,1,f,2,f,1,=,H,Hf,2,=,f,1,f,2,f,2,f,2,=,H,Hf,3,=,f,1,f,3,f,2,f,3,=,f,3,f,5,Hf,5,=,f,1,f,5,f,2,f,5,=,f,5,f,3,Hf,4,=,f,1,f,4,f,2,f,4,=,f,4,f,6,Hf,6,=,f,1,f,6,f,2,f,6,=,f,6,f,4,结论：,Hf,1,=,Hf,2,，,Hf,3,=,Hf,5,，,Hf,4,=,Hf,6,.,22,陪集的基本性质,定理,10.8,设,H,是群,G,的子群，则,(1),He,=,H,(2),a,G,有,a,Ha,证,(1),He,=,he,|,h,H,=,h,|,h,H,=,H,(2),任取,a,G,，由,a,=,ea,和,ea,Ha,得,a,Ha,23,定理,10.9,设,H,是群,G,的子群，则,a,b,G,有 ,a,Hb,ab,1,H,Ha,=,Hb,陪集的基本性质,证 先证,a,Hb,ab,1,H,a,Hb,h,(,h,H,a,=,hb,),h,(,h,H,ab,1,=,h,),ab,1,H,再证,a,Hb,Ha,=,Hb.,充分性,.,若,Ha,=,Hb,，由,a,Ha,可知必有,a,Hb,.,必要性,.,由,a,Hb,可知存在,h,H,使得,a,=,hb,，即,b,=,h,1,a,任取,h,1,a,Ha,，则有,h,1,a,=,h,1,(,hb,)=(,h,1,h,),b,Hb,从而得到,Ha,Hb,.,反之，任取,h,1,b,Hb,，则有,h,1,b,=,h,1,(,h,1,a,)=(,h,1,h,1,),a,Ha,从而得到,Hb,Ha,.,综合上述，,Ha,=,Hb,得证,.,24,定理,10.10,设,H,是群,G,的子群，在,G,上定义二元关系,R,：,a,b,G,R,ab,1,H,则,R,是,G,上的等价关系，且,a,R,=,Ha,.,陪集的基本性质,证 先证明,R,为,G,上的等价关系,.,自反性,.,任取,a,G,，,aa,1,=,e,H,R,对称性,.,任取,a,b,G,，则,R,ab,1,H,(,ab,1,),1,H,ba,1,H,R,传递性,.,任取,a,b,c,G,，则,R,R,ab,1,H,bc,1,H,ac,1,H,R,下面证明：,a,G,，,a,R,=,Ha,.,任取,b,G,，,b,a,R,R,ab,1,H,Ha,=,Hb,b,Ha,25,推论,推论 设,H,是群,G,的子群,则,(1),a,b,G,，,Ha,=,Hb,或,Ha,Hb,=,(2),Ha,|,a,G,=,G,证明：由等价类性质可得,.,定理,10.11,设,H,是群,G,的子群，则,a,G,，,H,Ha,证明 略,26,左陪集的定义与性质,设,G,是群，,H,是,G,的子群，,H,的左陪集，即,aH,=,ah,|,h,H,，,a,G,关于左陪集有下述性质：,(1),eH,=,H,(2),a,G,，,a,aH,(3),a,b,G,，,a,bH,b,1,a,H,aH,=,bH,(4),若在,G,上定义二元关系,R,，,a,b,G,，,R,b,1,a,H,则,R,是,G,上的等价关系，且,a,R,=,aH,.,(5),a,G,，,H,aH,27,Lagrange,定理,定理,10.12,（,Lagrange,）设,G,是有限群，,H,是,G,的子群，则,|,G,|=|,H,|,G,:,H,其中,G,:,H,是,H,在,G,中的不同右陪集,(,或左陪集,),数，称为,H,在,G,中的指数,.,证 设,G,:,H,=,r,，,a,1,a,2,a,r,分别是,H,的,r,个右陪集的代表元素，,G,=,Ha,1,Ha,2,Ha,r,|,G,|=|,Ha,1,|+|,Ha,2,|+|,Ha,r,|,由,|,Ha,i,|=|,H,|,，,i,=1,2,r,得 ,|,G,|=|,H,|,r,=|,H,|,G,:,H,28,Lagrange,定理的推论,推论,1,设,G,是,n,阶群，则,a,G,，,|,a,|,是,n,的因子，且有,a,n,=,e,.,证 任取,a,G,，,是,G,的子群，,的阶是,n,的因子,.,是由,a,生成的子群，若,|,a,|=,r,，则,=,a,0,=,e,a,1,a,2,a,r,1,即,的阶与,|,a,|,相等,所以,|,a,|,是,n,的因子,.,从而,a,n,=,e,.,推论,2,对阶为素数的群,G,，必存在,a,G,使得,G,=.,证 设,|,G,|=,p,，,p,是素数,.,由,p,2,知,G,中必存在非单位元,.,任取,a,G,，,a,e,，则,是,G,的子群,.,根据拉格朗日定理，,的阶是,p,的因子，即,的阶是,p,或,1.,显然,的阶不是,1,，,这就推出,G,=.,29,Lagrange,定理的应用,命题：如果群,G,只含,1,阶和,2,阶元，则,G,是,Abel,群,.,例,8,证明,6,阶群中必含有,3,阶元,.,证 设,a,为,G,中任意元素，有,a,1,=,a,.,任取,x,y,G,，则,xy,=(,xy,),1,=,y,1,x,1,=,yx,，,因此,G,是,Abel,群,.,证 设,G,是,6,阶群，则,G,中元素只能是,1,阶、,2,阶、,3,阶或,6,阶,.,若,G,中含有,6,阶元，设为,a,，则,a,2,是,3,阶元,.,若,G,中不含,6,阶元，下面证明,G,中必含有,3,阶元,.,如若不然，,G,中只含,1,阶和,2,阶元，即,a,G,，有,a,2,=,e,，由命题知,G,是,Abel,群,.,取,G,中,2,阶元,a,和,b,，,a,b,，令,H,=,e,a,b,ab,，则,H,是,G,的子群，但,|,H,|=4,，,|,G,|=6,，与拉格朗日定理矛盾,.,30,例,9,证明阶小于,6,的群都是,Abel,群,.,Lagrange,定理的应用,证,1,阶群是平凡的，显然是阿贝尔群,.,2,3,和,5,都是素数，由推论,2,它们都是单元素生成的群，都是,Abel,群,.,设,G,是,4,阶群,.,若,G,中含有,4,阶元，比如说,a,，则,G,=,，由上,述分析可知,G,是,Abel,群,.,若,G,中不含,4,阶元，,G,中只含,1,阶和,2,阶元，由命题可知,G,也是,Abel,群,.,31,10.3,循环群与置换群,定义,10.10,设,G,是群，若存在,a,G,使得,G,=,a,k,|,k,Z,则称,G,是循环群，记作,G,=,，称,a,为,G,的生成元,.,循环群的分类：,n,阶循环群和无限循环群,.,设,G,=,是循环群，若,a,是,n,阶元，则,G,=,a,0,=,e,a,1,a,2,a,n,1,那么,|,G,|=,n,，称,G,为,n,阶循环群,.,若,a,是无限阶元，则,G,=,a,0,=,e,a,1,a,2,称,G,为无限循环群,.,32,循环群的生成元,定理,10.13,设,G,=,是循环群,.,(1),若,G,是无限循环群，则,G,只有两个生成元，即,a,和,a,1,.,(2),若,G,是,n,阶循环群，则,G,含有,(,n,),个生成元,.,对于任何小,于,n,且与,n,互质的数,r,0,1,n,-1,a,r,是,G,的生成元,.,(,n,),成为欧拉函数，例如,n,=12,，小于或等于,12,且与,12,互素的,正整数有,4,个：,1,5,7,11,，,所以,(12)=4.,33,证明,证,(1),显然,G,.,a,k,G,，,a,k,=(,a,1,),k,，,因此,G,，,a,1,是,G,的生成元,.,再证明,G,只有,a,和,a,1,这两个生成元,.,假设,b,也是,G,的生成元，,则,G,=.,由,a,G,可知存在整数,t,使得,a,=,b,t,.,由,b,G,=,知存在整数,m,使得,b,=,a,m,.,从而得到,a,=,b,t,=(,a,m,),t,=,a,mt,由,G,中的消去律得,a,mt,1,=,e,因为,G,是无限群，必有,mt,1=0.,从而证明了,m,=,t,=1,或,m,=,t,=,1,，即,b,=,a,或,b,=,a,1,34,(2),只须证明：对任何正整数,r,(,r,n,),，,a,r,是,G,的生成元,n,与,r,互质,.,充分性,.,设,r,与,n,互质，且,r,n,，那么存在整数,u,和,v,使得 ,ur,+,vn,=1,从而,a,=,a,ur,+,vn,=(,a,r,),u,(,a,n,),v,=(,a,r,),u,这就推出,ak,G,，,a,k,=(,a,r,),uk,，即,G,.,另一方面，显然有,G,.,从而,G,=.,必要性,.,设,a,r,是,G,的生成元，则,|,a,r,|=,n,.,令,r,与,n,的最大公约数,为,d,，则存在正整数,t,使得,r,=,dt,.,因此,|,a,r,|,是,n/d,的因子，即,n,整除,n/d,.,从而证明了,d,=1.,证明,35,实例,例,10,(1),设,G,=,e,a,a,11,是,12,阶循环群，则,(12)=4.,小于,12,且,与,12,互素的数是,1,5,7,11,由定理,10.13,可知,a,a,5,a,7,和,a,11,是,G,的生成元,.,(2),设,G,=,是模,9,的整数加群，则,(9)=6.,小于,9,且与,9,互,素的数是,1,2,4,5,7,8.,根据定理,10.13,，,G,的生成元是,1,2,4,5,7,和,8.,(3),设,G,=3Z=3,z,|,z,Z,G,上的运算是普通加法,.,那么,G,只有,两个生成元：,3,和,3.,36,循环群的子群,定理,10.14,设,G,=,是循环群,.,(1),设,G,=,是循环群，则,G,的子群仍是循环群,.,(2),若,G,=,是无限循环群，则,G,的子群除,e,以外都是无限,循环群,.,(3),若,G,=,是,n,阶循环群，则对,n,的每个正因子,d,，,G,恰好含,有一个,d,阶子群,.,37,证明,证,(1),设,H,是,G,=,的子群，若,H,=,e,，显然,H,是循环群，否,则取,H,中的最小正方幂元,a,m,，下面证明,H=,.,易见,H,.,下面证明,H,.,为此，只需证明,H,中任何元素都可表成,a,m,的整数次幂,.,任取,a,l,H,，由除法可知存在整数,q,和,r,，使得,l,=,qm,+,r,，其中,0,r,m,1,a,r,=,a,l,qm,=,a,l,(,a,m,),q,由,a,l,a,m,H,且,H,是,G,的子群可知,a,r,H,.,因为,a,m,是,H,中最小正方幂元，必有,r,=0.,这就推出,a,l,=(,a,m,),q,38,证明,(2),设,G,=,是无限循环群，,H,是,G,的子群,.,若,H,e,可知,H,=,，其中,a,m,为,H,中最小正方幂元,.,假若,|,H,|=,t,，则,|,a,m,|=,t,，,从而得到,a,mt,=,e,.,这与,a,为无限阶元矛盾,.,(3),设,G,=,是,n,阶循环群，则,G,=,a,0,=,e,a,1,a,n,1,下面证明对于,n,的每个正因子,d,都存在一个,d,阶子群,.,易见 是,G,的,d,阶子群,.,假设,H,1,=,也是,G,的,d,阶子,群，其中,a,m,为,H,1,中的最小正方幂元,.,则由,(,a,m,),d,=,e,可知,n,整,除,md,，即,n,/,d,整除,m,.,令,m,=(,n,/,d,),l,，,l,是整数，则有,这就推出,H,1,H,.,又由于,|,H,1,|=|,H,|=,d,，得,H,1,=,H,.,39,实例,例,11,(1),G,=,是无限循环群，其生成元为,1,和,1.,对于自然数,m,N,，,1,的,m,次幂是,m,，,m,生成的子群是,m,Z,，,m,N.,即,=0=0Z =,mz,|,z,Z=,m,Z,，,m,0,(2),G,=Z,12,是,12,阶循环群,.12,正因子是,1,2,3,4,6,和,12,，,G,的子群,:1,阶子群,=0 2,阶子群,=0,6 3,阶子群,=0,4,8 4,阶子群,=0,3,6,9 6,阶子群,=0,2,4,6,8,10 12,阶子群,=Z,12,40,n,元置换及乘法,定义,10.11,设,S,=1,2,n,S,上的任何双射函数,:,S,S,称为,S,上的,n,元置换,.,例如,S,=1,2,3,4,5,下述为,5,元置换,定义,10.12,设,是,n,元置换,和,的复合,也是,n,元置换,称为,与,的乘积,记作,.,例如,41,n,元置换的轮换表示,设,S,=1,2,n,，对于任何,S,上的,n,元置换,存在着一个,有限序列,i,1,i,2,i,k,k,1,(,可以取,i,1,=1),使得,(,i,1,)=,i,2,(,i,2,)=,i,3,(,i,k,1,)=,i,k,(,i,k,)=,i,1,令,1,=(,i,1,i,2,i,k,),是,分解的第一个轮换,.,将,写作,1,继续对,分解,.,由于,S,只有,n,个元素,经过有限步得到,=,1,2,t,轮换分解式的特征,轮换的不交性,分解的惟一性,:,若,=,1,2,t,和,=,1,2,s,是,的两个轮换表示式，则有 ,1,2,t,=,1,2,s,42,例,12,设,S,=1,2,8,则 轮换分解式为：,=(1 5 2 3 6)(4)(7 8)=(1 5 2 3 6)(7 8),=(1 8 3 4 2)(5 6 7),实例,43,置换的对换分解,设,S,=1,2,n,，,=(,i,1,i,2,i,k,),是,S,上的,k,阶轮换，,可以,进一步表成对换之积，即,(,i,1,i,2,i,k,)=(,i,1,i,2,)(,i,1,i,3,)(,i,1,i,k,),任何,n,元置换表成轮换之积，然后将每个轮换表成对换之积,.,例如,8,元置换,=(1 5 2 3 6)(7 8)=(1 5)(1 2)(1 3)(1 6)(7 8),=(1 8 3 4 2)(5 6 7)=(1 8)(1 3)(1 4)(1 2)(5 6)(5 7),44,对换分解的特征,对换分解式中对换之间可以有交，分解式也不惟一,.,例如,4,元置换,可以有下面不同的对换表示：,=(1 2)(1 3),，,=(1 4)(2 4)(3 4)(1 4),表示式中所含对换个数的奇偶性是不变的,.,如果,n,元置换,可以表示成奇数个对换之积，则称,为奇置换，否则称为偶置换，不难证明奇置换和偶置换各有,n,!/2,个,.,45,n,元置换群,所有的,n,元置换构成的集合,S,n,关于置换乘法构成群，,称为,n,元对称群,.,n,元对称群的子群称为,n,元置换群,.,例,13,设,S,=1,2,3,，,3,元对称群,S,3,=(1),(1 2),(1 3),(2 3),(1 2 3),(1 3 2),(1)(1 2)(1 3)(2 3)(1 2 3)(1 3 2),(1),(1 2),(1 3),(2 3),(1 2 3),(1 3 2),(1)(1 2)(1 3)(2 3)(1 2 3)(1 3 2),(1 2)(1)(1 2 3)(1 3 2)(1 3)(2 3),(1 3)(1 3 2)(1)(1 2 3)(2 3)(1 2),(2 3)(1 2 3)(1 3 2)(1)(1 2)(1 3),(1 2 3)(2 3)(1 2)(1 3)(1 3 2)(1),(1 3 2)(1 3)(2 3)(1 2)(1)(1 2 3),46,S,n,的子群,n,元交错群,A,n,是,S,n,的子群，,A,n,是所有的,n,元偶置换的集合,.,证 恒等置换,(1),是偶置换，所以,A,n,非空,.,根据判定定理三，只需证明封闭性：,任取,A,n,，,都可以表成偶数个对换之积，那么,也可以表成偶数个对换之积，所以,A,n,.,实例：,S,3,的子群格,S,3,=(1),(12),(13),(23),(123),(132),A,3,=(1),(123),(132),(1),(1),(12),(1),(13),(1),(23).,47,Polya,定理,定理,10.15,设,N,=1,2,n,是被着色物体的集合,G=,1,2,g,是,N,上的置换群,.,用,m,种颜色对,N,中的元素进行着色，,则在,G,的作用下不同的着色方案数是,其中,c,(,k,),是置换,k,的轮换表示中包含,1-,轮换在内的轮换个数,.,Polya,定理主要用于等价类的计数,.,48,Polya,定理在组合计数中的应用,例,14,用两种颜色着色方格图形，允许方格绕中心转动,.,求不同的方案数,.,群,G,中的所有置换是：,1,=(1),，,2,=(1234),，,3,=(13)(24),，,4,=(1432),代入,Polya,定理得,49,10.4,环与域,定义,10.12,设,是代数系统，,+,和,是二元运算,.,如果满足,以下条件,:,(1),构成交换群,(2),构成半群,(3),运算关于,+,运算适合分配律,则称,是一个环,.,通常称,+,运算为环中的加法，,运算为环中的乘法,.,环中加法单位元记作,0,，乘法单位元（如果存在）记作,1.,对任何元素,x,，称,x,的加法逆元为负元，记作,x,.,若,x,存在乘法逆元的话，则称之为逆元，记作,x,1,.,50,环的实例,例,15,(1),整数集、有理数集、实数集和复数集关于普通的加法和,乘法构成环，分别称为整数环,Z,，有理数环,Q,，实数环,R,和复数环,C.,(2),n,(,n,2),阶实矩阵的集合,M,n,(R),关于矩阵的加法和乘法构,成环，称为,n,阶实矩阵环,.,(3),集合的幂集,P,(,B,),关于集合的对称差运算和交运算构成环,.,(4),设,Z,n,0,1,.,n,1,，,和,分别表示模,n,的加法和乘,法，则,构成环，称为模,n,的整数环,.,51,定理,10.16,设,是环，则,(1),a,R,，,a,0=0,a,=0(2),a,b,R,，,(,a,),b,=,a,(,b,)=,ab,(3),a,b,c,R,，,a,(,b,c,)=,ab,ac,，,(,b,c,),a,=,ba,ca,(4),a,1,a,2,.,a,n,b,1,b,2,.,b,m,R,(,n,m,2),环的运算性质,证,(1),a,R,有,a,0=,a,(0+0)=,a,0+,a,0,由环中加法的消去律得,a,0=0.,同理可证,0,a,=0.(2),a,b,R,，有 ,(,a,),b,+,ab,=(,a,+,a,),b,=0,b,=0,ab,+(,a,),b,=(,a,+(,a,),b,=0,b,=0(,a,),b,是,ab,的负元,.,由负元惟一性,(,a,),b,=,ab,，同理,a,(,b,)=,ab,52,同理可证,b,1,b,2,.,b,m,有,(4),证明思路：用归纳法证明,a,1,a,2,.,a,n,有,于是,证明,(4),53,实例,例,16,在环中计算,(,a,+,b,),3,(,a,b,),2,解,(,a,+,b,),3,=(,a,+,b,)(,a,+,b,)(,a,+,b,)=(,a,2,+,ba,+,ab,+,b,2,)(,a,+,b,)=,a,3,+,ba,2,+,aba,+,b,2,a,+,a,2,b,+,bab,+,ab,2,+,b,3,(,a,b,),2,=(,a,b,)(,a,b,)=,a,2,ba,ab,+,b,2,54,特殊的环,定义,10.13,设,是环,(1),若环中乘法,适合交换律，则称,R,是交换环,(2),若环中乘法,存在单位元，则称,R,是含幺环,(3),若,a,b,R,，,ab,=0,a,=0,b,=0,，则称,R,是无零因子环,(4),若,R,既是交换环、含幺环、无零因子环，则称,R,是整环,(5),设,R,是整环，且,R,中至少含有两个元素,.,若,a,R,*,，其中,R,*=,R,0,，都有,a,1,R,，则称,R,是域,.,55,例,17,(1),整数环,Z,、有理数环,Q,、实数环,R,、复数环,C,都是交换,环,含幺环,无零因子环和整环,.,除了整数环以外都是域,.,(2),令,2Z=2,z,|,z,Z,，则,构成交换环和无零因子环,.,但不是含幺环和整环,.,(3),设,n,Z,n,2,则,n,阶实矩阵的集合,M,n,(R),关于矩阵加法和乘,法构成环，它是含幺环，但不是交换环和无零因子环，,也不是整环,.,(4),构成环，它是交换环,含幺环,但不是无零因子,环和整环,.2,3=3,2=0,，,2,和,3,是零因子,.,注意：对于一般的,n,Z,n,是整环当且仅当,n,是素数,.,实例,56,实例,例,18,设,p,为素数，证明,Z,p,是域,.,证,p,为素数，所以,|Z,p,|2.,易见,Z,p,可交换，单位元是,1,对于任意的,i,j,Z,p,i,0,有,i,j,=0,p,整除,ij,p,|,j,j,=0,所以,Z,p,中无零因子，,Z,p,为整环,.,下面证明每个非零元素都有逆元,.,任取,i,Z,p,，,i,0,，令,i,Z,p,=,i,j,|,j,Z,p,则,i,Z,p,=Z,p,，否则,j,k,Z,p,，使得,i,j,=,i,k,，由消去律,得,j,=,k,.,由,1Z,p,，存在,j,Z,p,，使得,i,j,=1.,由于交换性可知,j,就是,i,的逆元,.,57,第十章 习题课,主要内容,半群、独异点与群的定义,群的基本性质,子群的判别定理,陪集的定义及其性质,拉格朗日定理及其应用,循环群的生成元和子群,置换群与,Polya,定理,环的定义与性质,特殊的环,58,基本要求,判断或证明给定集合和运算是否构成半群、独异点和群,熟悉群的基本性质,能够证明,G,的子集构成,G,的子群,熟悉陪集的定义和性质,熟悉拉格朗日定理及其推论，学习简单应用,会用,Polya,定理进行计数,会求循环群的生成元及其子群,熟悉,n,元,置换的表示方法、乘法以及,n,元,置换群,能判断给定代数系统是否为环和域,59,证 设G是6 阶群，则G中元素只能是1阶、2阶、3阶或6阶.,6 设G为群，aG，令H=ak|kZ，,找出G的所有子群.,证明