Haskellで学ぶ圏論・入門編 写像を対象に

１．圏の定義

一般的に、圏は次のように定義されている。圏は５つの要素と二つの条件により構成される。５つの要素は次のようになっている。

(1) 対象
圏は対象を有する。対象は、通常は大文字を用いて、\(A,B,C,..\)と表す（対象は多くの場合何かの集まりである。例えば、集合などが対象になる。しかし、集合の要素はこの場合対象とはいわない）。

(2) 射
圏は対象（複数の場合も可）から対象（こちらも複数の場合可）へ移す射を有する。射は、通常小文字を用いて、\(f,g,h,..\)と表す（これまで習ってきた関数は射となるが、射となるのは関数だけではない。これから説明するモノイドの場合はこれまでの関数とは異なる）。

(3) ドメインとコドメイン
射の出発（入力）側の対象をドメインといい、到着（出力）側の対象をコドメインという。

(4) 恒等射
射は恒等射\(id\)を有する。恒等射は自分から自分へ移す射である。

(5) 合成
任意の二つの射に対して、合成\(\circ\)が可能である。二つの射を\(f,g\)とした時、その合成は\(g \circ f\)と表す。この時、\(f\)のコドメインと\(g\)のドメインは同一である。

二つの条件は次の通りである。
(1) 恒等射では単位律が成り立つ。これは、ある射のドメインで適応したとしても、その射のコドメインで適応したとしても、変化を与えない。\(f: A \rightarrow B\)を任意の射とし、対象\(A\)での恒等射を\(id_A\)とし、対象\(B\)での恒等射を\(id_B\)としたとき、\(f \circ id_A = f = id_B \circ f\)である。

(2) 射では結合律が成り立つ。即ち、合成できる三つの射\(f,g,h\)において、\((h \circ g) \circ f = h \circ (g \circ f)\)である。

２．集合圏

集合圏を表す時は、これまでは、要素の集まりである集合を対象に、集合間の写像を対象にしてきた。
例えば下図においては、

(1) 対象：\(A=\{a_1, a_2, a_3, a_4\}\), \(B=\{b_1, b_2, b_3\}\), \(C=\{c_1, c_2,\}\),
(2) 射：\(f_i\), \(g_j\), \(h_k\)
(3) ドメインとコドメイン：\(f_i : A \rightarrow B \), \(g_j : A \rightarrow C \), \(h_k : B \rightarrow C \)
(4) 恒等射：\(id_A\), \(id_B\), \(id_C\)
(5) 合成：\(f_i \circ h_k \)、（その他に射で定義されている写像と恒等射との間）
条件
(1) 単位律が成り立っている。
\begin{eqnarray}
f_i \circ id_A & = & id_B \circ f_i \\
g_j \circ id_A & = & id_C \circ g_j \\
h_k \circ id_B & = & id_C \circ h_k
\end{eqnarray}
(2) 結合律：\(f_i \circ h_k \)しかないので自明

今、集合\(A,B,C\)の要素数を2とした時の集合圏をHaskellで表現すると次のようになる。

data SetA = A1 | A2 deriving (Show, Eq)
data SetB = B1 | B2 deriving (Show, Eq)
data SetC = C1 | C2 deriving (Show, Eq)

f1 x
 | x == A1 = B1
 | x == A2 = B1
 | otherwise = error "not an element."
f2 x
 | x == A1 = B1
 | x == A2 = B2
 | otherwise = error "not an element."
f3 x
 | x == A1 = B2
 | x == A2 = B1
 | otherwise = error "not an element."
f4 x
 | x == A1 = B2
 | x == A2 = B2
 | otherwise = error "not an element."
g1 x
 | x == A1 = C1
 | x == A2 = C1
 | otherwise = error "not an element."
g2 x
 | x == A1 = C1
 | x == A2 = C2
 | otherwise = error "not an element."
g3 x
 | x == A1 = C2
 | x == A2 = C1
 | otherwise = error "not an element."
g4 x
 | x == A1 = C2
 | x == A2 = C2
 | otherwise = error "not an element."
h1 x
 | x == B1 = C1
 | x == B2 = C1
 | otherwise = error "not an element."
