群 台大數學系 齊震宇.

Presentation on theme: "群 台大數學系 齊震宇."— Presentation transcript:

1 群 台大數學系 齊震宇

2 問題一 將正立方體的頂點 以三種顏色 著色。 若允許旋轉， 共有多少種不同的著 色法？

3 問題二 將 放置於正立方體八頂點。 若允許旋轉， 共有多少 種不同的放置法？

4 問題三 將 等間隔地放置於一圓周。 若允許旋轉， 共有多少 種不同的放置法？ 若還允許翻面呢？

5 問： 是否有一種方法/觀點 可以 同時對付這些 不太一樣 卻 又有點像的問題？ 這些問題哪裡相像？

6 二元運算(binary operation)
我們常用 表示一集合 及其上的一個 「二元運算」。 例1： 、 (普通的加法) (普通的乘法) 。 例2： 給定一集合 。 (1) 、 與 。 (2) 。 這裡的 是先前提過 的映射的合成操作：

7 二元運算 更精確地說， 定義 一集合 上的一個二元運算 指的是 一個映射 。 約定 為了符號上的簡約， 對於 、 ， 會將 記作 ， 這裡的
一集合 上的一個二元運算 指的是 一個映射 。 約定 為了符號上的簡約， 對於 、 ， 會將 記作 ， 這裡的 可能是任一個符號， 像是 或 等， 只要討論中明確固定下來就好； 在不 會引起誤解時， 我們甚至會寫成 。

8 ( ) 群(groups) 我們先引進幾個與二元運算有關的概念。 以下令 為 一集合 上的一個二元運算。 定義
以下令 為 一集合 上的一個二元運算。 定義 當我們說 是結合的(associative)， 意思是 對任意三個 的元素 、 與 ， 總有 。 ( ) 例3： 、 (普通的加法) (普通的乘法) 。

9 群 我們先引進幾個與二元運算有關的概念。 以下令 為 一集合 上的一個二元運算。 定義 當我們說 是結合的(associative)，
以下令 為 一集合 上的一個二元運算。 定義 當我們說 是結合的(associative)， 意思是 對任意三個 的元素 、 與 ， 總有 。 練習一： 給定一集合 ， 以下何者是結合的？ 、 、 、 。

10 群 我們先引進幾個與二元運算有關的概念。 以下令 為 一集合 上的一個二元運算。 定義 當我們說某個元素 是 的
以下令 為 一集合 上的一個二元運算。 定義 當我們說某個元素 是 的 單位元(unit element)， 意思是 對每個 都有 。 練習二： 有單位元嗎？ 呢？ 練習三： 給定一集合 ， 以下何者有單位元？ 、 、 、 。

11 群 我們先引進幾個與二元運算有關的概念。 以下令 為 一集合 上的一個二元運算。 定義 當我們說某個元素 是 的
以下令 為 一集合 上的一個二元運算。 定義 當我們說某個元素 是 的 單位元(unit element)， 意思是 對每個 都有 。 這樣的元素 如果存在，只會有一個： 如果 也是某個這樣的元素， 則有 。

12 群 我們先引進幾個與二元運算有關的概念。 以下令 為 一集合 上的一個二元運算。 定義 假設 具有單位元 。
以下令 為 一集合 上的一個二元運算。 定義 假設 具有單位元 。 當我們說一個元素 (對 )可逆， 意思是存在某個元素 使得 。 我們稱這樣的元素 為 (對 )的一個反元素或逆元(inverse)。

13 群 練習四： 找出以下每種情況中可逆的元素。 (1) ； (2) ； (3) ； (4) ； (5) ； (6) (給定一集合 ) 、 、
(給定一集合 ) 、 、 。 練習五： 設 具有單位元 而且是結合的。 說明 一個可逆的元素 只有一個反元素。 (此時以 記該反元素； 有些情況下會記為 。)

14 群 定義 一個集合及其上的一個二元運算 被稱為一個群， 如果滿足以下三條件。 (1) 是結合的： (2) 有單位元： (3)
的每個元素都(對 )可逆：

15 群 練習六： 以下哪幾個二元運算給出了群？ (1) ； (2) ； (3) ； (4) (這裡 )； (5) ； (6) (給定一集合 )
(5) ； (6) (給定一集合 ) ( : 映射合成)； (7) (給定一集合 ) 是個對射 (這裡 。)

