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

1离散数学（二）1离散数学（二）拉格朗日定理陪集11拉格朗日定理2主要内容:陪集的性质重点:

重点和难点:拉格朗日定理陪集11拉格朗日定理2主要内容:陪集的性质重点:一、陪集陪集的定义：

设<H，>为<G，>的子群，对任一aG，定义aH=aH={ah|hH},称为元素a关于H的左陪集

a:左陪集aH的表示元素Ha=Ha={ha|hH},称为元素a关于H的右陪集

a:右陪集Ha的表示元素例1：<I,+>是<R,+>的子群，则

3I={3+i|iI}=I，4I={4+i|iI}=I

2.5I={2.5+i|iI},3.4I={3.4+i|iI}3I=4I2.5I∩3.4I=Ø一、陪集陪集的定义：3I=4I2.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=ah1=bh2,因此a=bh2h1-1

下面证明aH⊆bH

：

∀x∈aH,存在h3∈H使得x=ah3,因而x=bh2(h1)-1h3,根据H中运算的封闭性知h2(h1)-1h3∈H，所以x∈bH。

同理可证bH⊆aH。因此aH=bH。一、陪集定理1：设<H,>是群<G,>的子群,一、陪集定理2：设<H，>为<G，>的子群,则H的任意左陪集的大小(基数)是相同的。即对任意a,bG有aH=bH=H。证明:假设H

=

{h1,

h2,

…

,

hm}，那么aH={ah1,ah2,

…,

ahm}。定义函数f:H→aH,对任何一hH，f(h)=ah。

f:H→aH单射,对∀h1,h2∈H,若h1≠h2,则ah1≠ah2。

f:H→aH为满射是显然的。因此f为双射，故aH=H

得证。一、陪集定理2：设<H，>为<G，>的子群,则H的任意一、陪集定理3：设<H,>是群<G,>的子群,则H的所有左陪集构成G的一个划分。证明(1)证明H所有左陪集的并集为G。即∀a∈G，有

由于H⊆G且G对封闭可得，。

下面证明。由可得(2)由定理1可知，G中两个元素的左陪集要么相等要么不相交。由(1)和(2)可得，H的所有左陪集构成G的一个划分一、陪集定理3：设<H,>是群<G,>的子群,一、陪集例2群<N6,+6>的子群,H1=<{0,2,4},+6>,H2=<{0,3},+6>

H1左陪集：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}例3<H,＋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的一个划分。一、陪集例2群<N6,+6>的子群,H1=<{0,2,4}二、拉格朗日定理定理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：一个质数阶的群必定是循环的,并且任一与么元不同的元素都是生成元。二、拉格朗日定理定理4：(拉格朗日定理)设<H,>是有二、拉格朗日定理设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四元群。二、拉格朗日定理设G={e,a,b,c}，Klein四元群满二、拉格朗日定理四阶群仅有以下两个：<{e,a,b,c},*>五阶群仅有一个：<{e,a,b,c,d},*>循环群Klein四元群*eabcdeeabcdaabcdebbcdeaccdeabddeabc*eabceeabcaabcebbceacceab*eabceeabcaaecbbbceaccbae二、拉格朗日定理四阶群仅有以下两个：<{e,a,b,c},*二、拉格朗日定理例3令A＝{1,2,3}，A上置换的全体S3={pi

i=1,2,3,4,5,6}。

<S3,

>为三次对称群，此六阶群不是阿贝尔群。

二、拉格朗日定理例3令A＝{1,2,3}，A上置换的全体S二、拉格朗日定理定理5：设<H,>是群<G,>的子群,于是b∈aH,当且仅当a-1b∈H证明:b∈aH,当且仅当存在一h∈H,使b=ah,即a-1b=h,因而，b∈aH当且仅当a-1b∈H。设<H,>是群<G,>的子群,则H

所有不同的左陪集构成G的一个划分，这个划分可以生成G的一个左陪集等价关系R：aRba-1b∈H验证R为等价关系(自反性、对称性和传递性)(1)自反性

a-1a=e∈H,所以aRa(2)对称性若aRb,则a-1b∈H,所以b-1a=(a-1b)-1∈H,故bRa(3)传递性若aRb,bRc,则a-1b∈H,b-1c∈H,a-1c=a-1

(b*b-1)*c=(a-1b)*(b-1c)∈H,故aRc二、拉格朗日定理定理5：设<H,>是群<G,>的子群,二、拉格朗日定理例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的一个划分

p1p2p3p4p5p6p1p1p2p3p4p5p6p2p2p1p5p6p3p4p3p3p6p1p5p4p2p4p4p5p6p1p2p3p5p5p4p2p3p6p1p6p6p3p4p2p1p5Attention:表示元素相同的左陪集和右陪集未必相等,例如p2H≠Hp2。左右陪集确定的等价关系也未必是<G,*>的同余关系,例如,p3~p5,p2~p6,p3

p2~p5

p6。二、拉格朗日定理例4：我们来考察<S3,

>取H={p1,二、拉格朗日定理例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,*>上的同余关系，也可以不是。那么在什么情况下它一定是同余关系呢？(引入正规子群和商群)二、拉格朗日定理例4(续)：取