h2 x
 | x == B1 = C1
 | x == B2 = C2
 | otherwise = error "not an element."
h3 x
 | x == B1 = C2
 | x == B2 = C1
 | otherwise = error "not an element."
h4 x
 | x == B1 = C2
 | x == B2 = C2
 | otherwise = error "not an element."

３．写像を対象に

対象を集合としたときの欠点は、集合の内部が判明しないと圏の構造が分からない点にある。しかし、写像の集合を対象とすると、集合の外側にある写像から圏の構造が探れるようになる。例えると、太陽の内部構造を知ることなしに、太陽からの放射光や放射線によってその内部構造を探ることに似ている。

写像を対象ととらえると以下のような図が得られる。

ここでは、集合の圏は次のように表される。
(1) 対象：\( {\rm Hom}_{Sets} (A,B)\), \( {\rm Hom}_{Sets} (A,C)\)
(2) 射：\( \varphi_i \)
(3) ドメインとコドメイン：\( \varphi_i : {\rm Hom}_{Sets} (A,B) \rightarrow {\rm Hom}_{Sets} (A,C)\)
(4) 恒等射：\(id_{{\rm Hom}_{Sets} (A,B)} \), \(id_{{\rm Hom}_{Sets} (A,C)} \)
(5) 合成：（\( \varphi_i \)と恒等射の間）
条件
(1) 単位律が成り立っている。
\begin{eqnarray}
\varphi_i \circ id_{{\rm Hom}_{Sets} (A,B)} = id_{{\rm Hom}_{Sets} (A,C)} \circ \varphi_i
\end{eqnarray}
(2) 結合律：自明

それではいくつかの例を見ていく。写像を集合として扱うために、HaskellではMapというデータ型が用意されている。Mapというデータ型は、写像する側と写像する側の対を並べたリストから構成される。対はタプルで表現される。

写像の集合を対象として表した集合の圏をデータ型Morphで表す。Morphは、射\(\varphi\)を関数として有する。これをmorphとすると、以下のように定義できる。

module Mapsets where

import Data.Map (Map)
import qualified Data.Map as Map
import Data.Set (Set)
import qualified Data.Set as Set
class Morph f where
  morph :: Ord a => a -> f a b -> Maybe b
instance Morph Map where
  morph = Map.lookup 

上記のプログラムでは、Morphという型クラスを用意した後で、データ型MapをMorphのインスタンスとした。また、関数のmorphは、データ型Mapに用意されている関数lookupにより、写像する側の関数が与えられれば、写像する側の関数が得られるようにした。

具体的な例で示す。最初の例は、集合\(A,B,C\)の要素数が3, 2, 1の場合である。
下記のプログラムで、集合\(A,B,C\)は、setA, setB, setCである。また、setAからsetBへの写像の集合はhomABであり（各写像はf1, f2,..,f8)、setAからsetCへの写像の集合はhomACである（写像はg1の一つのみ)。また、homABからhomACへの射はphi1のみである。

module Mapsets where

import Data.Map (Map)
import qualified Data.Map as Map
import Data.Set (Set)
import qualified Data.Set as Set
class Morph f where
  morph :: Ord a => a -> f a b -> Maybe b
instance Morph Map where
  morph = Map.lookup 

data SetA = A1 | A2 | A3 deriving (Show, Eq, Ord)
data SetB = B1 | B2      deriving (Show, Eq, Ord)
data SetC = C1           deriving (Show, Eq, Ord)

setA = Set.fromList [A1, A2, A3]
setB = Set.fromList [B1, B2]
setC = Set.fromList [C1]
f1 = Map.fromList([(A1, B1), (A2, B1), (A2, B1)])
f2 = Map.fromList([(A1, B2), (A2, B1), (A2, B1)])
f3 = Map.fromList([(A1, B1), (A2, B2), (A2, B1)])
f4 = Map.fromList([(A1, B1), (A2, B1), (A2, B2)])
f5 = Map.fromList([(A1, B2), (A2, B2), (A2, B1)])
f6 = Map.fromList([(A1, B2), (A2, B1), (A2, B2)])
f7 = Map.fromList([(A1, B1), (A2, B2), (A2, B2)])
f8 = Map.fromList([(A1, B2), (A2, B2), (A2, B2)])
homAB = Set.fromList[f1,f2,f3,f4,f5,f6,f7,f8]

