《离散数学第7讲拉格朗日定理ppt课件》由会员分享,可在线阅读,更多相关《离散数学第7讲拉格朗日定理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对 封闭可得, 。 下面证明 。 由 可得(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 = 3, 5, 14H1 = 4, 0, 25H1 = 5, 1,
5、 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:质数阶的群没有非平凡子群。说明:说明:和叫做群的平凡子群。推论推论2:在有限群中, 任何元素的阶必是|G|的一个因子。
6、说明:说明:如果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,a2,a3C4(表示同构)。(2) 若若G中无中无4阶元素阶元素
7、 则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*eabceeabcaaecbbbceaccbae二、拉格朗日定理二、拉格朗日定理例例3 令A
8、1,2,3,A上置换的全体S3 = pi i = 1,2,3,4,5,6。 为三次对称群,此六阶群不是阿贝尔群。 二、拉格朗日定理二、拉格朗日定理定理定理5:设是群的子群, 于是baH, 当且仅当a-1 bH证明证明:baH, 当且仅当存在一hH, 使b=ah, 即a-1 b=h, 因而,baH当且仅当a-1 bH。 设是群的子群, 则H 所有不同的左陪集构成G的一个划分,这个划分可以生成G的一个左陪集等价关系R:aRba-1 bH验证验证R为等价关系为等价关系(自反性、对称性和传递性自反性、对称性和传递性)(1)自反性自反性 a-1a=eH,所以aRa(2)对称性对称性 若aRb,则a-1b
9、H,所以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 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,p
10、5,p3, p6是S3的一个划分 p1p2p3p4p5p6p1p1p2p3p4p5p6p2p2p1p5p6p3p4p3p3p6p1p5p4p2p4p4p5p6p1p2p3p5p5p4p2p3p6p1p6p6p3p4p2p1p5Attention: 表示元素相同的左陪集和右陪集未必相等, 例如p2HHp2。左右陪集确定的等价关系也未必是的同余关系, 例如, p3p5, p2p6, p3p2p5p6。二、拉格朗日定理二、拉格朗日定理例例4(4(续续) ):取H=p1, p5, p6, 是的子群。左陪集:左陪集: p1H= p5H = p6H =p1, p5, p6 p2H= p3H = p4H =
11、p2, p3, p4可以看出,p1, p5, p6,p2, p3, p4是S3的一个划分右陪集:右陪集: Hp1 = Hp5 = Hp6=p1, p5, p6 Hp2 = Hp3= Hp4=p2, p3, p4可以看出, 元素相同的左陪集和右陪集是相同的。H的左陪集等价关系也是一个同余关系。 p1p2p3p4p5p6p1p1p2p3p4p5p6p2p2p1p5p6p3p4p3p3p6p1p5p4p2p4p4p5p6p1p2p3p5p5p4p2p3p6p1p6p6p3p4p2p1p5从例4可以看出,H的左陪集等价关系可以是上的同余关系,也可以不是。那么在什么情况下它一定是同余关系同余关系呢?(引
12、入正规子群和商群)三、正规子群三、正规子群设是群的子群,对任意元素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 1517谢谢同学们谢谢同学们! !