16 圈表達法(cycle expression)
如果 是個有限的集合， 我們常採用 「圈表達法」 來表示 的元素： 比如說， 若 ， 我們會把 記作 或 。

17 子群(subgroups) 。 定義 給定一個群 ， 我們說一個子集 構成 的一個的子群， 如果 (1) 對任何 與 有
給定一個群 ， 我們說一個子集 構成 的一個的子群， 如果 (1) 對任何 與 有 。 (因此 給出一個 上的二元運算。) (2) 是一個群。 例4： 構成 的一個子群。 例5： 構成 的一個子群。

18 子群 。 定義 給定一個群 ， 我們說一個子集 構成 的一個的子群， 如果 (1) 對任何 與 有 (因此 給出一個 上的二元運算。)
給定一個群 ， 我們說一個子集 構成 的一個的子群， 如果 (1) 對任何 與 有 。 (因此 給出一個 上的二元運算。) (2) 是一個群。 練習七： 設 構成 的一個的子群， 為 的單位元， 為 的單位元。 試說明 (1) ； (2) 一元素 在 中的逆元 等於它在 中的逆元。 (提示：群滿足「消去律」。)

19 子群 給定一個群 。 定義 對任一元素 及一整數 ， 我們以 ， 當 。 記 當 。 ， ， 當 。 構成 的一個子群， 記作 ，
給定一個群 。 定義 對任一元素 及一整數 ， 我們以 ， 個 當 。 記 當 。 ， ， 個 當 。 構成 的一個子群， 記作 ， 稱為(由 生成的)循環子群(cyclic subgroup)。 若 構成 的一個的子群且 ， 則 。 換句話說， 在包含關係之下， 是含有 的子群中「最小」的。

20 子群 兩種情況可能發生： (1) 若 則 。 此時 是無窮集。 此時我們說 的階數是無限大。 (2) 存在兩整數 使得 。 此時有 ，
若 則 。 此時 是無窮集。 此時我們說 的階數是無限大。 (2) 存在兩整數 使得 。 此時有 ， 故 是有限集。 我們稱數字 為 的階數。 練習八： 假設 是有限的(也就是第二種狀況)。 令 是使 的正整數 中最小的。 說明 (1) 對任一正整數 ， 有 。 (2) 。

21 子群 練習九： 求 每個元素的階數。 例6： 考慮 。 任給一整數 ， 。 ( 、 。) (還有別的子群嗎？) 練習十：
求 每個元素的階數。 例6： 考慮 。 任給一整數 ， 。 ( 、 。) (還有別的子群嗎？) 練習十： 說明 的每個子群都形如 (此處 為一整數)。 (提示：考慮ㄧ子群中最小的正元素及除法。) 練習十ㄧ： 找出 所有的子 群。 當中哪些是循環子群？ 有元素個數為五或七的子群嗎？

22 子群 例7： 令 。 任何一個保持輪廓的 旋轉與翻面 都可視為 一個 的元素。 比如說， 逆時針轉 度 對應到 ； 以虛線為軸的翻面對應到 。

23 子群 所有保持輪廓的旋轉與翻面構成 例7： ㄧ個 的子群， 它有 個元素。 其中八個是旋轉： 、 、 、 、 、 、 與 。

24 子群 所有保持輪廓的旋轉與翻面構成 例7： ㄧ個 的子群， 它有 個元素。 其他八個是翻面： 、 、 、 、 、 、 與 。

25 子群 練習十二： 所有保持輪廓的剛體運動構成了 的ㄧ個子群。 事實上， 這個子群 有 個元素。 請找出它們全部。

26 關係(relations)  岔題ㄧ下！ 給定一個集合 。 假設 表示某種 可以對任兩個 的元素 談論成立與否的「關係」。
講個集合論的基本概念。 給定一個集合 。 假設 表示某種 可以對任兩個 的元素 談論成立與否的「關係」。 我們通常用 表示 間 關係 成立。 例8： 所有地球人構成的集合， 表示「 是 的父親」。 我們有 「老布希 小布希」。 例9： ， 表示「 大於或等於 」。 則 「 」。

27 等價關係(equivalence relations)
給定一個集合 及 其上的一個關係 。 定義 我們說 是一個等價關係的意思是 滿足以下三個條件。 反身性 對稱性 傳遞性 例10： 所有地球人構成的集合， 表示「 與 有相同的父母」。

