7.1-7.2 二元運算、么半群與群

集合論讓我們用函數、關係和基數比較集合。但很多數學對象之所以有趣，不 只是因為它們包含哪些元素，而是因為那些元素上還帶有額外結構。

例如，只看基數時，集合 {5, dog} 和 $\{0,1\}$ 都只有兩個元素。但 $\{0,1\}$ 可以配上模 $2$ 的加法和乘法規則；相反，5 + dog 在未指定額外結 構之前沒有明確意義。

帶結構的集合

許多基本例子都符合這個模式：自然數帶有加法與乘法，平面帶有向量加法， 置換帶有合成。

共同模式是：

1. 先有一個集合；
2. 在集合上指定某些運算、關係、函數或特殊元素；
3. 寫下這些額外資料要滿足的公理；
4. 只由公理推出定理。

這是現代數學的一個基本習慣。與其在每個例子中重複證明同一類事實，不如 先定義一種結構，再證明所有具有該結構的例子都必須滿足甚麼。

二元運算

定義

二元運算

設 $X$ 是集合。$X$ 上的一個 二元運算 是一個函數

$$*:X\times X\to X.$$

對 $a,b\in X$，通常寫 $a*b$，而不是 $*(a,b)$。

這個定義有兩個重點。

第一，運算從 $X$ 中取兩個輸入。第二，輸出仍然必須屬於 $X$。第二點常 被稱為封閉性；在這門課的寫法中，它已經包含在函數型別 $X\times X\to X$ 裡。

常見錯誤

一條公式不會自動成為每個集合上的二元運算

減法是 $Z$ 上的二元運算，因為 $a-b\in Z$ 對所有 $a,b\in Z$ 都成立。 但若要求結果仍留在 $N$ 中，減法就不是 $N$ 上的二元運算，因為 $2-5$ 不 是自然數。

Boolean integers

定義

$$B=\{0,1\}.$$

在這個集合上，加法規則為

$$0+0=0,\qquad 0+1=1,\qquad 1+0=1,\qquad 1+1=0,$$

乘法規則為

$$0\cdot 0=0,\qquad 0\cdot 1=0,\qquad 1\cdot 0=0,\qquad 1\cdot 1=1.$$

定義

Boolean integers

Boolean integers 是三元組

$$(B,+,\cdot),$$

其中 $B=\{0,1\}$，而 $+$ 與 $\cdot$ 是上面顯示的兩個二元運算。

同一個二元素集合可以承載不同的運算，各種運算滿足的規律需要分別檢查。

例題

在 $B$ 中解 $x+y=0$

每個 $x\in B$ 都能與某個元素相加而得到零：

$$\forall x\in B,\ \exists y\in B\ (x+y=0).$$

只需檢查 $x$ 的兩個可能值。

若 $x=0$，取 $y=0$，因為 $0+0=0$。

若 $x=1$，取 $y=1$，因為 $1+1=0$。

所以在這個加法規則下，$B$ 的每個元素都有加法逆元。

更多二元運算例子

常見例子包括：

• $+$ 和 $\times$ 是 $N$ 上的二元運算；
• $+$ 和 $\times$ 是 $Z$ 上的二元運算；
• 對任意集合 $X$，函數集合 $X^X$ 上的合成是二元運算。

若 $f:X\to X$ 且 $g:X\to X$，則合成 $g\circ f$ 仍將 $X$ 映到 $X$。 因此合成定義了二元運算

$$\circ:X^X\times X^X\to X^X.$$

例題

合成作為二元運算

設 $X=\{a,b\}$，其中 $a\ne b$。定義 $f(a)=f(b)=a$，並令 $g$ 交換這兩個 元素，即 $g(a)=b$、$g(b)=a$。於是

$$(g\circ f)(a)=(g\circ f)(b)=b, \qquad (f\circ g)(a)=(f\circ g)(b)=a.$$

兩個合成都屬於 $X^X$，卻是不同的函數。因此合成在 $X^X$ 上封閉，但不滿足 交換律。這裏參與運算的元素是函數，不是 $X$ 本身的元素。

么半群

函數合成有兩條不依賴具體集合 $X$ 的規律：改變連續合成的括號位置不改變 結果，與 $id_X$ 合成也不改變原函數。么半群把這兩條規律抽象為公理，使同一 論證可以用於加法、乘法和函數合成。

