写像のグラフと射のグラフ

$(\Longrightarrow)$
spanの同型の意味で$(A;1_A,f)\simeq (T;f_1,f_2)$が成り立つ。したがってある同型射$\theta\colon A \to T$が存在して、
$1_A = f_1 \circ \theta$かつ$f = f_2 \circ \theta$が成立。$f_1 = \theta^{-1}$より$f_1$は同型射で、$f = f_2 \circ f_1^{-1}$が成り立つ。

$(\Longleftarrow)$2-table$(T;f_1,f_2)$の$f_1$が同型射ならば、$(T;f_1,f_2)$が射$f_2\circ f_1^{-1}\colon A \to B$のグラフであることは次の図式より明らか。
射のグラフを表示する2-tableの特徴

$(\Longrightarrow)f = f\circ 1_A$という分解を考える。$f$はmonicかつcoverであるから、coverの定義より$f$は同型射でなければならない。

$(\Longleftarrow)f$は同型射だとする。$f$はmonicである。実際、$f \circ x = f \circ y$ならば、両辺に左から$f^{-1}$を合成して$x = y$が従う。
$f$はcoverであることを示す。$f = m \circ f',f' \colon A \to B',m\colon B' \to B$と任意に分解し、$m$はmonicだと仮定する。
このとき$m \circ f' \circ f^{-1} \circ m = m = m \circ 1_{B'}$であるから、monicの定義より$f' \circ f^{-1}\circ m = 1_{B'}$が成立。
さらに$f^{-1}\circ m \circ f' = f^{-1}\circ f = 1_A$であるから、$f^{-1}\circ m$は$f'$の逆射であり、$f'$は同型射である。
よって$m = f \circ f'^{-1}$が成立し、同型射の合成は再び同型射であるから、$m$は同型射。よって$f$がcoverであることが示された。

$R$がsimpleかつentireであることは、$R$の任意の表示$(T;f_1,f_2)$に対して$f_1$がmonicかつcover、則ち同型射であることと同値であり、そのとき$R$は射$f_2\circ f_1^{-1}$のグラフである。
このことから双方向が直ちに従う。

$(\Longrightarrow)f$が全単射のとき、これが同型射であることを示す。
$f$が三つ組$(G_f,X,Y)$で与えられているとする。このとき、二項関係$G_f^{\circ} \subseteq Y \times X$を次で定義する。
$$ G_f^{\circ} \overset{\mathrm{def}}{=} \{ (y,x) \in Y \times X \mid (x,y) \in G_f \} $$
(二項関係$G_f^{\circ}$は、$G_f$のreciprocationという。)
$(G_f^{\circ},Y,X)$は写像としてwell-definedであることを示そう。

