対応 ⑫

Prop&Proof.

1. 合成対応の定義より、
   $$ \Delta\circ\Gamma = (A,C,R_{\Delta\circ\Gamma}) $$
   であり、
   $$ R_{\Delta\circ\Gamma} = \{(a,c)\in A\times C\mid \exists b\in B\ ((a,b)\in R\land(b,c)\in Q)\} $$
   である。
   したがって、逆対応の定義より、
   $$ (\Delta\circ\Gamma)^{-1} = (C,A,(R_{\Delta\circ\Gamma})^{-1}) $$
   である。
   $ $
2. 一方、逆対応の定義より、
   $$ \Gamma^{-1} = (B,A,R^{-1}) $$
   であり、
   $$ R^{-1} = \{(b,a)\in B\times A\mid (a,b)\in R\} $$
   である。また、
   $$ \Delta^{-1} = (C,B,Q^{-1}) $$
   であり、
   $$ Q^{-1} = \{(c,b)\in C\times B\mid (b,c)\in Q\} $$
   である。
   $ $
3. ここで、$\Delta^{-1}$ は $C$ から $B$ への対応であり、$\Gamma^{-1}$ は $B$ から $A$ への対応である。
   したがって、$\Gamma^{-1}\circ\Delta^{-1}$ は $C$ から $A$ への対応として定まる。
   合成対応の定義より、
   $$ \Gamma^{-1}\circ\Delta^{-1} = (C,A,R_{\Gamma^{-1}\circ\Delta^{-1}}) $$
   であり、
   $$ R_{\Gamma^{-1}\circ\Delta^{-1}} = \{(c,a)\in C\times A\mid \exists b\in B\ ((c,b)\in Q^{-1}\land(b,a)\in R^{-1})\} $$
   である。
   ゆえに、
   $$ (\Delta\circ\Gamma)^{-1} = \Gamma^{-1}\circ\Delta^{-1} $$
   を示すには、
   $$ (R_{\Delta\circ\Gamma})^{-1} = R_{\Gamma^{-1}\circ\Delta^{-1}} $$
   を示せばよい。
   $ $
4. 両辺はともに $C\times A$ の部分集合である。
   したがって、外延性により、任意の $(c,a)\in C\times A$ に対して、
   $$ (c,a)\in (R_{\Delta\circ\Gamma})^{-1} \Longleftrightarrow (c,a)\in R_{\Gamma^{-1}\circ\Delta^{-1}} $$
   を示せば十分である。任意に $(c,a)\in C\times A$ をとる。
   このとき、逆関係の定義、合成対応の定義、逆関係の定義より、
   $$ \begin{align} (c,a)\in (R_{\Delta\circ\Gamma})^{-1} &\Longleftrightarrow (a,c)\in R_{\Delta\circ\Gamma}\\ &\Longleftrightarrow \exists b\in B\ ((a,b)\in R\land(b,c)\in Q)\\ &\Longleftrightarrow \exists b\in B\ ((c,b)\in Q^{-1}\land(b,a)\in R^{-1})\\ &\Longleftrightarrow (c,a)\in R_{\Gamma^{-1}\circ\Delta^{-1}}. \end{align} $$
   ゆえに、任意の $(c,a)\in C\times A$ に対して、
   $$ (c,a)\in (R_{\Delta\circ\Gamma})^{-1} \Longleftrightarrow (c,a)\in R_{\Gamma^{-1}\circ\Delta^{-1}} $$
   が成り立つ。
   したがって、外延性により、
   $$ (R_{\Delta\circ\Gamma})^{-1} = R_{\Gamma^{-1}\circ\Delta^{-1}} $$
   である。

-よって、
$$ \begin{align} (\Delta\circ\Gamma)^{-1} &= (C,A,(R_{\Delta\circ\Gamma})^{-1})\\ &= (C,A,R_{\Gamma^{-1}\circ\Delta^{-1}})\\ &= \Gamma^{-1}\circ\Delta^{-1} \end{align} $$
が成り立つ。
$$ \Box$$

外延性により、任意の $a\in A$ に対して、
$$ a\in(\Delta\circ\Gamma)^{-1}(T) \Longleftrightarrow a\in\Gamma^{-1}\bigl(\Delta^{-1}(T)\bigr) $$
が成り立つことを示せば十分である。
任意の $a\in A$ をとる。

