自由モノイド

４．自由モノイド

圏論では、普遍性という概念はとても大切である。普遍性は、その言葉が示すように、数学の多くの分野で共通する性質を示したものである。前の記事で説明した極限と余極限も広い分野での共通の性質であるため、圏論での重要な普遍性の一つとなっている。ここでは、普遍性のさらなる例として自由モノイドを説明する。

４．１　自由モノイドの定義

加算や乗算などの二項演算子を用いて計算されるものはモノイドと呼ばれる。モノイドについても普遍性を考えることができる。それは自由モノイドと呼ばれるものだ。これを説明するために、モノイドについて、まずは、集合論での定理から始めてみよう。

１）集合論での定義

集合論でのモノイドは、ある集合\(M\)に対して、
1)　二項演算子\(\mu\)が存在し、\(\mu : M \times M \rightarrow M\)である。
2)　単位律が成り立つ。即ち、単位元\(e\)が存在し、任意の\(x \in M\)に対して\(e \ \mu \ x = x = x \ \mu \ e\)である。
3)　結合律が成り立つ。即ち、任意の\(x,y,z \in M\)に対して\( (x \ \mu \ y) \ \mu \ z = x \ \mu \ (y \ \mu \ z) \)である(わかりにくい時は、\(\mu\)を\(\times\)あるいは\(+\))などで置き換えるとよい。

モノイドの例を挙げておこう。整数での加算は、単位元を0とするモノイドである。ただし、どの整数も二つの整数を加算することで得られるが、その組み合わせは無数である。例えば、3という数は、0+3,1+2, 2+1,3+0,4+(-1),....となる。

もう一つの例は数である。例えば、346という数は、3という数に、4という数を接続し、さらに、6という数を接続することで得られる。これは、加算とは異なり、一つの数を得る方法は複数存在せず、一意であることに注意する必要がある。

そこで、モノイドを作る元(これを生成元と呼ぼう)を用意して、モノイドの定義に従って、集合\(M\)を得ることを考えよう。

今、生成元を\(a,b\)としよう。これに二項演算子\(\mu\)を適用して、モノイドの集合\(M\)を作ってみよう。\(M\)には、生成元と単位元が含まれる。そこで、\(M\)に\(e,a,b\)を含めよう。

次に、これらから\(M\)の新しい要素を作ろう。また、新しい要素は\(\mu\)を省いて表すことにする。
\begin{eqnarray}
a \ \mu \ a &=& a a \\
a \ \mu \ b &=& a b \\
b \ \mu \ a &=& b a \\
b \ \mu \ b &=& b b \\
a \ \mu \ e &=& a \\
e \ \mu \ a &=& a \\
b \ \mu \ e &=& b \\
e \ \mu \ b &=& b
\end{eqnarray}

ここまでで、\(M=\{e,a,b,aa,ab,ba,bb\}\)となる。
新しく得られた要素を利用して、さらに\(M\)の要素を作ってみよう。
\begin{eqnarray}
a a \ \mu \ a &=& a a a \\
a a \ \mu \ b &=& a a b \\
a b \ \mu \ a &=& a b a \\
a b \ \mu \ b &=& a b b \\
b a \ \mu \ a &=& b a a \\
b a \ \mu \ b &=& b a b \\
b b \ \mu \ a &=& b b a \\
b b \ \mu \ b &=& b b b \\
a a \ \mu \ e &=& a a \\
…………..
\end{eqnarray}

ここまでで、\(M=\{e,a,b,aa,ab,ba,bb,aaa,aab,aba,abb,baa,bab,bba,bbb\}\)をえる。
この操作を繰り返すことで、モノイドの要素を求めることができる。そして、このように定義だけを利用して作られたモノイドは自由モノイドと呼ばれる。

これに対して、出現した生成元の順番が異なるにもかかわらず、それらを同一なものと見直すモノイドもある。例えば、加算や乗算では、\(a \ \mu \ b= b \ \mu \ a\)と見なされる。このようなモノイドは自由モノイドとは言わない。

２）圏論での定義

圏論ではモノイドは、集合論での定義の時に用いた\(M,e,\mu\)を利用して、次のように定義される。圏論を学び始めると、モノイドは次のように定義される
1)　対象：シングルトン(星印で表されることが多い)
2)　射：集合\(M\)の要素
3)　ソースとドメイン:＊
4)　恒等射：単位元\(e\)
5)　結合：関数\(\mu\)
さらに、単位律、結合律が成り立つである。

