§6.4離散數(shù)學(xué)子群及其陪集

1、§6.4 子 群 及 其 陪 集,6.4.1 子 群 的 定 義 6.4.2 子群的判別條件 6.4.3 循 環(huán) 群 6.4.4 陪 集,6.4.1 子 群 的 定 義,子群 設(shè)（G，·）是一個群， H ? G， 如果 (H， ·) 仍是一個群，則 （H，·）叫做（G，·）的子群。真子群 如果G的一

2、個子群H不等于G， 即H ? G，則（H，·）叫做 （G，·）的真子群。 Note: G的子群H的運算必須與G的運算一樣， 比如， （C*，·）不是（C，+）的子群。,子群的例,例. （mZ，+）是整數(shù)加法群（Z，+） 的一個子群，其中m為整數(shù)。例. （C，+）以（R，+）、（Q，+）、（Z，+） 為其

3、真子群。 例. （C*，·）以（R*，·）、（Q*，·） 為其真子群。例. 行列式等于1的所有n階矩陣作成實數(shù)域上 所有n階非奇異矩陣的乘法群的一個真子群。例. n次交代群是n次對稱群的一個真子群。,平凡子群,任一群G都有兩個明顯的子群,稱為G的平凡子群：由其單位元素組成的子群{1}，稱為G的單位子群；G本身。其余的子群（如果有的話）稱為非平凡子群。,6.4.2 子

4、群的判別條件,判別條件一定理6.4.1 群G的一個子集H是G的一個子群的充分必要條件是： (1)    若a∈H，b∈H，則ab∈H； (2)    若a∈H，則a-1∈H； (3) H非空。,判別條件一,證明： 必要性 若H是G的子群，則(1)、(3)顯然。現(xiàn)要證（2）.(錯誤證法：由H是G的子群知，H是群，故對?a∈H，有b∈H，使得a

5、b=1，所以b是a的逆，由a的逆的唯一性，知a-1 =b,而b ∈H ，故 a-1 ∈H 。),判別條件一,先證H中的單位元就是G中的單位元。 設(shè)1G是G中的單位元，1H是H中的單位元。任取a∈H，則在H中有： 1H a=a，故在G中也成立。以a-1右乘得 （1H a）a-1 = aa-1，即， 1H （aa-1） = 1G ， 1H 1G = 1G ，故，1H=1G。,判別條件一,由群的定義，對于H中的a，

6、應(yīng)有b∈H，使，ab= 1H，而1H=1G ，因此， ab= 1G，此式在G中亦成立，以a-1左乘得b= a-1 1G = a-1 ，因而a-1∈H，即（2）成立。必要性證畢。,充分性 設(shè)(1),(2),(3)成立。由(3)，H非空。由(1)，H內(nèi)運算封閉.在G中成立的結(jié)合律在子集H中自然成立。往證H中有單位元1G。任取a∈H,由(2),a-1∈H,由(1),aa-1∈H，即1G∈H；1G在G中適合1Ga=a，故在H

7、中亦有此性質(zhì)。往證H中任意元素a有逆.因由(2),a-1∈H，但是G中，a-1a=1G，此式在H中亦應(yīng)成立，故a-1即a在H中之逆。綜上，H在G的運算下是一個群，故是G的子群。,子群H與大群G的關(guān)系：H的單位元就是G的單位元，H中任一元素a在H中的逆元也就是a在G中的逆元。,應(yīng)用判別條件一 例,設(shè)（H1，·），（H2，·）是群（G，·）的兩個 互不包含的子群，證明：H1∪H2≠G。證明：因H1∪

8、H2 ?G，故只需證 G中存在一個元素，它既不屬于H1， 也不屬于H2。由H1，H2互不包含知，存在x，y，使得x∈H1，且x?H2，y∈H2，且y?H1。往證 x·y?H1，且x·y?H2。,用反證法，若x·y∈H1，則由x∈H1 及由H1是G的子群知，x-1∈H1，故， x-1·（x·y）∈H1，即， y∈H1，與y ? H1矛盾。若x