28 等價關係 例11： 所有地球人構成的集合， 表示「 與 有相同的生日」。 例12： 所有地球人構成的集合， 表示「 與 就讀過相同學校」。
表示「 與 有相同的生日」。 例12： 所有地球人構成的集合， 表示「 與 就讀過相同學校」。 例13： 元素為平面上所有三角形的集合， 表示「 與 全等」。 例14： ， 為一給定整數， 表示「 」。

29 等價關係 給定一個集合 及 其上的一個等價關係 。 定義 (1) 對任一元素 ， 我們稱子集 為 (在 之下)的等價類， 記作 。 (2)
給定一個集合 及 其上的一個等價關係 。 定義 (1) 對任一元素 ， 我們稱子集 為 (在 之下)的等價類， 記作 。 (2) 我們稱以所有等價類為元素的集合 為 (在 之下)的商集， 記作 。 換句話說， 。 練習十三： 描述例14中的等價類與商集。 (這有沒有稍稍解釋了「商集」這個怪名稱？)

30 等價關係 給定一個集合 及 一等價關係 。 練習十四： 說明 (1) 對任何 ， 有 。 (2) 對任何 、 ， 有 或 。 推論：
給定一個集合 及 一等價關係 。 練習十四： 說明 (1) 對任何 ， 有 。 (2) 對任何 、 ， 有 或 。 推論： 換句話說， (1) 是所有等價類的聯集， (2) 不同的等價類互不相交。 反過來， 每一種將ㄧ個集合 分割成若干塊 互不相交的子集的方法 恰給出一個等價關係： 兩個元素等價 它們屬於同一個分塊。 (為何是等價關係？ 這時等價類和商集分別是什麼？)

31 群作用(group actions) 。 在現實中， 群常扮演「驅動」其他物件的角色。 給定一個集合 、 一個群 與 一個映射 。 約定
給定一個集合 、 一個群 與 一個映射 。 (用來驅動 的元素) 約定 對任意的 與 ， 為了精簡符號， 我們將 簡記作 或甚至 。 定義 我們說 是一個 在 上的作用， 如果 (1) 對任何 、 與 ， 總有 。 (2) 對任何 ， 總有 。

32 群作用 例15： 可以作用於 如下： 對於 滿足 ， 以及 ， 令 。 例16： 可以作用於 (座標平面)如下： 對於 以及 ， 令 。
以及 ， 令 。 例16： 可以作用於 (座標平面)如下： 對於 以及 ， 令 。 例17： (給定一集合 ) 可以作用於 如下： 對於 與 ， 令 。

33 群作用 假設有一個群 作用在一集合 上。 定義 對任一 ， 我們稱集合 為 (在此作用下的)的軌道。 練習十五：
假設有一個群 作用在一集合 上。 定義 對任一 ， 我們稱集合 為 (在此作用下的)的軌道。 練習十五： 請描述前述三個例子裡群作用的軌道。 你是否發現， 每個例子裡被作用的集合 都是互不相交的軌道的聯集？ (這敘述是不是似曾相識？ 回顧ㄧ下練習十四。)

34 群作用 練習十六： (由群作用所引導出的等價關係) 假設有一個群 作用在一集合 上， 令 表示以下關係： 對任何 與 ， 存在 使得 。
假設有一個群 作用在一集合 上， 令 表示以下關係： 對任何 與 ， 存在 使得 。 (1) 請說明 是一個等價關係。 (2) 此時等價類跟群作用的軌道有關嗎？ 註： 上述由群作用所導出的等價關係是非常重要的概念， 它們的等價類與商集會出現在數學的很多討論當中。

35 群作用 為了討論群作用的應用， 我們現在先 細思一個很具啟發性的例子。 考慮以下問題： 在一個正方形的四個 頂點塗上黑色或白色。 若允許旋轉， 問共有幾種著色法？

36 群作用 令 為以所有(不考慮旋轉)的塗色法為元素 的集合， 它有以下 個元素：

37 群作用 令 為以所有(不考慮旋轉)的塗色法為元素 為保持輪廓的旋轉全體構成的群。 若以 記逆時針旋轉 度， 則 。
令 為以所有(不考慮旋轉)的塗色法為元素 為保持輪廓的旋轉全體構成的群。 若以 記逆時針旋轉 度， 則 。 這個問題的設定有個自然的群作用，比方說 。 可以轉成彼此的著色法最後要視為一樣， 換句話說， 問題歸結為計算相異軌道的個數。

38 群作用 此例中有六個軌道 (六種相異的塗色法)。 如何不靠列舉就求得軌道數呢？ 且待下面分解！