• 左全域性について、任意の$y \in Y$に対し、ある$x \in X$が存在して、$(y,x) \in G_f^{\circ}(\mathrm{iff}\ y = f(x))$が成り立つことは、$f$が全射であることから従う。
• 右一意性について、任意の$y \in Y,x,x' \in X$に対し、$(y,x),(y,x') \in G_f^{\circ}$ならば$y = f(x)$かつ$y = f(x')$であり、なおかつ$f$の単射性より$f(x) = f(x')$ならば$x = x'$が従うので、
      $(y,x),(y,x') \in G_f^{\circ}$ならば$x = x'$である。

よって$G_f^{\circ}$は写像のグラフである。

次に$(G_f^{\circ},Y,X)$が$f$の逆写像を与えることを示す。$(G_f^{\circ},Y,X)$が表す写像を$f^{\circ}$と書くとき、写像$f^{\circ}\circ f$は三つ組$(G_f^{\circ}\circ G_f,X,X)$で定義される。
$G_f^\circ \circ G_f$は二項関係の合成であるが、これが$X$上の対角線集合であることを示そう。
$$G_f^\circ \circ G_f = \{ (x,x') \mid \exists y . (x,y) \in G_f \land (y,x') \in G_f^\circ \}$$
ある$y \in Y$で$(x,y) \in G_f$かつ$(y,x') \in G_f^\circ$のとき、ある$y \in Y$で$y = f(x)$かつ$y = f(x')$であるから、$f$の単射性より、$x = x'$が従う。
よって$(x,x') \in G_f^\circ \circ G_f$ならば$x = x'$。
さらに$G_f,G_f^\circ$は左全域的であるから、任意の$x \in X$に対しある$x'$が存在して$(x,x') \in G_f^\circ \circ G_f$。
よって、$G_f^\circ \circ G_f = \{ (x,x) \mid x \in X \}$。

ほとんど同様にして、$G_f \circ G_f^\circ = \{ (y,y) \mid y \in Y \}$が成り立つ。

以上より$(G_f^\circ \circ G_f ,X,X),(G_f \circ G_f^\circ , Y,Y)$はそれぞれ恒等写像$1_X,1_Y$を定めるから、$f^\circ$は$f$の逆写像。
よって$f$は同型射である。

$(\Longleftarrow)f$が同型射のとき、逆写像$f^{-1}\colon Y \to X$が存在して、$f^{-1}\circ f = 1_X$かつ$f \circ f^{-1} = 1_Y$が成立する。
ここで恒等写像$1_X,1_Y$は全射かつ単射であるから、$f^{-1}\circ f = 1_X$より$f$は単射、$f \circ f^{-1} = 1_Y$より$f$は全射、したがって$f$は全単射である。

$g\circ f$が単射のとき、任意の$x,y \in X$に対し、$x \neq y$ならば$g(f(x)) \neq g(f(y))$である。
写像のwell-defined性の対偶より、$g(f(x)) \neq g(f(y))$ならば$f(x) \neq f(y)$。よって任意の$x,y \in X$に対し、$x \neq y$ならば$f(x) \neq f(y)$が成立し、$f$は単射。

$g\circ f$が全射のとき、任意の$z \in Z$に対し、ある$x \in X$で$z = g(f(x))$を満たすものが存在する。
よって任意の$z \in Z$に対し、ある$y \in Y$で$z = g(y)$を満たすものが存在し、$g$は全射。

$(\Longrightarrow)m\colon M \to X$をmonicとする。$x,y \in M$を任意に取り、$m(x) = m(y)$と仮定する。
このとき、一元集合$\{*\}$から$M$への写像$\overline{x},\overline y \colon \{*\} \to M,\overline x(*) = x,\overline y(*) = y$が存在して、
写像の等号の定義より$m\circ \overline x = m \circ \overline y$が成立する。$m$はmonicなので、$\overline x = \overline y$が成立し、$x = \overline x(*) = \overline y (*)= y$。
よって$m(x) = m(y)$ならば$x = y$であるから、$m$は単射の定義を満たす。

$(\Longleftarrow)m \colon M \to X$を単射とする。任意の集合$W$と任意の写像$f,g \colon W \to M$を取り、$m\circ f = m \circ g$と仮定する。
写像の等号の定義より、任意の$w \in W$で$m(f(w)) = m(g(w))$であるから、単射の定義より任意の$w \in W$で$f(w) = g(w)$が成立。よって写像の等号の定義より$f = g$が成立し、$m$はmonicの定義を満たす。

$(\Longrightarrow)c\colon X \to Y$をcoverとする。$c$を像分解して、$c = X \overset{\overline{c}}{\to} \mathrm{Im}(c) \overset{i}{\hookrightarrow} Y$とする。
命題6より、単射とmonicは一致するから、包含写像$i \colon \mathrm{Im}(c)\hookrightarrow Y$はmonicである。よってcoverの定義より$i$は同型射でなければならないが、
集合と写像の圏では同型射は全単射と一致するのであった。包含写像が全単射なので、$\mathrm{Im}(c) = Y$が成立し、$c$は全射である。

$(\Longleftarrow)c\colon X \to Y$を全射とする。任意の$\overline c,m$を取り、$c = m \circ \overline c$かつ$m$はmonic(則ち単射)と仮定する。
$c$が全射なので$m$も全射、よって$m$は全射かつ単射であるから全単射、則ち同型射である。したがって$c$はcoverの定義を満たす。

2-tableとして、$(R;\pi_A \circ i,\pi_B \circ i)$を取る。ただし$i$は包含写像$i\colon R\hookrightarrow A\times B$で、$\pi_A,\pi_B$は積の射影。
$A,B$上の2-table間の同型$(T;f_1,f_2)\simeq (T';g_1,g_2)$が成り立つとき、$f_1$がmonicならば$g_1$もmonic,$f_1$がcoverならば$g_1$もcoverであることは、容易に確かめられるので、
証明は2-tableの代表の取り方に依らない。

$R$が右一意的$\iff \pi_A \circ i$が単射

$(\Longrightarrow)R$は右一意的であると仮定する。つまり、任意の$a \in A,b,b' \in B$に対し、$(a,b),(a,b') \in R$ならば$b = b'$が成り立つと仮定する。
任意の$(a,b),(a',b') \in R$を取り、$\pi_A \circ i(a,b) = \pi_A \circ i(a',b')$、則ち$a = a'$と仮定。このとき$R$の右一位性より、$b = b'$が従うから、$(a,b) = (a',b')$が成り立つ。
よって$\pi_A \circ i$は単射の定義を満たす。

$(\Longleftarrow)\pi_A \circ i$が単射であると仮定する。このとき、任意の$(a,b),(a',b')\in R$に対し、$a = \pi_A \circ i(a,b) = \pi_A \circ i(a',b') = a'$ならば$(a,b) = (a',b')$であるから、
任意の$(a,b),(a',b')\in R$に対し、$a = a'$ならば$b = b'$である。これは$R$が右一意的であることを示している。

$R$が左全域的$\iff \pi_A \circ i$が全射

$(\Longrightarrow)R$が左全域的であると仮定する。つまり、任意の$a \in A$に対し、ある$b \in B$で$(a,b) \in R$を満たすものが存在すると仮定する。
このとき任意の$a \in A$に対し、ある$(a,b) \in R$で$a = \pi_A \circ i(a,b)$を満たすものが存在することになるので、$\pi_A \circ i$は全射である。

$(\Longleftarrow)\pi_A \circ i$が全射であるとする。つまり任意の$a \in A$に対し、ある$(a,b)\in R$で$a = \pi_A \circ i(a,b)$を満たすものが存在すると仮定する。
このとき任意の$a \in A$に対しある$b \in B$で$(a,b) \in R$を満たすものが存在するから、$R$は左全域性の定義を満たす。