bitterharvest’s diary

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

Haskellで学ぶ圏論・ウォームアップ編 写像のまとめ

1.全射単射

圏論では写像は重要な概念である。簡単な圏では写像は射となるが、圏をさらに抽象化すると、写像は対象として扱われる。そこで、ここでは、写像に関する重要な性質をまとめる。

全射写像\(f:X \rightarrow Y\)とした時、\(Y\)の任意の要素\(y \in Y\)に対して、\(y=f(x)\)とするような\(x\)が存在するとき、\(f\)は全射であるという。
下図は全射の例である。
f:id:bitterharvest:20150309141723p:plain

単射の定義:写像\(f:X \rightarrow Y\)とした時、任意の\(x,x' \in X\)に対して、\(x \neq x'\)であるとき、\(f(x) \neq f(x')\)であるならば、\(f\)は単射であるという。
下図は単射の例である。
f:id:bitterharvest:20150309142225p:plain

全単射の定義:写像\(f:X \rightarrow Y\)が全射でありかつ単射である時、\(f\)は全単射であるという。この時、写像\(f^{-1}:Y \rightarrow X\)が存在する。\(f\)が全単射の時、\(X\)と\(Y\)は同型であるという。
下図は全単射の例である。
f:id:bitterharvest:20150309142623p:plain

2.セクションとリトラクション

集合\(A\)から集合\(B\)を経由して集合\(A\)に戻る二つの写像\(s: A \rightarrow B\), \(r: B \rightarrow A\)を考え、この二つの写像は\(r \circ s = 1_A\)を満足するものとする(下図参照)。
f:id:bitterharvest:20150309144442p:plain

この時、\(r\)は全射となり、\(s\)は単射となる。
このことから、\(B\)の要素数は\(A\)のそれを下回ることはない。
\(B\)の要素数と\(A\)のそれとが同数の時は、\(A\)と\(B\)は同型である。
\(B\)の要素数が\(A\)のそれを上回るときは、\(r\)は単射にはならない。また、\(s\)は全射にはならない。この時、\(r\)によって、\(B\)の複数の要素が\(A\)の一つの要素に写像されることになる(後退させられる)ので、\(r\)をリトラクションという。また、\(f\)によって、\(B\)の複数の要素の中から\(A\)の一つの要素に写像されるものが選ばれる(区切られる)ので、\(s\)をセクションという。

また、\(e=r \circ f\)とすると、\(e=e \circ e\)となるので、\(r \circ f\)は冪等性を有する。

3.モノ射とエピ射

セクションとリトラクションと一般化したのが、モノ射とエピ射である。
モノ射の定義:\(m: A \rightarrow B\)がモノ射であるとは、任意の対象\(X\)と任意の射\(f,g: X \rightarrow A\)に対して、\(m \circ f = m \circ g\)ならば、\(f = g\)が成り立つことである(下図参照)。
f:id:bitterharvest:20150310090224p:plain

集合の圏ならば、モノ射は単射である(モノ射であれば単射となること、単射であればモノ射であることを証明する)。

モノ射の例を下図に挙げる。
f:id:bitterharvest:20150310093823p:plain
この射は、円盤を三角柱の上端に写像したものである。

エピ射の定義:\(e: A \rightarrow B\)がエピ射であるとは、任意の対象\(X\)と任意の射\(f,g: B \rightarrow X\)に対して、\(f \circ e = g \circ e\)ならば、\(f = g\)が成り立つことである(下図参照)。
f:id:bitterharvest:20150310101723p:plain
集合の圏ならば、エピ射は全射である

エピ射の例を下図に挙げる。
f:id:bitterharvest:20150310102015p:plain
この射は、三角柱の年輪を円盤に写像したものである。

4.イコライザとコイコライザ

モノ射、エピ射を応用したものに、コイコライザ、イコライザがあるが、これについては、前の記事できしたがここでは簡単にまとめておく。

イコライザの定義:\(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

イコライザの圏は次のようになっている。
(1) 対象:\(A\),\(B\),\(E\),\(X\)
(2) 射:\(f,g: A \rightarrow\ B\),\(e:E \rightarrow\ A\),\(u: X \rightarrow E\)

コイコライザの定義:\(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

コライザの圏は次のようになっている。
(1) 対象:\(A\),\(B\),\(Q\),\(X\)
(2) 射:\(f,g: A \rightarrow\ B\),\(q: B \rightarrow\ Q\),\(u': Q \rightarrow X\)

5.写像の集合

集合\(A\)から\(B\)への写像の集まりがいくつあるかを考える。
今、\(A\), \(B\)のそれぞれの要素数を\(m\), \(n\)とする。

最初に\(A\)の数を制限したときの写像の数を求める。
\(m=0\)のとき、下図に示すように、写像の数は、空写像の1個である。
この時の圏は次のようになる。
(1)対象:\(A=\{a_1 \}\), \(B=\{ b_1, b_2,.., b_n \}\)
(2)射:空集合\(f:A \rightarrow B\)
f:id:bitterharvest:20150311052352p:plain

\(m=1\)のとき、下図に示すように、写像の数は、\(f_i:A \rightarrow B\) (ここで、\(i=1..n\)である)の\(n\)個である。集合\(A\)から集合\(B\)への写像の集合を\({\rm Hom}(A,B)\)とすると、\({\rm Hom}(A,B)\)と\(B\)は同型である。
(1)対象:\(A=\{a_1 \}\), \(B=\{ b_1, b_2,.., b_n \}\)
(2)射:\(f_i:A=\{ a_1\} \rightarrow B=\{b_1,.., b_i,.., b_n \}\)
f:id:bitterharvest:20150311053118p:plain
以下にHaskellでの例を示す。

data SetA = A1 deriving (Show, Eq)
data SetB = B1 | B2 | B3 | B4 deriving (Show, Eq)
f1 x
 | x == A1 = B1
 | otherwise = error "not an element of setA."
f2 x
 | x == A1 = B2
 | otherwise = error "not an element of setA."
f3 x
 | x == A1 = B3
 | otherwise = error "not an element of setA."
f4 x
 | x == A1 = B4
 | otherwise = error "not an element of setA."

\(m=2\)のとき、下図に示すように、写像の数は、\(f_{i,j}\) (ここで、\(i,j=1..n_B\))の\( n^ 2\)個である。これは、\({\rm Hom}(A,B)\)と\(B \times B\)は同型と見なすことができる。
(1)対象:\(A=\{ a_1,a_2 \}\), \(B=\{ b_1, b_2,.., b_n \}\)
(2)射:\(f_{i,j}:A =\{ a_1,a_2\} \rightarrow B =\{ b_1,..,b_i, b_j,.., b_n \}\)
f:id:bitterharvest:20150311054554p:plain
以下にHaskellでの例を示す。

data SetA = A1 deriving (Show, Eq)
data SetB = B1 | B2 | B3 | B4 deriving (Show, Eq)
data SetA = A1 | A2 deriving (Show, Eq)
data SetB = B1 | B2 | B3 | B4 deriving (Show, Eq)

f1 x
 | x == A1 = B1
 | x == A2 = B1
 | otherwise = error "not an element of setA."
f2 x
 | x == A1 = B1
 | x == A2 = B2
 | otherwise = error "not an element of setA."
f3 x
 | x == A1 = B1
 | x == A2 = B3
 | otherwise = error "not an element of setA."
f4 x
 | x == A1 = B1
 | x == A2 = B4
 | otherwise = error "not an element of setA."
f5 x
 | x == A1 = B2
 | x == A2 = B1
 | otherwise = error "not an element of setA."
f6 x
 | x == A1 = B2
 | x == A2 = B2
 | otherwise = error "not an element of setA."
f7 x
 | x == A1 = B2
 | x == A2 = B3
 | otherwise = error "not an element of setA."
f8 x
 | x == A1 = B2
 | x == A2 = B4
 | otherwise = error "not an element of setA."
f9 x
 | x == A1 = B3
 | x == A2 = B1
 | otherwise = error "not an element of setA."
f10 x
 | x == A1 = B3
 | x == A2 = B2
 | otherwise = error "not an element of setA."
f11 x
 | x == A1 = B3
 | x == A2 = B3
 | otherwise = error "not an element of setA."
f12 x
 | x == A1 = B3
 | x == A2 = B4
 | otherwise = error "not an element of setA."
f13 x
 | x == A1 = B4
 | x == A2 = B1
 | otherwise = error "not an element of setA."
f14 x
 | x == A1 = B4
 | x == A2 = B2
 | otherwise = error "not an element of setA."
f15 x
 | x == A1 = B4
 | x == A2 = B3
 | otherwise = error "not an element of setA."
f16 x
 | x == A1 = B4
 | x == A2 = B4
 | otherwise = error "not an element of setA."

\(m=3\)のとき、下図に示すように、写像の数は、\(f_{i,j,k}\) (ここで、\(i,j,k=1..n\))の\( n^ 3\)個である。これは、\({\rm Hom}(A,B)\)と\(B \times B \times B\)は同型と見なすことができる。
(1)対象:\(A=\{a_1,a_2,a_3\}\), \(B=\{ b_1, b_2,.., b_n \}\)
(2)射:\(f_{i,j,k}:A =\{ a_1,a_2,a_3\} \rightarrow B=\{b_1,.., b_i, b_j,b_k,.., b_n \}\)
f:id:bitterharvest:20150311054617p:plain

次は\(B\)の数を制限したときの写像の数を求める。
\(n=0\)のとき、写像の数は0個である。
(1)対象:\(A=\{a_1, a_2,.., a_m\}\), \(B=\{ \}\)
(2)射:なし

\(n=1\)のとき、下図に示すように、写像の数は、\(f\) の\(1\)個である。
(1)対象:\(A=\{a_1, a_2,.., a_m\}\), \(B=\{ b_1 \}\)
(2)射:\(f:A =\{a_1, a_2,.., a_m\} \rightarrow B=\{b_1 \}\)
f:id:bitterharvest:20150311063437p:plain

以下にHaskellでの例を示す。

data SetA = A1 | A2 | A3 | A4 deriving (Show, Eq)
data SetB = B1 deriving (Show, Eq)
f x
 | x == A1 = B1
 | x == A2 = B1
 | x == A3 = B1
 | x == A4 = B1
 | otherwise = error "not an element of setA." 

\(n=2\)のとき、下図に示すように、写像の数は\(B\)の部分集合の総数である。
(1)対象:\(A=\{a_1, a_2,.., a_m\}\), \(B=\{ b_1,b_2 \}\)
(2)射:\(f_{A' \in \mathcal{P}(A)}:A =\{A',A-A'\} \rightarrow B=\{b_1,b_2 \}\)
上記で\(\mathcal{P}(A)\)は\(A\)の冪集合(部分集合の集まり)である。
f:id:bitterharvest:20150311064028p:plain
以下にHaskellでの例を示す。

data SetA = A1 | A2 | A3 | A4 deriving (Show, Eq)
data SetB = B1 | B2 deriving (Show, Eq)
f1 x
 | x == A1 = B1
 | x == A2 = B1
 | x == A3 = B1
 | x == A4 = B1
 | otherwise = error "not an element of setA." 
f2 x
 | x == A1 = B2
 | x == A2 = B1
 | x == A3 = B1
 | x == A4 = B1
 | otherwise = error "not an element of setA." 
f3 x
 | x == A1 = B1
 | x == A2 = B2
 | x == A3 = B1
 | x == A4 = B1
 | otherwise = error "not an element of setA." 
f4 x
 | x == A1 = B1
 | x == A2 = B1
 | x == A3 = B2
 | x == A4 = B1
 | otherwise = error "not an element of setA." 
f5 x
 | x == A1 = B1
 | x == A2 = B1
 | x == A3 = B1
 | x == A4 = B2
 | otherwise = error "not an element of setA." 
f6 x
 | x == A1 = B2
 | x == A2 = B2
 | x == A3 = B1
 | x == A4 = B1
 | otherwise = error "not an element of setA." 
f7 x
 | x == A1 = B2
 | x == A2 = B1
 | x == A3 = B2
 | x == A4 = B1
 | otherwise = error "not an element of setA." 
f8 x
 | x == A1 = B2
 | x == A2 = B1
 | x == A3 = B1
 | x == A4 = B2
 | otherwise = error "not an element of setA." 
f9 x
 | x == A1 = B1
 | x == A2 = B2
 | x == A3 = B2
 | x == A4 = B1
 | otherwise = error "not an element of setA." 
f10 x
 | x == A1 = B1
 | x == A2 = B2
 | x == A3 = B1
 | x == A4 = B2
 | otherwise = error "not an element of setA." 
f11 x
 | x == A1 = B1
 | x == A2 = B1
 | x == A3 = B2
 | x == A4 = B2
 | otherwise = error "not an element of setA." 
f12 x
 | x == A1 = B2
 | x == A2 = B2
 | x == A3 = B2
 | x == A4 = B1
 | otherwise = error "not an element of setA." 
f13 x
 | x == A1 = B2
 | x == A2 = B2
 | x == A3 = B1
 | x == A4 = B2
 | otherwise = error "not an element of setA." 
f14 x
 | x == A1 = B2
 | x == A2 = B1
 | x == A3 = B2
 | x == A4 = B2
 | otherwise = error "not an element of setA." 
f15 x
 | x == A1 = B1
 | x == A2 = B2
 | x == A3 = B2
 | x == A4 = B2
 | otherwise = error "not an element of setA." 
f16 x
 | x == A1 = B2
 | x == A2 = B2
 | x == A3 = B2
 | x == A4 = B2
 | otherwise = error "not an element of setA."  

以上を一般化すると、集合\(A\)から集合\(B\)写像の数は、それぞれの要素数を\(m,n\)とした時、\( n ^ m\)個となる。また、\({\rm Hom}(A,B)\)と\(m\)次元の\(B \times B \times,..., \times B\)は同型と見なすことができる。

6.カリー化

集合の積\(X \times A\)から集合\(B\)への可能な写像を図で示すと下図のようになる。
f:id:bitterharvest:20150312100329p:plain
この時、\(X\), \(A\), \(B\)の要素数を\(p\), \(m\), \(n\)とすると、写像の総数は\(n^{pm}\)である。

いま、集合\(A\)から\(B\)への写像の集まりを\(B^A\)で表す(即ち、\({\rm Hom}(A,B)=B^A\)とする)。

集合の積\(X \times A\)から集合\(B\)への写像をカリー化して、集合\(X\)から写像の集まり\(B^A\)への写像を図で表すと下図のようになる。
f:id:bitterharvest:20150312100356p:plain
この時\(g_i:X \rightarrow B^A\)の写像の数は\(n^{pm}\)となる。

二つの写像\({\rm Hom}(X \times A ,B)\)と\({\rm Hom}(X,B^A)\)とは同型であることが分かる。これを利用すると、下図の互換図を得る(なお図で\(e\)は評価関数と呼べれる)。
f:id:bitterharvest:20150311094335p:plain

Haskellでの例を挙げる。

data SetX = X1 | X2 deriving (Show, Eq)
data SetA = A1 | A2 deriving (Show, Eq)
data SetB = B1 | B2 deriving (Show, Eq)

f1 x a
 | x == X1 && a == A1 = B1
 | x == X1 && a == A2 = B1
 | x == X2 && a == A1 = B1
 | x == X2 && a == A2 = B1
 | otherwise = error "not elements."
f2 x a
 | x == X1 && a == A1 = B2
 | x == X1 && a == A2 = B1
 | x == X2 && a == A1 = B1
 | x == X2 && a == A2 = B1
 | otherwise = error "not elements."
f3 x a
 | x == X1 && a == A1 = B1
 | x == X1 && a == A2 = B2
 | x == X2 && a == A1 = B1
 | x == X2 && a == A2 = B1
 | otherwise = error "not elements."
f4 x a
 | x == X1 && a == A1 = B1
 | x == X1 && a == A2 = B1
 | x == X2 && a == A1 = B2
 | x == X2 && a == A2 = B1
 | otherwise = error "not elements."
f5 x a
 | x == X1 && a == A1 = B1
 | x == X1 && a == A2 = B1
 | x == X2 && a == A1 = B1
 | x == X2 && a == A2 = B2
 | otherwise = error "not elements."
f6 x a
 | x == X1 && a == A1 = B2
 | x == X1 && a == A2 = B2
 | x == X2 && a == A1 = B1
 | x == X2 && a == A2 = B1
 | otherwise = error "not elements."
f7 x a
 | x == X1 && a == A1 = B2
 | x == X1 && a == A2 = B1
 | x == X2 && a == A1 = B2
 | x == X2 && a == A2 = B1
 | otherwise = error "not elements."
f8 x a
 | x == X1 && a == A1 = B2
 | x == X1 && a == A2 = B1
 | x == X2 && a == A1 = B1
 | x == X2 && a == A2 = B2
 | otherwise = error "not elements."
f9 x a
 | x == X1 && a == A1 = B1
 | x == X1 && a == A2 = B2
 | x == X2 && a == A1 = B2
 | x == X2 && a == A2 = B1
 | otherwise = error "not elements."
f10 x a
 | x == X1 && a == A1 = B1
 | x == X1 && a == A2 = B2
 | x == X2 && a == A1 = B1
 | x == X2 && a == A2 = B2
 | otherwise = error "not elements."
f11 x a
 | x == X1 && a == A1 = B1
 | x == X1 && a == A2 = B1
 | x == X2 && a == A1 = B2
 | x == X2 && a == A2 = B2
 | otherwise = error "not elements."
f12 x a
 | x == X1 && a == A1 = B2
 | x == X1 && a == A2 = B2
 | x == X2 && a == A1 = B2
 | x == X2 && a == A2 = B1
 | otherwise = error "not elements."
f13 x a
 | x == X1 && a == A1 = B2
 | x == X1 && a == A2 = B2
 | x == X2 && a == A1 = B1
 | x == X2 && a == A2 = B2
 | otherwise = error "not elements."
f14 x a
 | x == X1 && a == A1 = B2
 | x == X1 && a == A2 = B1
 | x == X2 && a == A1 = B2
 | x == X2 && a == A2 = B2
 | otherwise = error "not elements."
f15 x a
 | x == X1 && a == A1 = B1
 | x == X1 && a == A2 = B2
 | x == X2 && a == A1 = B2
 | x == X2 && a == A2 = B2
 | otherwise = error "not elements."
f16 x a
 | x == X1 && a == A1 = B2
 | x == X1 && a == A2 = B2
 | x == X2 && a == A1 = B2
 | x == X2 && a == A2 = B2
 | otherwise = error "not elements."


g1 x
 | x == X1 = \a -> f1 X1 a
 | x == X2 = \a -> f1 X2 a
 | otherwise = error "not an element."
g2 x
 | x == X1 = \a -> f2 X1 a
 | x == X2 = \a -> f2 X2 a
 | otherwise = error "not an element."
g3 x
 | x == X1 = \a -> f3 X1 a
 | x == X2 = \a -> f3 X2 a
 | otherwise = error "not an element."
g4 x
 | x == X1 = \a -> f4 X1 a
 | x == X2 = \a -> f4 X2 a
 | otherwise = error "not an element."
g5 x
 | x == X1 = \a -> f5 X1 a
 | x == X2 = \a -> f5 X2 a
 | otherwise = error "not an element."
g6 x
 | x == X1 = \a -> f6 X1 a
 | x == X2 = \a -> f6 X2 a
 | otherwise = error "not an element."
g7 x
 | x == X1 = \a -> f7 X1 a
 | x == X2 = \a -> f7 X2 a
 | otherwise = error "not an element."
g8 x
 | x == X1 = \a -> f8 X1 a
 | x == X2 = \a -> f8 X2 a
 | otherwise = error "not an element."
g9 x
 | x == X1 = \a -> f9 X1 a
 | x == X2 = \a -> f9 X2 a
 | otherwise = error "not an element."
g10 x
 | x == X1 = \a -> f10 X1 a
 | x == X2 = \a -> f10 X2 a
 | otherwise = error "not an element."
g11 x
 | x == X1 = \a -> f11 X1 a
 | x == X2 = \a -> f11 X2 a
 | otherwise = error "not an element."
g12 x
 | x == X1 = \a -> f12 X1 a
 | x == X2 = \a -> f12 X2 a
 | otherwise = error "not an element."
g13 x
 | x == X1 = \a -> f13 X1 a
 | x == X2 = \a -> f13 X2 a
 | otherwise = error "not an element."
g14 x
 | x == X1 = \a -> f14 X1 a
 | x == X2 = \a -> f14 X2 a
 | otherwise = error "not an element."
g15 x
 | x == X1 = \a -> f15 X1 a
 | x == X2 = \a -> f15 X2 a
 | otherwise = error "not an element."
g16 x
 | x == X1 = \a -> f16 X1 a
 | x == X2 = \a -> f16 X2 a
 | otherwise = error "not an element."

実行結果を示す。

*Morphism> (g1 X1) A1
B1
*Morphism> (g1 X1) A2
B1
*Morphism> (g1 X2) A1
B1
*Morphism> (g1 X2) A2
B1
*Morphism> (g2 X1) A1
B2
*Morphism> (g2 X1) A2
B1
*Morphism> (g2 X2) A1
B1
*Morphism> (g2 X2) A2
B1


\(({\rm Hom} (X \times A \times B,C)\)をカリー化するときに、二つの方法がある。
一つは、\(A \times B\)を一つの集合と考え、\({\rm Hom} (X, C ^ {A \times B})\)とする。
もう一つは、\(X \times A\)を一つの集合と考え、\({\rm Hom} (X \times A , C ^ B)\)とする。その後、さらにカーリー化すると、\({\rm Hom} (X , (C ^ B)^A)\)となる。
\({\rm Hom} (X, C ^ {A \times B})\)と\({\rm Hom} (X , (C ^ B)^A)\)は同型なので、\(C ^ {A \times B}=(C ^ B)^A\)となる。