関係合成の結合律と正則圏

仮定のように$f$は像を持ち、かつ$f = m \circ c$とcover,monicの合成の形で書かれるとする。
像の最小性より、$[(\exists f A ; i)] \subseteq [(M;m)]$、則ち、あるmonic$\theta \colon \exists f A \to M$が存在して、$i = m \circ \theta$が成り立つ。
すると$f = m \circ c = m \circ \theta \circ \overline f$であり、$m$はmonicであるから、$c = \theta \circ \overline f$が従う。
$c$はcoverだったから、coverの定義より$\theta$は同型射でなければならない。よって$\theta$は1-table間の同型$(\exists f A;i) \simeq (M;m)$を与える。
これは$[(M;m)]$が$f$の像であることを示している。

定義に従って、$G_g\circ G_f$を計算する。
射のグラフの合成

図式より、$1_A = m_1 \circ c$であるから、$c$はmonic。($g \circ f$がmonicならば$f$はmonic。)
よって$c$はmonicかつcoverであるから同型射になり、spanとして$(A;1_A,g\circ f)\simeq (\exists \langle \pi_A,\pi_C \rangle A;m_1,m_2)$が成立。
したがって、$G_g \circ G_f = [(A;1_A,g\circ f)] = G_{g\circ f}$が成立する。