9、·y∈H2，則由y∈H2 及由H2是G的子群知，y-1∈H2，故， （x·y）·y-1∈H2，即， x∈H2，與x ? H2矛盾。因此，x·y?H1∪H2，而x·y∈G，所以H1∪H2≠G。,判別條件二,定理6.4.2 判別條件一中的兩個條件（1），（2）可以換成下面一個條件（*） 若a∈H，b∈H，則ab-1∈H。證明：設(shè)(1),(2)成立，往證（

10、*）成立。設(shè)a∈H，b∈H，由（2），b-1∈H，故由（1），ab-1∈H，因而（*）成立。,設(shè)（*）成立，往證(1),(2)成立。設(shè)a∈H，由（*）可推得，a∈H ，a∈H，故aa-1∈H,即1∈H。若a∈H，又由（*）可推得，1∈H，a∈H，則1a-1∈H，即a-1∈H，因而（2）成立。設(shè)a∈H，b∈H，因為（2）已證,故b-1∈H。再由(*)推知,a∈H, b-1∈H, 則 a（b-1）-1∈H，即 ab∈

11、H，故（1）成立。,應(yīng)用判別條件二 例,給定整數(shù)m，證明(mZ,+)是一個群。證明：注意到(Z,+)是一個群， mZ是Z的非空子集，因此，只需證(mZ,+)是(Z,+)的子群。對任意x,y∈ mZ,存在k,l ∈Z，使得x=km, y=lm, 于是 x-y=km-lm=(k-l)m ∈ mZ 。因此， (mZ,+)是(Z,+)的子群，當(dāng)然本身是一個群。,判別條件三,定理6.4.3 設(shè)H群G的一個有限非空子集

12、，則H是G的子群的充分必要條件是H對G的運算是封閉的，即若a∈H，b∈H，則ab∈H 。提示：充分性證明可用教材201頁習(xí)題2得出的結(jié)論：若集合非空、有限、運算封閉、且適合結(jié)合律、消去律，則為群。還可以利用判別條件一證。,證明：必要性顯然。充分性。由判別條件一知，只需證明若a∈H，則a-1∈H即可。任取a?H, 則由運算封閉性， a,a2, a3,... ?H。 因為 H有限 ,所以?i,j ,有 ai=aj, j

13、>i，故 aj-i=1, a aj- i -1=1 a) 若j- i>1, 則 a-1 =aj- i -1?H。b) 若j- i=1, 則 a=1, 故 a-1 =a ?H。因此，H是G的子群。,應(yīng)用判別條件三 例,設(shè)G是n次對稱群，判斷其非空子集是否是群只需驗證運算是否封閉。試判斷下面子集在置換的乘法下是否是群：(1)所有偶置換的集合(2)所有奇置換的集合 (3){I,(1 2)}(4){

14、I,(12),(13)},6.4.3 循 環(huán) 群,定理6.4.4 設(shè)a是群G的一個元素。于是a的所有冪的集合 an，n=0，±1，±2，…做成G的一個子群，記為（a）。此群稱為由a生成的子群。證明：顯然，（a）? G。（1）（a）非空，至少a0=1∈（a）。（2） 任取（a）中二元素am，an，有 am（an）-1 = ama-n = am-n ∈（a）。故由子群

15、判別條件二，（a）做成G的一個子群。（還可用子群的定義或判別條件一證明）,6.4.3 循 環(huán) 群,定義.如果群G可以由它的某元素a生成，即有a∈G，使G=（a），則G叫做一個循環(huán)群，或巡回群。上面定理中的（a）稱為由a生成的循環(huán)子群。 例. 整數(shù)加法群（Z，+）是由1生成的循環(huán)群。（mZ，+）是由m生成的循環(huán)群。例.設(shè)G是4次對稱群（本身不是循環(huán)群），由（1 2）生成的循環(huán)子群為{I，（1 2）}。,元素的周期,看由元素a所生