さらに学習を続けると、モノイドは、抽象度をたためて、モノイド圏として次のように定義される。

1)　対象：関手の集まり\(\{M,I\}\)
2)　射：自然変換\(\mu\)
3)　ドメイン・コドメイン
4)　恒等射：自然変換
5)　合成：\(\circ\)

ここで、モノイド圏の\(M\),\(\mu\)は、集合論での集合\(M\)と二項演算子\(\mu\)と同じ役割を持つ。また、モノイド圏の\(I\),は、集合論での単位元\(e\)と同じ役割を持つ。ただし、モノイド圏では、\(M\)と\(I\)は対象となっている。そして、専門的な用語で説明すると、\(M\)は自己関手で、\(I\)は恒等関手である。射\(\mu\)は、\(M \times M\)から\(M\)への自然変換である。抽象度が上がっているので、特殊な用語を用いているが、二項演算子の定義と同じ役割を担っている。恒等射は、\(I\)を\(M\)に写す自然変換である。これは、単位元をモノイドの集合に組み込む仕掛けを与えていると思えばよい。

また、モノイド圏である時、上記で説明した関手と自然変換の間では次の可換図式が成り立つ。この可換図式は、\(mu:M \times M \rightarrow M\)であり、である。

なお、この可換図式から、モノイド圏では単位律と結合律が満たされることが分かる。これらについて詳しく知りたいときは、モノイド圏の記事を見て欲しい。

３）Haskellとの関係

Haskellでの自由モノイドは、リストである。圏論での自由モノイドと対比させると、恒等射は[ ]、結合は++となる。対象は、数を扱っている場合であれば数のリスト、文字を扱っている場合であれば文字のリストとなる。

例えば、数のリストだとすると、次のような例を得ることができる。

Prelude> a=[]
Prelude> b = [1]++[]
Prelude> b
[1]
Prelude> c = [2]++b
Prelude> c
[2,1]
Prelude> d =[2,4,5]++c
Prelude> d
[2,4,5,2,1]
Prelude> :t d
d :: Num a => [a]

文字のリストの例も挙げておこう。

Prelude> a=[]
Prelude> b= ['a']++a
Prelude> b
"a"
Prelude> c =['n','a','r']++b
Prelude> c
"nara"
Prelude> :t c
c :: [Char]

自由モノイドではないモノイドの例としては、数での加算や乗算などを挙げることができる。
乗算のモナイドを例にとってみよう。最初の例で、恒等射[ ]を1とし、結合++を＊にすると、

Prelude> a=1
Prelude> b = 1*a
Prelude> b
1
Prelude> c = 3*b
Prelude> c
3
Prelude> d = 2*5*6*c
Prelude> d
180
Prelude> :t d
d :: Num a => a

４．２　集合論をベースにしたモノイドの圏

集合論の世界の中で、モノイドを構成する要素を生成元から作り出す手順を説明したが、これを圏にすることとしよう。そして、この圏を\(\mathbf{Set}\)と呼ぶこととしよう。

このために、生成元だけで構成された集合\(X\)を用意する。次に、この生成元から自由モノイドを作り出す。ここで得られた集合を\(M\)とし、\(\mathbf{Set}\)の対象の一つとすることとしよう。なお、自由モノイドは、その生成の仕方からわかるように、一つであることが分かる。なお、この時の生成方法を射\(p:X \rightarrow M\)とする。

さらに、\(X\)を必要な生成元とすることで作られたモノイドの集合\(N,N’…\)をそれぞれ\(\mathbf{Set}\)の対象の一つとすることとしよう。この時の生成方法を射\(q,q’...:X \rightarrow N,N’\)とする。

このようにして作られるモノイドには、異なる二つの要素間での二項演算の結果が一致するような加算や乗算から作られたものが含まれるし、\(X\)にさらに元を加えて作り出されたモノイドなども含まれる。これにより下図のような圏が得られる。

４．３　圏論をベースにしたモノイドの圏

集合論をベースにしたモノイドの圏\(\mathbf{Set}\)が作れたので、次は、圏論をベースにしたモノイドの圏\(\mathbf{Mon}\)を作ることにしよう。これは、簡単で、モノイド圏をそのまま使えばよいので、下図を得る。また、自由モノイドでの射は\(\mu\)とし、そうでないモノイドの射は\(\nu,\nu ’\)とした。

さて、圏\(\mathbf{Mon}\)は、対象間に射を設けられる可能性がある。ここでは、とりあえず、自由モノイドとそうでないモノイドとの間に射を定義しておこう。それらを\(h,h’...\)としよう。

