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

第 7 章開始轉換視角。

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

例如，只看基數時，集合 {5, dog} 和 $\{0,1\}$ 都只有兩個元素。但 $\{0,1\}$ 可以配上熟悉的加法和乘法規則；相反，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$

一個有用練習是證明

$$\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\to X.$$

所以合成把 $X^X$ 的兩個元素合併，並得到 $X^X$ 的另一個元素。

例題

合成作為二元運算

設 $X=\{a,b\}$。$X^X$ 的元素是所有從 $X$ 到自身的函數。

若 $f,g\in X^X$，則 $g\circ f$ 仍然是 $X$ 到自身的函數。因此合成定義了

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

這裡被合併的元素是函數，不是 $X$ 本身的元素。

么半群

第 7 章首先研究的結構是 monoid。

定義

么半群

一個 么半群 $(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',$$

故單位元唯一。

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

群

么半群很有用，但條件較弱。群額外要求每個元素都可以被「復原」。

定義

群

一個 群 是一個集合 $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.$$

由逆元唯一性，$a*b$ 的逆元必為 $b^\{-1\}*a^\{-1\}$。

順序反轉是必要的。在非交換群中，$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$ 成立。

定理

同態保持單位元和逆元

令 $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$

$S_2$ 的元素是恆等置換 $id$ 與換位 $\tau=(1\ 2)$，並且 $\tau\circ\tau=id$。

例題

$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$。

對群 $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$。

互動檢查運算律

下面的 checker 是定義的輔助工具：可用來測試小型運算表的封閉性、結合 律、單位元與逆元行為。真正的數學內容仍然是上面的公理。

圖示。monoid 與 group 的分別不是名稱，而是除結合律外，單位元與逆元公理是否成立。

快速檢查

思考檢查

一條規則 $*$ 要成為集合 $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 函數與關係 和 6.4-6.7 區間、Cantor 集、稠密性與良序。 這一節也會用到 1.2 量詞與否定 以及 3.4 有理數與良定義運算 中的證明習慣。