16、成的循環(huán)群（a）：…，a-2，a-1，a0，a，a2，… （1）情形10 如果（1）中所有元素都彼此不同，則稱a的周期為無窮大或0。此時，對任意兩個不同的整數(shù)s與t，as≠at。情形20 如果（1）中出現(xiàn)重復(fù)的元素，即有整數(shù) s≠t，使as=at。不妨設(shè)s>t，于是s-t>0且as-t=1， 即有正整數(shù)m使am=1。若n為適合an=1的最小正整數(shù)，則稱a的周期為n。,結(jié)論：群的單位元的周期為

17、1，（1）={1}。 結(jié)論：群中任一元素和它的逆元具有同樣的周期。 證明:若a的周期為無窮大,則顯然a-1的周期也為無窮大。若a的周期為n, a-1的周期為m， 由(a-1)n=a-1?n=(an)-1=1-1=1，知 m≤n（m|n）。由am=((a-1)m)-1=1-1=1 ，知 n≤m (n|m) 。因此，m=n。,周期的例,例. 4次對稱群中（1 2 3 4）的周期是4，因為

18、 （1 2 3 4）2=（1 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ù)r≠1的復(fù)數(shù)z=reiθ的周期為無窮大。 例. （Z,+)中除0以外,其余元素的周期為無窮大。,周期的例,例. 設(shè)（G，·）是群，x，y∈G，且y·x·y-1=

19、 x2，其中x≠1，y的周期是2，試求x的周期。解：由已知x≠1，斷言x2≠1.反證，若x2=1，由已知y·x·y -1= x 2，得y·x·y -1=1，即，y·（x·y -1）=1，又由群中任意元素的逆是唯一的得y-1= x·y-1，兩邊同時右乘y，得x=1，與已知矛盾。,由y·x·y -1= x 2，得：x4=（y·

20、;x·y –1）·（y·x·y –1） =（y·x）·（y–1·y）·（x·y–1） =（y·x）·1·（x·y –1） = y·

21、x2·y –1 = y·（y·x·y –1）·y –1 由已知 = y2·x·y –2由y的周期是2知，y2=1，且 y–2=1。因此，x4= 1·x·1=x。即，x3=1。因此，3是滿足xn=1的n的最小正整數(shù)，即，x的周期是3。

22、,周期的性質(zhì),定理6.4.5 若群G中元素a的周期為n，則 （1） 1，a，a2，a3，…，an-1為n個不同元素； （2）  am=1當(dāng)且僅當(dāng)n∣m; （3） as=at當(dāng)且僅當(dāng)n∣(s-t)。,證明：因為任意整數(shù)m恒可唯一地表為m=nq+r，0≤r<n故am=anqar=(an ) qar=1qar=lar=ar；由于0≤r<n，故按周期的定義知ar=1 iff r

23、=0所以am=1 iff r=0 iff n∣m即（2）得證。由（2）即知 as=at iff as-t=1 iff n∣(s-t)，即（3）得證，最后由（3）立即可得（1）。,結(jié)論：設(shè)a為群G的一個元素，（1）如果a的周期為無窮大，則（a）是無限循環(huán)群，（a）由彼此不同的元素 …，a-2，a-1，1，a，a2，…組成。（2）如果a的周期為n，則（a）為n元循環(huán)群，它

24、由n個不同的元素1，a，a2，a3，…，an-1組成。,加法群中元素的周期,在加法群中，(a)應(yīng)換為a的所有倍數(shù)的集合： …，-2a，-a，0，a，2a，… *當(dāng)(*)中的所有元素均彼此不同時，稱a的周期為無窮大或為0；否則當(dāng)n為適合na=0的最小正整數(shù)時，稱a的周期為n. 定理6.4.5’ 若加法群中a的周期為n，則有(1′) 0，a，2a，…，（n-1）a為n個不同元素；(2

25、′) ma=0當(dāng)且僅當(dāng)n∣m;(3′) sa=ta當(dāng)且僅當(dāng)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)個生成元素。,證明：（1）如果ak是（a）的一個生成元，那么（a）中每個元素都可表示為ak的方冪。特別地，a也可表示為ak的方冪。設(shè) a = (ak) m

