半群與么半群

你每天都在加數字、連接字串、合併串列。這些感覺是完全不同的操作——但它們其實都秘密地擁有相同的數學形狀。一旦你知道那個形狀的名字，你就會開始在任何地方發現它，而認識它將幫助你更清晰地推理程式碼。

什麼是二元運算？

集合 $S$ 上的**二元運算（binary operation）**是一條規則，它取 $S$ 的兩個元素並產生一個元素，也在 $S$ 中。

更精確地說，二元運算是一個函式：

$$\star : S \times S \to S$$

符號 $\star$ 只是一個佔位符——實際的運算可能是 $+$、$\times$、字串串接，或任何你能想到的東西。

關鍵約束是封閉性（closure）：組合 $S$ 的兩個元素的結果必須落回 $S$ 內部。如果你把兩個自然數相加，你得到另一個自然數——不是字串，不是分數，是另一個自然數。這個運算永遠不會逃出這個集合。

幾個具體的例子：

• $\mathbb{N}$ 上的 $+$：$3 + 5 = 8$，仍在 $\mathbb{N}$ 中。✓
• $\mathbb{N}$ 上的 $\times$：$3 \times 5 = 15$，仍在 $\mathbb{N}$ 中。✓
• 所有字串集合上的串接："hello" $\mathbin{++}$ " world" $=$ "hello world"，仍是字串。✓
• $\mathbb{N}$ 上的 $\max$：$\max(3, 5) = 5$，仍在 $\mathbb{N}$ 中。✓

關鍵性質：結合性

不是所有的二元運算都一樣。一個二元運算能擁有的最重要性質是結合性（associativity）。

$S$ 上的運算 $\star$ 是結合的，如果對每個 $a, b, c \in S$：

$$(a \star b) \star c = a \star (b \star c) \tag{1}$$

用通俗的話說：當依次組合三個東西時，你在哪裡放括號並不重要。你可以先組合前兩個元素，或先組合後兩個元素——答案永遠相同。

讓我們對 $\mathbb{N}$ 上的加法驗證這一點：

$$(2 + 3) + 4 = 5 + 4 = 9$$ $$2 + (3 + 4) = 2 + 7 = 9$$

兩種方式結果相同。加法是結合的。

字串串接也是結合的。讓我們驗證：

$$(\texttt{"ab"} \mathbin{++} \texttt{"cd"}) \mathbin{++} \texttt{"ef"} = \texttt{"abcd"} \mathbin{++} \texttt{"ef"} = \texttt{"abcdef"}$$ $$\texttt{"ab"} \mathbin{++} (\texttt{"cd"} \mathbin{++} \texttt{"ef"}) = \texttt{"ab"} \mathbin{++} \texttt{"cdef"} = \texttt{"abcdef"}$$

結果相同。括號的位置真的不重要。

現在考慮整數 $\mathbb{Z}$ 上的減法。那是結合的嗎？

$$(10 - 3) - 2 = 7 - 2 = 5$$ $$10 - (3 - 2) = 10 - 1 = 9$$

結果不同——減法不是結合的。移動括號改變了答案。

結合性是有力的，因為它意味著你可以安全地省略長串運算中的所有括號。你不用擔心是寫 $(a \star b) \star c$ 還是 $a \star (b \star c)$，直接寫 $a \star b \star c$，毫無歧義。

半群

你現在已經具備了理解第一個結構所需的一切。

定義。 **半群（semigroup）**是一個數對 $(S, \star)$，其中 $S$ 是一個非空集合，$\star$ 是 $S$ 上一個結合的二元運算。

這就是整個定義——一個集合和一個結合的運算。不需要其他任何東西。

半群的例子

正整數在加法下。 設 $\mathbb{Z}^+ = \{1, 2, 3, \ldots\}$。加法是一個二元運算（兩個正整數之和還是正整數），且是結合的。所以 $(\mathbb{Z}^+, +)$ 是一個半群。

自然數在乘法下。 兩個自然數的乘積還是自然數，且乘法是結合的，所以 $(\mathbb{N}, \times)$ 是一個半群。

非空字串在串接下。 設 $S^+$ 是所有至少有一個字元的字串的集合。串接兩個非空字串總是得到一個非空字串，且串接是結合的。所以 $(S^+, \mathbin{++})$ 是一個半群。

自然數在最大值下。 $\max(a, b)$ 當 $a$ 和 $b$ 是自然數時總是自然數，且：

$$\max(\max(a, b),\; c) = \max(a,\; \max(b, c))$$

兩邊只是等於 $a$、$b$、$c$ 中最大的值。所以 $(\mathbb{N}, \max)$ 是一個半群。

一個反例

$(\mathbb{Z}, -)$，整數在減法下，不是半群：你剛剛在上面看到減法不滿足結合性。

缺少的東西：單位元

半群已經很有用了，但它們中的一些有一個其他的所沒有的額外性質。

想想當你把 $0$ 加到任何自然數時會發生什麼：

$$n + 0 = n \qquad \text{且} \qquad 0 + n = n$$

或者當你把空字串 "" 和任何字串串接時：

$$s \mathbin{++} \texttt{""} = s \qquad \text{且} \qquad \texttt{""} \mathbin{++} s = s$$

數字 $0$ 和字串 "" 各自扮演一個特殊的角色：它們什麼也不做。把它們與任何元素組合只是把那個元素原樣返回。這個特殊的元素叫做單位元（identity element）。