定義

么半群

一個 么半群 $(M,*)$ 是一個集合 $M$，連同一個二元運算

$$*:M\times M\to M$$

使得：

• 對所有 $a,b,c\in M$，

  $$(a*b)*c=a*(b*c)$$

  （結合律）；

• 存在 $e\in M$，使得對所有 $a\in M$，

  $$a*e=e*a=a$$

  （單位元存在）。

結合律說明三個元素連乘時括號位置不影響結果。單位元則是一個從左邊或右 邊合併也不改變元素的元素。

標準例子包括：

• $(N,+)$ 是么半群，單位元為 $0$；
• $(N,\times)$ 是么半群，單位元為 $1$；
• $(Z,+)$ 是么半群，單位元為 $0$；
• $(Z,\times)$ 是么半群，單位元為 $1$；
• 對任意集合 $X$，$X^X$ 在合成下是么半群，單位元為 $id_X$；
• $(B,+)$ 是么半群；
• $(B,\cdot)$ 是么半群。

例題

檢查 $(N,+)$ 是么半群

$+$ 是 $N$ 上的二元運算。

結合律成立：

$$(a+b)+c=a+(b+c)$$

對所有自然數 $a,b,c$ 成立。

單位元是 $0$，因為

$$a+0=0+a=a.$$

所以 $(N,+)$ 是么半群。

例題

檢查函數合成么半群

設 $X$ 是任意集合。$X^X$ 的元素是函數 $X\to X$。

合成滿足結合律：

$$(h\circ g)\circ f=h\circ(g\circ f).$$

恆等函數 $id_X$ 滿足

$$f\circ id_X=f,\qquad id_X\circ f=f.$$

所以 $X^X$ 在合成下是么半群。

不是么半群的例子

例題

$(Z^+,+)$ 不是么半群

若 $Z^+$ 表示正整數，則加法封閉且滿足結合律。但 $Z^+$ 裡沒有加法單位 元。

加法單位元必須是 $0$，因為 $a+0=a$。但 $0\notin Z^+$。所以 $(Z^+,+)$ 不是么半群。

例題

$(Z,-)$ 不是么半群

減法是 $Z$ 上的二元運算，但不滿足結合律。例如

$$(5-3)-1=1,$$

而

$$5-(3-1)=3.$$

結果不同，所以結合律失敗，$(Z,-)$ 不是么半群。

常見錯誤

有單位元仍然不夠

一個運算可能看起來有單位元，但若不滿足結合律，仍然不是么半群。結合律 和單位元是兩個獨立要求。

單位元唯一

定理

單位元唯一性

一個么半群恰好只有一個單位元。

證明

假設 $e$ 和 $e'$ 都是單位元。因為 $e$ 是單位元，

$$e*e'=e'.$$

因為 $e'$ 是單位元，

$$e*e'=e.$$

所以

$$e=e*e'=e',$$

故單位元唯一。

這個證明很短，原因是單位元律可以左右兩邊使用。兩個候選單位元必須互相 不改變對方，因而被迫相等。

群

么半群允許運算連續進行，卻不要求每個運算都可逆。在前面的二元素例子中， $f(a)=f(b)=a$。不可能有函數 $h$ 滿足 $h\circ f=id_X$，因為這個等式要求 同一個值 $h(a)$ 同時等於 $a$ 和 $b$。相反，交換兩個元素的 $g$ 滿足 $g\circ g=id_X$，再次施行 $g$ 就能恢復原狀。

若只保留雙射 $X\to X$，這個障礙便消失了：雙射的合成仍是雙射，$id_X$ 是雙射，每個雙射也都有從 $X$ 到自身的反函數。這些可逆運算構成了群的一個 基本模型。幾何對稱也具有這些性質：可以合成，有恆等對稱，而且可以逆轉。 群公理把這些規律抽象出來，不再要求元素本身必須是函數。

定義

群

一個 群 是一個集合 $G$，連同一個元素 $e\in G$ 和一個二元運算

$$(a,b)\longmapsto a\cdot b$$

使得：

• 對所有 $a\in G$，

  $$e\cdot a=a=a\cdot e;$$