そして、以下の議論で、これらの射\(h,h’...\)が、一意的な準同型写像になることを示し、自由モノイドが圏論での普遍性の一つとなることを示す。

４．４　モノイド圏と集合圏を忘却関手でつなぐ

圏論での世界と集合論の世界をベースにした圏が構成できたので、この二つの圏を関手でつなぐことを考えよう。そこで、圏\(\mathbf{Mon}\)から圏\(\mathbf{Set}\)への関手\(U:\mathbf{Mon} \rightarrow \mathbf{Set}\)を用意しよう(下図)。この関手は、\(\mathbf{Mon }\)の対象を\(\mathbf{Set}\)の対象に写し、射については何も行わない。この関手\(U\)は忘却関手(forgettable functor)と呼ばれる。これは、圏論の世界でモノイドが有していた構造が、集合論の世界に写したときに失われることによる。

忘却関手を用意したので、集合論の世界での対象\(M\)は対象\(N\)に\(U(h)\)で写される。

４．５　モノイド圏と集合圏を忘却関手でつなぐ

今までの説明だけではわかりにくいので、例を用いて具体的に示そう。二進数\(0,1\)の場合を考えてみよう。自由モノイドの方を二進数の数とし、そうでないモノイドの方を2進数の乗算とすると下図を得る。この図で、\(p\)は2進数の数を、\(q\)は2進数の乗算の結果を作り出す関数である。なお、任意の\(a,b \in \{0,1\}\)に対して、\(h([a]++[b])=h(a)*h(b)\)とする。この時、準同型写像になっていることを確認して欲しい。

次の例は、生成元を増やしてモノイドを作る例だ。ここでは、右側のモノイドを生成するときに、生成元に2を加えて、3進数の数を作り出すことを考えよう。この場合には、下図をえる。もちろん、\(q\)は3進数の乗算の結果を作り出す関数である。この時も、任意の\(a,b \in \{0,1\}\)に対して、\(h([a]++[b])=h(a)*h(b)\)とする。そして、準同型写像になっていることを確認して欲しい。

生成元を増やしたので、次は、いくつかの生成元は同じだと見なしてモノイドを作る例を考えよう。次の例は、いずれの生成元に対しても、集合\(N\)の同じ要素に写像されるようにしよう。以下の例では、1に写されるようにした。そして、下図のようになる。同じように、任意の\(a,b \in \{0,1\}\)に対して、\(h([a]++[b])=h(a)*h(b)\)とする。これも、準同型写像になっていることを確認して欲しい。

４．６　普遍性としての自由モノイド

自由モノイドを理解してもらうために、自由モノイドを集合論に基づいて定義し、その性質について説明してきた。

しかし、我々が議論しているのは、集合論の世界ではなくて圏論の世界である。このため、自由モノイドを圏論の世界の中で定義する必要がある。そこで、下図の可換図式で示されるように、次のように定義する。

モノイド圏を対象とした圏\(\mathbf{Mon}\)と集合からなる圏\(\mathbf{Set}\)が存在したとする。忘却関手\(U\)は、\(\mathbf{Mon}\)の対象となっているモノイド圏のそれぞれに対して、その対象を\(\mathbf{Set}\)の対象に写すとする。

今、あるモノイド圏\(\mathcal{M}\)から任意のモノイド圏\(\mathcal{N}\)に対して準同型写像\(h\)があったとする。また、これらの圏\(\mathcal{M,N}\)は忘却関手\(U\)で\(\mathbf{Set}\)に写されるので、これらの対象を\(\{M,I\},\{N,I\}\)とすれば、写される先は\(U(\{M,I\}),U(\{N,I\})\)となる。

さらに、生成元{X}を対象とする圏を考えよう。この圏から、先に説明した方法により、モノイドを生成することができる。このため、\(U(\{M,I\}),U(\{N,I\})\)への射が存在するはずである。それらを\(p\),\(q\)としよう。

この時、\(p \circ U(h) = q\)とするような\(h\)が一意的に定まるとき、\(\mathcal{M}\)を自由モノイドと呼ぶ。但し\(U(h):U(\{M,I\})\rightarrow U(\{N,I\})\)である。

自由モノイドが、任意のモノイド圏\(\mathcal{N}\)に対して、準同型写像\(h\)が一意的に定まるといっているので、これは圏論での重要な概念である普遍性であるということができる。

前後が逆になるが、例で挙げたものが自由モノイドになっていることを改めて確認して欲しい。