$R,S$の表示をそれぞれ$(T;f_1,f_2),(T';g_1,g_2)$とすると、次の図が成り立つ。
恒等射のグラフの関係合成

図中の$c,d$は2-table間のspanの射であるからmonicである。よって$c,d$はmonicかつcoverであるから、monic-coverより$c,d$は同型射。
よって$(\exists \langle \pi_X,\pi_A \rangle T;m_1,m_2) \simeq (T;f_1,f_2)$かつ$(\exists \langle \pi_A,\pi_Y \rangle T' ; n_1,n_2) \simeq (T';g_1,g_2)$が従うので、
$1_A \circ R = [(T;f_1,f_2)] = R,\ S \circ 1_A = [(T';g_1,g_2)] = S$が成り立つ。

定義に従って、関係合成$c \circ c^\circ$を構成する。
二項関係によるcoverの特徴付け

$(\Longrightarrow)$
射として$c = m_1 \circ d = m_2 \circ d$である。圏は二項積と引き戻しを持つと仮定したから、圏はイコライザを持つ。よって$d$はcoverなのでepicであるから、$m_1 = m_2$が従う。(以後、$m_1,m_2$は$m$で統一する。)
今$(\exists \langle \pi_B,\pi_B \rangle A;m,m)$は2-tableであるから、$\langle m,m \rangle \colon \exists \langle \pi_B,\pi_B \rangle A \to B \times B$はmonicである。そして$\langle m,m \rangle = \langle 1_B,1_B \rangle \circ m$であるから、$m$はmonicでなければならない。
$c = m \circ d$かつ$c$はcoverで$m$はmonicだから、定義より$m$は同型射である。
則ち、$(\exists \langle \pi_B,\pi_B \rangle A; m,m) \simeq (B;1_B,1_B)$が成り立ち、二項関係として$c\circ c^{\circ} = [(B;1_B,1_B)] = 1_B$が従う。
2-tableの同型

$(\Longleftarrow)c \circ c^\circ= [(B;1_B,1_B)]$と仮定する。射$c$を$c = m \circ \overline c$と像分解し、$\overline c$はcover、$m$はmonicと仮定する。
射$c$の像分解

このとき次が成り立つ。
像由来の2-table

よって$(\exists c A;m,m)$は$c \circ c^\circ$を表示する。一方仮定より、$c \circ c^\circ = [(B;1_B,1_B)]$であったから、$(\exists c A;m,m) \simeq (B;1_B,1_B)$でなければならない。
則ち、ある同型射$\theta \colon \exists c A \to B$で次を満たすものが存在する。
像と終域の同型

図式より$\theta = m$であるから、$m$は同型射である。
像が終域と同型なので、$c$はcoverである。

まず$(x \circ x^\circ)\circ y$について。
cover-entireより、$x \circ x^\circ = 1_C$であるから、$(x \circ x^\circ) \circ y = 1_C \circ y$である。
identity-relより$1_C \circ y = y$が従う。

次に$x \circ (x^\circ \circ y)$について。
まず$x^\circ \circ y$は次のように合成される。
関係合成$x^\circ \circ y$

図中で引き戻し$(P;z,w)$が2-tableであることに注意を払うと、$c$はjointly monic spanの間の射であるから、$c$はmonicである。
つまり$c$はmonicかつcoverなので同型射であるから、$(\exists \langle \pi_B,\pi_A \rangle P;m_1,m_2) \sim (P;z,w)$。
よって$(P;z,w)$は二項関係$x^\circ \circ y$の表示を与えるので、以後これを採用する。

すると、$x \circ (x^\circ \circ y)$は次のように合成される。
関係合成$x\circ (x^\circ \circ y)$

図式およびcover-basicpropertyより、$n_1$がcoverならば、$n_1 \circ d$はcoverであるから、$z$はcoverになる。
対偶より、$z$がcoverでなければ、$n_1$はcoverではない。
今、仮定より$z$はcoverではないから、$n_1$はcoverではない。よってmonic-coverより、$n_1$は同型射足り得ない。したがってsimple-entireより、$(\exists \langle \pi_B,\pi_C \rangle P;n_1,n_2)$はmap足り得ない。

以上より、$(x\circ x^\circ)\circ y$は射$y$のグラフであるのに対し、$x \circ (x^\circ \circ y)$はどの射のグラフにもならない。則ち、$(x \circ x^\circ) \circ y \neq x \circ (x^\circ \circ y)$である。

$g = i \circ \overline g$を$g$のcover-monic分解として、次の図式が成り立つ。
共通の像を持つ

$f = i \circ (\overline g \circ \theta)$が成り立ち、$\overline g \circ \theta$はcoverかつ$i$はmonicである。
cover-monic-factorizationより、$[(\exists g B;i)]$は$f$の像であるから、$f,g$は共通の像を持つ。

証明の方針

$T \circ (S \circ R)$と$(T \circ S)\circ R$それぞれの表示を構成し、$A \times D$の部分対象として一致することを示す。
対象$A,B$上の二項関係$R$、$B,C$上の二項関係$S$、$C,D$上の二項関係$T$を任意に取る。
これらの表示を順番に、$(M_1;a_1,a_2),(M_2;b_1,b_2),(M_3;c_1,c_2)$として、
$T \circ (S \circ R) = (T \circ S) \circ R$が成り立つことを証明していく。

$T \circ (S \circ R)$の表示の構成

$T \circ (S \circ R)$の表示は次のように構成できる。
関係合成$T \circ (S \circ R)$

図中の$(P_2;g_1,g_2)$は、$f_2,c_1$の引き戻しである。この図式の中から、次の図式が読み取れる。
さっきの図式から取り出した引き戻し

ここで$e,g_1$の引き戻しを考える。
引き戻しがcoverを引き戻す

仮定より引き戻しがcoverを引き戻すので、$e$がcoverであるから$j_2$もcoverであることに注目。

図式を読み解くと$f_2 \circ e = b_2 \circ d_2$であるから、引き戻しのpasting lemmaより大外の四角形図式は$b_2 \circ d_2,c_1$の引き戻しである。

$\langle a_1 \circ d_1 \circ j_1,c_2 \circ g_2 \circ j_2 \rangle\colon P_3 \to A \times D$の像分解

次の図式が成立している。
像分解その１

diagram chase及び積の普遍性により、$\langle a_1 \circ d_1 \circ j_1,c_2 \circ g_2 \circ j_2 \rangle = \langle i_1,i_2 \rangle \circ h \circ j_2$が成り立つ。
像分解の様子

仮定より圏は像を持つので、cover-monic-factorizationより、coverとmonicの合成の形で書かれたこれは$\langle a_1 \circ d_1 \circ j_1,c_2 \circ g_2 \circ j_2 \rangle$の像分解を与えている。
つまり$[(\exists \langle \pi_A,\pi_D \rangle P_2;\langle i_1,i_2 \rangle)]$は$\langle a_1\circ d_1 \circ j_1,c_2 \circ g_2 \circ j_2 \rangle$の像である。

$(T\circ S)\circ R$の表示の構成

次に関係合成$(T \circ S)\circ R$の構成を図式化する。
関係合成$(T \circ S) \circ R$

図中の$(P_5;n_1,n_2)$は$a_2,m_1$の引き戻しである。
この図式の中から、次の図式が読み取れる。
さっきの図式の中の引き戻し

$l,n_2$の引き戻し$(P_6;q_1,q_2)$を取る。

引き戻しがcoverを引き戻すと仮定したので、$l$がcoverであるから$q_2$もcoverであることに注目。

$m_1 \circ l = b_1 \circ k_1$なので、引き戻しのpasting lemmaより大外の四角形図式は$b_1 \circ k_1,a_2$の引き戻しである。

$\langle a_1 \circ n_1 \circ q_2,c_2 \circ k_2 \circ q_1 \rangle \colon P_6 \to A \times D$の像分解

次が成り立っている。
像分解その２

diagram chase及び積の普遍性により、$\langle a_1 \circ n_1 \circ q_2 , c_2 \circ k_2 \circ q_1 \rangle = \langle p_1,p_2 \rangle \circ o \circ q_2$が成立。
像分解の様子

今、圏は像を持つと仮定したので、cover-monic-factorizationより$[(\exists \langle \pi_A,\pi_D\rangle P_5; \langle p_1,p_2 \rangle)]$は$\langle a_1\circ n_1 \circ q_2,c_2 \circ k_2 \circ q_1 \rangle$の像である。

二つの像の一致

ここでさらに次の構成を考えてみる。
引き戻しのピラミッド

引き戻しのpasting lemmaより、$(P_7;r_1,k_2 \circ r_2)$は$b_2 \circ d_2,c_1$の、$(P_7;d_1\circ r_1,r_2)$は$a_2,b_1 \circ k_1$の、それぞれ引き戻しである。
既に確かめたように、$(P_3;j_1,g_2\circ j_2)$は$b_2 \circ d_2,c_1$の引き戻しであり、$(P_6;q_1,n_1 \circ q_2)$は$b_1 \circ k_1,a_2$の引き戻しであったから、
spanの同型$(P_7;r_1,k_2 \circ r_2) \simeq (P_3; j_1,g_2 \circ j_2),(P_7; r_2,d_1 \circ r_1) \simeq (P_6;q_1,n_1 \circ q_2)$がそれぞれ成り立つ。
したがって、ある同型射$\theta_1 \colon P_7 \to P_3,\theta_2 \colon P_7 \to P_6$が存在して、次が成り立つ。
像の比較その１
像の比較その２

commonimageより、$[(\exists \langle \pi_A,\pi_D \rangle P_2 ; \langle i_1,i_2 \rangle)],[(\exists\langle \pi_A,\pi_D \rangle P_5;\langle p_1,p_2 \rangle)]$はいずれも$\langle a_1 \circ d_1 \circ r_1,c_2 \circ k_2 \circ r_2 \rangle$の像ということになる。
像の最小性より、両者は一致しなければならない。
前者は$T \circ (S \circ R)$を、後者は$(T \circ S)\circ R$を、積の部分対象の形式でそれぞれ表したものだから、$T \circ (S \circ R) = (T \circ S) \circ R$が示された。