39 左陪集(left cosets)與商集(quotient sets)
作為練習十六的重要例子， 我們詳細探討以下的 例18： 給定一個群 及它的一個子群 。 可以作用於 如下： 對於 與 ， 令 。 在此例中， 的軌道(等價類)為 任一個 ， 記作 。 定義 稱作 的( )左陪集(left coset)。 (注意到有 ， 也就是不寫 也無妨。) Why?

40 左陪集與商集 對於 、 ， 我們有 。 練習十七： 假裝我們沒做過練習十六， 而是 直接規定群 元素間如下的一種關係 ： 。
對於 、 ， 我們有 。 練習十七： 假裝我們沒做過練習十六， 而是 直接規定群 元素間如下的一種關係 ： 。 請直接證明此 是 上的一個等價關係且 ㄧ元素 的等價類恰為 。 群 是所有 左陪集的聯集， 且不相同的 左陪集彼此的交集為空集合。

41 左陪集與商集 定義 我們將此等價關係的商集記為 ， 它的元素為所有的 左陪集， 稱為「 對 的商集」。 練習十八： (1)
我們將此等價關係的商集記為 ， 它的元素為所有的 左陪集， 稱為「 對 的商集」。 練習十八： (1) 描述 對各個子群的商集。 (2) 描述 對子群 的商集 。 (這與前面例14中的等價關係有何關聯？) (例14： 給定整數 ， 若 為「 」， 則 是 上的一個等價關係。)

42 左陪集與商集 練習十九： 任兩個 左陪集都有相同的基數。 定理 給定一有限群 及它的一個子群 ， 必有 。 也可說成： (1) 整除 ；
任兩個 左陪集都有相同的基數。 定理 給定一有限群 及它的一個子群 ， 必有 。 也可說成： (1) 整除 ； (2) 共有 個相異的 左陪集。 證明： 由於 是個有限集合， 與 也是。 被分割成 塊互不相交的 左陪集， 每塊的元素個數又都與 的相同， 故得證。

43 左陪集與商集 練習十九： 任兩個 左陪集都有相同的基數。 定理 給定一有限群 及它的一個子群 ， 必有 。 也可說成： (1) 整除 ；
任兩個 左陪集都有相同的基數。 定理 給定一有限群 及它的一個子群 ， 必有 。 也可說成： (1) 整除 ； (2) 共有 個相異的 左陪集。 推論 給定一有限群 及任一元素 ， 必有 。 證明： 因為 整除 且 ， 故得證。

44 群作用 Burnside 引理 假設一有限群 作用於 一有限集 ， 則全部有 個軌道。 換句話說， 軌道的個數等於
假設一有限群 作用於 一有限集 ， 則全部有 個軌道。 換句話說， 軌道的個數等於 群 的每個元素所「固定」的 的元素的 個數的平均。 我們先舉例說明如何應用 Burnside 引理！

45 群作用 先前提過的問題： 在一個正方形的四個頂點 塗上黑色或白色。 若允許旋轉， 問共有幾種著色法？
令 為所有(不考慮旋轉)的塗色法的集合。 它有以下 個元素：

46 群作用 先前提過的問題： 在一個正方形的四個頂點 塗上黑色或白色。 若允許旋轉， 問共有幾種著色法？
令 為所有(不考慮旋轉)的塗色法的集合。 若以 記逆時針旋轉 度，則 群 自然地作用在 上， 比方說 。 可以轉成彼此的著色法最後要視為是一樣。

47 群作用 先前提過的問題： 在一個正方形的四個頂點 塗上黑色或白色。 若允許旋轉， 問共有幾種著色法？
令 為所有(不考慮旋轉)的塗色法的集合。 若以 記逆時針旋轉 度，則 群 自然地作用在 上， 被 的四元所固定的 的元素的個數分別為 16、2、4 及 2， 故共有 ( ) / 4 = 6 個軌道。

48 群作用 這與我們以前用列舉的方式得到的相同。

49 群作用 以一開始的問題三為例。 將 等間隔地放置於一圓周。 若允許旋轉， 共有多少 種不同的放置法？ 若還允許翻面呢？

50 群作用 所有保持輪廓的旋轉與翻面 在合成操作下構成一個群， 它共有 個元素， 我們按照 它們的「圈形態」列出： 其中有八個旋轉： I. 、
它共有 個元素， 我們按照 它們的「圈形態」列出： 其中有八個旋轉： I. 、 II. 、 III. 、 、 IV. 、 、 與 。

