日々の流転

λ. めがまり

良く出来てるなぁ。懐かしい。とりあえず、咲夜・うどんげ・チルノ・霊夢をこの順で倒した。キャラ二人分のライフゲージがあるせいか、ボス戦はそこまで辛くない。といっても、元のロックマン2をもう覚えてないんだけどね。技は、咲夜とチルノの技は魔理沙に、うどんげと霊夢の技はアリスに持たせた。そういえば、ロックマンのボスといえば弱点があるのがお約束のはずだけど、まだ弱点には出会ってない気がする。はて?

パスワードのメモ

●　　　　
　　　●●
●　●　　
●　　　●
●●●●　

λ. 余代数と余帰納法

2006-06-24で「coalgebra等の簡単な解説は近いうちに書こうと思います」と書いたが、このままだといつになっても書けそうにないので、とりあえず書き始めてみる。ちょっとずつ書き足していく予定。

代数と余代数

余代数は代数の双対……といっても何が何だかわかんないと思うので、まずは代数を考える。

代数は集合と演算と演算の満たす規則から構成される。例えば群。集合Gは、演算「e: G」「*: G×G->G」「_^-1: G->G」を持っていて、規則「(a*b)*c = a*(b*c)」「e*x = x」「a^-1*a = e」を満たすとき、群と呼ばれる。同様に集合Lは、演算「⊥: L」「∨: L×L→L」を持っていて、規則「a∨b = b∨a」「a∨(b∨c) = (a∨b)∨c」「a∨a = a」「a∨⊥ = a」を満たすとき、上半束と呼ばれる。これらを見ると、代数では演算はすべて値域がその集合になっていることがわかる(「演算に関して閉じている」という言い方をしたりする)。

圏論では関数の向きを逆向きにすることで双対を考えるので、値域ではなく定義域がその集合になっているような演算を集合に加えることが考えられる。これが余代数。

例) Kripkeモデル

Kripkeモデルは、ノードないしは「世界」の集合 W に、以下の二つの演算を加えた余代数と考えることが出来る。

• 各ノードからの到達可能性を定める関数 W -> ℘(W) と
• 各ノードで成り立つ原子命題の集合を定める関数 W -> ℘(A)

例) オートマトン

言語理論では言語の識別機械としてオートマトンが使われるが、Σをアルファベットの集合とすると、このオートマトンは集合 S に以下の二つの演算を加えた余代数と考えることが出来る。まあ、実際には初期状態も必要なので、この余代数自体ではなく、この余代数の要素をオートマトンと呼ぶべきかも。

• 文字を受け取って状態遷移するための関数 trans: S -> S^Σ
• 受理状態かを判断する関数 accept: S -> Bool

非決定性オートマトンにしたければ、trans: S -> S^Σ を trans: S -> ℘(S)^Σ にすれば良いし、さらにε遷移を許したければ ε: S -> ℘(S) という演算を加えればよい。

例) オートマトン (2)

後で使いたいので、もうちょっと単純なオートマトンも考えておく。 数字(自然数)を表示するディスプレイとボタン一つだけからなり、ボタンを押すと表示されている数字が切り替わるような、そんな機械があったとする。そうすると、この機械は状態の集合Sに以下の二つの演算を加えた余代数としてモデル化できる。

• 現在の数字を得る関数 value: S -> N
• ボタンを押したときに次の状態に遷移する関数 next: S -> S

始代数

余代数の例を幾つか紹介したところで話を代数に戻す。 また唐突だが、自然数全体の集合は、集合Nに以下の二つの演算を加えた代数と考えることが出来る。

• 0: N
• s: N->N

同じ種類の代数 (X, c:X, f:X->X) は他にいくらでも考えることが出来るけど、この (N,0,s) はその中でも「全ての要素が 0 と s の有限回の適用で一意に表記できる」という良い性質を持っている。これは直観的には「潰れていない(0 = s(n) が成り立ったりしない)」ことと「(0とsで表記できない)余計な要素を含んでいない」ことを意味している。

この性質があると嬉しいのは、再帰によって関数を定義することが出来、また(構造)帰納法による証明が出来る点。例えば、以下のような等式を満たす関数は唯一つするので、これによって関数hを定義することが出来る。

• h(0) = c
• h(s(n)) = f(h(n))

この等式を良く見ると、cを集合Xの要素、fをX->Xの関数として、この関数hは実は (N,0,s) から (X,c,f) への準同型になっている。圏論ではこのような「同じ種類の代数への準同型が一意に存在するような代数」のことを始代数(initial algebra)と呼ぶ。

(後で: 帰納法についても書く)

始代数の特徴とはある種の等式の集まりによって関数を定義することが出来、これはつまり「同じ種類の任意の代数への準同型が一意に存在する」ということだった。

(続く)

終余代数 (final coalgebra)

「同じ種類の任意の代数への準同型が一意に存在する」の双対を考えると、「同じ種類の任意の余代数からの準同型が一意に存在する」になる。 なんで、そんなものを考えるか。例えば、上の「オートマトン(2)」で考えた余代数だと、ある状態 s∈S から next を繰り返し適用していって表示される数字を集めると、value(s), value(next(s)), value(next(next(s)), ... という数列が出来るが、以下の二つの点から扱いにくい。

• 異なる s1,s2∈S が同じ数列を生成することがあるかもしれない。この機械を観察することでわかるのは結果の数列だけなので、観察から区別できないような状態が存在することがある。つまり、状態空間が冗長かも知れない。
• また、全ての数列が生成出来るとは限らない。つまり状態が足らないかも知れない。

これらの問題がない、ある意味理想的な余代数が終余代数(final coalgebra)で……

(続く)