圏論的二項関係の合成

概要

• 本稿では、圏論的二項関係の合成の定義を紹介する。

• 圏論的に二項関係の合成を定義する上で、柱体化(cylindrification)という操作が重要になる。柱体化とは積の射影で逆像を取る操作であり、二項関係$R \subseteq A \times B$を三項関係$R \times C \subseteq A \times B \times C$へと自明に拡張する。$R \subseteq A \times B,S \subseteq B \times C$が与えられているならば、柱体化を駆使して、$R \times C \cap A \times S \subseteq A \times B \times C$を取ることによって、二項関係の合成のベースを作ろうという魂胆である。

• 一方で、圏論的な二項関係とは2-table、則ちjointly monic spanによって表示されるものと定義したのだった。jointly monic spanで二項関係を表示すると、柱体化のintersectionを取る操作をグッと楽に構成する方法があることを最後に提示する。

1 柱体(cylinder)

1.1 平面を立体にする自明な方法

平面図形を立体図形にする最も自明な方法はなんだろうか？有力な方法の一つは、垂直方向に無限に引き伸ばしていくことである。
無限に延びる円筒

この操作を平面図形の柱体化と呼ぶことにする。

1.2 射影写像による引き戻し(逆像)

全単射$\mathbb R \times \mathbb R \times \{0\} \leftrightarrow \mathbb R \times \mathbb R,\ (x,y,0) \leftrightarrow (x,y)$により、座標空間中の$xy$平面を、二次元平面としての$xy$座標平面と同一視する。$xy$平面上の図形の柱体化は、$\mathbb R^2$の部分集合から$\mathbb R^3$の部分集合を作る操作である。単位円及びその内部の例で具体的に考えてみよう。

$xy$平面上で単位円及びその内部が成す平面図形$C$は、$C = \{(x,y) \in \mathbb R^2 \mid x^2 + y^2 \leq 1\}$のように書ける。では、$C$を柱体化した立体($V$とする)はどのように書かれるか？簡単である。$V$は$C$の上下無限遠まで延びているから、$z$方向の値は$\mathbb R$の元であれば何でも良い。よって$V$は、次のように表示される。

$$ V = \{ (x,y,z) \in \mathbb R^3 \mid x^2 + y^2 \leq 1 \} $$

この$V$は、次を満たす。

$$ V = \{ (x,y,z) \in \mathbb R^3 \mid \langle \pi_x,\pi_y \rangle(x,y,z) \in C \} = \langle \pi_x,\pi_y\rangle^{-1}C $$

則ち、$C$の柱体化$V$とは、積の射影写像$\langle \pi_x,\pi_y \rangle$による$C$の逆像である。
積の射影の逆像

2 部分対象の柱体化(cylindrification)

二項積と引き戻しを持つ圏で考える。対象$A,B$上の二項関係$R$とは、$A,B$上の2-tableの同型類、則ち$A,B$を足に持つjointly monic spanの同型類のことを言った。二項積を持つ圏では、これは$A \times B$の部分対象と自然に同一視できる。(積の普遍性が同一視を与える。)
2-tableとmonic

さて、二項積と引き戻しを持つ圏では、次が成り立つ。

comonadより、二項積と引き戻しを持つ圏では、部分対象の柱体化を二項積の表示に従属させて次のように定義できる。

なお、二項積の順序を入れ替えても同様に引き戻しを得られる。

3 圏論的二項関係の合成

3.1 集合論の二項関係の合成

集合論では、二項関係のグラフ$R\subseteq A \times B,S \subseteq B \times C$に対し、二項関係の合成のグラフ$S \circ R$が次で定義できた。

$$ S \circ R = \{ (a,c) \in A \times C \mid \exists b . Rab \land Sbc \} $$

ただし$Rab,Sbc$は、$(a,b) \in R,(b,c) \in S$の別表記である。前回の記事の内容でも見た通り、$S \circ R$は、集合$T \overset{\mathrm{def}}{=}\{(a,b,c) \in A \times B \times C \mid Rab \land Sbc\}$を積の射影写像$\langle \pi_A,\pi_C \rangle \colon A \times B \times C \to A \times C$によって順像を取ったものに等しい。

3.2 圏論的二項関係の合成

前回の記事で、積の射影で順像を取る操作が、射影で消える対象と対応する自由変数で存在量化を取ることと対応する話をした。

順像と存在量化∃

