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

《离散数学-第7讲-拉格朗日定理ppt课件.ppt》由会员分享，可在线阅读，更多相关《离散数学-第7讲-拉格朗日定理ppt课件.ppt（17页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、1离散数学（二）离散数学（二）拉格朗日定理拉格朗日定理陪集陪集1 11 1拉格朗日定理拉格朗日定理2 2主要内容主要内容: :陪集的性质陪集的性质重点重点: : 重点和难点重点和难点: :一、陪集一、陪集陪集的定义：陪集的定义： 设为的子群，对任一aG，定义aH= aH=ah|hH, 称为元素元素a关于关于H的左陪集的左陪集 a:左陪集左陪集aH的表示元素的表示元素Ha=Ha=ha|hH, 称为元素元素a关于关于H的右陪集的右陪集 a:右陪集右陪集Ha的表示元素的表示元素例例1：是的子群，则 3I=3+i|i I=I， 4I=4+i|i I=I 2.5I=2.5+i|i I, 3.4I=3.4

2、+i|i I 3I=4I 2.5I3.4I=一、陪集一、陪集定理定理1：设设是群是群的子群的子群, aH和和bH是任意二个左陪集是任意二个左陪集, 那么那么, 或或aH=bH或或aHbH=。思路：令命题思路：令命题P：aHbH= 命题命题Q： aH=bH要证要证PQ为真，即要证为真，即要证PQ为真。即要证为真。即要证(aHbH=)aH=bH证明证明:假设aHbH ，我们证明aH=bH。 设aHbH, 那么必存在一个公共元素f, 有faHbH,则存在h1,h2 H, 使f=ah1= bh2,因此 a=bh2h1-1 下面证明下面证明aHbH ： xaH,存在h3H使得x=ah3, 因而x=bh2

3、(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: HaH为满射是显然的。因此f为双射，故aH = H 得证。一、陪集一、陪集定理定理3： 设是群的子群, 则H 的所有左陪集构成

4、G的一个划分。证明证明 (1)证明证明H所有左陪集的并集为所有左陪集的并集为G。即aG，有 由于HG且G对 封闭可得， 。 下面证明 。 由 可得GaGaHGaGaHGaGaH*,aeaaHeHGaGaGaaH(2)(2)由定理由定理1 1可知，可知，G G中两个元素的左陪集要么相等要么不相交。中两个元素的左陪集要么相等要么不相交。由由(1)(1)和和(2)(2)可得，可得，H H的所有左陪集构成的所有左陪集构成G G的一个划分的一个划分一、陪集一、陪集例例2 群的子群,H1=,H2 = H1左陪集：左陪集：0H1 = 0, 2, 41H1 = 1, 3, 52H1 = 2, 4, 03H1

5、= 3, 5, 14H1 = 4, 0, 25H1 = 5, 1, 3H2左陪集：左陪集：0H2 = 0, 31H2 = 1, 42H2 = 2, 53H2 = 3, 04H2 = 4, 15H2 = 5, 2例例3 是的子群,其中H0 ,2,则H的左陪集为： 0H0，22H0，2 1H1，33H1，3于是有0H1H0，1，2，3为N4的一个划分。二、拉格朗日定理二、拉格朗日定理定理定理4：(拉格朗日定理) 设是有限群的子群,且|G|=n，|H|=m，那么m|n。说明：说明：设H的不同左陪集有 k个，那么n=|G|=k|H|=km推论推论1：质数阶的群没有非平凡子群。说明：说明：和叫做群的平凡

6、子群。推论推论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阶元阶元a 则|a|=4,=e,a

7、,a2,a3 C4( 表示同构)。(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四元群四元群*eabcdeeabcdaabcdebbcdeaccdeabddeabc*eabceeabcaabcebbceacceab*eabceeabcaa

8、ecbbbceaccbae二、拉格朗日定理二、拉格朗日定理例例3 令A1,2,3，A上置换的全体S3 = pi i = 1,2,3,4,5,6。 3213211p3123212p1233213p2313214p1323215p2133216p为三次对称群，此六阶群不是阿贝尔群。 213321132321231321312321312321132321 二、拉格朗日定理二、拉格朗日定理定理定理5：设是群的子群, 于是baH, 当且仅当a-1 bH证明证明:baH, 当且仅当存在一hH, 使b=ah, 即a-1 b=h, 因而，baH当且仅当a-1 bH。 设是群的子群, 则H 所有不同的左陪集构

9、成G的一个划分，这个划分可以生成G的一个左陪集等价关系R：aRba-1 bH验证验证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= p4H=p1, p4 p2H= p6H=p2, p6 p

10、3H= 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的一个划分213321132321231321123321312321321321654321pppppp p1p2p3p4p5p6p1p1p2p3p4p5p6p2p2p1p5p6p3p4p3p3p6p1p5p4p2p4p4p5p6p1p2p3p5p5p4p2p3p6p1p6p6p3p4p2p1p5Attention:

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

12、是相同的。H的左陪集等价关系也是一个同余关系。 p1p2p3p4p5p6p1p1p2p3p4p5p6p2p2p1p5p6p3p4p3p3p6p1p5p4p2p4p4p5p6p1p2p3p5p5p4p2p3p6p1p6p6p3p4p2p1p5从例4可以看出，H的左陪集等价关系可以是上的同余关系，也可以不是。那么在什么情况下它一定是同余关系同余关系呢？(引入正规子群和商群)三、正规子群三、正规子群设是群的子群,对任意元素aG, 如果aH=Ha, 则称为正正规子群规子群。定义中的aH=Ha是指对每一h1H, 都存在h2H, 使a * h1=h2 * a, 并不要求对每一hH有a * h=h * a。

13、 对正规子群来说,左陪集和右陪集相等。所以,可以简称陪集。显然,所有阿贝尔群的子群都是正规子群;所有平凡子群都是正规子群。设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 1517谢谢同学们谢谢同学们! !