1. 合成対応の逆像の定義より、
   $$ \begin{align} a\in(\Delta\circ\Gamma)^{-1}(T) &\Longleftrightarrow a\in A\land \exists c\in T\ ((a,c)\in R_{\Delta\circ\Gamma}) \end{align} $$
   である。
   合成対応のグラフの定義より、
   $$ (a,c)\in R_{\Delta\circ\Gamma} \Longleftrightarrow \exists b\in B\ ((a,b)\in R\land(b,c)\in Q) $$
   であるから、存在記号の順序交換( 証明はコチラ )より
   $$ \begin{align} a\in(\Delta\circ\Gamma)^{-1}(T) &\Longleftrightarrow a\in A\land \exists c\in T\ \exists b\in B\ ((a,b)\in R\land(b,c)\in Q)\\ &\Longleftrightarrow a\in A\land \exists b\in B\ \exists c\in T\ ((a,b)\in R\land(b,c)\in Q)\\ &\Longleftrightarrow a\in A\land \exists b\in B\ \bigl((a,b)\in R\land \exists c\in T\ ((b,c)\in Q)\bigr) \end{align} $$
   である。
   ここで、$\Delta^{-1}(T)$ の定義より、
   $$ b\in\Delta^{-1}(T) \Longleftrightarrow b\in B\land \exists c\in T\ ((b,c)\in Q) $$
   である。したがって、
   $$ \begin{align} a\in(\Delta\circ\Gamma)^{-1}(T) &\Longleftrightarrow a\in A\land \exists b\in \Delta^{-1}(T)\ ((a,b)\in R) \end{align} $$
   である。
   $ $
2. 一方、$\Gamma$ による $\Delta^{-1}(T)$ の逆像の定義より、
   $$ \Gamma^{-1}\bigl(\Delta^{-1}(T)\bigr) = \{a\in A\mid \exists b\in \Delta^{-1}(T)\ ((a,b)\in R)\} $$
   である。ゆえに、
   $$ a\in(\Delta\circ\Gamma)^{-1}(T) \Longleftrightarrow a\in\Gamma^{-1}\bigl(\Delta^{-1}(T)\bigr) $$
   が成り立つ。

-$a\in A$ は任意であったから、外延性により、
$$ (\Delta\circ\Gamma)^{-1}(T) = \Gamma^{-1}\bigl(\Delta^{-1}(T)\bigr) $$
である。
$$ \Box$$

合成対応の定義より、
$$ \Delta\circ\Gamma = (A,C,R_{\Delta\circ\Gamma}) $$
であり、
$$ R_{\Delta\circ\Gamma} = \{(a,c)\in A\times C\mid \exists b\in B\ ((a,b)\in R\land(b,c)\in Q)\} $$
である。
したがって、逆対応の定義より、
$$ (\Delta\circ\Gamma)^{-1} = (C,A,(R_{\Delta\circ\Gamma})^{-1}) $$
である。ゆえに、グラフの定義より、
$$ G\bigl((\Delta\circ\Gamma)^{-1}\bigr) = (R_{\Delta\circ\Gamma})^{-1} $$
である。
また、
$$ \Gamma^{-1}=(B,A,R^{-1}) $$
であり、
$$ \Delta^{-1}=(C,B,Q^{-1}) $$
であるから、
$$ G(\Gamma^{-1})=R^{-1}, \qquad G(\Delta^{-1})=Q^{-1} $$
である。
ここで、両辺はともに $C\times A$ の部分集合である。
したがって、外延性により、任意の $(c,a)\in C\times A$ に対して、
$$ (c,a)\in G\bigl((\Delta\circ\Gamma)^{-1}\bigr) \Longleftrightarrow (c,a)\in G(\Gamma^{-1})\circ G(\Delta^{-1}) $$
を示せば十分である。
任意に $(c,a)\in C\times A$ をとる。
このとき、
$$ \begin{align} (c,a)\in G\bigl((\Delta\circ\Gamma)^{-1}\bigr) &\Longleftrightarrow (c,a)\in (R_{\Delta\circ\Gamma})^{-1}\\ &\Longleftrightarrow (a,c)\in R_{\Delta\circ\Gamma}\\ &\Longleftrightarrow \exists b\in B\ ((a,b)\in R\land(b,c)\in Q)\\ &\Longleftrightarrow \exists b\in B\ ((c,b)\in Q^{-1}\land(b,a)\in R^{-1})\\ &\Longleftrightarrow \exists b\in B\ ((c,b)\in G(\Delta^{-1})\land(b,a)\in G(\Gamma^{-1}))\\ &\Longleftrightarrow (c,a)\in G(\Gamma^{-1})\circ G(\Delta^{-1}). \end{align} $$
ゆえに、任意の $(c,a)\in C\times A$ に対して、
$$ (c,a)\in G\bigl((\Delta\circ\Gamma)^{-1}\bigr) \Longleftrightarrow (c,a)\in G(\Gamma^{-1})\circ G(\Delta^{-1}) $$
が成り立つ。
したがって、外延性により、
$$ G\bigl((\Delta\circ\Gamma)^{-1}\bigr) = G(\Gamma^{-1})\circ G(\Delta^{-1}) $$
である。
$$ \Box$$