Groups
===

###### tags: `Mathematics` `Abstract Algebra` `Groups`

[TOC]

## 定義與基本定理
群 (Group) 為基本代數結構之一，首先給定一個群 $G$，我們列出此代數結構的基本定義 :
:::info
__Definition__ Group :
1. _滿足封閉性 (Closure)_. $a,b\in G\implies a\cdot b\in G$
2. _滿足結合律 (Associativity)_. $a,b,c\in G\implies (a\cdot b)\cdot c=a\cdot (b\cdot c)$
3. _存在單位元素 (Identity)_. $\exists e\in G$ s.t. $\forall a\in G,a\cdot e=e\cdot a=a$
4. _存在反元素 (Inverses)_. $\forall a\in G,\exists b\in G$ s.t. $a\cdot b=b\cdot a=e$ (i.e. $b=a^{-1}$)
:::
:::danger
__註__: 一般我們所說的集合 (Set) 並非群，集合裡只有元素而無法運算，需要搭配 __單一個__ 運算子並且滿足上面的定義才稱為群。
:::
:::success
__Theorem 1.__ 單位元素唯一性 (Uniqueness of the Identity) :
在 $G$ 中, 只會存在唯一一個單位元素。
:::
__證明__ : 在這我們可以使用反證法，首先我們假設 $G$ 中存在兩個不同單位元素 $e$ 和 $e'$ ($e\neq e'$)，則透過群的第三個定義我們可知 :
1. $e'\cdot e=e$
2. $e'\cdot e=e'$

這代表 $e'=e$，這與我們一開始假設 $e\neq e'$ 矛盾，所以可推得 $e$ 和 $e'$ 是同一個單位元素。