• 對所有 $a,b,c\in G$，

  $$(a\cdot b)\cdot c=a\cdot(b\cdot c);$$

• 對每個 $a\in G$，存在逆元 $a^{-1}\in G$，使得

  $$a\cdot a^{-1}=e \qquad\text{且}\qquad a^{-1}\cdot a=e.$$

在這個標準讀法下，每個群在忘記逆元公理之後都是么半群。群更強，不是因 為它有另一套結合律或單位元，而是因為每個元素都有逆元。

常見錯誤

群不是任意帶二元運算的集合

運算必須滿足結合律，必須有雙邊單位元，而且每個元素都必須有逆元。任何 一條失敗，也不是群。

群的例子

基本例子包括：

• $(Z,+)$；
• $(Q,+)$；
• $(Q^+,\cdot)$，其中 $Q^+$ 表示正有理數。

例題

為甚麼 $(Z,+)$ 是群

單位元是 $0$。

對每個整數 $a$，逆元是 $-a$，因為

$$a+(-a)=0=(-a)+a.$$

加法滿足結合律，所以 $(Z,+)$ 是群。

例題

為甚麼 $(Q^+,\cdot)$ 是群

單位元是 $1$。

對每個正有理數 $q$，逆元是 $1/q$，它仍然是正有理數，且

$$q\cdot \frac1q=1=\frac1q\cdot q.$$

乘法滿足結合律，所以 $(Q^+,\cdot)$ 是群。

常見錯誤

$(Z,\times)$ 是么半群，但不是群

$Z$ 上乘法的單位元是 $1$，且乘法滿足結合律。但大多數整數在 $Z$ 中沒有 乘法逆元。例如不存在整數 $b$ 使得 $2b=1$。

逆元唯一

定理

逆元唯一性

對每個 $a\in G$，逆元 $a^{-1}$ 是唯一的。

證明

假設 $b$ 和 $c$ 都是 $a$ 的逆元。則

$$a*b=e,\qquad b*a=e,$$

且

$$a*c=e,\qquad c*a=e.$$

利用單位元與結合律，

$$b=b*e=b*(a*c)=(b*a)*c=e*c=c.$$

所以 $b=c$。

這個證明說明了為甚麼逆元記號是合理的：只要逆元存在，它就是唯一的，所 以 $a^{-1}$ 不會有歧義。

襪鞋性質

乘積逆元公式常被稱為 socks-shoes property：要復原兩個連續 操作，先復原第二個，再復原第一個。

定理

襪鞋性質

對群中元素 $a,b$，

$$(a*b)^{-1}=b^{-1}*a^{-1}.$$

證明

計算：

$$(a*b)*(b^{-1}*a^{-1}) =a*(b*b^{-1})*a^{-1} =a*e*a^{-1} =a*a^{-1} =e.$$

反向的乘積也等於單位元：

$$(b^{-1}*a^{-1})*(a*b) =b^{-1}*(a^{-1}*a)*b =b^{-1}*e*b =b^{-1}*b =e.$$

所以 $b^{-1}*a^{-1}$ 是 $a*b$ 的雙側逆元，再由逆元唯一性得到所述公式。

順序反轉是必要的。在非交換群中，$a^{-1}*b^{-1}$ 未必能復原 $a*b$。

消去律

定理

消去律

在群中：

• 若 $a*b=a*c$，則 $b=c$；
• 若 $b*a=c*a$，則 $b=c$。

左消去證明

假設

$$a*b=a*c.$$

左乘 $a^{-1}$：

$$a^{-1}*(a*b)=a^{-1}*(a*c).$$

由結合律，

$$(a^{-1}*a)*b=(a^{-1}*a)*c.$$

因為 $a^{-1}*a=e$，得到

$$e*b=e*c,$$

所以 $b=c$。

右消去的證明類似，只是改為右乘 $a^{-1}$。

單側逆元與非交換性

對函數而言，$g\circ f=id$ 的左逆推出 $f$ 單射，$f\circ h=id$ 的右逆 推出 $f$ 滿射；兩者同時存在才得到反函數。在一般么半群中，單側逆元 不應自動視為雙側逆元，所以必須記錄等式在哪一側成立。

定理

兩側等式足以識別逆元