g1 = Map.fromList([(A1, C1), (A2, C1)])
homAC = Set.fromList[g1]

phi1  = Map.fromList([(f1, g1), (f2, g1),(f3, g1), (f4, g1), (f5, g1), (f6, g1),(f7, g1), (f8, g1)])

実行例を示す（予想通りの結果が得られていることが分かる）。

*Mapsets> setA
fromList [A1,A2,A3]
*Mapsets> setB
fromList [B1,B2]
*Mapsets> setC
fromList [C1]
*Mapsets> homAB
fromList [fromList [(A1,B1),(A2,B1)],fromList [(A1,B1),(A2,B2)],fromList [(A1,B2),(A2,B1)],fromList [(A1,B2),(A2,B2)]]
*Mapsets> homAC
fromList [fromList [(A1,C1),(A2,C1)]]
*Mapsets> morph f1 phi1
Just (fromList [(A1,C1),(A2,C1)])
*Mapsets> morph f2 phi1
Just (fromList [(A1,C1),(A2,C1)])
*Mapsets> morph f3 phi1
Just (fromList [(A1,C1),(A2,C1)])
*Mapsets> morph f4 phi1
Just (fromList [(A1,C1),(A2,C1)])
*Mapsets> morph f5 phi1
Just (fromList [(A1,C1),(A2,C1)])
*Mapsets> morph f6 phi1
Just (fromList [(A1,C1),(A2,C1)])
*Mapsets> morph f7 phi1
Just (fromList [(A1,C1),(A2,C1)])
*Mapsets> morph f8 phi1
Just (fromList [(A1,C1),(A2,C1)])

二番目の例は、集合\(A,B,C\)の要素数が3, 1, 2の場合である。下記のプログラムで、homABの要素はf1のみであり、homACの要素はg1, g2,..,g8である。これら写像の集合の間の射は、phi1, phi2である。

module Mapsets where

import Data.Map (Map)
import qualified Data.Map as Map
import Data.Set (Set)
import qualified Data.Set as Set
class Morph f where
  morph :: Ord a => a -> f a b -> Maybe b
instance Morph Map where
  morph = Map.lookup 

data SetA = A1 | A2 | A3 deriving (Show, Eq, Ord)
data SetB = B1           deriving (Show, Eq, Ord)
data SetC = C1 | C2      deriving (Show, Eq, Ord)

setA = Set.fromList [A1, A2, A3]
setB = Set.fromList [B1]
setC = Set.fromList [C1, C2]
f1 = Map.fromList([(A1, B1), (A2, B1), (A3, B1)])
homAB = Set.fromList[f1]

g1 = Map.fromList([(A1, C1), (A2, C1), (A2, C1)])
g2 = Map.fromList([(A1, C2), (A2, C1), (A2, C1)])
g3 = Map.fromList([(A1, C1), (A2, C2), (A2, C1)])
g4 = Map.fromList([(A1, C1), (A2, C1), (A2, C2)])
g5 = Map.fromList([(A1, C2), (A2, C2), (A2, C1)])
g6 = Map.fromList([(A1, C2), (A2, C1), (A2, C2)])
g7 = Map.fromList([(A1, C1), (A2, C2), (A2, C2)])
g8 = Map.fromList([(A1, C2), (A2, C2), (A2, C2)])
homAC = Set.fromList[g1,g2,g3,g4,g5,g6,g7,g8]

phi1  = Map.fromList([(f1, g1)])
phi2  = Map.fromList([(f1, g8)])

実行例を示す。

*Mapsets> morph f1 phi1
Just (fromList [(A1,C1),(A2,C1)])
*Mapsets> morph f1 phi2
Just (fromList [(A1,C2),(A2,C2)])

