离散数学(二)拉格朗日定理

《离散数学(二)拉格朗日定理》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、离散数学(二)第七讲计算机学院:焦晓鹏拉格朗日定理主要内容:11陪集2拉格朗日定理重点和难点:重点:陪集的性质一、陪集陪集的定义：设为的子群，对任一a∈G，定义aH=a∗H={a∗h

2、h∈H},称为元素a关于H的左陪集a:左陪集aH的表示元素Ha=H∗a={h∗a

3、h∈H},称为元素a关于H的右陪集a:右陪集Ha的表示元素例1：是的子群，则3I={3+i

4、i∈I}=I，4I={4+i

5、i∈I}=I3I=4I2.5I={2.5+i

6、i∈I},3.4I={3.4+i

7、i∈I}2.5I∩3.4I=Ø一、陪集定理1：设<

8、H,∗>是群的子群,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,则存在h,h∈H,使f=a∗h=b∗h,因此a=b∗h∗h-1121221下面证明aH⊆bH：∀x∈aH,存在h∈H使得x=a∗h,因而x=b∗h∗(h)-1∗h,根据H33213中运算的封闭性知h∗(h)-1∗h∈H，所以x∈bH。21

9、3同理可证bH⊆aH。因此aH=bH。一、陪集定理2：设为的子群,则H的任意左陪集的大小(基数)是相同的。即对任意a,b∈G有

10、aH

11、=

12、bH

13、=

14、H

15、。证明:假设H={h,h,…,h}，那么aH={a∗h,a∗h,…,a∗h}。12m12m定义函数f:H→aH,对任何一h∈H，f(h)=a∗h。f:H→aH单射,对∀h,h∈H,若h≠h,则a∗h≠a∗h。121212f:H→aH为满射是显然的。因此f为双射，故

16、aH

17、=

18、H

19、得证。一、陪集定理3：设是群的子群,则H的所有左陪集构成G的一个划分。证明(1)证明H所有

20、左陪集的并集为G。即∀a∈G，有aH=Ga∈G由于H⊆G且G对∗封闭可得，aH⊆G。a∈G下面证明aH⊇G。a∈G由H⊇{e},aH⊇{a*e}={a}可得aH⊇{a}=Ga∈Ga∈G(2)由定理1可知，G中两个元素的左陪集要么相等要么不相交。由(1)和(2)可得，H的所有左陪集构成G的一个划分一、陪集例2群的子群,H=<{0,2,4},+>,H=<{0,3},+>661626H1左陪集：H2左陪集：0H1={0,2,4}0H2={0,3}1H1={1,3,5}1H2={1,4}2H1={2,4,0}2H2={2,5}3H1={3,5,

21、1}3H2={3,0}4H1={4,0,2}4H2={4,1}5H1={5,1,3}5H2={5,2}例3是的子群,其中H＝{[0],[2]},则H的左陪集为：444[0]H＝{[0]，[2]}＝[2]H＝{[0]，[2]}[1]H＝{[1]，[3]}＝[3]H＝{[1]，[3]}于是有{[0]H}∪{[1]H}＝{[0]，[1]，[2]，[3]}为N的一个划分。4二、拉格朗日定理定理4：(拉格朗日定理)设是有限群的子群,且

22、G

23、=n，

24、H

25、=m，那么m

26、n。说明：设H的不同左陪集有k个，那么n=

27、G

28、=k

29、H

30、=k

31、m推论1：质数阶的群没有非平凡子群。说明：<{e},*>和叫做群的平凡子群。推论2：在有限群中,任何元素的阶必是

32、G

33、的一个因子。说明：如果a∈G的阶是r,则<{e,a,a2,…,ar-1},∗>是的子群。推论3：一个质数阶的群必定是循环的,并且任一与么元不同的元素都是生成元。二、拉格朗日定理设G={e,a,b,c}，Klein四元群满足下列条件：(1)e的阶为1，a,b,c的阶均为2；(2)a,b,c中任意两个元素运算的结果为第三个元素。推论4：任一四阶群，或为循环群C，或为Klein四元群。4证明：设G={e,a

34、,b,c},其中e是幺元。根据拉格朗日定理可知元素阶只可能是1,2,4。(1)若G中有4阶元a则

35、a

36、=4,={e,a,a2,a3}≌C(≌表示同构)。4(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},*>*eabc*eabceeabceeabc循环群aabceaaecbKlein

37、四元群bbceabbceacceabccbae*eabcd五阶群仅