若么半群中 $b*a=e=a*c$，則 $b=b*e=b*(a*c)=(b*a)*c=e*c=c$。在群中，每個元素都有唯一逆元， 並且左、右消去分別透過在相應一側乘以逆元得到。

定理

么半群中處處有右逆元就成為群

設 $M$ 是么半群。若每個 $a\in M$ 都有右逆元，取 $b,c\in M$ 使 $a*b=e$ 且 $b*c=e$。結合律給出

$$a=a*(b*c)=(a*b)*c=e*c=c$$

所以 $b*a=b*c=e$。每個右逆元也是左逆元，$M$ 因而是群；另一側的恆等式 是由結合律推導出來的。

例題

群 $GL(2,R)$ 非交換

$GL(2,R)$ 是所有行列式非零的實 $2\times2$ 矩陣，在矩陣乘法下成群。取

$$A=\begin{pmatrix}1&1\\0&1\end{pmatrix},\qquad B=\begin{pmatrix}1&0\\1&1\end{pmatrix}$$

兩者行列式都是 $1$，但 $AB=\begin{pmatrix}2&1\\1&1\end{pmatrix}$， 而 $BA=\begin{pmatrix}1&1\\1&2\end{pmatrix}$，所以 $AB\ne BA$。 結合律不推出交換律；單位元是單位矩陣，每個矩陣仍有逆元。

常見錯誤

Boolean 乘法不是群

Boolean 乘法么半群的單位元是 $1$，但 $0$ 沒有逆元，因為 $0b=0$ 永遠 不等於 $1$。因此 $(B,\cdot)$ 不是群。

同態與同構

雙射可以比較兩個集合的大小，卻未必保持它們的運算。比較群時，映射還需要 尊重乘法：先相乘再映射，應當與先分別映射再在目標群中相乘得到相同結果。 這個要求使一個群中的代數計算可以傳到另一個群中。

定義

群同態

若 $(G,*)$、$(H,\star)$ 是群，$\varphi:G\to H$ 是同態，當且僅當 $\varphi(a*b)=\varphi(a)\star\varphi(b)$ 對所有 $a,b\in G$ 成立。同態保持運算，但不一定是單射或滿射。

定理

同態保持單位元和逆元

令 $u=\varphi(e_G)$。由 $u=u\star u$，在左側乘以 $u^{-1}$ 得 $e_H=u$，所以 $\varphi(e_G)=e_H$。又有兩條等式 $\varphi(a)\star\varphi(a^{-1})=\varphi(a*a^{-1})=e_H$ 與 $\varphi(a^{-1})\star\varphi(a)=\varphi(a^{-1}*a)=e_H$；因此 $\varphi(a^{-1})$ 是 $\varphi(a)$ 的雙側逆元，唯一性完成證明。

若同態同時是雙射，它既不把不同元素合併，也不遺漏目標群中的元素。 這種可逆的重新標記保持每個乘積，因而兩群具有相同的代數結構。

定義

同構

同構是雙射群同態。若存在同構，寫作 $G\cong H$；重新標記元素後，兩群 具有相同的運算結構。

對稱群與 $S_2\cong Z_2$

對於有限集合 $X$，對稱群 $S_X$ 是所有雙射 $X\to X$ 在合成下組成的群， 也就是前面討論的可逆自映射。若 $X=\{1,\ldots,n\}$，則記作 $S_n$。 循環記號 $(a_1\ a_2\ \cdots\ a_k)$ 將每個列出的元素映到下一個，將 $a_k$ 映到 $a_1$，並固定所有未列出的元素。

$S_2$ 的元素是恆等置換 $id$ 與換位 $\tau=(1\ 2)$，並且 $\tau\circ\tau=id$。以 $Z_2$ 表示前面定義的 Boolean 加法群 $(B,+)$。 它的加法表與 $S_2$ 的合成表具有相同形式：把 $id$ 改記為 $0$，把 $\tau$ 改記為 $1$，便能保持運算結果。

例題

$S_2$ 的合成表

$$\begin{array}{c|cc} \circ&id&\tau\\\hline id&id&\tau\\ \tau&\tau&id \end{array}$$

令 $\varphi(id)=0$、$\varphi(\tau)=1$。合成表說明 $\varphi(\sigma\circ\rho)=\varphi(\sigma)+\varphi(\rho)\pmod2$， 而 $\varphi$ 是雙射，所以 $S_2\cong Z_2$。

