bitterharvest’s diary

A Bitter Harvestは小説の題名。作者は豪州のPeter Yeldham。苦闘の末に勝ちえた偏見からの解放は命との引換になったという悲しい物語

Haskellで学ぶ圏論・ウォームアップ編 仲間を求めて

1.血液型と性格

最近はあまり話題に上がることが少なくなったが、ちょっと前まで、血液型と性格が大いに関係しているということで、テレビの娯楽番組などでも取り上げられたことがある。番組では、几帳面な人はA型、二重人格の人はAB型、マイペースなタイプはB型、おおらかなタイプはO型などと、性格から血液型を想像し、当たったり外れたりを楽しんでいた。

また、交通事故と性格にはかなりの相関関係があるので、自分の適性を知っておく方がよいということで、自動車学校へ入校するときに性格(適性)検査を受けた人もいるのではないかと思う。しかし、人の性格は測りにくいので様々な実験やテストがいろいろな場面で使われている。そのため、複数の実験を受けた人は結果をどのような判断をしたらよいのか迷うことがある。

二つの種類の検査結果を得て同じなのかそうではないのかを判断するための圏論でのモデルはイコライザとコイコライザである。イコライザは二種類のテストをしたときに、二つの結果が一致している人だけ(人が同じであれば結果は同じでないといけないが、人が異なればお互いの結果は異なっていて良い)を選び出すものである。これに対して、コイコライザの方は、二つの結果が違っている場合には、それは同じ人が与えたのだから、その結果は言葉の表現は違うだけで本質的に同じものであると見なして、それらを一つにまとめ、同じ結果をもたらす人々のグループに類別しようとするものである。

これは、対象の積と対象の和を説明したときのケチ型とゴージャス型に似ている。対象の積と対象の和の可換図で、\(B_1 \times B_2\)と\(B_1 + B_2\)の位置を上の方に移動すると、下図のような図を得る。
f:id:bitterharvest:20150207103556p:plain

これらの図で対象を表す記号を変えて下図のようにする。
f:id:bitterharvest:20150207171337p:plain

イコライザは(二つの対象\(A,B\)とその間の二つの射\(f,g\)が存在したとき)二つの写像\(f \circ x\)と\(g \circ x\)に対して、対象\(B\)では\(f \circ x = g \circ x\)を成り立たせるような対象\(X\)の中で最大の対象\(E\)を探すことである(但し、\(x\)は対象\(X\)から\(A\)への射である)。二つの数の最大公約数が、二つの数の約数の中で最大のものを求めていたのと同じである。

例えば、下図のように、二つの対象\(A,B\)とその間の二つの射\(f,g\)が与えられたとする。
f:id:bitterharvest:20150207144025p:plain
この時、イコライザとなるように、対象\(X\)と射\(x\)を探すことにする。\(f \circ x = g \circ x\)を成り立たせるような対象\(X\)と射\(x\)を求めると下図のようになる。
f:id:bitterharvest:20150207144045p:plain
しかし、もっと大きな(要素数の多い)対象\(X\)が存在するので、さらに求め続けると以下のようになる。この時、\(X\)は\(E\)となる。
f:id:bitterharvest:20150207144054p:plain

コイコライザは(二つの対象\(A,B\)とその間の二つの射\(f,g\)が存在したとき)二つの写像\(y \circ f\)と\(y \circ g\)に対して、対象\(Y\)では\(y \circ f = y \circ g\)を成り立たせるような対象\(Y\)の中で最小の対象\(Q\)を探すことである(但し、\(y\)は対象\(B\)から\(Y\)への射である)。二つの数の最小公倍数が、二つの数の倍数の中で最小のものを求めていたのと同じである。

例えば、下図のように、二つの対象\(A,B\)とその間の二つの射\(f,g\)が与えられたとする。
f:id:bitterharvest:20150207145557p:plain
この時、コイコライザとなるように、対象\(Y\)と射\(y\)を探すことにする。\(y \circ f = y \circ g\)を成り立たせるような対象\(Y\)と射\(y\)を求めると下図のようになる。
f:id:bitterharvest:20150207150229p:plain
しかし、もっと小さな(要素数の少ない)対象\(Y\)が存在するので、さらに求め続けると以下のようになる。この時、\(Y\)は\(Q\)となる。
f:id:bitterharvest:20150207145747p:plain

2.イコライザの定義

イコライザのおおよそが分かったので、ここでは厳密な定義をしておく。

\(f,g: A \rightarrow\ B\)のイコライザとは、対象\(E\)と、\(f \circ e\)と\(g \circ e\)が成り立つ\(e:E \rightarrow\ A\)からなり、任意の\(f \circ x = g \circ x\)が成り立つ\(x: X \rightarrow\ A\)に対して、\(x = e \circ u\)を満たす\(u: X \rightarrow E\)が唯一つ存在するものである。\(e\)のことを単にイコライザともいう。

上記の定義の可換図は次の通りである。
f:id:bitterharvest:20150207172018p:plain

3.イコライザの応用例

イコライザから\(f = g\)を求めることができる。例えば、\(f(a) = a^2 + 4, \ g(a) = 5 \times a\)、ここで、\( a \in A, f(a), f(b) \in B\)とする。 この時、\(E = \{1,4\}\)である。\(X\)は \(\{ \}\),\(\{1\}\),\(\{4\}\)あるいは\(\{1,4\}\)である。

4.コイコライザの定義

コイコライザについても厳密な定義をしておく。

\(f,g: A \rightarrow\ B\)のコイコライザとは、対象\(Q\)と、\(q \circ f\)と\(q \circ g\)が成り立つ\(q: B \rightarrow\ Q\)からなり、任意の\(y \circ f = y \circ g\)が成り立つ\(y: B \rightarrow\ Y\)に対して、\(y = u' \circ q\)を満たす\(u': Q \rightarrow X\)が唯一つ存在するものである。\(q\)のことを単にコイコライザともいう。

上記の定義の可換図は次の通りである。
f:id:bitterharvest:20150207172033p:plain

5.コイコライザの応用

コイコライザは類別するので、ある数での剰余などを求めることができる。例えば、8進数は次のようにして求めることができる。\(f(a) = a, \ g(a) = a + 8\)、ここで、\( a \in A, f(a), f(b) \in B\)とする。この時、\(E = \{0,1,2,3,4,5,6,7\}\)となる。\(Y\)はこれらにその他の自然数を加えたものである。


イコライザとコイコライザをデータ型にすることはHaskellでは困難であるので、今回はHaskellのコードは無しとする。