51 群作用 還有八個翻面： V. 、 、 、 、 VI. 、 、 與 。 按照 Burnside 引理，我們要計算的是這 16 個
旋轉及翻面每個能使幾種放置法保持不變。 在以上分成的六大類動作中，同一類的作用顯 然會使同樣多的放置法保持不動。

52 群作用 I. 任何的放置法都會被 保持。 每個放置法相當於將八個色球按 1 至 8 排序。 這樣的方法總數為 。 II.
這樣的方法總數為 。 II. 被 保持不變的放置法必須 將同一個「圈」中的位置放置同色的色球， 也就是位置 1 與 5 要放同色球， 2 與 6 要放 同色球， 3 與 7 要放同色球， 4 與 8 要放同 色球。 這是不可能的，因為只有一顆藍球。 所以沒有被 固定的放置法。

53 群作用 III. 被 保持的放置法也不存在， 因為位置1、3、5、7要放同色，2、4、6、8 也要放同色， 可是我們共有四種顏色的球。
被 保持的放置法也不存在， 因為位置1、3、5、7要放同色，2、4、6、8 也要放同色， 可是我們共有四種顏色的球。 IV. 被 固定的放置法必須將所有 位置放置同色的色球， 這是不可能的。 V. 被 固定的放置法必須將位置 2 與 8、3 與 7、4 與 6 分別放置同色的球， 而這相當於將紅、綠、黃色球分別放在這三 組位置， 再將剩下的藍球與黃球任意放入位 置 1 與 5， 這共有 種可能。

54 群作用 VI. 被此類動作保持的放置法不存在，道理同 II.。 因此， Burnside 引理告訴我們， 若只考慮旋轉，
不同的色球放置法共有 種。 若還考慮旋轉， 不同的色球放置法共有 種。

55 群作用 證明 Burnside 引理前，先做一些一般的討論。 先考慮任一群 作用在任一集合 上。 定義 對每個 ， 我們稱
先考慮任一群 作用在任一集合 上。 定義 對每個 ， 我們稱 為 (在此作用下的)的穩定子(stablizer)。 練習二十： 證明 構成 的一個子群。 練習二十一： 針對前面的方形頂點著色問題， 找出原本16個著色法每個的穩定子。

56 群作用 考慮一個元素 的「軌道映射」： 。 練習二十二： 對於 、 ， 我們有 。 換句話說， 兩個 中的元素作用於 時 給出同樣的結果，
考慮一個元素 的「軌道映射」： 。 練習二十二： 對於 、 ， 我們有 。 換句話說， 兩個 中的元素作用於 時 給出同樣的結果， 若且唯若它們有相同 的 左陪集。

57 群作用 剛才的練習的示意圖如下： 全部的 左陪集 推論： 的所有 左陪集構成的集合 (也就是 對 的商集 ) 與 間有個對射。
的所有 左陪集構成的集合 (也就是 對 的商集 ) 與 間有個對射。 若 與 都是有限的， 則 。 (這個等式來自練習十九，或是其後的定理。)

58 群作用 現在我們已經做好證明 Burnside 引理的準備。 Burnside 引理 假設一有限群 作用於 一有限集 ， 則全部有 個軌道。
假設一有限群 作用於 一有限集 ， 則全部有 個軌道。 證明 關鍵是以下兩點： (1) 上一頁的推論：對每個 ，均有 。 (2) 以「兩種不同的順序」計算 ：

59 群作用 所謂計算 時的兩種不同順序， 指的是 (a) 對每個 先算滿足 的 有幾個， 然後再把對每個 得到的結果加總。 這個和等於 。
對每個 先算滿足 的 有幾個， 然後再把對每個 得到的結果加總。 這個和等於 。 注意到 軌道個數： 可以分成若干個互不相交的軌道的聯集， 而同一軌道中的 所具有的 都相同， 且和為 ， 因為分母恰好是軌道的元素個數。

60 群作用 (b) 對每個 先算滿足 的 有幾個， 然後再把對每個 得到的結果加總。 這個和等於 。 (a) 與 (b) 得到的是同一個數字
對每個 先算滿足 的 有幾個， 然後再把對每個 得到的結果加總。 這個和等於 。 (a) 與 (b) 得到的是同一個數字 (因為是在算同一 個東西啊！)， 所以我們得到 (軌道的個數) 。 兩邊同時除以 便完成了證明。 Q. E. D.