離散數(shù)學(xué)II課件：6_4子群及其陪集

1、6.4 子 群 及 其 陪 集,6.4.1 子 群 的 定 義 6.4.2 子群的判別條件 6.4.3 循 環(huán) 群 6.4.4 陪 集,捉大頭游戲,它是一種相傳很久的有趣游戲,如下圖,最上面一排是參加抽簽者的名字,最下面一排是簽號、獎品或公差。每個人依次順著豎線往下走，碰到有橫線時，即轉(zhuǎn)向橫向前進，碰到豎線再往下走，依次類推，則只要橫線不要跨過3條豎線（只能跨在兩豎線之間），那么此游戲執(zhí)行完畢后，最上面的每個人會1-1對應(yīng)到最下面一排的位置。一般在設(shè)計游戲時，是由主持人先畫好豎線和橫線，且在最下面先標好簽號，由抽簽者自行填上最上面的人名。有時，為了增加趣味性，先畫好豎線填好上排的人名和下面的簽

2、號，再請參加者自行畫上橫線（不過速度要快，要不然觀察力強者，很快可以找出對應(yīng)關(guān)系）。請同學(xué)們考慮是否可以使用置換的復(fù)合編程處理,6.4.1 子 群 的 定 義,子群 設(shè)（G，）是一個群， H G， 如果 (H， ) 仍是一個群，則 （H，）叫做（G，）的子群。 真子群 如果G的一個子群H不等于G， 即H G，則（H，）叫做 （G，）的真子群。 Note: G的子群H的運算必須與G的運算一樣， 比如， （C*，）不是（C，+）的子群。在群中成立的性質(zhì)在子群仍成立。,子群的例,例. （mZ，+）是整數(shù)加法群（Z，+） 的一個子群。 例. （C，+）以（R，+）、（Q，+）、（Z，+） 為其真子群。

3、 例. （C*，）以（R*，）、（Q*，） 為其真子群。 例. 行列式等于1的所有n階矩陣作成所有n階非 奇異矩陣的乘法群的一個子群。 例. n次交代群是n次對稱群的一個真子群。,平凡子群,群G一般都有兩個明顯的子群,稱為G 的平凡子群： 由其單位元素組成的子群1，稱為G的單位子群； G本身。 其余的子群（如果有的話）稱為非平 凡子群。,子群的例,設(shè)Z6=0,1,2,3,4,5是模6的剩余類集合，則Z6在剩余類加法下是一個群，其中0和Z6是該群的兩個平凡子群，0，3和0，2，4是其非平凡子群，而0，1，3，5不是子群。,例子,例 設(shè)(G,*)是群，對G中任意a,令H=x|x*a=a*x, xG

4、,試證明(H,*)是(G,*)的子群。 證明：顯然1H,即H非空，對H中任意x,y 有(x*y)*a=x*(y*a)=x*(a*y)=(x*a)*y=(a*x)*y=a*(x*y)，故x*yH，即H中*運算封閉。在H中*運算顯然仍滿足結(jié)合律。對H中任意x 有x*a=a*x，于是x-1*(x*a)*x-1=x-1*(a*x)*x-1，化簡得到a*x-1=x-1*a，即x-1 H。證畢 使用同樣辦法可以證明下面練習： 設(shè)G是一個群，H是G的一個子群。aG。試證 aHa-1=aha-1 |hH是G的子群。也稱共扼子群。,6.4.2 子群的判別條件,判別條件一 定理6.4.1 群G的一個子集H是G的一

5、個子群的充分必要條件是： (1) 若aH，bH，則abH； (2) 若aH，則a-1H； (3) H非空。,判別條件一,證明： 必要性 若H是G的子群，則(1)、(3)顯然?，F(xiàn)要證（2）. 先證H中的單位元就是G中的單位元。 設(shè)1G是G中的單位元，1H是H中的單位元。 任取aH，則在H中有： 1H a=a， 故在G中也成立。以a-1右乘得 (1H a)a-1 =aa-1，即，1H (aa-1) =1G ， 1H 1G = 1G ， 故，1H=1G。,判別條件一(證明續(xù)),由群的定義，對于H中的a，應(yīng)有 bH使，ab= 1H=1G ，此式在G中亦成 立，以a-1左乘得b= a-1 1G = a-

