# 拉格朗日定理 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$，然後併到子群的每個人

<center>


</center>

要注意的是，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 數量)

<center>


</center>

||~~當然這不夠嚴謹啦! 但我喜歡這樣表示~~||

### 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