半群とモノイド

プログラマーとして毎日、数値を加えて、文字列を結合して、リストをマージしている。これらは全く異なる演算のように感じられるが、実は密かに同じ数学的な形を持っている。その形の名前を知ると、至るところでそれを見つけ始め、コードについてより明確に推論する助けになる。

二項演算とは何か

集合 $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$ が結合的（associative）とは、すべての $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$ 上の結合的な二項演算である組 $(S, \star)$ のことだ。

これが定義のすべて — 集合と結合的な演算。それ以外は何も要求されない。

半群の例

加算のもとでの正の整数。 $\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$ が存在するには、$n + e = n$ がすべての $n \in \mathbb{Z}^+$ に対して成り立つような正の整数 $e$ が必要になる。それは $e = 0$ を意味するが、$0$ は正の整数ではない。だから $(\mathbb{Z}^+, +)$ には単位元がない。

同様に、空でない文字列の連結 $(S^+, \mathbin{++})$ にも単位元がない：空文字列 "" は完璧に機能するが、空でない文字列の集合 $S^+$ には含まれていない。

単位元があるかどうかは、集合に「空」または「ゼロ」の場合を注意深く含めたかどうかにかかっていることが多い。

モノイド

単位元を持つ半群は新しい名前を得る。

定義。 モノイド（monoid）とは、$(S, \star)$ が半群で $e \in S$ が $\star$ の単位元である三つ組 $(S, \star, e)$ のことだ。

すべてのモノイドは半群だが、すべての半群がモノイドであるわけではない。追加の要素は正確に単位元だ。

モノイドの例

集合 $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$ は最も小さな自然数なので、任意の $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) を使う。詳細は帰納法による証明の良い練習問題だ。

ポイント：モノイド $(\mathbb{N}, +, 0)$ は例の中に観察するパターンではなく — ペアノの定義から従う定理だ。構造は公理自体に焼き込まれている。

まとめ

• $S$ 上の二項演算 $\star$ は $S$ の任意の二つの要素を $S$ の別の要素に対応させる — これを閉包と呼ぶ。
• 演算が結合的とは $(a \star b) \star c = a \star (b \star c)$ が常に成り立つことだ。結合法則によって長い連鎖から括弧を取り除いても結果が変わらない。
• 半群 $(S, \star)$ は結合的な二項演算を持つ集合だ。例：$(\mathbb{Z}^+, +)$、$(\mathbb{N}, \times)$、空でない文字列の連結。
• 単位元 $e$ はすべての $a \in S$ に対して $e \star a = a \star e = a$ を満たす。単位元が存在する場合、それは一意だ。
• モノイド $(S, \star, e)$ は単位元を持つ半群だ。例：$(\mathbb{N}, +, 0)$、$(\mathbb{N}, \times, 1)$、単位元 "" を持つすべての文字列の連結。
• すべての半群がモノイドであるわけではない：$(\mathbb{Z}^+, +)$ と空でない文字列の連結は単位元を持たない半群だ。
• ペアノの公理から $(\mathbb{N}, +, 0)$ がモノイドであることを証明できる — 構造は $0$、$S$、$+$ の定義の論理的な帰結だ。