6、1 ，因而 a-1H，即（2）成立。 必要性證畢。,判別條件一,充分性 設(shè)(1),(2),(3)成立。 由(3)，H非空。 由(1)，H中的兩個元素a，b可以在H內(nèi)相乘. 在G中成立的結(jié)合律在子集H中自然成立。 往證H中有單位元1G 。任取aH,由(2),a-1H,由(1),aa-1H，即1GH；1G在G中適合1a=a，故在H中亦有此性質(zhì)。 往證H中任意元素a有逆.因由(2),a-1H，但是G中，a-1a=1G，此式在H中亦應(yīng)成立，故a-1即a在H中之逆。 綜上，H在G的運算下是一個群，故是G的子群。,H的單位元素就是G的單位元素， H中任一元素a在H中的逆元素也就是a在G中的逆元素。,子群H

7、與大群G的關(guān)系,判別條件二,定理6.4.2 判別條件一中的兩個條件（1），（2）可以換成下面一個條件 （*） 若aH，bH，則ab-1H。 證明：設(shè)(1),(2)成立，往證（*）成立。設(shè)aH，bH，由（2），b-1H，故由（1），ab-1H，因而（*）成立。,判別條件二(證明續(xù)),設(shè)（*）成立，往證(1),(2)成立。 設(shè)aH，由（*）可推得，aH ，aH，故 aa-1H,即1H。又由（*）可推得，1H，aH，故1a-1H，即a-1H，因而（2）成立。設(shè)aH，bH，因為（2）已證,故b-1H。再由(*)推知,aH,b-1H,故a（b-1）-1H，即 abH，故（1）成立。,例子,例 設(shè)H和K都

8、是群G的子群，令HK=xy|xH,yK。試證若HK=KH，則HK是G的子群（此題的逆命題就是書中習題6.4的14）因為1H,1K，故1HK，即非空。 對于任意的x=hk, y=h1k1,這里h, h1H, k, k1K，有xy- 1 =(hk)(h1k1)-1=h(kk1-1)h-1。 記k2=kk1-1K, 由HK=KH，存在h3H, k3K使k2h1-1=h3k3。 從而xy-1=hh3k3=(hh3)k3HK。由定理6.4.2知HK是G的子群。,判別條件三,定理6.4.3 設(shè)H群G的一個有限非空子集，則H是G的子群的充分必要條件是H對G的運算是封閉的，即若aH，bH，則abH 。 提示：

9、充分性證明用教材201頁習題2得出的結(jié)論：若非空、運算封閉、結(jié)合律、消去律、有限，則為群。,6.4.3 循 環(huán) 群,定理6.4.4 設(shè)a是群G的一個元素。于是a的所有冪的集合 an，n=0，1，2， 做成G的一個子群，記為（a）。此群稱為由a生 成的子群。 證明： （1）（a）非空，至少a0=1（a）。 （2）任?。╝）中二元素am，an，有 am（an）-1=ama-n=am-n（a）。 故由子群判別條件二，（a）做成G的一個子群。,6.4.3 循 環(huán) 群,定義.如果群G可以由它的某元素a生成，即有aG使G=（a），則G叫做一個循環(huán)群，或巡回群。上面定理中的（a）稱為由a生成的循環(huán)子群。 例

10、. 整數(shù)加法群（Z，+）是由1生成的循環(huán)群。（nZ，+）是由n生成的循環(huán)群。 容易證明循環(huán)群必是 Abel群,元素的周期,看由元素a所生成的循環(huán)群（a）： ，a-2，a-1，a0，a，a2， （1） 情形10 如果（1）中所有元素都彼此不同，則稱a的周期為無窮大或0。此時，對任意兩個不同的整數(shù)s與t，asat。 情形20 如果（1）中出現(xiàn)重復(fù)的元素，即有整數(shù) st，使as=at。不妨設(shè)st，于是 s-t0且as-t=1， 即有正整數(shù)m使am=1。 若n為適合an=1的最小正整數(shù)，則稱a的周期（階）為n。,周期的例,例. 4次對稱群中（1 2 3 4）的周期是4，因為 （1 2 3 4）2=（1

