离散数学 第7讲 拉格朗日定理ppt课件.ppt

《离散数学 第7讲 拉格朗日定理ppt课件.ppt》由会员分享，可在线阅读，更多相关《离散数学 第7讲 拉格朗日定理ppt课件.ppt（17页珍藏版）》请在三一办公上搜索。

1、1,离散数学（二）,拉格朗日定理,主要内容:,重点和难点:,一、陪集,陪集的定义：设为的子群，对任一aG，定义aH=aH=ah|hH,称为元素a关于H的左陪集 a:左陪集aH的表示元素Ha=Ha=ha|hH,称为元素a关于H的右陪集 a:右陪集Ha的表示元素例1：是的子群，则 3I=3+i|iI=I，4I=4+i|iI=I 2.5I=2.5+i|iI,3.4I=3.4+i|iI,一、陪集,定理1：设是群的子群,aH和bH是任意二个左陪集,那么,或aH=bH或aHbH=。思路：令命题P：aHbH=命题Q：aH=bH要证PQ为真，即要证PQ为真。即要证(aHbH=)aH=bH证明:假设aHbH，我

2、们证明aH=bH。设aHbH,那么必存在一个公共元素f,有faHbH,则存在h1,h2 H,使f=ah1=bh2,因此 a=bh2h1-1 下面证明aHbH：xaH,存在h3H使得x=ah3,因而x=bh2(h1)-1h3,根据H中运算的封闭性知h2(h1)-1h3H，所以xbH。同理可证bHaH。因此aH=bH。,一、陪集,定理2：设为的子群,则H的任意左陪集的大小(基数)是相同的。即对任意a,bG有aH=bH=H。证明:假设H=h1,h2,hm，那么aH=ah1,ah2,ahm。定义函数f:HaH,对任何一hH，f(h)=ah。f:HaH单射,对h1,h2H,若h1h2,则ah1ah2。f

3、:HaH为满射是显然的。因此f为双射，故aH=H 得证。,一、陪集,定理3：设是群的子群,则H 的所有左陪集构成G的一个划分。,证明(1)证明H所有左陪集的并集为G。即aG，有 由于HG且G对封闭可得，。下面证明。由 可得,(2)由定理1可知，G中两个元素的左陪集要么相等要么不相交。由(1)和(2)可得，H的所有左陪集构成G的一个划分,一、陪集,例3 是的子群,其中H0,2,则H的左陪集为：0H0，22H0，2 1H1，33H1，3于是有0H1H0，1，2，3为N4的一个划分。,二、拉格朗日定理,定理4：(拉格朗日定理)设是有限群的子群,且|G|=n，|H|=m，那么m|n。说明：设H的不同左

4、陪集有 k个，那么n=|G|=k|H|=km推论1：质数阶的群没有非平凡子群。说明：和叫做群的平凡子群。推论2：在有限群中,任何元素的阶必是|G|的一个因子。说明：如果aG的阶是r,则是的子群。推论3：一个质数阶的群必定是循环的,并且任一与么元不同的元素都是生成元。,二、拉格朗日定理,设G=e,a,b,c，Klein四元群满足下列条件：(1)e的阶为1，a,b,c的阶均为2；(2)a,b,c中任意两个元素运算的结果为第三个元素。,推论4：任一四阶群，或为循环群C4，或为Klein四元群。,证明：设G=e,a,b,c,其中e是幺元。根据拉格朗日定理可知元素阶只可能是1,2,4。(1)若G中有4阶

5、元a 则|a|=4,=e,a,a2,a3C4(表示同构)。(2)若G中无4阶元素 则G中除了幺元,剩余的3个元素阶均为2,即a2=b2=c2=e。a*b不可能是a,b或e,否则将导致b=e,a=e或者a=b,产生矛盾。所以a*b=c,同样地有b*a=c及a*c=c*a=b,b*c=c*b=a。因此这个群是Klein四元群。,二、拉格朗日定理,四阶群仅有以下两个：,五阶群仅有一个：,循环群,Klein四元群,二、拉格朗日定理,例3 令A1,2,3，A上置换的全体S3=pi i=1,2,3,4,5,6。,为三次对称群，此六阶群不是阿贝尔群。,二、拉格朗日定理,定理5：设是群的子群,于是baH,当且

6、仅当a-1 bH证明:baH,当且仅当存在一hH,使b=ah,即a-1 b=h,因而，baH当且仅当a-1 bH。设是群的子群,则H 所有不同的左陪集构成G的一个划分，这个划分可以生成G的一个左陪集等价关系R：aRba-1bH验证R为等价关系(自反性、对称性和传递性)(1)自反性 a-1a=eH,所以aRa(2)对称性 若aRb,则a-1bH,所以b-1a=(a-1b)-1H,故bRa(3)传递性 若aRb,bRc,则a-1bH,b-1cH,a-1c=a-1(b*b-1)*c=(a-1b)*(b-1c)H,故aRc,二、拉格朗日定理,例4：我们来考察,取H=p1,p4,是的子群。左陪集：p1H

7、=p4H=p1,p4 p2H=p6H=p2,p6 p3H=p5H=p3,p5 可以看出,p1,p4,p2,p6,p3,p5是S3的一个划分右陪集：Hp1=Hp4=p1,p4 Hp2=Hp5=p2,p5 Hp3=Hp6=p3,p6 可以看出,p1,p4,p2,p5,p3,p6是S3的一个划分,Attention:表示元素相同的左陪集和右陪集未必相等,例如p2HHp2。左右陪集确定的等价关系也未必是的同余关系,例如,p3p5,p2p6,p3p2p5p6。,二、拉格朗日定理,例4(续)：,取H=p1,p5,p6,是的子群。左陪集：p1H=p5H=p6H=p1,p5,p6 p2H=p3H=p4H=p2

8、,p3,p4可以看出,p1,p5,p6,p2,p3,p4是S3的一个划分右陪集：Hp1=Hp5=Hp6=p1,p5,p6 Hp2=Hp3=Hp4=p2,p3,p4可以看出,元素相同的左陪集和右陪集是相同的。H的左陪集等价关系也是一个同余关系。,从例4可以看出，H的左陪集等价关系可以是上的同余关系，也可以不是。那么在什么情况下它一定是同余关系呢？(引入正规子群和商群),三、正规子群,设是群的子群,对任意元素aG,如果aH=Ha,则称为正规子群。定义中的aH=Ha是指对每一h1H,都存在h2H,使a*h1=h2*a,并不要求对每一hH有a*h=h*a。对正规子群来说,左陪集和右陪集相等。所以,可以简称陪集。显然,所有阿贝尔群的子群都是正规子群;所有平凡子群都是正规子群。,设aH和bH是两个陪集，a1是aH中任一元素，b1是bH中任一元素，现证明全都在H的同一陪集中。设a1=a*h1,b1=b*h2,其中h1，h2是H中某一元素。a1*b1=(a*h1)*(b*h2)=(a*h1)*(h3*b)=a*h4*b=a*b*h5.因此，a1*b1都在陪集(a*b)H中。另外对于一元求逆运算，保持运算也满足。若a1,a2aH,a1-1,a2-1a-1H,下面说明正规子群H的左陪集等价关系是一个同余关系：,作业：P217 习题6.7 15,17,谢谢同学们!,