三番目の例は、集合\(A,B,C\)の要素数が2, 2, 2の場合である。下記のプログラムで、homABの要素はf1, f2, f3, f4であり、homACの要素はg1, g2, g3, g4である。（f1, f2は、一つの点に写像しているので、これの写像先はg1, g4しかないことに注意して射を考えると）これら写像の集合の間の射は、phi1, phi2,..,phi64である。

module Mapsets where

import Data.Map (Map)
import qualified Data.Map as Map
import Data.Set (Set)
import qualified Data.Set as Set
class Morph f where
  morph :: Ord a => a -> f a b -> Maybe b
instance Morph Map where
  morph = Map.lookup 

data SetA = A1 | A2 deriving (Show, Eq, Ord)
data SetB = B1 | B2 deriving (Show, Eq, Ord)
data SetC = C1 | C2 deriving (Show, Eq, Ord)

setA = Set.fromList [A1, A2]
setB = Set.fromList [B1, B2]
setC = Set.fromList [C1, C2]
f1 = Map.fromList([(A1, B1), (A2, B1)])
f2 = Map.fromList([(A1, B2), (A2, B1)])
f3 = Map.fromList([(A1, B1), (A2, B2)])
f4 = Map.fromList([(A1, B2), (A2, B2)])
homAB = Set.fromList[f1,f2,f3,f4]

g1 = Map.fromList([(A1, C1), (A2, C1)])
g2 = Map.fromList([(A1, C2), (A2, C1)])
g3 = Map.fromList([(A1, C1), (A2, C2)])
g4 = Map.fromList([(A1, C2), (A2, C2)])
homAC = Set.fromList[g1,g2,g3,g4]

