圏論の言葉

Haskell を勉強し始めて IO モナドなんかに出くわさなければ圏論など近づこうともしなかっただろうが、モナドを正確に理解したくなって、圏論の入門書 Conceptual Mathematics: A First Introduction to Categories F. William Lawvere、 Stephen H. Schanuel を読み始めた。高校卒業程度の予備知識でも読めるように懇切丁寧に書かれているのがうれしい。

しかし、圏論は圏論なので、そう簡単に理解できるようには思えない。そこで、分かったと思えたところをまとめてみる事にした。

圏論は適用範囲が広い抽象的な考え方なので、具体的なイメージが作りにくい。やはり、慣れ親しんだ集合と写像を使える「集合の圏」から始めた方が良いようだ。集合と写像を、対象と射として取り扱う事によって、他の圏に対してもイメージを広げていく事ができるのではないだろうか。ということで、以下では集合と写像からなる集合の圏について考えることにする。

圏には2つの要素がある。対象と射だ。集合の圏でいえば、対象は集合で射は集合から集合への写像になる。対象と射がどのような性質を持つものかは分からないでも、集合と写像ならイメージできる。

集合 A と 集合 B があって、集合 A から集合 B への写像 f があるとする。これが、圏であるためには、関数 f の domain が 集合 A で、codomain が集合 B でなければならない。

このとき、domain である集合 A のどの要素に対しても関数 f が定義されている必要がある。つまり、集合 A は関数 f の定義域である必要がある。なぜなら、圏では射の合成が定義できなければならないが、写像 g と f の合成 g . f がいつでも定義されるためには、g はその domain の全ての値に対して定義されていなければならないからだ。

しかし、codomain である集合 B の場合は関数の値域である必要はない。関数 f による集合 A の像が集合 B の部分集合である必要はあるが、codomain である集合 B と f(A) が一致する必要はない。ここのところが分かっていないと、後で述べる section や retraction の意味が分からなくなる。

また、写像の定義から 集合 A の要素 a の関数 f による像 f(a) は一つだけで(もちろん集合 B の要素であるが)f(a) = {b1, b2} のような対応の仕方はしない。

このように見てくると集合と写像を「集合の圏」にするための制約が結構多いことがわかる。この基本的な制約から「集合の圏」の性質を調べていかなければならないのだが、集合と写像といったり、対象と射と言ったりするとなかなか面倒なので、これ以後は対象と射という用語で統一する事にする。

集合の圏の定義が上のようであれば、対象 A から 対象 B への射 f と対象 B から 対象 C への射が g である場合射の合成 g . f ができて、これは 対象 A から 対象 C への射となる。つまり、

f : A -> B かつ g : B -> C のとき、g . f : A -> C

を考える事ができる。このとき、f は B への全射でなくてもいいが、g の定義域は B である必要がある。つまりどの B の要素にも g が定義されている必要がある。

集合の間の写像が圏の射であるためには、さらに制約がでてくる。それは、射の合成が結合法則に従う必要があるという事だ。つまり、

f : A -> B, g : B -> C, h : C -> D のとき

h . (g . f) = (h . g) . f

が成り立つということだ。したがって、射の合成の結果はその合成の順序によらないから、

h . (g . f) = h . g . f

のように括弧を外して使う事ができる。

なぜ結合法則が大切かというと、例えば、射 g についてその逆方向の射 i : C -> B があって i . g = idB だったとする。idB は対象 Bのどの要素についてもその要素自身を対応させる写像だ。つまり x を対象 B の要素だとすると、idB (x) = x であるということだ。Haskell では単に id と定義されている。

そうすると次のように合成射の縮約ができる。

i . (g . f) = (i . g) . f = idB . f = f

このように、射の合成に関して演算を施す事ができるためには、どうしても結合法則が必要なのだ。

idB については特に説明せずに使ったが、これは対象 B から対象 B への恒等射で B の全ての要素 x について idB (x) = x となるようなものである。このような idB に対して、

idB . f = f および g . idB = g 、ただし、f : A -> B, g : B -> C

が成り立つ。

今までの議論をもっと定式的に述べるために、圏論の Wikipedia の記述を抜粋すると次のようになる。

圏(category)[1] は、射(morphism,map,arrow)と対象(object)と呼ばれる2種の集団からなる。

圏 C の射 f は必ずドメイン(domain)、余ドメイン(codomain)と呼ばれる C の対象が割り当てられている。 A が f のドメイン dom(f) = A かつ B が f の余ドメイン codom(f) = B であるとき f : A → B と表記する[2]。 圏の射について以下が成り立つ

射の合成演算(composite operator)’・’の存在
C の射 f , g in C について、dom(g) = codom(f) ならばそれらの合成 g・f in C が唯一つ存在する

結合律(associative law)
合成射 h・g , g・f が存在するとき、
h・(g・f) = (h・g)・f
がいつでも成り立つ。

単位元律(unit law)
ドメインと余ドメインが同一の射 1B : B → B が存在し、任意の射の合成について
1B・f = f かつ g・1B = g ただし、f : A → B , g : B → C
が成り立つ。1B のような各対象に対して割り当てられ、上記性質を持つ射を恒等射(identity)と呼ぶ。

上のように簡潔に書かれた圏の定義が、具体的な集合の圏になると、結構制約が多く、細かい所に注意が必要になる事がわかる。

ところで、Haskell の記法は圏を記述するのに便利だ。たとえば、関数の型のシグネチャー、

square :: Doublle -> Double

というのは、圏論風に表現すると、射 square は対象 Double から対象 Double への射であるということができる。実際、Haskell のプログラムは、データ型を対象とし、関数を射とする圏である。したがって、圏論で述べられる様々な定理は、そのまま Haskell のプログラムにも適用される。

したがって、Haskell を使って、圏の性質を実験することができる。たとえば上の単位元律を使った合成射の縮約は次のように実験できる。

Prelude> let f = (*2)
Prelude> let g x = x + 1
Prelude> let h x = x - 1
Prelude> map f [1,2,3]
[2,4,6]
Prelude> map g [1,2,3]
[2,3,4]
Prelude> map h [2,3,4]
[1,2,3]
Prelude> map (h.g) [1,2,3]
[1,2,3]
Prelude> map (h. g. f) [1,2,3]
[2,4,6]
Prelude> map (id .f) [1,2,3]
[2,4,6]

理論的なものを実験で確かめる事ができれば、理論のイメージを作るのがずいぶん楽になる。
[PR]
by tnomura9 | 2013-07-26 03:09 | 圏論 | Comments(0)
<< 中国のバブル崩壊のタイミングと... All About Monad... >>