離散數(shù)學(xué)-第7講-拉格朗日定理課件

1離散數(shù)學(xué)（二）1離散數(shù)學(xué)（二）拉格朗日定理陪集11拉格朗日定理2主要內(nèi)容:陪集的性質(zhì)重點(diǎn):

重點(diǎn)和難點(diǎn):拉格朗日定理陪集11拉格朗日定理2主要內(nèi)容:陪集的性質(zhì)重點(diǎn):一、陪集陪集的定義：

設(shè)<H，>為<G，>的子群，對任一aG，定義aH=aH={ah|hH},稱為元素a關(guān)于H的左陪集

a:左陪集aH的表示元素Ha=Ha={ha|hH},稱為元素a關(guān)于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：設(shè)<H,>是群<G,>的子群,aH和bH是任意二個(gè)左陪集,那么,或aH=bH或aH∩bH=?。思路：令命題P：aH∩bH=?

命題Q：aH=bH要證P∨Q為真，即要證┐P→Q為真。即要證┐(aH∩bH=?)→aH=bH證明:假設(shè)aH∩bH≠?，我們證明aH=bH。設(shè)aH∩bH≠?,那么必存在一個(gè)公共元素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,根據(jù)H中運(yùn)算的封閉性知h2(h1)-1h3∈H，所以x∈bH。

同理可證bH?aH。因此aH=bH。一、陪集定理1：設(shè)<H,>是群<G,>的子群,一、陪集定理2：設(shè)<H，>為<G，>的子群,則H的任意左陪集的大小(基數(shù))是相同的。即對任意a,bG有aH=bH=H。證明:假設(shè)H

=

{h1,

h2,

…

,

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

…,

ahm}。定義函數(shù)f:H→aH,對任何一hH，f(h)=ah。

f:H→aH單射,對?h1,h2∈H,若h1≠h2,則ah1≠ah2。

f:H→aH為滿射是顯然的。因此f為雙射，故aH=H

得證。一、陪集定理2：設(shè)<H，>為<G，>的子群,則H的任意一、陪集定理3：設(shè)<H,>是群<G,>的子群,則H的所有左陪集構(gòu)成G的一個(gè)劃分。證明(1)證明H所有左陪集的并集為G。即?a∈G，有

由于H?G且G對封閉可得，。

下面證明。由可得(2)由定理1可知，G中兩個(gè)元素的左陪集要么相等要么不相交。由(1)和(2)可得，H的所有左陪集構(gòu)成G的一個(gè)劃分一、陪集定理3：設(shè)<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的一個(gè)劃分。一、陪集例2群<N6,+6>的子群,H1=<{0,2,4}二、拉格朗日定理定理4：(拉格朗日定理)設(shè)<H,>是有限群<G,>的子群,且|G|=n，|H|=m，那么m|n。說明：設(shè)H的不同左陪集有k個(gè)，那么n=|G|=k|H|=km推論1：質(zhì)數(shù)階的群沒有非平凡子群。說明：<{e},*>和<G,*>叫做群<G,*>的平凡子群。推論2：在有限群<G,>中,任何元素的階必是|G|的一個(gè)因子。說明：如果a∈G的階是r,則<{e,a,a2,…,ar-1},>是<G,>的子群。推論3：一個(gè)質(zhì)數(shù)階的群必定是循環(huán)的,并且任一與么元不同的元素都是生成元。二、拉格朗日定理定理4：(拉格朗日定理)設(shè)<H,>是有二、拉格朗日定理設(shè)G={e,a,b,c}，Klein四元群滿足下列條件：

(1)e的階為1，a,b,c的階均為2；

(2)a,b,c中任意兩個(gè)元素運(yùn)算的結(jié)果為第三個(gè)元素。推論4：任一四階群，或?yàn)檠h(huán)群C4，或?yàn)镵lein四元群。證明：設(shè)G={e,a,b,c},其中e是幺元。根據(jù)拉格朗日定理可知元素階只可能是1,2,4。(1)若G中有4階元a則|a|=4,<a>={e,a,a2,a3}≌C4(≌表示同構(gòu))。(2)若G中無4階元素

則G中除了幺元,剩余的3個(gè)元素階均為2,即a2=b2=c2=e。a*b不可能是a,b或e,否則將導(dǎo)致b=e,a=e或者a=b,產(chǎn)生矛盾。所以a*b=c,同樣地有b*a=c及a*c=c*a=b,b*c=c*b=a。因此這個(gè)群是Klein四元群。二、拉格朗日定理設(shè)G={e,a,b,c}，Klein四元群滿二、拉格朗日定理四階群僅有以下兩個(gè)：<{e,a,b,c},*>五階群僅有一個(gè)：<{e,a,b,c,d},*>循環(huán)群Klein四元群*eabcdeeabcdaabcdebbcdeaccdeabddeabc*eabceeabcaabcebbceacceab*eabceeabcaaecbbbceaccbae二、拉格朗日定理四階群僅有以下兩個(gè)：<{e,a,b,c},*二、拉格朗日定理例3令A(yù)＝{1,2,3}，A上置換的全體S3={pi

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

<S3,

>為三次對稱群，此六階群不是阿貝爾群。

二、拉格朗日定理例3令A(yù)＝{1,2,3}，A上置換的全體S二、拉格朗日定理定理5：設(shè)<H,>是群<G,>的子群,于是b∈aH,當(dāng)且僅當(dāng)a-1b∈H證明:b∈aH,當(dāng)且僅當(dāng)存在一h∈H,使b=ah,即a-1b=h,因而，b∈aH當(dāng)且僅當(dāng)a-1b∈H。設(shè)<H,>是群<G,>的子群,則H

所有不同的左陪集構(gòu)成G的一個(gè)劃分，這個(gè)劃分可以生成G的一個(gè)左陪集等價(jià)關(guān)系R：aRba-1b∈H驗(yàn)證R為等價(jià)關(guān)系(自反性、對稱性和傳遞性)(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：設(shè)<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的一個(gè)劃分右陪集：

Hp1=

Hp4={p1,p4}

Hp2=

Hp5={p2,p5}

Hp3=

Hp6={p3,p6}

可以看出,{{p1,p4},{p2,p5},{p3,p6}}是S3的一個(gè)劃分

p1p2p3p4p5p6p1p1p2p3p4p5p6p2p2p1p5p6p3p4p3p3p6p1p5p4p2p4p4p5p6p1p2p3p5p5p4p2p3p6p1p6p6p3p4p2p1p5Attention:表示元素相同的左陪集和右陪集未必相等,例如p2H≠Hp2。左右陪集確定的等價(jià)關(guān)系也未必是<G,*>的同余關(guān)系,例如,p3~p5,p2~p6,p3

p2~p5

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

>取H={p1,二、拉格朗日定理例4(續(xù))：取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的一個(gè)劃分右陪集：

Hp1=

Hp5

=

Hp6={p1,p5,

p6}

Hp2=

Hp3=

Hp4={p2,p3,p4}可以看出,元素相同的左陪集和右陪集是相同的。H的左陪集等價(jià)關(guān)系也是一個(gè)同余關(guān)系。

p1p2p3p4p5p6p1p1p2p3p4p5p6p2p2p1p5p6p3p4p3p3p6p1p5p4p2p4p4p5p6p1p2p3p5p5p4p2p3p6p1p6p6p3p4p2p1p5從例4可以看出，H的左陪集等價(jià)關(guān)系可以是<G,*>上的同余關(guān)系，也可以不是。那么在什么情況下它一定是同余關(guān)系呢？(引入正規(guī)子群和商群)二、拉格朗日定理例4(續(xù))：取