11、 3）（2 4） （1 2 3 4）3=（1 4 3 2） （1 2 3 4）4= I 例. 在（C*，）中，1的周期為1，-1的周期為2，i的周期為4，模數(shù)r1的復(fù)數(shù)z=rei的周期為無窮大。,周期的例,例 一個有限群中，周期大于2的元素個數(shù)為偶數(shù)。 證明：任取群中周期大于2的元素a，于是a21，由群的概念知a有逆元a-1，且a a- 1 (否則，若a=a-1，有a2=1，矛盾），這就是說a與a的逆a-1是成對出現(xiàn)的且它們的周期都大于2，由于a的任意性知周期大于2的元素個數(shù)為偶數(shù)。證畢。,周期的例,例 若有限群G的元數(shù)為偶數(shù)，則G中周期等于2的元素個數(shù)一定是奇數(shù)。 例 若群中除單位元外，所有

12、其他元素的周期為2，則該群為Abel群。,周期的性質(zhì),定理6.4.5 若群G中元素a的周期為n，則 （1） 1，a, a2，a3，an-1為n個不同元素； （2）am=1當且僅當nm; （3） as=at當且僅當n(s-t)。,證明：因為任意整數(shù)m恒可唯一地表為 m=nq+r，0rn 故 am=anqar=(an ) qar=1qar=lar=ar； 由于0rn，故按周期的定義知 ar=1 iff r=0 所以 am=1 iff r=0 iff nm 即（2）得證。由（2）即知 as=at iff as-t=1 iff n(s-t)， 即（3）得證，最后由（3）立即可得（1）。,結(jié)論：設(shè)a為群

13、G的一個元素， （1）如果a的周期為無窮大，則（a）是無限循環(huán)群，（a）由彼此不同的元素 ，a-2，a-1，1，a，a2， 組成。 （2）如果a的周期為n，則（a）為n元循環(huán)群，它由n個不同的元素 1，a，a2，a3，an-1 組成。,周期的例,例 設(shè)Sn是n次對稱群。 （1）若Sn， =(a1a2ak)，則 的周期是k。 （2） Sn， = 1 2 s是不相雜輪換的乘積，若i是ki階輪換，i=1,2,s，則的周期是1, 2, ,s的最小公倍數(shù)k1,k2,ks 證（1） k= (a1a2ak) k =(a1)，假若 的周期jk，則 j(a1)= (a1a2ak)j(a1)=aj+1a1,矛盾，

14、這就證明了j=k。,周期的例子,（2）設(shè)的周期為t，k1,k2,ks=d。由于1, 2, ,s是不相雜的，則d= 1d2d sd =(a1)，因此有td。另一方面， t =(a1), 由于兩兩不相雜，必有it =(a1),i=1,2,s。根據(jù)（1）部分的結(jié)果知i的周期為ki，因此對于所有的i 1,2,s有kit，即t是k1,k2,ks的公倍數(shù)，由于d是k1,k2,ks的最小公倍數(shù)，必有dt。綜合上述結(jié)果有t=d。,加法群中元素的周期,在加法群中，(a)應(yīng)換為a的所有倍數(shù)的集合： ，-2a，-a，0，a，2a， *當(*)中的所有元素均彼此不同時，稱a的周期為無窮大或為0；否則當n為適合na=0

15、的最小正整數(shù)時，稱a的周期為n。 注意這里的加法表示滿足交換律的一種抽象運算。 定理6.4.5 若加法群中a的周期為n，則有(1) 0，a，2a，（n-1）a為n個不同元素；(2) ma=0當且僅當nm;(3) sa=ta當且僅當n(s-t),循環(huán)群的生成元素,定理6.4.6 （1） 無限循環(huán)群（a）一共有兩個生成元： a及a-1。 （2） n元循環(huán)群（a）中，元素ak 是（a） 的生成元的充要條件是（n，k）=1。 所以（a）一共有(n)個生成元素。,證明：如果ak是（a）的一個生成元，那么（a）中每個元素都可表示為ak的方冪。特別地，a也可表示為ak的方冪。設(shè) a = (ak) m = a

16、k m。 （1） 由（a）是無限循環(huán)群知，km=1。 因此，k=1。即， a及a-1為無限循環(huán)群 （a）的生成元。,（2） 如果（a）是一個n元有限群，那么a的周期為n。由周期的性質(zhì)知，n|km-1。因此， km-1=nq， km-nq=1。 這說明k與n互質(zhì)。 另一方面，如果k與n互質(zhì)，則有h和-q，使 h k-qn=1， 即，hk-1=qn，故 n(kh-1)，由周期的性質(zhì)知，a1=akh， a=(ak)h.故a可表為ak的若干次方. 總之，a可表為ak的若干次方 iff k與n互質(zhì)。 但在0kn中，共有(n)個k與n互質(zhì)，故共有(n)個元素ak可生成（a）。,例子,例 (Z,+)的生成元

17、只能是1和-1. 若G=(a)是元數(shù)為12的群， (12)=4，與12互質(zhì)的數(shù)有1，5，7，11，因此a, a5,a7， a11是G的所有4個生成元。,群的結(jié)構(gòu),有時需要根據(jù)子群H的一些特點將群分解成（劃分成）一些不相交的子集合之并。如，在（Z,+)中，取一個正整數(shù)m，可得子群nZ=nzzZ，當m=2時，就是所有偶數(shù)在加法下作成的子群，通過這個子群就可以把整數(shù)加法群分解為奇數(shù)和偶數(shù)兩個不相交子集合，它們就是相對于該子群（等價關(guān)系）的等價類-陪集。,6.4.4 陪 集,合同關(guān)系 定義. 設(shè)G是群，H是G的子群，a，bG，若有hH， 使得a =bh，則稱a合同于b(右模H)， 記為ab（右mod