26、 = ak m。由（a）是無限循環(huán)群知，km=1。因此，k=±1。即， a及a-1為無限循環(huán)群（a）的生成元。,（2） 必要性。若ak是（a）的一個生成元，那么（a）中每個元素都可表示為ak的方冪。特別地，a也可表示為ak的方冪。設(shè) a = (ak) m = ak m。因（a）是一個n元循環(huán)群，即a的周期為n。由周期的性質(zhì)知，n|km-1。因此， km-1=qn， mk-qn=1。這說明k與n互質(zhì)

27、。,充分性。若k與n互質(zhì)，則有s和t，使sk+tn=1， 故 a1=ask+tn = askatn = (ak) s ( an)t = (ak) s.即a可表為ak的若干次方，因此（a）中每個元素都可表示為ak的方冪， ak是（a）的一個生成元?？傊?ak 是（a）的生成元 iff （n，k）=1。但在0≤k<n中，共有?(n)個k與n互質(zhì)，故共有?(n)個元素ak可生成（a）。,6.4.4 陪

28、 集,合同關(guān)系定義. 設(shè)G是群，H是G的子群，a，b∈G，若有h∈H， 使得a=bh，則稱a合同于b(右模H)，記為a≡b（右mod H）。,例. 設(shè)G是三次對稱群： G={I,(1 2),(1 3),(2 3),(1 2 3),(1 3 2)} ，H是由（1 2 3）生成的子群：H={I，（1 2 3），（1 3 2）}。因為有I∈H，使得（1 2）=（1 2）I，所以 （1 2） ≡（1 2）（右mod

29、 H）。因為有(1 2 3)∈H,使得(2 3)=(1 2)(1 2 3)，所以 （2 3） ≡（1 2）（右mod H）?？沈炞C：（1 2 ） ≡（2 3）（右mod H）， （1 2 ） ≡（1 3）（右mod H）， （1 3 ） ≡（1 2）（右mod H）， （1 3 ） ≡（2 3）（右mod H）， （2 3 ） ≡（1 3）（右mod

30、 H）， H中元素互相合同。,結(jié)論:合同關(guān)系(右模H)是一個等價關(guān)系。證明：1) 證反身性。因為對任意a∈G， 有1∈H ，使得a=a1，所以a≡a（右mod H）。2）證對稱性。即證若a≡b(右mod H)，則b≡a(右mod H)。由a=bh,h∈H 可以推出b =ah-1，而且h-1∈H，故b≡a(右mod H)。3)證傳遞性。即證若a≡b(右mod H)，b≡c(右mod H)，則a≡c(右

31、mod H)。由a=bh，b=ck，h，k∈H，可得a=ckh，其中kh∈H，故a≡c（右mod H）。,陪集,定義. 群G在合同關(guān)系（右模H）下的一個等價類叫做H的一個右陪集。同樣，可以界說a合同于b（左模H）：a≡b（左 mod H）和H的左陪集。,結(jié)論：a所在的右陪集為 aH={ah|h∈ H}。分析：只需證明aH是合同關(guān)系（右模H）下的一個等價類即可。即證明：（1）aH中元素

32、互相合同(等價)。（2）若b與aH中某元素c合同(等價)，則b∈aH .（即證aH中任意元素與aH外任意元素不等價）,陪集的例,設(shè)G是整數(shù)加法群。H是m的所有倍數(shù)作成的子群，因為加法適合交換律，所以左右之分不存在，因而，（左mod H） 和（右mod H）是一樣的，左右陪集也是一樣的。 a≡b（mod H），即a=b+h(h∈H),亦即， a=b+km, m|a-b，故a≡b（mod m）。 可見，H的陪集就是模m的剩余類