共軛：重新標記後的同一運算

對於置換，改變元素的標記也會改變運算的表示。若 $k$ 把舊標記映到新標記， 則運算 $h$ 在新標記下表示為 $k\circ h\circ k^{-1}$：先還原為舊標記， 施行 $h$，再恢復新標記。把合成換成群的乘法，這個表達式在任意群中都有意義。

對群 $G$ 及 $g,h\in G$，定義 $g\sim h$ 當且僅當存在 $k\in G$ 使 $g=khk^{-1}$，稱為共軛關係。由 $g=ege^{-1}$ 得自反性。若 $g=khk^{-1}$，則 $h=k^{-1}gk$，故有對稱性。若還有 $h=\ell j\ell^{-1}$，則 $g=(k\ell)j(k\ell)^{-1}$，故有傳遞性。 因此共軛是 $G$ 上的等價關係。它的等價類稱為共軛類，這些類構成群的一個劃分。

二面體群 $D_8$

在正方形的對稱群中，共軛只允許用正方形本身的對稱來改變頂點標記。 共軛類把沿對角線的反射與沿對邊中點連線的反射區分開來，儘管兩者都使 正方形的定向反轉。

把正方形頂點標為 $1=(1,1)$、$2=(-1,1)$、$3=(-1,-1)$、$4=(1,-1)$。 令 $r=(1\ 2\ 3\ 4)$ 是四分之一轉動，$s=(2\ 4)$ 是關於對角線 $y=x$ 的反射。置換合成約定最右邊的置換先作用。八個對稱是

$$e, r, r^2, r^3, s, rs, r^2s, r^3s$$

對 $(1,2,3,4)$ 的作用如下，因此幾何描述也可以直接核對：

它們滿足 $r^4=e$、$s^2=e$ 以及反射關係 $srs=r^{-1}$。因此可用 $sr=r^{-1}s$ 把含有 $r$、$s$ 的乘積化成列出的形式。

例題

$D_8$ 的共軛類

由 $srs=r^{-1}$，轉動 $r$ 與 $r^3$ 共軛。$r^2$ 在轉動和反射下都保持不變， 所以單獨成類。反射按指數奇偶分成兩族，完整的共軛類是

$$\{e\},\qquad \{r^2\},\qquad \{r,r^3\},\qquad \{s,r^2s\},\qquad \{rs,r^3s\}$$

例如 $rsr^{-1}=r^2s$，$r(rs)r^{-1}=r^3s$，而用 $s$ 共軛會反轉轉動指數。 用生成元 $r$ 或 $s$ 共軛，都保持每個所列集合不變。每個群元素都是這些 生成元的乘積，所以任何共軛都不能把元素移到另一個所列集合。上面的計算又把 每個二元素集合中的兩個元素連接起來，因此這些集合恰為全部共軛類。

涉及 $S_2$ 與 $S_3$ 的兩個同態

定義 $f:S_2\to S_3$，讓 $S_2$ 的置換固定第三個元素： $f(id)=id$、$f((1\ 2))=(1\ 2)$。合成規則沒有改變，因此 $f$ 是同態。它是單射，卻不是滿射：任何移動第三個元素的置換都不在其像中。保持運算並不要求覆蓋整個目標群。

反向映射可直接由置換計算得到。令 $c=(1\ 2\ 3)$、$t=(1\ 2)$。 直接合成可核對 $c^3=t^2=e$ 及 $tct=c^{-1}$。六個不同置換是 $e,c,c^2,t,ct,c^2t$；後三個依次為 $(1\ 2),(1\ 3),(2\ 3)$。 所以每個元素唯一寫成 $c^i t^\varepsilon$，其中 $i\in\{0,1,2\}$、 $\varepsilon\in\{0,1\}$。由 $tc=c^{-1}t$，

$$(c^i t^\varepsilon)(c^j t^\delta) =c^{i+(-1)^\varepsilon j}t^{\varepsilon+\delta}.$$

