半群

定義

半群

半群(semigroup)とは，以下の2つのデータからなる．

集合 $𝑆$
積と呼ばれる $𝑆$ 上の2項演算 $\cdot : 𝑆 \times 𝑆 \to 𝑆$

これらは以下を満たす．

結合律: $\forall 𝑎, 𝑏, 𝑐 \in 𝑆, (𝑎 \cdot 𝑏) \cdot 𝑐 = 𝑎 \cdot (𝑏 \cdot 𝑐)$

準同型

半群 $𝑆, 𝑇$ を与える．写像 $𝑓 : 𝑆 \to 𝑇$ で以下を満たすものを，（半群）準同型と呼ぶ．

$\forall 𝑥, 𝑦 \in 𝑆, 𝑓 (𝑥 𝑦) = 𝑓 (𝑥) 𝑓 (𝑦)$

積の記号を省略しているためわかりづらいが，準同型は $𝑆$ の元を $𝑇$ の元へ送るだけでなく， $𝑆$ の積を $𝑇$ の積へ送る．

同型

全単射な準同型を同型と呼ぶ．

同型の始域と終域の（組の）ことも同型(isomorphic)と呼ぶ．

半群の圏

対象を全ての半群，射を全ての半群準同型とする圏を半群の圏(category of semigroups)と呼び $𝐒𝐞𝐦𝐢𝐆𝐫𝐩$ と表す．

同型定理

半群の圏の部分対象，商対象を確認し，同型定理を示す．

部分半群

半群 $𝑆$ を与える．

$𝑆$ の部分集合 $𝑇 \subset 𝑆$ が， $𝑆$ の積に関して半群になる，つまり以下を満たすとき， $𝑇$ を $𝑆$ の部分半群と呼ぶ．

$𝑇 𝑇 \subset 𝑇$

自明な部分半群

半群 $𝑆$ を与える．

$𝑆$ 自身は $𝑆$ の部分半群となる．これを $𝑆$ の自明な部分半群(trivial subsemigroup)と呼ぶ．

それ以外の部分半群を非自明と呼ぶ．

生成系

半群 $𝑆$ と部分集合 $𝑇 \subset 𝑆$ を与える．

$⟨ 𝑇 ⟩ ≔ ⋃_{𝑛 = 0}^{\infty} 𝑇^{𝑛}$ は $𝑇$ を含む最小の $𝑆$ の部分半群となる．これを $𝑇$ で生成される部分半群と呼ぶ．

特に， $𝑆 = ⟨ 𝑇 ⟩$ を満たすとき， $𝑇$ を $𝑆$ の生成系と呼ぶ．

商半群を定義する準備をしよう．安定関係に関してはマグマに同じ．

安定閉包

半群 $𝑆$ と $𝑆$ 上の関係 $\sim$ を与える．

$\sim$ の安定閉包は，以下に等しい． $\sim \cup 𝑆 \cdot \sim \cup \sim \cdot 𝑆$

関係の正規閉包

半群 $𝑆$ と $𝑆$ 上の関係 $\sim$ を与える．

$\sim$ の正規閉包 $\sim_{ncl}$ に関して，以下が成り立つ． $\sim_{ncl} = ⋃_{𝑛 = 0}^{\infty} {(\sim \cup 𝑆 \cdot (\sim \cup \sim^{op}) \cup (\sim \cup \sim^{op}) \cdot 𝑆)}^{\circ 𝑛}$

合同（正規関係）に関してはマグマに同じ．

商半群

半群 $𝑆$ を与える．

$𝑆$ の誘導する合同 $\equiv$ に対し， $𝑆 ∕ \equiv$ は自然な積 $\forall 𝑥, 𝑦 \in 𝑆, [𝑥] \cdot [𝑦] ≔ [𝑥 \cdot 𝑦]$ に対して半群をなす．これを $\equiv$ による商半群と呼ぶ．

同型定理

第一同型定理

半群

𝑆, 𝑇

と準同型

𝑓 : 𝑆 \to 𝑇

を与えると，以下が成り立つ．

$\sim : 𝑓 (𝑥) = 𝑓 (𝑦)$ で定義される関係は合同．
$𝑓$ の像 $𝑓 (𝑆)$ は $𝑇$ の部分半群
$𝑓$ の像 $𝑓 (𝑆)$ と商半群 $𝑇 ∕ \sim$ は同型

半群の圏

反対半群

半群 $𝑆$ を与える．集合 $𝑆$ に積を $\forall 𝑥, 𝑦 \in 𝑆, 𝑥 \cdot 𝑦 ≔ 𝑦 \cdot_{𝑆} 𝑥$ により定義したものを， $𝑆$ の反対半群と呼び， $𝑆^{op}$ と表す．

自由半群

（文字の）集合 $𝐴$ を与える．

（集合） $𝐴$ 上の自由半群(free semigroup)とは，以下のデータからなる．

語(word)と呼ばれる（文字列の）集合 $𝛺_{𝐴} ≔ ⋃_{𝑛 = 1}^{\infty} 𝐴^{𝑛}$
2文字列の結合（ $𝛺_{𝐴}$ 上の二項演算） $\forall 𝑎 = (𝑎_{1}, \dots, 𝑎_{𝑚}), 𝑏 = (𝑏_{1}, \dots, 𝑏_{𝑛}) \in 𝛺_{𝐴}, 𝑎 𝑏 ≔ (𝑎_{1}, \dots, 𝑎_{𝑚}, 𝑏_{1}, \dots, 𝑏_{𝑛})$

形式的には上のようになるが，語（文字列）を数学的な列というより，「普通の」文字列として $𝑠𝑒𝑚𝑖𝑔𝑟𝑜𝑢𝑝$ のように書く慣習である．

自由半群は半群

集合上の自由半群は半群をなす．

半群の表示

集合 $𝐴$ ， $𝐴$ 上の自由半群 $𝛺_{𝐴}$ を与える．

以下の方法で表される半群を，半群の表示と呼ぶ．

$𝛺_{𝐴}$ 上の関係 $\sim$ に対し， $\sim$ の正規閉包 $\sim_{ncl}$ による商半群 $⟨ 𝐴 | \sim ⟩ ≔ 𝛺_{𝐴} ∕ \sim_{ncl}$

このとき（半群の生成系と同じ意味で） $𝑋$ を生成系(generators)と呼ぶ．また，関係 $\sim$ またはその正規閉包のことを関係（式）(relation)と呼ぶことがある．

非自明な関係

集合 $𝐴$ ， $𝐴$ 上の自由半群 $𝛺_{𝐴}$ を与える．

半群の表示に対する以下の関係のことを非自明な関係と呼ぶ．

$𝛺_{𝐴}$ 上の関係 $\sim$ に対し， $\sim$ の正規閉包 $\sim_{ncl}$ と $\sim$ の安定閉包の反射閉包の対称閉包 $𝛺_{𝐴} \cdot (\sim \cup \sim^{op}) \cdot 𝛺_{𝐴} \cup =$ の差 $\sim_{ncl} ∖ (\sim \cup \sim^{op} \cup 𝛺_{𝐴} \cdot (\sim \cup \sim^{op}) \cup (\sim \cup \sim^{op}) \cdot 𝛺_{𝐴} \cup =)$

有限表示

生成系が有限な半群の表示を有限表示と呼ぶ．

半群の表示の性質

任意の半群は，（無限個の）半群の表示を持つ．
異なる有限表示を持つ半群が等しいかは，（計算可能性の意味で）決定不能．（群の表示がそうだから，そのはず…）