正式地，$e \in S$ 是 $(S, \star)$ 的單位元，如果對每個 $a \in S$：

$$e \star a = a \qquad \text{且} \qquad a \star e = a \tag{2}$$

兩個條件都必須成立。單位元在左邊或右邊出現都必須是中性的。

半群什麼時候有單位元？

不是每個半群都有。取 $(\mathbb{Z}^+, +)$——正整數在加法下。要使單位元 $e$ 存在，你需要某個正整數 $e$ 使得 $n + e = n$ 對每個 $n \in \mathbb{Z}^+$ 成立。那意味著 $e = 0$，但 $0$ 不是正整數。所以 $(\mathbb{Z}^+, +)$ 沒有單位元。

類似地，$(S^+, \mathbin{++})$——非空字串在串接下——沒有單位元：空字串 "" 會完美地工作，但它不在非空字串 $S^+$ 的集合中。

單位元是否存在通常取決於你是否小心地在你的集合中包含了「空的」或「零」的情況。

么半群

有單位元的半群獲得一個新名字。

定義。 **么半群（monoid）**是一個三元組 $(S, \star, e)$，其中 $(S, \star)$ 是一個半群，$e \in S$ 是 $\star$ 的一個單位元。

每個么半群都是半群，但不是每個半群都是么半群。額外的成分恰恰是單位元。

么半群的例子

集合 $S$	運算 $\star$	單位元 $e$
$\mathbb{N}$	$+$	$0$
$\mathbb{N}$	$\times$	$1$
所有字串	串接	""
所有串列	串接	[]
$\mathbb{N}$	$\max$	$0$

最後一行可能會讓你驚訝。$0$ 真的是 $\mathbb{N}$ 上 $\max$ 的單位元嗎？

$$\max(0, n) = n \qquad \text{且} \qquad \max(n, 0) = n$$

是的——因為 $0$ 是最小的自然數，把 $0$ 與任何 $n$ 取最大值總是返回 $n$。所以 $(\mathbb{N}, \max, 0)$ 確實是一個么半群。

單位元是唯一的

一個么半群有恰好一個單位元——你永遠不可能有兩個不同的。原因如下：假設 $e$ 和 $f$ 都是同一個運算的單位元。那麼：

$$e = e \star f = f$$

第一個等號成立因為 $f$ 是一個單位元（它在右邊什麼都不改變）。第二個等號成立因為 $e$ 是一個單位元（它在左邊什麼都不改變）。所以 $e$ 和 $f$ 必須是同一個元素。

這令人放心：一旦你找到一個單位元，你就知道它是那個單位元。

案例研究：皮亞諾公理中的自然數加法

如果你讀過皮亞諾公理這個關卡，你會記得 $\mathbb{N}$ 上的加法是用兩條規則遞迴定義的：

$$m + 0 \coloneqq m \tag{A1}$$ $$m + S(n) \coloneqq S(m + n) \tag{A2}$$

其中 $S(n)$ 意思是「$n$ 的後繼」，即緊接在 $n$ 後面的數。

只從這兩條規則出發，你可以證明 $(\mathbb{N}, +, 0)$ 是一個么半群——你不需要憑信念接受它。

單位元（右邊）。 規則 (A1) 直接陳述 $m + 0 = m$，所以 $0$ 是一個右單位元。✓

單位元（左邊）。 主張 $0 + m = m$ 需要對 $m$ 進行一個簡短的歸納：

• 基本情況 ($m = 0$)：$0 + 0 = 0$，由 (A1) 得。✓
• 歸納步驟：假設 $0 + m = m$。那麼 $0 + S(m) = S(0 + m) = S(m)$，由 (A2) 和假設得。✓

所以 $0$ 也是一個左單位元，確認它就是單位元。✓

結合性。 證明 $(a + b) + c = a + (b + c)$ 是一個類似的對 $c$ 的歸納，在每個步驟使用 (A1) 和 (A2)。細節是一個很好的歸納法（proof by induction）練習。

結論：么半群 $(\mathbb{N}, +, 0)$ 不只是你在例子中觀察到的模式——它是一個從皮亞諾的定義中得出的定理。這個結構被烘焙進了公理本身。

摘要

• $S$ 上的二元運算（binary operation） $\star$ 把 $S$ 的任意兩個元素映射到 $S$ 的另一個元素——這叫做封閉性。
• 一個運算是結合的，如果 $(a \star b) \star c = a \star (b \star c)$ 總是成立。結合性讓你能從長串中省略括號而不改變結果。
• 半群（semigroup） $(S, \star)$ 是一個配備了結合的二元運算的集合。例子：$(\mathbb{Z}^+, +)$、$(\mathbb{N}, \times)$ 和非空字串在串接下。
• 單位元（identity element） $e$ 對每個 $a \in S$ 滿足 $e \star a = a \star e = a$。當單位元存在時，它是唯一的。
• 么半群（monoid） $(S, \star, e)$ 是一個也有單位元的半群。例子：$(\mathbb{N}, +, 0)$、$(\mathbb{N}, \times, 1)$、以 "" 為單位元的所有字串在串接下。
• 不是每個半群都是么半群：$(\mathbb{Z}^+, +)$ 和非空字串在串接下是沒有單位元的半群。
• 從皮亞諾公理出發，你可以證明 $(\mathbb{N}, +, 0)$ 是一個么半群——這個結構是 $0$、$S$ 和 $+$ 的定義的邏輯結果。