這裏 $c$ 的指數模三化簡，$t$ 的指數模二化簡。定義 $g(c^i t^\varepsilon)=\tau^\varepsilon\in S_2$。乘積中 $t$ 的指數模二相加， 與 $\tau$ 的指數規則相同，因此 $g(\sigma\rho)=g(\sigma)g(\rho)$。 這就是奇偶性同態；映到單位元的元素恰為 $e,c,c^2$，通常把這個集合記作 $A_3$。 由 $g(e)=id$、$g(t)=\tau$ 可知它是滿射；但 $e,c,c^2$ 有相同的像，所以不是 單射。這兩個例子分別說明，同態的定義不包含單射或滿射的要求。

互動檢查運算律

下面的工具可以檢驗小型運算表的封閉性、結合律、單位元與逆元條件。比較 Boolean 加法與乘法，可以看出哪條公理區分了群與么半群。

圖示。么半群與群都要求結合律和單位元；群還要求每個元素都有逆元。

快速檢查

思考檢查

一條規則 $*$ 要成為集合 $X$ 上的二元運算，必須滿足甚麼輸入與輸出要求？

用函數型別回答。

解答 · 答案

它必須是一個函數 $*:X\times X\to X$。也就是說，它取兩個 $X$ 的元素作 為輸入，並輸出一個仍在 $X$ 中的元素。

思考檢查

為甚麼 $(Z,-)$ 不是么半群？

指出失敗的公理，並給一個具體計算。

解答 · 答案

減法不滿足結合律。例如

$$(5-3)-1=1$$

但

$$5-(3-1)=3.$$

兩者不同，所以 $(Z,-)$ 不是么半群。

思考檢查

為甚麼 $(Z,\times)$ 不是群？

集中看逆元。

解答 · 答案

$Z$ 上乘法滿足結合律並有單位元 $1$，但不是每個整數都有乘法逆元。例如 不存在整數 $b$ 使 $2b=1$。

思考檢查

在群中，$a*b$ 的逆元是甚麼？

留意順序。

解答 · 答案

逆元是

$$(a*b)^{-1}=b^{-1}*a^{-1}.$$

順序會反轉。

練習

練習 1

直接證明 $(B,+)$ 是么半群，其中 $+$ 是上面定義的 Boolean 加法。

解答 · 提示

檢查結合律並指出單位元。

解答 · 引導解答

單位元是 $0$，因為 $0+0=0$、$0+1=1$、$1+0=1$，所以對兩個 $x\in B$ 都有 $x+0=0+x=x$。

結合律可由有限情況 $x,y,z\in\{0,1\}$ 直接檢查。Boolean 加法就是模 $2$ 加法，所以 $(x+y)+z$ 與 $x+(y+z)$ 都記錄 $x,y,z$ 中 $1$ 的個數奇偶性， 因此相等。

練習 2

集合 $X$ 上的二元運算有左單位元 $e$ 和右單位元 $f$。證明 $e=f$，且這個共同元素是雙側單位元。需要結合律嗎？

解答 · 提示

分別使用左右單位元的性質計算 $e*f$。

解答 · 參考解答

因為 $e$ 是左單位元，$e*f=f$；因為 $f$ 是右單位元，$e*f=e$，所以 $e=f$。這個共同元素同時具有左右單位元性質。論證沒有使用結合律：只計算一個乘積，沒有改變括號。

練習 3

設 $a$ 是么半群中的元素，且有左逆 $h$，即 $h*a=e$。證明 $a*b=a*c$ 蘊含 $b=c$，並說明為甚麼不需要右逆。

解答 · 提示

在等式兩邊左乘 $h$，保持因子的次序。

解答 · 參考解答

由 $a*b=a*c$，兩邊左乘 $h$，再用結合律得 $(h*a)*b=(h*a)*c$。因為 $h*a=e$，這化為 $e*b=e*c$，所以 $b=c$。這裏只使用 $h*a=e$，沒有使用關於 $a*h$ 的等式。

相關筆記

2.2 函數與關係 提供了函數合成、反函數，以及共軛類所用的等價類劃分定理。代數公理中的 量詞則使用 1.3 量詞與否定 的語言。

3.4 有理數與良定義運算 給出了另一個例子：在數學對象上指定運算，並檢查定義是否依賴代表元。 序關係則是另一種附加結構，可與 6.3 區間、Cantor set、稠密性與良序 對照；其中的結論不是本節群論證明的前提。