18、H）。 例. 設(shè)G是三次對稱群，H是由（1 2 3）生成的 子群：H=I，（1 2 3），（1 3 2）。 因為有IH，使得（1 2）=（1 2）I，所以 （1 2） （1 2）（右mod H）。 因為有(1 2 3)H,使得(2 3)=(1 2)(1 2 3)， 所以 （2 3） （1 2）（右mod H）。,結(jié)論:合同關(guān)系(右模H)是一個等價關(guān)系。 證明： 1) 證反身性。因為對任意aG， 有1H ，使得a=a1，所以aa（右mod H）。 2）證對稱性。即證若ab(右mod H)，則ba(右mod H)。由a=bh,hH 可以推出b =ah-1，而且h-1H，故ba(右mod H)。 3

19、)證傳遞性。即證若ab(右mod H)，bc(右mod H)，則ac(右mod H)。由a=bh，b=ck，h，kH，可得a=ckh，其中khH，故 ac（右mod H）。,陪集,定義. 群G在合同關(guān)系（右模H）下的一個等價類叫做H的一個右陪集。 同樣，可以界說a合同于b（左模H）：ab（左modH）和H的左陪集。 結(jié)論：a所在的右陪集為 aH=ah|h H。 注意：有些書上把右陪集稱做左陪集，這沒有關(guān)系，只要我們弄清楚就可以了。,陪集的例,設(shè)G是整數(shù)加法群。H是m的所有倍數(shù)作成的子群，因為加法適合交換律，所以左右之分不存在，因而，（左mod H） 和（右mod H）是一樣的，左右陪集也是一樣

20、的。 ab（mod H），即a=b+h(hH),亦即， a=b+km, 故ab（mod m）。 可見，H的陪集就是模m的剩余類。,陪集的例,設(shè)G是所有非0復(fù)數(shù)的乘法群，所有其z=1的復(fù)數(shù)z=ei作成G的一個子群H。ab（mod H）等于說a=b。 在復(fù)平面上，H相當單位圓，H的所有陪集相當以原點為圓心的所有同心圓。,求陪集的簡單方法,若G是一個有限群，求H的右陪集： 首先，H本身是一個； 任取aH，aG,而求aH，又得到一個； 任取b HaH而求bH又得到一個； 如此類推，因G有限，最后必被窮盡，而 G=HaHbH。,例. 設(shè)G是3次對稱群：1,（1 2）,（1 3）,（2 3）,（1 2 3

21、）,（1 3 2）， H：1,（12）， H有三個右陪集： 1,(1 2)，(1 3),(1 2 3)， (2 3), (1 3 2) 。 H有三個左陪集： 1,(1 2)，(2 3), (1 2 3)，(1 3), (1 3 2),定理6.4.7,設(shè)H是群G的有限子群，則H的任意右陪集aH的元數(shù)皆等于H的元數(shù)。 證明： aH=ahhH，又G中有消法律： 由a=ay可以推出=y，故H中不同元素 以a左乘仍得不同的元素。因而aH的元數(shù)等 于H的元數(shù)。證畢 該定理結(jié)果表明所有陪集元素個數(shù)相等。,陪集的性質(zhì),（1）若H為G的有限子群，則|aH| = |H|。 （2）H本身也是H的一個右陪集。 （3）

