群とモノイドと半群
代数構造 algebrtic structure
集合に演算や作用をいれることによって決まる構造のことを代数構造という．
言いかえると，代数構造というのは特定の演算や規則に従うオブジェクト（object）の集合のことと言える．
代数系 algebraic system
代数的構造を持つ集合は代数系といいます．
つまり，$A$ に演算 $\circ$ が定義されているときに，この集合 $A$ と演算 $\circ$ を一緒に考慮した \[(A;\circ)\]を代数系という．
群 group
1832年にエヴァリスト・ガロア[Évariste Galois;1811-1832]が発見した重要な代数的構造に群というものがある．
群というのは代数系 $(A;\circ)$ が以下の性質を満たすもののこと．
- 演算 $\circ$ について結合律 $x \circ (y \circ z)=(x \circ y) \circ z$ が成立すること
- 演算 $\circ$，単位元 $e$（identity element） について，$x \circ e=e \circ x=x$ となること，つまり，単位元が存在すること
- $A$ のすべての元に演算 $\circ$ に関して，$x \circ x^{-1}=x^{-1} \circ x=e$ となること，つまり，逆元が存在すること
群[group]というのは,同じ性質を持つものの集まり,という意味に由来.
群と半群とモノイド
| 結合律 | 単位律 | 可逆律 |
| 群 | ○ | ○ | ○ |
| モノイド | ○ | ○ | × |
| 半群 | ○ | × | × |
- 結合律（associative law）：集合$S$の任意の要素$a，b$の間に演算$a \cdot b$が定義されていて，$（a \cdot b）\cdot c＝a \cdot（b \cdot c）$が任意の$a，b，c$について成り立つこと
- 単位律：集合$S$の任意の要素$a，b$の間に演算$a \cdot b$が定義されていて，$S$に属する1つの元 $e$ に対して $x \cdot e＝e \cdot x＝x$ を満たすときこれを単位元といい,これが成り立つこと
- 可逆律：集合$S$の任意の要素$a，b$の間に演算$a \cdot b$が定義されていて,$a \cdot b=e=b \cdot a$が成り立つこと
- 半群の例：0を含まない自然数と足し算
- モノイドの例：0を含めた自然数と足し算
つまり，モノイドとは単位元を持つ半群ということになります - 群の例：整数と足し算
整数は,
・・・・・,-3,-2,-1,0,1,2,3,・・・・・
自然数は,
1,2,3,・・・・・
「正規表現（regular expression）は有限モノイドへの準同型の逆像」
準同型（homomorphism）：代数系$A$から$B$への写像$f$が準同型とは，$A$の演算$\circ$に$B$の演算$\bullet$が対応しているとき，$A$の各元$x,y$について$f(x \circ y)＝f(x) \bullet f(y)$を満たすことと定義されます．
もし，準同型かつ全単射，すなわち１対１なら同型と呼ばれます．
Mathematics is the language with which God has written the universe.