圏論では対象の元を取れるとは限らないが、二項積と順像を持つ圏ならば、二項関係の合成に必要な存在量化を積の射影の順像で表示することができる。よって、圏論的二項関係$R \in \mathrm{Rel}(A,B),S \in \mathrm{Rel}(B,C)$でも、集合論の二項関係の合成と同様、適切な$T \in \mathrm{Sub}(A\times B\times C)$を構成できさえすれば、あとは積の射影$\langle \pi_A,\pi_C \rangle$の順像を取ることによって、$R,S$を合成した関係を得ることができる。この節では、この$T$を$S,R$から構成する方法を見ていく。

二項積、引き戻しと像を持つ圏で考える。対象$A,B$上の二項関係$R$と、対象$B,C$上の二項関係$S$が与えられたとする。$R,S$はそれぞれ$A \times B,B \times C$の部分対象と自然に同一視できるから、それぞれの表示を一つ選ぶ。$r\colon M \to A \times B,s \colon M' \to B \times C$を、それぞれ$R,S$を表示するmonicとする。柱体化を用いて、$(M;r),(M';s)$を$A \times B \times C$上の1-tableに持ち上げよう。

まずは$(M;r)$について。
$R$の柱体化

ただし、$\overline{r\times 1_C}$とは、次を満たす射である。

$$ \overline{r\times 1_C} \overset{\mathrm{def}}{=}\langle \pi_A\circ \pi_{A \times B},\pi_B \circ \pi_{A \times B},\pi_C\rangle \circ (r \times 1_C) = \langle \pi_A\circ r \circ \pi_M,\pi_B \circ r \circ \pi_M,\pi_C \rangle $$

同様に、$(M';s)$についても柱体化を行う。
$S$の柱体化

ただし$\overline{1_A\times s}$とは、次を満たす射である。

$$ \overline{1_A\times s} \overset{\mathrm{def}}{=} \langle \pi_A,\pi_B\circ \pi_{B \times C},\pi_C \circ \pi_{B \times C}\rangle \circ (1_A \times s) = \langle \pi_A,\pi_B \circ s \circ \pi_{M'},\pi_C \circ s \circ \pi_{M'} \rangle $$

こうして柱体化$(M \times C;\overline{r \times 1_C}),(A \times M';\overline{1_A \times s})$を得たので、これらのintersectionを取れば良い。これまでの図式をひとまとめにすると以下のようになる。
柱体同士のintersection

このようにして得た$A \times B \times C$上の1-table$(M\times C\cap A \times M';\overline{r \times 1_C} \circ \lambda)$に対して、$\langle \pi_A,\pi_C \rangle$で順像を取れば、$A \times C$上の1-tableで合成関係$S \circ R$の表示となるものを構成できる。

$\cdots$とまあ、論理的にはこれで正しいが、$(M\times C \cap A \times M';\overline{r \times 1_C}\circ \lambda)$が一体どんな$A \times B\times C$の部分対象を表示しているのか、イマイチよく分からないのは矢張り気になる。このmonicは一体、二項関係$R,S$とどういう繋がりを持っているのかをはっきりさせておきたい。

3.3 2-tableの目線で見る、圏論的二項関係の合成

先ほどは、intersectionを利用したいがために、二項関係$R,S$をそれぞれ$A\times B,B \times C$上の部分対象と見做し、$(M;r),(M';s)$というmonicで柱体化を図ったのだった。しかし圏論的な二項関係とは、定義の上では2-tableの形式で表示されるものである。つまり、$R,S$は、jointly monic span$(M;f_1,f_2),(M';g_1,g_2)\ \text{s.t.}\ \langle f_1,f_2\rangle = r,\langle g_1,g_2 \rangle = s$によって表示することができる。二項関係を2-tableで表したとき、関係の合成はどのように表されるだろうか？

ここで、直前の図を思い出すと、右下が欠けているのが気になる。ここは次のようにして自然に埋められる。
積の射影を補充して四つの可換四角形に

これで右下の四角形図式が引き戻しであれば、面白いことが起きるのである。

これにより、次の定理が従う。

3.4 総括

construction-intersectionより、二項積、引き戻し、像を持つ圏に於いて、$R \in \mathrm{Rel}(A,B),S \in \mathrm{Rel}(B,C)$及びこれらの表示$(M;f_1,f_2),(M';g_1,g_2)$が与えられたとき、二項関係の合成は次の手順で得られる。
2-tableで表した二項関係の合成
積の射影で順像を取る

この構成で得た2-table$(\exists\langle \pi_A,\pi_C \rangle P;\pi_A \circ m,\pi_C \circ m)$が、合成した関係$S \circ R$を表示する。