33、。,陪集的例,設(shè)G是所有非0復(fù)數(shù)的乘法群，所有其∣z∣=1的復(fù)數(shù)z=eiθ作成G的一個子群H。a≡b（mod H）等于說a=bh (h∈H) ，即∣a∣=∣b h∣=|b|。在復(fù)平面上，H相當(dāng)單位圓，H的所有陪集相當(dāng)以原點為圓心的所有同心圓。,求陪集的簡單方法,若G是一個有限群，求H的右陪集：首先，H本身是一個；任取a?H，a∈G,而求aH，又得到一個；任取b ? H∪aH,而求bH又得到一個；如此類推，因G有限，最后必被窮盡

34、，而G=H∪aH∪bH∪…。,例. 設(shè)G是3次對稱群：{I,(1 2),(1 3),(2 3),(1 2 3),(1 3 2)}，H：{I,(1 2)}，H有三個右陪集：{I,(1 2)}，{(1 3),(1 2 3)}，{ (2 3), (1 3 2) }。H有三個左陪集：{I,(1 2)}，{(2 3), (1 2 3)}，{(1 3), (1 3 2)},定理6.4.7,設(shè)H是群G的有限子群，則H的任意右陪集aH的

35、元數(shù)皆等于H的元數(shù)。證明： aH={ah│h∈H}，又G中有消去律：由ax=ay可以推出x=y，故H中不同元素以a左乘仍得不同的元素。因而aH的元數(shù)等于H的元數(shù)。,陪集的性質(zhì),（1）若H為G的有限子群，則|aH| = |H|。（2）H本身也是H的右陪集。 證明：因為H=1H，所以，H為1所在的右陪集。（3） a在陪集aH中。 證明：因為a=a1∈aH。 根據(jù)這點，把a叫做右陪集aH的一個陪集代表。,（4）aH

36、=H iff a∈H。 證明：必要性：由a=a1∈aH, aH=H得a∈H。充分性（證法一）：由a∈H， a∈aH,知aH=H，否則,a在兩個不同的等價類中，矛盾。（證法二）：往證 aH ? H。任取x∈aH, 則x=ah, h∈H，再由a∈H，及H是G的子群知， x=ah∈H。再證H ?aH。任取x∈H,x=（aa-1）x=a（a-1 x ）,由a∈H,x∈H,及H是G的子群知 a-1 x ∈H,因此， x=

37、a（a-1 x ）∈aH。,（5）對于右陪集aH中任意元素b，都有aH=bH。證法一：由b∈aH知，存在h∈H，使得b=ah。因此， bH=ahH=a（hH）=aH。 證法二：若aH≠bH，由b∈aH知，b在右陪集aH中，而又由（2）知，b在右陪集bH中，b在兩個不同的等價類中，矛盾。證法三：往證aH ?bH.任取x∈aH,則x=ah1,h1∈H，由b∈aH, 知b=ah2, h2∈H. 因此，x=

38、ah1= a(h2h2-1)h1= ah2 ( h2-1h1)=b ( h2-1h1) ∈bH.再證bH ?aH。任取x ∈bH, 則x=bh’, h’∈H，由b∈aH, 知b=ah’’, h’’∈H. 因此， x=bh’= ah’’ h’ ∈aH.(5)說明右陪集aH中任一元素都可以取做陪集代表。,陪集的性質(zhì),從（5）還可推出：（6）aH=bH的充分必要條件是a-1b∈H。 證明：必要性. 由b∈bH,及aH=

39、bH知， b∈aH,故a-1b∈H。充分性. 由a-1b∈H，知， b∈aH,故由性質(zhì)（5），知 aH=bH。,陪集的性質(zhì),（7）任意兩個右陪集aH和bH或者相等或者不相交。 證明： 如果aH和bH相交，則它們包含公共元素c，即c∈aH，且c∈bH。因此，由（5）得aH=cH，且bH=cH。故，aH=bH。,正規(guī)子群,定義. 設(shè)H是群G的子群,設(shè)對G中的任意元素g,都有g(shù)H=Hg,則稱H是G

