Category Theory for scientists(David spivak) メモ ... Monoidについて
圏の定義をした後、圏の例として集合の圏$\textrm{Set}$やモノイドの圏$\textrm{Mon}$の説明があるのだが、ここでは、モノイドについて説明する。
※CT4Sでは、事前に集合の圏論的な話をやって(Chapter2)、次にモノイドや群、プレ順序やグラフなどの説明(Chapter3)をした後に、圏の定義をしているため、すんなり説明が理解できるようになっている。
definition 3.1.1.1
モノイドとは、次の三つ組$(M,e,*)$で定義されるもので、$M$は、集合であり、$e$は、Mのある一つの要素$e \in M$であり、$*$は、$*:M \times M \to M$ の関数である。それぞれは、次を満たす。ただし、$ m,n,p \in M$。
- $ m * e = m $
- $ e * m = m $
- $ ( m * n ) * p = m * ( n * p ) $
eは単位元で、三番目の条件はmultiplication formulaである。
これで、$*$に逆元 $ m * m' = e$ なる$m' \in M$が存在すると群になる。さらに別の演算子$+$が定義できて分配則を満たすと環になり、さらに体になり...と数学の代数における基本的な構造の、もっとも基本的なところにmonoidはある。
モノイドの例としては、$(\mathbb{N} , 0 , + )$ とか、$(\mathbb{N} , 1 , \times )$とか。さらに、適当な集合$M$を用意して、自由モノイドというのを造ることができる。
Definition 3.1.1.15
Xを集合として、"Xによって生成された自由モノイド"とは、$ M=( \textrm{List}(X) , [ ] , ++ ) $ である。ここで、$\textrm{List}(X) $ とは、たとえば、$X={a,b,c}$ だとすると $[a,b,a,b,c,a,b,b]$ みたいな$X$の要素を用いて作った文字の並びリストのこと。$[ ]$は、空のListで$++$の演算子は、リストのコンカチを表わす。たとえばこんな感じ
\[ [a,b,a,b,c,a,b,b] ++ [a,b,c] \to [a,b,a,b,c,a,b,b,a,b,c] \]
Listはいろんなパターンが無限に続けられるが、これをすべて、モノイドの要素として考えてしまうのが自由monoidである。ここで、集合$X$をmonoid $ M$ の生成子(generators)と呼ぶ。
自由モノイドにおいて、$List(X)$の要素 $ m , m' \in \textrm{List}(X)$ を、"同値として定義することを考えらることができる。たとえば、
\[ [ a,b,a,b,c] \sim [ c,a] \]
なんていう定義を、自由モノイドの中に組み込んでおくと、先のListは、$ [a,b,a,b,c,a,b,b] = [c,a,a,b,b] $ と変換できて、これを$\textrm{List}(X)$において、同一の要素として定義することができる。これを"Presented monoid"という。
Definition 3.1.1.17
有限な集合$G$、nを自然数$ n \in \mathbb{N} $ とし、$m,m'$は、$\textrm{List}(G)$の要素$ m,m' \in \textrm{List}(G) $ で、 $i$を$ 1 \le i \le n $ とする。”生成子Gと関係$ \{ (m_i,m'_i) | 1 \le i \le n \}$ によって提示される(presented)モノイド”とは、次のように定義される。$ \sim$ を$\textrm{List}(G)$上の同値関係として $ \{ ( xm_iy \sim x m'_i y ) | x,y \in \textrm{LIst}(G),1 \le i \le n \} $ と定義し、 $ M = \textrm{List}(G)/\sim $と定義された自由モノイドである。
そんなにややこしい話ではない。たとえば$ ( \mathbb{N} , 0 , + ) $ 足し算のmonoidにおいては、$ 1 + 2 = 1 + 1 + 1 = 3 $のように、$1+2$と$1+1+1$は同値関係である。前述した定義が成り立つ構造のものならばmonoidであるから、monoidはいろいろなもの考えられるが、同値関係によってmonoidの構造の特徴が表せると考えられる。
次に、monoid 作用というものがある。
Definition 3.1.2.1
monoidを$(M,e,*)$として、 $S$を集合とする。"S上の$(M,e,*)$による作用"とは、次のような関数のこと：
\[ \circlearrowleft : M \times S \to S \]
これは、$ m,n \in M$ と$s \in S$において、次の条件が成り立つ。
- $ e \circlearrowleft s = s $
- $ m \circlearrowleft ( m \circlearrowleft s ) = ( m * n ) \circlearrowleft s $
$s \in S$という状態に対して、monoidの要素を"操作”と考えて、$s$がその操作によって次の状態$s'$へ遷移することが表現できる。つまりこれによって、決定性の有限状態機械、オートマトンを表現できるのである。
オートマトンの状態遷移図は、表によって記述することもできる。たとえば、モノイドを$G={a,b}$で生成される自由モノイドで、状態$S$を$S=\{状態0,状態1,状態2\}$とかけるとする。
| ID | a | b |
|---|---|---|
| 状態0 | 状態1 | 状態2 |
| 状態1 | 状態2 | 状態1 |
| 状態2 | 状態0 | 状態0 |
この表は、IDの状態が a or b のモノイド作用によってそれぞれの行の状態に遷移する、ということを表現している。たとえば、状態0の場合で、操作がaの場合は状態1、bの場合は状態2、(表の2列目)というふうに。
最後に、monoidのhomomorphismについて：
Definition 3.1.4.1
$\textit{M}:=(M,e,*) $ と$\textit{M'}:=(M',e',*')$をモノイドとしたとき、"$\textit{M}$から$\textit{M'}$へのモノイドの準同型写像"(monoid homomorphism)とは、$ f：\textit{M} \to \textit{M'} $ と書ける関数で、モノイドの要素に対しての関数 $ f:= M \to M' $ であり、次の条件を満足するもの。
- $ f(e) = e' $で
- $ f(m_1 * m_2) = f(m_1) *' f(m_2) for all m_1,m_2 \in M
つまりいろいろなモノイドについての写像が定義できるということである。
集合の圏$\textrm{Set}$が、いろいろな集合をobjectとし、集合の写像を圏の射として定義できたのと同様に、monoidについても、いろいろなモノイドをobjectとして、monoidの写像を圏の写像とみなして圏を構成することができる。これをmonoid圏$\textrm{Mon}$とかく。
