人気ブログランキング | 話題のタグを見る

モノイドと自由モノイド

モノイドの定義を Wikipedia で調べてみた。

集合 S とその上の二項演算 • : S × S → S が与えられたとき、組 (S, • ) が以下の条件を満たすならば、これを モノイド という。

結合律
    S の任意の元 a, b, c に対して、(a • b) • c = a • (b • c)
単位元の存在
    S の元 e が存在して、S の任意の元 a に対して e • a = a • e = a

二項演算の結果 a • b を a と b の積[* 1]と呼ぶ。手短に述べれば、モノイドとは単位元を持つ半群のことである。モノイドに各元の可逆性を課せば、群が得られる。逆に任意の群はモノイドである。

二項演算の記号は省略されることが多く、たとえば先ほどの公理に現れる等式は (ab)c = a(bc), ea = ae = a と書かれる。本項でも明示する理由がない限り二項演算の記号を省略する。

こういうのは実例を見ればすぐ分かる。自然数 {1, 2, 3, ... }と自然数の乗法 * の組みあわせはモノイドだ。自然数の積の値は自然数だし、次のように結合法則をみたす。

(2 * 3) * 4 = 2 * (3 * 4) = 24

また自然数の単位元は 1 だ。なぜなら次の等式が成り立つからだ。

1 * 3 = 3 * 1 = 3

モノイドといっても、自然数の集合とその乗法演算という具体例でみるとなんということはない。ただ、具体例からだけはモノイドという数学的構造が自然数の集合 {1, 2, 3, ... } に与えられているというのは見えない。具体的な計算は目に見えるが、「数学的構造」は目には見えないからだ。しかし、具体例と定義の間を行ったり来たりしているうちに、目に見えない「代数的構造」というものが見えてくる。

自由モノイドというのも乗法の導入された自然数と同じモノイドだ。ウィキペディアから定義を引用すると次のようになる。

逆に、ある固定された文字集合 Σ 上の有限文字列全体(空文字列を含む)は、文字列の連接を二項演算とし単位元を空文字列としてモノイドとなる。このモノイドを Σ∗ で表す[* 2]と、これは Σ を生成系としてもち、公理の等式以外に元の間の関係式をもたないので Σ 上の自由モノイドと呼ぶ。自由モノイド(英語版)はモノイドの圏における自由対象である。

これも具体例で考えると簡単だ。Σ = {a, b, c} とする。a b c は文字を想定しているが引用符は面倒なので省略した。これに文字の連結を行う演算 . を導入すると次のようになる。

a . b = ab, ab . bc = abbc, ...

また、

(a . b) . c = ab . c = abc だし、a . (b . c) = a . bc = abc になるので次のような結合法則が成り立つ。

(a . b) . c = a . (b . c)

さらに文字がなんにもない空文字 '' は次のように単位元になる事が分かる。

a . '' = '' . a = a

つまり自由モノイドは文字列の集合 {'', a, b, c, aa, ab, ac, ba, bb, bc, ca, cb, cc, abc, ... } に文字列の連結という二項演算 . があり、単位元 '' があるというだけのものだ。蓋を開けてみるとなんということはない。この自由モノイド (A, .) が自然数と乗法のモノイド (N, *) と同じ代数的構造をもっていることは、上の実例を見比べてみると分かる。

自由モノイドの「自由」の意味がわからなかったが、二項演算が文字列の連結であるだけなので、2 * 3 = 6 というようなルールがない。文字の並べ替えの規則以外の規則が全くない(意味論がなく、統語論だけで話がすむ)からのようだ。

数学的構造はこのように、定義と実例の両方を知っていないと理解できない。逆に実例をたくさん知っていれば数学の表現はやさしく感じられるのかもしれない。数学の本を理解したければ、こういう実例を昆虫採集のようにたくさん集めるといいのだろう。圏論が難しいのはこの具体例自体が数学的構造だからだ。
by tnomura9 | 2014-08-23 19:03 | 圏論 | Comments(0)
<< 群と自由群 アナロジー >>