--- # System prepended metadata title: 拉格朗日定理 Lagrange's Theorem tags: [內湖高中程式競賽] --- # 拉格朗日定理 Lagrange's Theorem 拉格朗日定理告訴我們子群、coset 的關係，算是群論中很重要的定理 這篇是我讀代數時做的筆記，以下證明都亂證一通，看起來很對但實際上我也不知道對不對 ## 子群 Subgroup 不知道為什麼，數學家都很喜歡研究一些數學物件的子物件，group 也不例外 ### 定義 設一個群 $G$，若 $H\subseteq G$ 符合下列三個條件 : 1. $H$ 非空 2. 對於所有 $a,b\in H$，$ab\in H$ 3. 對於所有 $a\in H$，$a^{-1}\in H$ 則 $H$ 為 $G$ 的子群，寫作 $H\leq G$ 第 1 點要這樣定是因為邏輯學本來就這樣要求，阿不然就會出現像是「建中女學生都很可愛」的例子 (建中女學生是空集合，他是假的，假的東西你怎麼瞎掰都會對) 第 2 點、第 3 點其實就是封閉性，這樣才能保證 $H$ 也是 group ### 例子 #### 僅有單位元素的集合 $\{e\}\subseteq G$ 顯然，因為 $\{e\}\neq \emptyset, e^{-1}=e, ee=e$ #### $G$ 本人 trivial #### dihedral group 的 rotate 這邊驗一下 $R=\{e,r,r^2,\cdots,r^{n-1}\}$ 是 $D_{2n}$ 的 subgroup - $R\subseteq D_{2n}$，顯然非空 - 對於所有 $a,b\in\{0,1,2,\cdots,n-1\}$，$r^a~r^b=r^{ab}\in R$，根據定義 - 對於所有 $a\in\{0,1,2,\cdots,n-1\}$，$r^{-a}\in R$，根據定義 ### 子群檢定 The Subgroup Criterion 這邊是個定理，我們可以利用它來驗證子群，很方便 #### 定理 $H\leq G$ 若且為若 : - $H\neq \emptyset$ - 對於所有 $a,b\in H$，$ab^{-1}\in H$ #### 證明 $\Rightarrow$ : 假設 $H\leq G$，對於所有 $a,b\in H$，根據逆元是封閉的性質 $b^{-1}\in H$，因此根據乘法封閉性 $ab^{-1}\in H$。$H\neq \emptyset$ trivial $\Leftarrow$ : 假設對於所有 $a,b\in H$，$ab^{-1}\in H$，且 $H$ 非空 要證明這個方向就要把原本的封閉性證出來，要先當封閉性不存在 (不可以用這個性質) 取出 $a,b\in H$ 感覺可以舉幾個 case : - 若 $a=b$，則 $ab^{-1}=aa^{-1}=e\in H$，單位元素 $e$ 也在 $H$ 中 - OK 上一步說 $e$ 也在裡面，所以取 $a=e$ 也沒問題，因此 $ab^{-1}=b^{-1}\in H$，逆元封閉性就出來了 - 上一步說逆元也在 $H$ 裡，那就設 $k=b^{-1}$ 應該沒問題，所以 $ak^{-1}=a(b^{-1})^{-1}=ab=H$，乘法封閉性就出現了 ### 更多例子 接下來就來驗驗一些怪怪的子群吧! #### 中心 給一個群 $G$，他的中心就是 $$Z(G) = \{ z \in G \mid zg = gz, \forall g \in G \}$$ 感覺就是會交換的東西。我們來驗一下他是不是子群 - 對於非空，可以挑 $e$ 使得對於所有 $g \in G$，$eg=ge=g$，所以這個子群至少有 $e$，所以非空 - 對任意 $y\in Z(G)$，根據定義 $yg=gy$ 對於所有 $g\in G$，如果左乘右乘 $y^{-1}$，那麼會得到 $(y^{-1}y)gy^{-1}=y^{-1}g(yy^{-1})$，然後就得到 $gy^{-1}=y^{-1}g$，因此逆元也在 $Z(G)$ - 接下來看看 $xy^{-1}$ 會不會也在裡面，感覺 $g$ 可以一個一個交換 $xy^{-1}g=xgy^{-1}=gxy^{-1}$。因為 $(xy^{-1})g=g(xy^{-1})$，所以 $xy^{-1}\in Z(G)$ 推完了 #### 子群的交集也是子群 設 $\{H\}_{\alpha\in A}$ 是一坨 $G$ 的子群，則 $H=\bigcap\limits_{\alpha\in A} H_\alpha$ 也是 $G$ 的子群 我們來驗一下 : - 非空 trivial，因為肯定有單位元 - 對於每個 $y\in H$，$y$ 都會存在於每個 $H_{\alpha}$，因此每個 $H_{\alpha}$ 也都存在 $y^{-1}$ (因為他們是子群)，因此 $y^{-1}\in H$ - 對於每個 $x\in H$，因為 $x$ 也都存在於每個 $H_{\alpha}$，因此每個 $H_{\alpha}$ 裡面都有 $xy^{-1}\in H_{\alpha}$，所以 $xy^{-1}\in H$ 驗完了 ## 生成子群 Generated Subgroup 就跟線性代數的 span 一樣，群論也提出類似的概念叫做 generate ### 定義 令 $S\subseteq G$，我們說 $S$ 生成的子群最小包含 $S$ 的子群，表示為 : $$\langle S\rangle=\bigcap_{H\le G, S\subseteq H}H$$ 前面有講說子群的交集也是子群，$\langle S\rangle\le G$ 無誤。其實也有另一種定義方式長這樣 : $$\overline{S}=\{s_1^{\epsilon_1}s_2^{\epsilon_2}\cdots s_n^{\epsilon_n}|n\in \mathbb{N}, n\ge 0\text{ and }s_i\in S, \epsilon_i=\pm1 \text{, for each } i\}$$ 兩種定義方式一樣，也就是 $\overline S=\langle S\rangle$ 其實只要證同時滿足 $\overline S\le\langle S\rangle$ 跟 $\overline S\ge\langle S\rangle$ 就好，因為我懶所以不想寫 ### 舉例 - $D_{8}$ 裡面的 $S=\{r^2, s\}$，他生成出的子群就是 : $\{e, r^2, s, sr^2\}$ - $D_{8}$ 的 $S=\{r\}$ 生成出來的子群就是 : $\{e,r,r^2,r^3\}$ - $\mathbb{Z}$ 加法群裡的 $S=\{3\}$，生成出來就是 $\{0,\pm3,\pm6,\pm9,\cdots\}$ ## 循環群 Cyclic Group ### 定義 這邊就簡單定義兩個東西 : - 若 $G$ 存在一個元素 $g\in G$ 使得 $\langle g\rangle=G$，則稱 $G$ 為循環群 - 若 $H\le G$，且存在一個元素 $g\in G$ 使得 $\langle g\rangle=H$ 則稱 $H$ 為循環子群 ### 舉例 - $\mathbb{Z}=\langle 1\rangle$ 是一個循環群 不難發現 $\langle 1\rangle$ 生成出來的群長這樣 : $\{0,\pm 1, \pm 2,\cdots\}$ - $\langle r\rangle$ 是 $D_8$ 的循環子群 ## 元素與群的 Order 老樣子，數學家在研究一個數學物件時，經常喜歡定義其大小，所以就有 order 這個東西 ### 定義 - $g\in G$ 的 order 為最小的正整數 $n$ 使得 $g^n=e$，寫作 $|g|=n$。若不存在 $n$，則稱 order 無限，也就是 $|g|=\infty$ - 一個群 $G$ 的 order 就是他的元素數量，寫作 $|G|$ ### 來一些有趣的性質 #### $|g|=|\langle g\rangle|$ 就...這個性質還蠻直觀的 #### $|g|=|g^{-1}|$ 假設 $|g| = n$，其中 $n$ 是一個正整數，我們要證明 $|g^{-1}|$ 也是 $n$，換句話說就是同時符合 $|g^{-1}| \le n$ 與 $|g^{-1}| \ge n$ - 第一步 : 證明 $|g^{-1}| \le n$ 根據假設 $e=g^n$，取反元素後 $e^{-1}=(g^n)^{-1}=(g^{-1})^n=e$，因此必滿足 $|g^{-1}| \le n$ - 第二步：證明 $n \le |g^{-1}|$ 設 $|g^{-1}| = m$，根據定義得 $(g^{-1})^m = e$，兩邊取反 $e^{-1}=((g^{-1})^m) ^{-1}=g^m=e$，因此 $n\le m=|g^{-1}|$ 因此得到 $|g|=|g^{-1}|$ 阿無限的情況應該反證法一下就出來了，所以我懶得寫 ## 陪集 Coset ### 定義 對於任何 $H\le G$，任何 $g\in G$ : - $gH = \{gh|h\in H\}$ 稱作 left coset - $Hg = \{hg|h\in H\}$ 稱作 right coset 其實就是找一個 $G$ 裡面的人 $g$，然後併到子群的每個人
![shapes at 26-02-04 09.07.33](https://hackmd.io/_uploads/HJcXhMlvWg.png =300x)
要注意的是，coset 是 set，不是 group ### Coset 的集合 設 $H\le G$，我們稱 $G/H$ 為 left coset 的集合，即 $$G/H=\{gH|g\in G\}$$ 其中 $gH=\{gh|h\in H\}$ 然後就是這些 left coset 的聯集會反過來形成 $G$。這邊我想稍微避免用到 quotient group 的東西，至於 quotient group 是什麼我們改天再來談，這邊要講 Lagrange's theorem 的話，這些材料就很夠了 ### Cosets 互斥 #### 定理 設 $H\le G$ 且 $a,b\in H$，則 $aH=bH$ 或 $aH\cap bH=\emptyset$ #### 證明 假設 $aH\cap bH=\emptyset$，則存在 $h_1,h_2\in H$ 使得 $ah_1=bh_2$。推得 $a=bh_2h_1^{-1}$，因此 $aH=(bh_2h_1^{-1})H$。由於 $h_2h_1^{-1}\in H$ (子群驗證可得)，所以 $bh_2h_1^{-1}=a\in bH$，得到 $aH\subseteq bH$。當然我們也可以反著做，所以得到 $bH\subseteq aH$。兩這合起來就是 $aH=bH$ ### Cosets 的大小 #### 定理 設 $H\le G$，所有 $H$ 的 cosets 都有相同大小 #### 證明 可以考慮用一個映射 $\varphi_a : H\to aH$，然後就會發現他是 bijection，所以就可以證明他們是相同 size。阿然後這裡空間太小了不適合寫證明 ### 子群的 Index 每個 coset 是互斥的關係，彼此之間不會有交集。因此可以用 index 表示他們的數量 子群 $H$ 的 index 就是指他的 coset 數量，表示成 $[G : H]$ 其實 index 就是 coset 的集合的大小 $|G/H|=[G:H]$ ## 拉格朗日定理 Lagrange's Theorem ### 定理 設 $G$ 是有限群且 $H\le G$，則 $|H|$ 整除 $|G|$ ### 證明 因為前面的映射可以知道 $H$ 跟 $gH$ 是 bijection，所以 $|H|=|gH|$ $$|G|=|H|\cdot[G : H]$$ 所以 $$\frac{|G|}{|H|}=[G : H]$$ 這邊直觀的理解就是 : ($G$ 的大小)$=$ (coset 大小) $\times$ (coset 數量)
![shapes at 26-02-03 11.43.13](https://hackmd.io/_uploads/B1AJye1v-l.png =350x)
||~~當然這不夠嚴謹啦! 但我喜歡這樣表示~~|| ### fun facts - 拉格朗日定理可以幫我們證出費馬小定理跟歐拉定理，是個很棒的定理 - Lagrange 並沒有證明出這個定理，他那個年代沒有群論 ---- ## 參考資料 - Dummit, Foote - Abstract Algebra, 3/e - [Wikipedia - Lagrange's theorem (group theory)](https://en.wikipedia.org/wiki/Lagrange%27s_theorem_(group_theory)) - 某讀書會用的 [ppt](https://github.com/bearomorphism/math-slides/blob/86f997d124ad2656d1d6cf023a3c3ff5436c39fc/subgroups/main.pdf) ---- > [ShanC 程式競賽筆記](https://hackmd.io/@ShanC/B1ouGxqcC) > 作者: ShanC > 更新: 2026/2/4