動機
許多熟悉的計算其實具有相同結構。在整數中解 x+5=2,可以在等式兩邊加上 −5;在非零實數中解 3x=7,可以乘以 31;要還原正方形的一次旋轉,可以向反方向旋轉。這些情況都有一個集合、一種將兩個元素合成第三個元素的運算、一個「不作任何改變」的元素,以及還原每個元素作用的方法。
群論把這些計算之所以成立的性質抽取出來。只要核實幾條公理,本章證明的所有推論便自然成立:消去律、方程解的唯一性,以及乘積逆元的計算規則。無論元素是數、剩餘類,還是物件的重新排列,這些結果都適用。
整章有兩點需要特別留意。第一,一個群由集合連同運算構成。同一集合在某種運算下可以是群,在另一種運算下卻未必是群。第二,元素的運算次序可能影響結果。在不少重要的群中,ab=ba;隨意交換次序會得出錯誤答案。
後面關於陪集與商群的章節直接建基於本章,尤其會用到子群、消去律及逆元的計算。
定義
集合 G 上的二元運算是一個函數 G×G→G。我們將它在 (a,b) 處的值寫成 a∗b,或簡寫為 ab。
陪域必須是 G 這項要求稱為封閉性:兩個 G 中的元素經運算後,結果必須仍是 G 的元素。封閉性是定義的一部分,不能只是希望它成立。減法是 Z 上的二元運算,卻不是 N={0,1,2,…} 上的二元運算,因為 1−2∈/N。
一個群是一對 (G,∗),其中 G 是集合,∗ 是 G 上的二元運算,並滿足以下三條公理。
- 結合律。 對所有 a,b,c∈G,有 (a∗b)∗c=a∗(b∗c)。
- 雙側單位元。 存在元素 e∈G,使每個 a∈G 都滿足 e∗a=a=a∗e。
- 雙側逆元。 對每個 a∈G,都存在元素 b∈G,使 a∗b=e=b∗a。
如果所有 a,b∈G 都滿足 a∗b=b∗a,便稱這個群為阿貝爾(Abel)群;否則稱為非阿貝爾群。群的階記作 ∣G∣,就是 G 的元素個數。公理並沒有要求 G 必須是有限集合,許多重要例子都是無限群。
結合律讓我們可以省略括號。對因子個數作歸納,可知乘積 a1a2⋯ak 無論如何加括號,結果都是同一元素。當 n≥1 時,an 表示 n 個 a 的乘積;另外定義 a0=e。由結合律可得,對 i,j≥0,有 aiaj=ai+j。
設 a 是群 G 的元素。如果有正整數 m 滿足 am=e,則當中最小的 m 稱為 a 的階。如果不存在這樣的 m,便稱 a 具有無限階。
記號。 群通常採用以下兩種記法之一。
- 採用乘法記法時,以 ab 表示乘積,以 e 或 1 表示單位元,以 a−1 表示逆元,以 an 表示冪。
- 採用加法記法時,以 a+b 表示運算,以 0 表示單位元,以 −a 表示逆元,並以 na 表示 a+⋯+a。此時,「a 的階為 m」表示 m 是滿足 ma=0 的最小正整數。
慣例上,加法記法只用於阿貝爾群。兩種記法描述的是相同的數學結構,因此用乘法記法證明的定理可以直接轉換。例如,ab−1 便轉換為 a−b。
描述同一個群時,不要混用兩種記法。尤其當同一集合上有兩種結構時,不能一處用加法記法、另一處用乘法記法,卻不加區分地把兩者都稱為「這個群」。運算本身就是結構的一部分。
例子與非例子
整數的加法。 (Z,+) 是無限阿貝爾群,單位元是 0,元素的逆元是 −a。每個非零元素都有無限階,因為若 ma=0 且 m≥1,便必有 a=0。
非零實數的乘法。 記 R×=R∖{0}。非零實數的乘積仍是非零實數,所以乘法是 R× 上的二元運算。乘法滿足結合律,1 是單位元,而 a−1=1/a。因此 R× 是無限阿貝爾群。同一道理說明,非零有理數集合 Q× 及非零複數集合 C× 在乘法下都是群。
剩餘類的加法。 當 n≥2 時,集合 Z/n={[0],[1],…,[n−1]} 在運算 [a]+[b]=[a+b] 下是阿貝爾群。單位元是 [0],逆元是 −[a]=[−a]。結合律由 Z 中的加法結合律繼承而來。
反例模式
不構成群的結構
- Z 上的減法不滿足結合律。 因為 (5−3)−1=1,但 5−(3−1)=3。所以即使減法在 Z 上具有封閉性,(Z,−) 仍不是群。
- 正整數在加法下沒有單位元。 假設正整數 e 滿足 1+e=1,則 e=0,但零不是正整數。這裏封閉性與結合律成立,但單位元公理不成立。
- 非負整數在加法下缺少逆元。 在 (N,+) 中,單位元 0 確實存在。然而,1+x=0 沒有滿足 x≥0 的解。
- Z 在乘法下缺少逆元。 單位元是 1,但 2x=1 沒有整數解。
置換群
設 X 是集合,以 Sym(X) 表示所有雙射 X→X 構成的集合,運算取為函數複合。每條群公理都有具體理由支持。
- 封閉性。 雙射的複合仍是雙射。
- 結合律。 (f∘g)∘h 及 f∘(g∘h) 都把 x 映至 f(g(h(x)))。
- 單位元。 恆等映射 idX 就是單位元。
- 逆元。 雙射的反函數仍是雙射,並且就是它在群中的逆元。
記 Sn=Sym({1,…,n})。這個群的階為 n!。
約定。 本書中,στ 表示 σ∘τ,所以先作用 τ,再作用 σ。因此,乘積要由右至左讀取。
一個循環 (a1a2⋯ak) 把 a1↦a2↦⋯↦ak↦a1,並固定其餘所有點。
要計算 (12)(23),可以逐點追蹤,先作用 (23):
- (23) 固定 1,然後 (12) 把它映至 2。
- (23) 把 2 映至 3,然後 (12) 固定它。
- (23) 把 3 映至 2,然後 (12) 把它映至 1。
因此 1↦2、2↦3、3↦1。
現在計算 (23)(12),先作用 (12):
- 1↦2↦3。
- 3↦3↦2。
- 2↦1↦1。
所以
(12)(23)=(123),(23)(12)=(132).
由於 (123)=(132),群 S3 是非阿貝爾群。
正方形的對稱
把正方形的頂點按逆時針方向標為 1,2,3,4。一個對稱是平面上保持距離、並把這個正方形映到自身的映射。
這樣的映射會把頂點映至頂點。要看清這一點,只需注意以下兩個事實:
- 在正方形的所有點中,恰好只有頂點不能寫成正方形內另外兩個點的中點。
- 平面上保持距離的映射會保持中點。
對稱也會保持頂點之間的距離。相鄰頂點的距離是一條邊長,相對頂點的距離則是一條對角線長,所以相鄰頂點仍會映至相鄰頂點。此外,平面上保持距離的映射由三個不共線點的像唯一決定,例如頂點 1,2,4 的像。因此,我們可以用每個對稱在頂點上誘導的置換來表示它。對稱的複合正好對應這些置換的複合。
設 r=(1234) 表示逆時針旋轉 90∘,設 s=(24) 表示以通過頂點 1 與 3 的對角線為軸的反射。則 r4=e 及 s2=e。
要計算 srs,先作用 s,再作用 r,最後再作用 s:
- 1↦1↦2↦4。
- 4↦2↦3↦3。
- 3↦3↦4↦2。
- 2↦4↦1↦1。
所以
srs=(1432)=r−1.
正方形恰好有八個對稱。
至多八個。 一個對稱由頂點 1、2、4 的像決定。頂點 1 可以映至 4 個頂點中的任何一個。頂點 2 隨後必須映至頂點 1 的像的 2 個相鄰頂點之一。頂點 4 則必須映至另一個相鄰頂點。因此,對稱至多有 4⋅2=8 個。
至少八個。 考慮 k∈{0,1,2,3} 時的元素 rk 及 rks。
- rk 把 1 映至頂點 1+k,這裏頂點標號按模 4 讀取。它把 2 映至該頂點沿逆時針方向的相鄰頂點。
- rks 也把 1 映至頂點 1+k,因為 s 固定 1。但 s 把 2 映至 4,所以 rks 把 2 映至 rk(4),即該頂點沿順時針方向的相鄰頂點。
這八個元素產生八對不同的「頂點 1 的像、頂點 2 的像」。因此它們彼此不同,正方形對稱群的階就是 8。
單位群 U(n)
固定 n≥2。在 Z/n 上,乘法定義為 [a][b]=[ab],滿足結合律,並以 [1] 為單位元。然而,Z/n 在這個運算下不是群,因為 [0] 沒有逆元。
如果存在 [x] 使 [a][x]=[1],便稱剩餘類 [a] 為一個單位。以 U(n) 表示所有單位構成的集合。
U(n) 在乘法下是群:
- 封閉性。 如果 [a] 及 [b] 的逆元分別為 [x] 及 [y],則 ([a][b])([y][x])=[1]。所以 [a][b] 也是單位。
- 結合律由 Z/n 中的乘法繼承而來。
- 單位元。 [1] 是單位,其逆元為 [1]。
- 逆元。 單位的逆元本身也是單位,因為 [a] 就是它的逆元。
剩餘類的乘法滿足交換律,因此 U(n) 是阿貝爾群。
留意,雖然 U(n)⊆Z/n,但 U(n) 不是 (Z/n,+) 的子群。兩個結構採用不同運算,而且 U(n) 甚至不包含加法單位元 [0]。
設 n≥2 及 a∈Z。則 [a] 在 Z/n 中可逆,當且僅當 gcd(a,n)=1。
證明
(由逆元得到貝祖(Bézout)關係,反之亦然)
首先,這個條件與所選的代表元無關。如果 a′=a+tn,則 a 與 a′ 各自和 n 的公因數完全相同,所以 gcd(a′,n)=gcd(a,n)。
(⇐) 假設 gcd(a,n)=1。由貝祖(Bézout)等式,存在整數 x,y 使 ax+ny=1。取模 n 得 [a][x]=[1]。由乘法交換律,亦有 [x][a]=[1],所以 [x] 是 [a] 的逆元。
(⇒) 假設 [a][x]=[1],則 n 整除 ax−1,所以存在整數 k 使 ax−nk=1。a 與 n 的任何公因數 d 都整除左邊,因此也整除 1。故 gcd(a,n)=1。■
公理的基本推論
一個群恰好有一個單位元。每個元素也恰好有一個逆元,我們將它記作 a−1。
單位元。 假設 e 與 e′ 都是單位元,則
e=ee′=e′.第一個等號用到 e′ 是單位元,第二個等號用到 e 是單位元。
逆元。 假設 b 與 c 都是 a 的逆元,則
b=be=b(ac)=(ba)c=ec=c.中間的一步用到結合律。■
設 G 是群,且 a,b,c∈G。
- 左消去律。 如果 ab=ac,則 b=c。
- 右消去律。 如果 ba=ca,則 b=c。
- 解方程。 方程 ax=b 的唯一解是 x=a−1b。方程 ya=b 的唯一解是 y=ba−1。
- 乘積的逆元。 (ab)−1=b−1a−1。
(1) 左消去律。 在 ab=ac 兩邊同時左乘 a−1,再用結合律:
b=(a−1a)b=a−1(ab)=a−1(ac)=(a−1a)c=c.(2) 右消去律。 同理,在 ba=ca 兩邊同時右乘 a−1 即可。
(3) 解方程。
- 存在性。 a(a−1b)=(aa−1)b=b。
- 唯一性。 如果 ax=b,則 x=a−1(ax)=a−1b。
在右邊作相同論證,可知 ya=b 成立當且僅當 y=ba−1。
(4) 乘積的逆元。 計算兩種次序的乘積:
(ab)(b−1a−1)=a(bb−1)a−1=aa−1=e,(b−1a−1)(ab)=b−1(a−1a)b=b−1b=e.所以 b−1a−1 是 ab 的一個逆元。由逆元的唯一性,它就是唯一的逆元。■
當 G 是非阿貝爾群時,a−1b 與 ba−1 可以不同。因此,只說「以 a 除 b」並不清楚,還必須說明從哪一側運算。
子群
群 G 的子集 H 若滿足以下全部三個條件,便稱為子群,記作 H≤G:
- e∈H;
- 只要 a,b∈H,便有 ab∈H;
- 只要 a∈H,便有 a−1∈H。
這些條件恰好表示,H 在限制後的運算下本身也是群。反過來,假設 H 在限制後的運算下是一個群,其單位元為某個 f。那麼在 G 中有 ff=f=fe,由消去律得 f=e。再由逆元的唯一性,H 中的逆元亦與 G 中的逆元相同。
設 H 是群 G 的非空子集。則 H≤G,當且僅當所有 a,b∈H 都滿足 ab−1∈H。
(⇒) 假設 H≤G 且 a,b∈H。因為 H 對取逆元封閉,所以 b−1∈H。再由 H 對乘法封閉,可得 ab−1∈H。
(⇐) 假設所有 a,b∈H 都滿足 ab−1∈H。由於 H 非空,可以選取一個 a∈H。
- 單位元。 e=aa−1∈H。
- 逆元。 對任何 b∈H,有 b−1=eb−1∈H。
- 封閉性。 對任何 a,b∈H,我們已知 b−1∈H。所以 ab=a(b−1)−1∈H。
子群的三個條件全部成立。■
設 G 是任意群,可以有限,也可以無限。設 H⊆G 是有限的非空子集,而且所有 a,b∈H 都滿足 ab∈H。則 H≤G。
固定 a∈H。由封閉性及歸納法,每個冪 a,a2,a3,… 都在 H 內。
由於 H 有限,這些冪不可能全部不同。因此,存在 1≤i<j 使 ai=aj。設 m=j−i≥1,則
aiam=aj=ai=aie.由左消去律得 am=e。由於 m≥1,元素 am 是 a 的其中一個正整數冪,所以 e∈H。
至於逆元,分兩種情況考慮。
- 如果 m=1,則 a=e,因此 a−1=e∈H。
- 如果 m≥2,則 am−1∈H。它是 a 的逆元,因為 a⋅am−1=am−1⋅a=am=e。
對乘法的封閉性已由假設給出。■
證明透視
有限性與消去律在哪裏起作用
證明依次用到三個要素。H 的有限性只用了一次,即鴿巢原理:無限多個冪 a,a2,a3,… 在 H 中必然重複。接著在 G 而不是在 H 中使用消去律:等式 aiam=aie 是外層群中的等式,在那裏 a−i 存在,儘管我們還不知道它是否屬於 H。分開 m=1 與 m≥2 兩種情況,只是為了確保候選逆元 am−1 是 a 的正冪,從而由封閉性屬於 H。外層群可以無限,只有 H 必須有限。例如,N={0,1,2,…} 是 (Z,+) 的非空子集,而且對加法封閉,但 −1∈/N。1 的加法「冪」1,2,3,… 永不重複,所以鴿巢原理那一步無從入手。
詳解例題
例題 1.3.10
(S3 中的左側與右側方程)
沿用由右至左作用的約定,設 S3 中的 a=(12) 及 b=(123)。
解 ax=b。 由消去律定理,利用 (12)−1=(12),有 x=a−1b=(12)(123)。先作用 (123):
- 1↦2↦1。
- 2↦3↦3。
- 3↦1↦2。
所以 x=(23)。核對可得 (12)(23)=(123),與本章前面的計算一致。
解 ya=b。 由消去律定理,y=ba−1=(123)(12)。先作用 (12):
- 1↦2↦3。
- 3↦3↦1。
- 2↦1↦2。
所以 y=(13)。為核對答案,計算 (13)(12):
- 1↦2↦2。
- 2↦1↦3。
- 3↦3↦1。
結果是 (123),符合要求。
兩個解 x=(23) 與 y=(13) 不同,正好顯示運算不滿足交換律的影響。
例題 1.3.11
(群 U(8))
滿足 0≤a≤7 及 gcd(a,8)=1 的整數 a 恰好是其中的奇數。由模 n 單位判別法,
U(8)={[1],[3],[5],[7]}.乘積。 將每個乘積取模 8:
- 3⋅3=9≡1。
- 5⋅5=25≡1。
- 7⋅7=49≡1。
- 3⋅5=15≡7。
- 3⋅7=21≡5。
- 5⋅7=35≡3。
階與逆元。 單位元 [1] 的階為 1。[3]、[5]、[7] 的階都是 2,因此每個元素都是自己的逆元。
非單位。 非零而不是單位的元素有 [2]、[4]、[6]。例如,[2] 沒有逆元:2x 必是偶數,所以不可能在模 8 下與 1 同餘。
集合 (Z/8)∖{[0]} 甚至不對乘法封閉,因為 [2][4]=[8]=[0]。
例題 1.3.12
(無限群中有限且對運算封閉的子集)
設 H={1,i,−1,−i}⊆C×。H 的每個元素都是 i 的冪:
i1=i,i2=−1,i3=−i,i4=1.所以 H 中任何兩個元素的乘積也必是 i 的冪。此外,由 i4=1 可知,i 的每個冪都等於 i1,i2,i3,i4 的其中一個,而它們全都在 H 內。因此 H 對乘法封閉。由有限子群判別法,即使 C× 是無限群,仍有 H≤C×。
這個例子也具體呈現了有限子群判別法的證明。取 a=i,冪首次在 i5=i1 時重複,得 m=4。證明所找出的逆元是 im−1=i3=−i。的確,i⋅(−i)=1。
在正方形的對稱群中,比較 rs 與 sr。
計算 rs(先作用 s):
- 1↦1↦2。
- 2↦4↦1。
- 3↦3↦4。
- 4↦2↦3。
所以 rs=(12)(34)。
計算 sr(先作用 r):
- 1↦2↦4。
- 4↦1↦1。
- 2↦3↦3。
- 3↦4↦2。
所以 sr=(14)(23)。
由於 rs=sr,這個群是非阿貝爾群。
一致性核對。 在 srs=r−1 兩邊同時左乘 s。由於 s2=e,得到 rs=sr−1。於是
sr−1=s(1432)=(24)(1432).逐點追蹤,先作用 (1432):
- 1↦4↦2。
- 2↦1↦1。
- 3↦2↦4。
- 4↦3↦3。
結果為 (12)(34),與 rs 一致。
常見錯誤
一般而言,(ab)−1=a−1b−1;正確規則是 (ab)−1=b−1a−1。在正方形的對稱群中,rs=(12)(34) 是自身的逆元,但 r−1s−1=(1432)(24)=(14)(23)=sr,是另一個元素。反轉次序後的 s−1r−1=(24)(1432)=(12)(34) 才是正確的逆元。
若把 (12)(23) 由左至右作用,即先作用 (12),會得到 (132) 而不是 (123)。對這個乘積,兩種約定給出互逆的答案。必須先說明約定,並在整個計算中貫徹使用。
U(n) 包含在 Z/n 中,但它是乘法下的群,而非加法下的群:在 Z/8 中,[1]+[1]=[2]∈/U(8),而且 U(8) 不含 [0]。同樣,Z 在 + 下是群,在 × 下卻不是。
其他需要檢查的地方:
- 忘記封閉性。 檢查公理之前,先確認運算結果仍在原集合內。奇整數在加法下,第一步便已不符合要求。
- 只檢查單側的單位元或逆元。 公理同時要求 ea=a=ae 及 ab=e=ba。在非阿貝爾的情況下,除非已知這是一個群,否則不能由一側成立便直接斷言另一側也成立。
- 把有限子集的簡便判別法用於無限集合。 單靠封閉性,不能說明 N 是 Z 的子群。
- 以為群必定有限。 Z 與 R× 都是群,而群中的元素可以有無限階。
練習
快速檢查
(在 S3 中,設 a=(12) 及 b=(23)。計算 (ab)−1、a−1b−1 及 b−1a−1。後兩者之中,哪一個等於 (ab)−1?)
解答
由本章前面的計算,ab=(12)(23)=(123)。取循環的逆元會反轉循環方向,所以 (ab)−1=(132)。
每個對換都是自己的逆元:a−1=(12) 及 b−1=(23)。因此
b−1a−1=(23)(12)=(132),a−1b−1=(12)(23)=(123).所以 (ab)−1=b−1a−1,正如消去律定理所述。另一個次序 a−1b−1 得到不同元素,因為 a 與 b 不交換。
快速檢查
(判斷以下哪些結構是群: (a) (Q,×); (b) (Q×,×); (c) 奇整數在加法下的結構; (d) Z 配以運算 a∗b=a+b+1。)
解答
(a) 不是群。 單位元應為 1,但對每個 x 都有 0⋅x=0=1,所以 0 沒有逆元。
(b) 是群。 非零有理數的乘積仍是非零有理數,所以運算具有封閉性。乘法滿足結合律,單位元是 1,而 p/q 的逆元是 q/p。
(c) 不是群。 集合不對加法封閉,因為 1+1=2 是偶數。
(d) 是群。 這個運算在 Z 上具有封閉性。
- 結合律。 (a∗b)∗c 及 a∗(b∗c) 都等於 a+b+c+2。
- 單位元。 單位元 e 必須滿足 a+e+1=a,所以 e=−1。由於 ∗ 滿足交換律,−1 在左右兩側都符合單位元的要求。
- 逆元。 a 的逆元 x 必須滿足 a+x+1=−1,所以 x=−a−2,仍是整數。
這個群是阿貝爾群。
快速檢查
(列出 U(10),求出每個元素的階與逆元,並舉出模 10 下的一個非零非單位,解釋它為甚麼不可逆。)
解答
滿足 0≤a≤9 及 gcd(a,10)=1 的整數 a 是 1,3,7,9,所以 U(10)={[1],[3],[7],[9]}。
[3] 的冪。 取模 10:
32=9,33=27≡7,34=81≡1.所以 [3] 的階為 4。
[7] 的冪。 取模 10:
72=49≡9,73=343≡3,74=2401≡1.所以 [7] 的階為 4。
[9] 的冪。 92=81≡1,所以 [9] 的階為 2。
逆元。 因為 3⋅7=21≡1,所以 [3]−1=[7] 及 [7]−1=[3]。因為 92≡1,所以 [9]−1=[9]。最後,[1] 的階為 1,而且是自己的逆元。
非零的非單位。 取 [5]。由於 gcd(5,10)=5=1,由模 n 單位判別法可知 [5] 不是單位。也可以直接看出,5x 的個位數總是 0 或 5,所以不可能在模 10 下與 1 同餘。
快速檢查
(證明 H={[0],[2],[4]} 是 (Z/6,+) 的子群。)
解答
H 是非空有限集合。檢查模 6 加法的封閉性:
- 任何元素加上 [0] 都保持不變。
- [2]+[2]=[4]。
- [2]+[4]=[0]。
- [4]+[4]=[8]=[2]。
每個和都在 H 內,所以由有限子群判別法得 H≤Z/6。
也可以直接讀出逆元:−[0]=[0]、−[2]=[4]、−[4]=[2]。
快速檢查
(設 ∗ 是集合 S 上的二元運算。假設 e 是左單位元(即對所有 a,有 e∗a=a),而 f 是右單位元(即對所有 a,有 a∗f=a)。證明 e=f,並由此推得雙側單位元是唯一的。)
解答
只需考慮元素 e∗f。
- 因為 e 是左單位元,e∗f=f。
- 因為 f 是右單位元,e∗f=e。
因此 e=f。這個論證不需要結合律。
現在假設 e 與 e′ 都是雙側單位元,則 e 尤其是左單位元,而 e′ 是右單位元。由上述論證得 e=e′,所以雙側單位元是唯一的。
快速檢查
(設 H={2k:k∈Z≥0}⊆Q×。證明 H 非空且對乘法封閉,但不是子群。指出有限子群判別法的證明中,哪一步在此不適用。)
解答
非空且封閉。 H 包含 1=20,所以非空。它對乘法封閉,因為 2j⋅2k=2j+k,而 j+k≥0。
不是子群。 元素 2∈H 在 Q× 中的逆元是 21。如果某個 k≥0 滿足 21=2k,則有 2k≥1>21,矛盾。所以 21∈/H,即 H 對取逆元並不封閉。
有限子群判別法的證明在哪裏失效。 把證明用於 a=2。各個冪 2,4,8,… 兩兩不同,因此不會出現 i<j 而 ai=aj 的重複情況。證明無法找出滿足 am=e 的 m≥1,因而無法產生候選逆元 am−1。原先正是 H 的有限性,保證了冪必須重複。