:::success
__Theorem 2.__ 消去律 (Cancellation) :
在 $G$ 中，$b\cdot a=c\cdot a\implies b=c$ 且 $a\cdot b=a\cdot c\implies b=c$.
:::
__證明__ : 假設 $b\cdot a=c
\cdot a$，由於群中的元素皆存在反元素，假設 $a'$ 為 $a$ 的反元素並得到新的等式 $(b\cdot a)\cdot a'=(c
\cdot a)\cdot a'$，再透過結合律可得 $b\cdot (a\cdot a')=c
\cdot (a\cdot a')$，又 $a\cdot a'=e$，$e$ 為單位元素，所以 $b\cdot e=c
\cdot e$ 可化簡為 $b=c$。
:::success
__Theorem 3.__ 反元素唯一性 (Uniqueness of Inverses) :
在 $G$ 中，$\forall a\in G,\,\exists b\in G$ s.t. $a\cdot b=b\cdot a=e$ 且 $b$ 唯一.
:::
__證明__ : 假設 $G$ 中的元素 $a$ 存在兩個不同的反元素 $b$ 和 $c$ ($b\neq c$)，我們可知 :
1. $a\cdot b=e$
2. $a\cdot c=e$

由於單位元素唯一，所以推得 $a\cdot b=a\cdot c$，再由消去律可知 $b=c$ 與假設矛盾，$a$ 只有唯一反元素。
:::success
__Theorem 4.__ Socks-Shoes Property :
在 $G$ 中，$\forall {a,b}\in G,\, (a\cdot b)^{-1}=b^{-1}\cdot a^{-1}$
:::
__證明__ : 由於群具有封閉性，$a\cdot b$ 仍為群中的元素必存在反元素 $(a\cdot b)^{-1}$ 使得 $(a\cdot b)\cdot(a\cdot b)^{-1}=e$。假設 $(a\cdot b)^{-1}=b^{-1}\cdot a^{-1}$，所以 $(a\cdot b)\cdot(a\cdot b)^{-1}=(a\cdot b)\cdot (b^{-1}\cdot a^{-1})$，由結合律可知等式左邊 $(a\cdot b)\cdot (b^{-1}\cdot a^{-1})=e$，兩邊等式成立。

---
### Examples
#### Example 1. Are the sets of $\mathbb {Z,Q,R}$ all groups?
The sets of $\mathbb {Z,Q,R}$ are all groups under the ordinary addition. In each case, the identity is 0, and the inverse of $a$ is $-a,\forall a\in G$.
#### Example 2. Is the set of $\mathbb Z$ a group under ordinary multiplication?
The set of $\mathbb Z$ is not a group under the ordinary multiplication. Since the identity is 1, we cannot find the inverse of 5 in $\mathbb Z$ s.t. $5\cdot 5^{-1}=1$.
#### Example 3. Is the set of $\mathbb Z$ a group under ordinary subtraction?
Because the ordinary subtraction is not associative, the set of $\mathbb Z$ is not a group under ordinary subtraction.

---
## 術語及符號定義
:::info
__Definition__ 群的階 (Order of a Group) :
群中元素的個數 (可為無限或有限個元素)，使用 $|G|$ 或 $ord(G)$ 來表示群 $G$ 的階。
:::
:::danger
__註__: $|G|\neq\infty$ 稱作 __有限群__。
:::
:::info
__Definition__ 元素的階 (Order of an Element):
$g$ 為群 $G$ 的一個元素，則 $g$ 在 $G$ 的階為 $n$，$n$ 為一最小正整數使得 $\underbrace {g\cdot g\cdot ...\cdot g}_{n\, times}=e$，用 $|g|$ 或 $ord(g)$ 表示。
:::
:::danger
__註__: 若 $n$ 不存在，則 $|g|=\infty$.
:::
:::info
__Definition__:
$G$ 為群且 $a\cdot b=b\cdot a,\forall a,b\in G$，則 $G$ 稱為交換群 (Abelian Group)。
:::
:::danger
__註__: 並不是所有群都是交換群。
:::
:::info
__Definition__:
$U(n)$ 為一集合，集合內的元素小於 $n$ $(n>1)$ 的正整數且與 $n$ 互質。
:::
:::danger
__註__: $U(n)$ 搭配乘法模餘 $n$ 的運算是一個群。
:::

---
### Examples

#### Exampe 4. Consider a group $U(15) under multiplication modulo 15.Find the order of the group and the order of each element of the group.
$U(15)=\{1,2,4,7,8,11,13,14\}$, so this group has order 8.
$|1|=1,|2|=4,|4|=2,|7|=4,|8|=4,|11|=2,|13|=4,|14|=2$
#### Example 5.
For fixed point $(a,b)\in\mathbb R^2$ define: $T_{a,b}:\mathbb R^2\rightarrow \mathbb R^2$ by $(x,y)\rightarrow (x+a,y+b)$. Then $G=\{T_{a,b}|a,b\in\mathbb R\}$ is an abelian group under function composition (_i.e._ $T_{a,b}\cdot T_{c,d}=T_{a+c,b+d}$). The elements of $G$ are called _translations_.
#### Example 6. Check $U(10)$ is a group under multiplication modulo 10.
$U(10)=\{1,3,7,9\}$. The Cayley table for $U(10)$ is
$$
\begin{array}{c|lcr}
\mod10&1&3&7&9\\\hline
1&1&3&7&9\\
3&3&9&1&7\\
7&7&1&9&3\\
9&9&7&3&1\\
\end{array}
$$
The Cayley table show that
1. The operation is closure.
2. The operation is associative.
3. The identity is 1.
4. Each element has an inverse of itself.
5. The operation is commutative.

Therefore, $U(10)$ is an abelian group under multiplication modulo 10.
:::warning
From this example, we can get the conclusion below.
The set $\{1,2,3,...,n-1\}$ is a group under multiplication modulo $n$$\iff n$ is prime.
:::

---
## Summary of Group Examples
($F$ can be any of $\mathbb {Q,R,C},Z_p$)
>This table is from **[Contemporary Abstract Algebra](http://www.d.umn.edu/~jgallian/)**.
---
## Subgroup
子群 (Subgroup) 的定義如下:
:::info
__Definition__ Subgroup:
若在群 $G$ 的運算下，$G$ 中的非空子集合 (Subset) $H$ 也是一個群，則 $H$ 為 $G$ 的子群。
1. _滿足封閉性 (Closure)_. $a,b\in H\implies a\cdot b\in H$
2. _滿足結合律 (Associativity)_. $a,b,c\in H\implies (a\cdot b)\cdot c=a\cdot (b\cdot c)$
3. _存在單位元素 (Identity)_. $G$ 的單位元素必須存在 $H$。
4. _存在反元素 (Inverses)_. $\forall a\in H,\exists b\in H$ s.t. $a\cdot b=b\cdot a=e$ (i.e. $b=a^{-1}$)
:::
若我們想證明一個群中的非空子集合是否為子群，我們不須證明定義中全部的特性。事實上，$G$中的元素都滿足第二個特性，而 $H$ 的元素都在 $G$ 所以必定符合。另外第三個特性也可以由特性一跟四推得，所以我們僅須測試群中的非空子集合是否滿足特性一跟四即可。下面列出幾個不同的測試子群定理，皆可使用:

:::success
__Theorem 5.__ One-step Subgroup Test:
給定一個群 $G$，$H$ 為 $G$ 中的非空子集合， $\forall a,b\in H,\exists a\cdot b^{-1}\in H\iff H$ 為 $G$ 的子群。
:::
__證明__ :
1. $H$ 為 $G$ 的子群 $\implies\forall a,b\in H,a\cdot b^{-1}\in H$
$b\in H\vdash b^{-1}\in H$ 又 $a,b^{-1}\in H\vdash a\cdot b^{-1}\in H$ 得證。
2. $\forall a,b\in H,a\cdot b^{-1}\in H$ $\implies H$ 為 $G$ 的子群
* 首先證明 $e\in H$，已知 $H$ 非空，$\forall a\in H$，當 $b=a$，由假設可知 $a\cdot b^{-1}=a\cdot a^{-1}=e$，$e\in H$ 得證。
* 已知 $e\in H$，令 $a=e,\,\forall b$ 可得 $a\cdot b^{-1}=b^{-1}\in H$ 得證。
* $\forall c,d\in H$ 已知 $a^{-1}\in H$，令 $a=c, b=d^{-1}$，$\because a\cdot b^{-1}\in H\therefore c\cdot d\in H$，封閉性得證。
:::success
__Theorem 6.__ Two-step Subgroup Test:
給定一個群 $G$，$H$ 為 $G$ 中的非空子集合且在 $G$ 的運算下滿足:

1. $\forall a,b\in H\implies a\cdot b\in H$
2. $\forall a\in H \implies a^{-1}\in H$

$\iff H$ 為 $G$ 的子群。
:::

__證明__ : 僅需證 $\forall a,b\in H\implies a\cdot b\in H$ 且 $\forall a\in H \implies a^{-1}\in H\iff H$ 為 $G$ 的子群。
令 $b=a$ 可得 $a\cdot b^{-1}=a\cdot a^{-1}=e\in H$ 得證。

:::success
__Theorem 7.__ Finite Subgroup Test:
給定一個有限群 $G$，$H$ 為 $G$ 中的非空子集合，則 $H$ 在 $G$ 的運算下為封閉的 $\iff H$ 為 $G$ 的子群。
:::

__證明__ : 僅需證 $H$ 在 $G$ 的運算下為封閉的 $\implies H$ 為 $G$ 的子群。
已知 $H$ 在 $G$ 的運算下為封閉，$\forall a\in H$，可推得 $\forall n\in \mathbb N, a^n\in H$ 但 $G$ 中元素有限所以 $H$ 元素必定有限，$\forall m,n\in\mathbb N, m\neq n,\,\exists a^m=a^n$，假設 $m>n$ 可產生等式 $a^{m-n}=e$。討論兩種情況:
1. $m-n=1\implies a=e=a^{-1}\in H$
2. $m-n>1\implies a^{m-n-1}\in H, a^{-1}\in H$。

$a^{-1}\in H$ 得證。

---
### Examples
#### Example 7. Let $G$ be an Abelian group with identity $e$. Proof $H=\{x\in G|x^2=e\}$ is a subgroup of $G$.
$\because e^2=e\therefore H\neq\emptyset$. Assume $a,b\in H$. Since $G$ is Abelian, $(a\cdot b^{-1})^2=a\cdot b^{-1}\cdot a\cdot b^{-1}=a\cdot a\cdot b^{-1}\cdot b^{-1}=a^2\cdot (b^2)^{-1}=e\cdot e=e.$$\therefore a\cdot b^{-1}\in H$
$\because a,b,a\cdot b^{-1}\in H\therefore H\le G$

---

## Normal Subgroups and Quotient Groups

說明正常子群 (Normal Subgroups) 和商群 (Quotient Groups) 之前，我們得先知道何謂等價關係 (equivalence relation) 以及等價類 (equivalence class)。

等價關係及等價類便是在討論集合分類的問題，其定義如下：
:::info
__Definition__ Equivalence Relation :
給定一個集合 $S$，$a,b,c\in S$ 的關係用 $a\sim b$ 表示 $a$ 和 $b$ 為等價關係，在 S 上的等價關係須符合：
1. _Reflexivity_ : $\forall a\in S,\,a\sim a$
2. _Symmetry_ : $a\sim b\implies b\sim a$
3. _Transitivity_ : $(a\sim b) \land (b\sim c)\implies a\sim c$
:::

透過以上定義，當 $\sim$ 為 $S$ 上的等價關係且 $a\in S$，我們用 $[a]=\{x\in S|x\sim a\}$ 表示為包含元素 $a$ 的 $S$ 的等價類，也就是在此等價類的所有元素都和 $a$ 有等價關係。

那等價關係與我們要說明的正常子群和商群有什麼關係呢？我們先來幫一個群 $G$ 的子群 $H$ 中的元素定一個等價關係吧。
$$
a^{-1}\cdot b\in H\implies a\sim b
$$
__證明__ : 我們需要證明符合等價關係的三個特性。
1. $\forall a\in G,\,a^{-1}\cdot a=e\land e\in H\therefore a^{-1}\cdot a\in H, a\sim a$ 得證。
2. $a^{-1}\cdot b\in H\land (a^{-1}\cdot b)^{-1}=b^{-1}\cdot a\in H\therefore a\sim b\implies b\sim a$ 得證。
3. $a,b,c\in H,\,a^{-1}\cdot b\in H \land b^{-1}\cdot c\in H\implies (a^{-1}\cdot b)\cdot(b^{-1}\cdot c)=a^{-1}\cdot c\in H$$\therefore (a\sim b)\land (b\sim c)\implies a\sim c$ 得證。

:::info
__Definition__ Normal Subgroup :
$H$ 為一個群 $G$ 的子群，$\forall a\in G,\forall h\in H$ 且 $a\cdot h\cdot a^{-1}\in H$，則 $H$ 為 $G$ 的正常子群，使用 $H\triangleleft G$ 表示。
:::

:::success
__Theorem 5.__ Normal Subgroup Test :
$H\triangleleft G\iff \forall x\in G, x\cdot H\cdot x^{-1}\subseteq H$
:::

正常子群的目的是為了幫助我們了解 $G$，而為了了解這個群，我們可以小一點的群，就叫商群。我們知道一個群其實就是在某一個運算底下的集合，我們首先先創造出這個集合，我們就以前面提供的等價關係來使用以下的引理：

:::info
__Lemma 1.__
$H$ 是 $G$ 的子群，利用等價關係 $a^{-1}\cdot b\in H\implies a\sim b$ 所形成與 $a$ 有等價關係的集合為
$$
a\cdot H=\{a\cdot h|h\in H\}
$$
:::

__證明__ : $a^{-1}\cdot b=h\in H\implies b=a\cdot h\in a\cdot H$ 得證。

再有了這個集合後，我們要為這個集合提供一種運算，讓它成為一個群，稱為商群。

:::success
__Theorem 6.__ Quotient Group:
$H\triangleleft G$，集合 $G/H=\{a\cdot H|a\in G\}$ 在 $(aH)(bH)=abH$ 的運算下則為一個群。
:::

---

## Group Homomorphisms

相較於前面我們在定義各種的群，群同態 (Group Homomorphism) 著重的是在描述不同群之間關係的函數。

:::info
__Definition__ Group Homomorphism :
給定兩個群 $G$ 和 $G'$，$\phi: G\rightarrow G'$ 為從 $G$ 映射到 $G'$ 的函數。$\forall a,b\in G,\,\phi(a\cdot b)=\phi(a)\cdot\phi(b)$，則 $\phi$ 稱為 __群同態 (Group Homomorphism)__。
:::

:::info
__Definition__ Image of a Homomorphism :
一個群同態 $\phi: G\rightarrow G'$，其象 (image) 為:
$$
im(\phi)=\{\phi(a)\in G'|a\in G\}
$$
:::

:::info
__Definition__ Kernel of a Homomorphism :
一個群同態 $\phi: G\rightarrow G'$，其核 (kernel) 為:
$$
ker(\phi)=\{a\in G|\phi(a)=e'\in G'\}
$$
:::

:::success
__Theorem 5.__
給定兩個群 $G$ 和 $G'$ 且其單位元素分別為 $e$ 和 $e$。
$\phi: G\rightarrow G'$ 為群同態 $\implies$
1. $\phi(e)=e'$
2. $\forall a\in G, \phi(a^{-1})=\phi(a)^{-1}$
:::
__證明__ :
1. 當 $b=\phi(e)\in G'$，可推得 $b\cdot\phi(e)=\phi(e\cdot e)=b$，$\phi(e)=e'$ 得證。
2. $\phi(a)^{-1}\cdot\phi(a)=\phi(a^{-1}\cdot a)=\phi(e)=e'$，$\phi(a^{-1})=\phi(a)^{-1}$ 得證。

:::success
__Theorem 6.__
$\phi: G\rightarrow G'$ 為群同態 $\implies im(\phi)$ 為 $G'$ 的子群，而 $ker(\phi)$ 為 $G$ 的正常子群。
:::
__證明__ : 由前面 Subgroups 所提到的測試定理可以很容易證明。
1. 假設 $a, b\in G$，$\phi(a),\phi(b)\in im(\phi)\implies\phi(a)\cdot\phi(b)^{-1}=\phi(a\cdot b^{-1})$ 且因 $a,b^{-1}\in G$，故 $\phi(a)\cdot\phi(b)^{-1}\in im(\phi)$ 得證。
2. $a,b\in ker(\phi)$ i.e. $\phi(a)=\phi(b)=e'\implies \phi(a\cdot b^{-1})=\phi(a)\cdot\phi(b)^{-1}=e'$，$a\cdot b^{-1}\in ker(\phi)$，得證 $ker(\phi)$ 是 $G$ 的子群。
3. $\forall g\in G, a\in ker(\phi)\implies\phi(g\cdot a\cdot g^{-1})=\phi(g)\cdot\phi(a)\cdot\phi(g^{-1})=e'$ 得證。

知道了群同態的幾個基本知識後，我們可以透過以下幾個定理來確認 $G$ 和 $G'$ 是否為同構。

:::success
__Theorem 7.__ First Isomorphism Theorem
$\phi: G\rightarrow G'$ 為群同態 $\implies G/ker(\phi)\simeq im(\phi)$
:::

__證明__ : 假設一函數
$$
\Psi:
\begin{cases}
G/ker(\phi)\rightarrow im(\phi)\\
a\cdot ker(\phi)\mapsto\phi(a),a\in G
\end{cases}
$$
根據同構的定義，$\Psi$ 必須是 1-to-1 且 onto 的函數。
1. 假設 $\phi(a)=\phi(b)$，$e=\phi(b)^{-1}\cdot\phi(a)=\phi(b^{-1}\cdot a),b^{-1}\cdot a\in ker(\phi)$$\implies a\cdot ker(\phi)=b\cdot ker(\phi)$，1-to-1 得證。
2. $\Psi(a\cdot ker(\phi)\cdot b\cdot ker(\phi))=\Psi(a\cdot b\cdot ker(\phi))=\phi(a\cdot b)$$=\phi(a)\cdot\phi( b)=\Psi(a\cdot ker(\phi))\cdot \Psi(b\cdot ker(\phi))$，群同態得證。

:::success
__Theorem 8.__ Second Isomorphism Theorem
$H$ 是 $G$ 的子群且 $N$ 是 $G$ 的正常子群$\implies H\cap N$ 是 $H$ 的正常子群且 $H/(H\cap N)\simeq (H\cdot N)/N$
:::

:::success
__Theorem 9.__ Third Isomorphism Theorem
$\phi: G\rightarrow G'$ 為群蓋同態，假設 $N'$ 是 $G'$ 的正常子群，令 $N=\{a\in G|\phi(a)\in N'\}\implies$ $N$ 是 $G$ 的正常子群且 $G/N\simeq G'/N'$
:::

## 參考資料
* [大學基礎代數](http://math.ntnu.edu.tw/~li/algebra-html/)
* [Contemporary Abstract Algebra](http://www.d.umn.edu/~jgallian/)