22、aH=H的充分必要條件是aH。 （4）a在陪集aH中。 根據(jù)這點，把a叫做右陪集aH的一個陪集代表。,陪集的性質(zhì),（5）對于右陪集aH中任意元素b，都有aH=bH。 證明： 由baH知，存在hH，使得b=ah。因此，bH=ahH=a（hH）=aH。 這點說明右陪集aH中任一元素都可以取做陪集代表。 從（5）還可推出： （6）aH=bH的充分必要條件是a-1bH。,陪集的性質(zhì),（7）任意兩個右陪集aH和bH或者相等或者不相交。 證明： 如果aH和bH相交，則它們包含公共元素c，即caH，且cbH。因此， 由（5）得aH=cH，且bH=cH。故， aH=bH。,正規(guī)子群,定義. 設(shè)H是群G的子群,

23、設(shè)對G中的任意元素g,都有g(shù)H=Hg,則稱H是G的正規(guī)子群。 結(jié)論1 “平凡”子群H=1和G都是G的正規(guī)子群 結(jié)論2 Abel群的任意子群是正規(guī)子群。,結(jié)論3 H是G的正規(guī)子群，必要而且只要對任意的gG，gHg-1 H. 證明：必要性. 由H是G的正規(guī)子群，知，對于 任意gG，gH=Hg,即,gHg-1=H，故 gHg-1 H. 充分性. 設(shè)對任意gG，gHg-1 H。既然此式 對任意gG成立，則以g-1G代g仍成立： g-1H（g-1）-1 H，即，g-1Hg H； 以g左乘以g-1右乘之，得H gHg-1 因此，H=gHg-1對任意gG都成立,即，gH=Hg, 因而H是正規(guī)子群。,例子,結(jié)

24、論4；設(shè)H是G的一個子群。H是G的正規(guī)子群當且僅當對G中任意的a，都有aHa-1=H，即H只有一個共扼子群，就是H自己。 證明： aHa-1=HaH=Ha，故有定義可知H是G的正規(guī)子群 aHa-1=H，對G中任意的a成立。,Lagrange定理,設(shè)G為有限群，則G的任意子群H的元數(shù)整除群G 的元數(shù)。 證明： 設(shè)|G|= n，|H|=r。 設(shè)H有s個右陪集,則每個右陪集的元數(shù)等于H 的元數(shù)r，再由不同的右陪集沒有公共元素，知 所有右陪集的并集有元數(shù)rs。 而G等于所有右陪集的并集，故 |G|=n=rs=|H|s， 即，子群H的元數(shù)整除群G的元數(shù)。,反例,注意：此定理逆命題不一定成立，換句話說,若

25、正整數(shù)d是n的因子，但G不一定有d元子群。 如4次交代群（所有偶置換作成的群）A4的元數(shù)為12，6是其因子，但A4沒有6元子群。,H在G中的指數(shù):有限群G的元數(shù)除以H的元數(shù) 所得的商，記為（G：H），稱作H在G中的指數(shù)。 結(jié)論：H的指數(shù)也就是H的右(左)陪集的個數(shù)。 右代表系:從每個右陪集中選出一個元素為代表，全體代表的集合叫做一個右代表系或右代表團。 結(jié)論：設(shè)G有限而g1，gs作成一個右代表系，則g1H，gsH便是H的所有右陪集而 G= g1HgsH。 結(jié)論：指數(shù)等于2的子群一定是正規(guī)子群。,應(yīng)用Lagrange定理,定理6.4.8 設(shè)G為有限群，元數(shù)為n，對任意aG，有an=1。 證明：因為G有限，a的周期必有限，否則a所生成的循環(huán)子群（a）將無限，G的元素將無窮多。命a的周期為m，則a生成一個m元循環(huán)子群（a）。按Lagrange定理，mn，即 n0（mod m），因此an=1。,Lagrange定理的使用,我們可以使用拉格朗日定理確定一個群內(nèi)可能存在的子群、元素的周期等，從而搞清一個群的結(jié)構(gòu)。以前我們確定一個群內(nèi)的子群時，主要利用元素生成的子群。有個這個定理，就可以首先有G的元數(shù)的因子來確定可能存在子群的元數(shù)以及元素的周期，然后根據(jù)子群的元數(shù)來尋找子群。,例子,證明6元群中一定有周期為3的元