phi1  = Map.fromList([(f1, g1), (f2, g1), (f3, g1), (f4, g1)])
phi2  = Map.fromList([(f1, g1), (f2, g2), (f3, g1), (f4, g1)])
phi3  = Map.fromList([(f1, g1), (f2, g3), (f3, g1), (f4, g1)])
phi4  = Map.fromList([(f1, g1), (f2, g4), (f3, g1), (f4, g1)])
phi5  = Map.fromList([(f1, g1), (f2, g1), (f3, g2), (f4, g1)])
phi6  = Map.fromList([(f1, g1), (f2, g2), (f3, g2), (f4, g1)])
phi7  = Map.fromList([(f1, g1), (f2, g3), (f3, g2), (f4, g1)])
phi8  = Map.fromList([(f1, g1), (f2, g4), (f3, g2), (f4, g1)])
phi9  = Map.fromList([(f1, g1), (f2, g1), (f3, g3), (f4, g1)])
phi10 = Map.fromList([(f1, g1), (f2, g2), (f3, g3), (f4, g1)])
phi11 = Map.fromList([(f1, g1), (f2, g3), (f3, g3), (f4, g1)])
phi12 = Map.fromList([(f1, g1), (f2, g4), (f3, g3), (f4, g1)])
phi13 = Map.fromList([(f1, g1), (f2, g1), (f3, g4), (f4, g1)])
phi14 = Map.fromList([(f1, g1), (f2, g2), (f3, g4), (f4, g1)])
phi15 = Map.fromList([(f1, g1), (f2, g3), (f3, g4), (f4, g1)])
phi16 = Map.fromList([(f1, g1), (f2, g4), (f3, g4), (f4, g1)])
phi17 = Map.fromList([(f1, g1), (f2, g1), (f3, g1), (f4, g4)])
phi18 = Map.fromList([(f1, g1), (f2, g2), (f3, g1), (f4, g4)])
phi19 = Map.fromList([(f1, g1), (f2, g3), (f3, g1), (f4, g4)])
phi20 = Map.fromList([(f1, g1), (f2, g4), (f3, g1), (f4, g4)])
phi21 = Map.fromList([(f1, g1), (f2, g1), (f3, g2), (f4, g4)])
phi22 = Map.fromList([(f1, g1), (f2, g2), (f3, g2), (f4, g4)])
phi23 = Map.fromList([(f1, g1), (f2, g3), (f3, g2), (f4, g4)])
phi24 = Map.fromList([(f1, g1), (f2, g4), (f3, g2), (f4, g4)])
phi25 = Map.fromList([(f1, g1), (f2, g1), (f3, g3), (f4, g4)])
phi26 = Map.fromList([(f1, g1), (f2, g2), (f3, g3), (f4, g4)])
phi27 = Map.fromList([(f1, g1), (f2, g3), (f3, g3), (f4, g4)])
phi28 = Map.fromList([(f1, g1), (f2, g4), (f3, g3), (f4, g4)])
phi29 = Map.fromList([(f1, g1), (f2, g1), (f3, g4), (f4, g4)])
phi30 = Map.fromList([(f1, g1), (f2, g2), (f3, g4), (f4, g4)])
phi31 = Map.fromList([(f1, g1), (f2, g3), (f3, g4), (f4, g4)])
phi32 = Map.fromList([(f1, g1), (f2, g4), (f3, g4), (f4, g4)])
phi33 = Map.fromList([(f1, g4), (f2, g1), (f3, g1), (f4, g1)])
phi34 = Map.fromList([(f1, g4), (f2, g2), (f3, g1), (f4, g1)])
phi35 = Map.fromList([(f1, g4), (f2, g3), (f3, g1), (f4, g1)])
phi36 = Map.fromList([(f1, g4), (f2, g4), (f3, g1), (f4, g1)])
phi37 = Map.fromList([(f1, g4), (f2, g1), (f3, g2), (f4, g1)])
phi38 = Map.fromList([(f1, g4), (f2, g2), (f3, g2), (f4, g1)])
phi39 = Map.fromList([(f1, g4), (f2, g3), (f3, g2), (f4, g1)])
phi40 = Map.fromList([(f1, g4), (f2, g4), (f3, g2), (f4, g1)])
phi41 = Map.fromList([(f1, g4), (f2, g1), (f3, g3), (f4, g1)])
phi42 = Map.fromList([(f1, g4), (f2, g2), (f3, g3), (f4, g1)])
phi43 = Map.fromList([(f1, g4), (f2, g3), (f3, g3), (f4, g1)])
phi44 = Map.fromList([(f1, g4), (f2, g4), (f3, g3), (f4, g1)])
phi45 = Map.fromList([(f1, g4), (f2, g1), (f3, g4), (f4, g1)])
phi46 = Map.fromList([(f1, g4), (f2, g2), (f3, g4), (f4, g1)])
phi47 = Map.fromList([(f1, g4), (f2, g3), (f3, g4), (f4, g1)])
phi48 = Map.fromList([(f1, g4), (f2, g4), (f3, g4), (f4, g1)])
phi49 = Map.fromList([(f1, g4), (f2, g1), (f3, g1), (f4, g4)])
phi50 = Map.fromList([(f1, g4), (f2, g2), (f3, g1), (f4, g4)])
phi51 = Map.fromList([(f1, g4), (f2, g3), (f3, g1), (f4, g4)])
phi52 = Map.fromList([(f1, g4), (f2, g4), (f3, g1), (f4, g4)])
phi53 = Map.fromList([(f1, g4), (f2, g1), (f3, g2), (f4, g4)])
phi54 = Map.fromList([(f1, g4), (f2, g2), (f3, g2), (f4, g4)])
phi55 = Map.fromList([(f1, g4), (f2, g3), (f3, g2), (f4, g4)])
phi56 = Map.fromList([(f1, g4), (f2, g4), (f3, g2), (f4, g4)])
phi57 = Map.fromList([(f1, g4), (f2, g1), (f3, g3), (f4, g4)])
phi58 = Map.fromList([(f1, g4), (f2, g2), (f3, g3), (f4, g4)])
phi59 = Map.fromList([(f1, g4), (f2, g3), (f3, g3), (f4, g4)])
phi60 = Map.fromList([(f1, g4), (f2, g4), (f3, g3), (f4, g4)])
phi61 = Map.fromList([(f1, g4), (f2, g1), (f3, g4), (f4, g4)])
phi62 = Map.fromList([(f1, g4), (f2, g2), (f3, g4), (f4, g4)])
phi63 = Map.fromList([(f1, g4), (f2, g3), (f3, g4), (f4, g4)])
phi64 = Map.fromList([(f1, g4), (f2, g4), (f3, g4), (f4, g4)])