40、的正規(guī)子群。 gH=Hg 與 對任意 h ∈H,gh=hg是一個意思嗎？ 結(jié)論1 “平凡”子群H={1}和G都是G的正規(guī)子群. 結(jié)論2 Abel群的任意子群是正規(guī)子群。,結(jié)論3 H是G的正規(guī)子群，必要而且只要對任意的g∈G，gHg-1 ? H.證明：必要性. 由H是G的正規(guī)子群，知，對于任意g∈G，gH=Hg,即,gHg-1=H，故 gHg-1 ? H.充分性. 設(shè)對任意g∈G，gHg-1 ? H。既然此

41、式對任意g∈G成立，則以g-1∈G代g仍成立：g-1H（g-1）-1 ?H，即，g-1Hg ?H；以g左乘以g-1右乘之，得H ? gHg-1因此，H=gHg-1對任意g∈G都成立,即，gH=Hg,因而H是正規(guī)子群。,正規(guī)子群的例,例. 設(shè)G是3次對稱群: {I,(1 2),(1 3),(2 3),(1 2 3),(1 3 2)}, 則（1）H1={I,(1 2)}不是正規(guī)子群，因為（1 3）H1≠ H1（1 3）（

42、2） H2={I,(1 2 3),（1 3 2）}是正規(guī)子群.證明：對任意σ∈H2 ，σH2 = H2 σ= H2(1 2) H2= H2 (1 2) ={(1 2),(2 3),(1 3)},因(2 3) ∈(1 2) H2，故(2 3) H2 =(1 2) H2 = H2 (1 2) 。因(2 3) ∈ H2 (1 2) ，故H2(2 3) =H2 (1 2) = (2 3) H2 同理， (1 3) H2= H2 (1

43、3) 。,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ù)。,H在G中的指數(shù):有限群G的元數(shù)除以H的元數(shù)所得的商，記為（G：H），稱作H在G中

44、的指數(shù)。結(jié)論：H的指數(shù)也就是H的右(左)陪集的個數(shù)。右代表系:從每個右陪集中選出一個元素為代表，全體代表的集合叫做一個右代表系或右代表團(tuán)。結(jié)論：設(shè)G有限而g1，…，gs作成一個右代表系，則g1H，…，gsH便是H的所有右陪集而 G= g1H∪…∪gsH。,應(yīng)用Lagrange定理,定理6.4.8 設(shè)G為有限群，元數(shù)為n，對任意a∈G，有an=1。 證明：因為G有限，a的周期必有限，否則a所生成的循環(huán)子群（a）將無限，G的元

45、素將無窮多。命a的周期為m，則a生成一個m元循環(huán)子群（a）。按Lagrange定理，m│n，即n≡0（mod m），因此an=1。,應(yīng)用Lagrange定理,例. 設(shè)有限交換群（G，·）中所有元素之積不等于單位元1，試證明G必為偶數(shù)元群。證明：用反證法。假設(shè)（G，·）為奇數(shù)元群，往證（G，·）中所有元素之積等于單位元1。 由G有限，設(shè)G={1，a1，a2,…,a2n}。,,首先證明對G中任意非單

46、位元的元素a，a≠a-1。假設(shè)G中有元素a，a=a-1，則a2=1，顯然（{1，a}，·）是（G，·）的元數(shù)為2的子群。由Lagrange定理知，2應(yīng)該整除G的元數(shù)。因為G的元數(shù)為2n+1，所以2不整除G的元數(shù)，這就產(chǎn)生了矛盾。,由于任意元素的逆元素是唯一的，即不同的元素有不同的逆元，所以在a1，a2,…,a2n中按如下方法取元素：先任取一ai1及其逆元aj1(i1≠j1)，再在剩下的2（n-1）個元