离散数学-第7讲-拉格朗日定理

1离散数学（二）拉格朗日定理陪集11拉格朗日定理2主要内容:陪集的性质重点:重点和难点:一、陪集陪集的定义：设H，为G，的子群，对任一aG，定义aH=aH={ah|hH},称为元素a关于H的左陪集a:左陪集aH的表示元素Ha=Ha={ha|hH},称为元素a关于H的右陪集a:右陪集Ha的表示元素例1：I,+是R,+的子群，则3I={3+i|iI}=I，4I={4+i|iI}=I2.5I={2.5+i|iI},3.4I={3.4+i|iI}3I=4I2.5I∩3.4I=Ø一、陪集定理1：设H,是群G,的子群,aH和bH是任意二个左陪集,那么,或aH=bH或aH∩bH=Ø。思路：令命题P：aH∩bH=Ø命题Q：aH=bH要证P∨Q为真，即要证┐P→Q为真。即要证┐(aH∩bH=Ø)→aH=bH证明:假设aH∩bH≠Ø，我们证明aH=bH。设aH∩bH≠Ø,那么必存在一个公共元素f,有f∈aH∩bH,则存在h1,h2∈H,使f=ah1=bh2,因此a=bh2h1-1下面证明aH⊆bH：∀x∈aH,存在h3∈H使得x=ah3,因而x=bh2(h1)-1h3,根据H中运算的封闭性知h2(h1)-1h3∈H，所以x∈bH。同理可证bH⊆aH。因此aH=bH。一、陪集定理2：设H，为G，的子群,则H的任意左陪集的大小(基数)是相同的。即对任意a,bG有aH=bH=H。证明:假设H={h1,h2,…,hm}，那么aH={ah1,ah2,…,ahm}。定义函数f:H→aH,对任何一hH，f(h)=ah。f:H→aH单射,对∀h1,h2∈H,若h1≠h2,则ah1≠ah2。f:H→aH为满射是显然的。因此f为双射，故aH=H得证。一、陪集定理3：设H,是群G,的子群,则H的所有左陪集构成G的一个划分。证明(1)证明H所有左陪集的并集为G。即∀a∈G，有由于H⊆G且G对封闭可得，。下面证明。由可得GaGaHGaGaHGaGaH}{}*{},{aeaaHeHGaGaGaaH}{(2)由定理1可知，G中两个元素的左陪集要么相等要么不相交。由(1)和(2)可得，H的所有左陪集构成G的一个划分一、陪集例2群N6,+6的子群,H1={0,2,4},+6,H2={0,3},+6H1左陪集：0H1={0,2,4}1H1={1,3,5}2H1={2,4,0}3H1={3,5,1}4H1={4,0,2}5H1={5,1,3}H2左陪集：0H2={0,3}1H2={1,4}2H2={2,5}3H2={3,0}4H2={4,1}5H2={5,2}例3H,＋4是N4,＋4的子群,其中H＝{[0],[2]},则H的左陪集为：[0]H＝{[0]，[2]}＝[2]H＝{[0]，[2]}[1]H＝{[1]，[3]}＝[3]H＝{[1]，[3]}于是有{[0]H}∪{[1]H}＝{[0]，[1]，[2]，[3]}为N4的一个划分。二、拉格朗日定理定理4：(拉格朗日定理)设H,是有限群G,的子群,且|G|=n，|H|=m，那么m|n。说明：设H的不同左陪集有k个，那么n=|G|=k|H|=km推论1：质数阶的群没有非平凡子群。说明：{e},*和G,*叫做群G,*的平凡子群。推论2：在有限群G,中,任何元素的阶必是|G|的一个因子。说明：如果a∈G的阶是r,则{e,a,a2,…,ar-1},是G,的子群。推论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,a={e,a,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四元群。二、拉格朗日定理四阶群仅有以下两个：{e,a,b,c},*五阶群仅有一个：{e,a,b,c,d},*循环群Klein四元群*eabcdeeabcdaabcdebbcdeaccdeabddeabc*eabceeabcaabcebbceacceab*eabceeabcaaecbbbceaccbae二、拉格朗日定理例3令A＝{1,2,3}，A上置换的全体S3={pii=1,2,3,4,5,6}。3213211p3123212p1233213p2313214p1323215p2133216pS3,◇为三次对称群，此六阶群不是阿贝尔群。213321132321231321312321312321132321◇◇二、拉格朗日定理定理5：设H,是群G,的子群,于是b∈aH,当且仅当a-1b∈H证明:b∈aH,当且仅当存在一h∈H,使b=ah,即a-1b=h,因而，b∈aH当且仅当a-1b∈H。设H,是群G,的子群,则H所有不同的左陪集构成G的一个划分，这个划分可以生成G的一个左陪集等价关系R：aRba-1b∈H验证R为等价关系(自反性、对称性和传递性)(1)自反性a-1a=e∈H,所以aRa(2)对称性若aRb,则a-1b∈H,所以b-1a=(a-1b)-1∈H,故bRa(3)传递性若aRb,bRc,则a-1b∈H,b-1c∈H,a-1c=a-1(b*b-1)*c=(a-1b)*(b-1c)∈H,故aRc二、拉格朗日定理例4：我们来考察S3,◇取H={p1,p4},H,◇是S3,◇的子群。左陪集：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,p5},{p3,p6}}是S3的一个划分213321132321231321123321312321321321654321pppppp◇p1p2p3p4p5p6p1p1p2p3p4p5p6p2p2p1p5p6p3p4p3p3p6p1p5p4p2p4p4p5p6p1p2p3p5p5p4p2p3p6p1p6p6p3p4p2p1p5Attention:表示元素相同的左陪集和右陪集未必相等,例如p2H≠Hp2。左右陪集确定的等价关系也未必是G,*的同余关系,例如,p3~p5,p2~p6,p3◇p2~p5◇p6。二、拉格朗日定理例4(续)：取H={p1,p5,p6},H,◇是S3,◇的子群。左陪集：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}可以看出,元素相同的左陪集和右陪集是相同的。H的左陪集等价关系也是一个同余关系。◇p1p2p3p4p5p6p1p1p2p3p4p5p6p2p2p1p5p6p3p4p3p3p6p1p5p4p2p4p4p5p6p1p2p3p5p5p4p2p3p6p1p6p6p3p4p2p1p5从例4可以看出，H的左陪集等价关系可以是G,*上的同余关系，也可以不是。那么在什么情况下它一定是同余关系呢？(引入正规子群和商群)三、正规子群设H,*是群G,*的子群,对任意元素a∈G,如果aH=Ha,则H,*称为正规子群。定义中的aH=Ha是指对每一h1∈H,都存在h2∈H,使a*h1=h2*a,并不要求对每一h∈H有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,a2∈aH,a1-1,a2-1∈a-1H下面说明正规子群H的左陪集等价关系是一个同余关系：作业：P217习题6.71517谢谢同学们!