対応 ⑪

Def.

Prop&Proof

まず、$S\subseteq A$ であるから、合成対応 $\Delta\circ\Gamma$ による $S$ の像 $(\Delta\circ\Gamma)(S)$ は定義される。
また、$\Gamma(S)\subseteq B$ であるから、$\Delta(\Gamma(S))$ も定義される。
外延性により、任意の $c\in C$ に対して、
$$ c\in(\Delta\circ\Gamma)(S) \Longleftrightarrow c\in\Delta(\Gamma(S)) $$
が成り立つことを示せばよい。
$ $
任意に $c$ をとる。
集合の像の定義より、
$$ \begin{align} c\in(\Delta\circ\Gamma)(S) &\Longleftrightarrow c\in C\land\exists a\in S\ ((a,c)\in R_{\Delta\circ\Gamma})\\ &\Longleftrightarrow c\in C\land\exists a\in S\ \exists b\in B\ ((a,b)\in R\land(b,c)\in Q) \end{align} $$
である。
ここで、$\Gamma(S)$ の定義より、
$$ b\in\Gamma(S) \Longleftrightarrow b\in B\land\exists a\in S\ ((a,b)\in R) $$
である。
したがって、存在記号の順序交換( 証明はコチラ )と論理積の交換法則( 証明はコチラ )より
$$ \begin{align} c\in(\Delta\circ\Gamma)(S) &\Longleftrightarrow c\in C\land\exists b\in B\bigl((b,c)\in Q\land\exists a\in S\ ((a,b)\in R)\bigr)\\ &\Longleftrightarrow c\in C\land\exists b\in\Gamma(S)\ ((b,c)\in Q)\\ &\Longleftrightarrow c\in\Delta(\Gamma(S)) \end{align} $$
である。
ゆえに、任意の $c\in C$ に対して、
$$ c\in(\Delta\circ\Gamma)(S) \Longleftrightarrow c\in\Delta(\Gamma(S)) $$
が成り立つ。
したがって、外延性により、
$$ (\Delta\circ\Gamma)(S)=\Delta(\Gamma(S)) $$
である。
$$ \Box$$

1. $A,B,C$ を集合とし、
   $$ R\subseteq A\times B,\quad Q\subseteq B\times C $$
   を二項関係とする。このとき、$R$ と $Q$ の合成関係は
   $$ Q\circ R := \{(a,c)\in A\times C\mid \exists b\in B\ ((a,b)\in R\land(b,c)\in Q)\} $$
   で定義される( 詳しくはコチラ )。
   $ $
2. また、$\Gamma=(A,B,R)$ と $\Delta=(B,C,Q)$ に対して、
   合成対応の定義より、
   $$ \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)\} $$
   である。
   したがって、対応のグラフの定義より、
   $$ G(\Delta\circ\Gamma)=R_{\Delta\circ\Gamma} $$
   である。
   $ $
3. ここで、対応のグラフの定義より、
   $$ G(\Gamma)=R $$
   かつ
   $$ G(\Delta)=Q $$
   である。
   よって、二項関係の合成の定義より、
   $$ \begin{align} G(\Delta)\circ G(\Gamma) &= Q\circ R\\ &= \{(a,c)\in A\times C\mid \exists b\in B\ ((a,b)\in R\land(b,c)\in Q)\}\\ &= R_{\Delta\circ\Gamma}\\ &= G(\Delta\circ\Gamma) \end{align} $$
   である。

-したがって、
$$ G(\Delta\circ\Gamma)=G(\Delta)\circ G(\Gamma) $$
が成り立つ。
$$ \Box$$

1. 対応の包含の定義より、
   $$ \Delta\circ\Gamma_1\subseteq\Delta\circ\Gamma_2 $$
   を示すには、
   $$ G(\Delta\circ\Gamma_1)\subseteq G(\Delta\circ\Gamma_2) $$
   を示せばよい。
   i) 合成対応の定義より、
   $$ \Delta\circ\Gamma_1=(A,C,R_{\Delta\circ\Gamma_1}) $$
   　 であり、
   $$ R_{\Delta\circ\Gamma_1} = \{(a,c)\in A\times C\mid \exists b\in B\ ((a,b)\in R_1\land(b,c)\in Q)\} $$
   　 である。
   ii) また、
   $$ \Delta\circ\Gamma_2=(A,C,R_{\Delta\circ\Gamma_2}) $$
   　 であり、
   $$ R_{\Delta\circ\Gamma_2} = \{(a,c)\in A\times C\mid \exists b\in B\ ((a,b)\in R_2\land(b,c)\in Q)\} $$
   　 である。
   対応のグラフの定義より、
   $$ G(\Delta\circ\Gamma_1)=R_{\Delta\circ\Gamma_1} $$
   かつ
   $$ G(\Delta\circ\Gamma_2)=R_{\Delta\circ\Gamma_2} $$
   である。
   $ $
2. したがって、
   $$ R_{\Delta\circ\Gamma_1}\subseteq R_{\Delta\circ\Gamma_2} $$
   を示せばよい。
   そこで、任意に
   $$ (a,c)\in R_{\Delta\circ\Gamma_1} $$
   をとる。
   合成対応のグラフの定義より、
   $$ (a,c)\in A\times C $$
   かつ、ある $b\in B$ が存在して、
   $$ (a,b)\in R_1\land(b,c)\in Q $$
   が成り立つ。
   仮定より、
   $$ R_1\subseteq R_2 $$
   であるから、
   $$ (a,b)\in R_2 $$
   である。したがって、
   $$ (a,b)\in R_2\land(b,c)\in Q $$
   が成り立つ。
   ゆえに、合成対応のグラフの定義より、
   $$ (a,c)\in R_{\Delta\circ\Gamma_2} $$
   である。よって、
   $$ R_{\Delta\circ\Gamma_1}\subseteq R_{\Delta\circ\Gamma_2} $$
   が成り立つ。
   したがって、
   $$ G(\Delta\circ\Gamma_1)\subseteq G(\Delta\circ\Gamma_2) $$
   である。

-ゆえに、対応の包含の定義より、
$$ \Delta\circ\Gamma_1\subseteq\Delta\circ\Gamma_2 $$
が成り立つ。
$$ \Box$$

ここで、$\Delta_1\circ\Gamma$ と $\Delta_2\circ\Gamma$ はいずれも $A$ から $C$ への対応である。
したがって、対応の包含を示すには、それぞれのグラフの包含を示せばよい。

1. 対応の包含の定義より、
   $$ \Delta_1\circ\Gamma\subseteq\Delta_2\circ\Gamma $$
   を示すには、
   $$ G(\Delta_1\circ\Gamma)\subseteq G(\Delta_2\circ\Gamma) $$
   を示せばよい。
   i) 合成対応の定義より、
   $$ \Delta_1\circ\Gamma=(A,C,R_{\Delta_1\circ\Gamma}) $$
   　 であり、
   $$ R_{\Delta_1\circ\Gamma} = \{(a,c)\in A\times C\mid \exists b\in B\ ((a,b)\in R\land(b,c)\in Q_1)\} $$
   　 である。
   ii) また、
   $$ \Delta_2\circ\Gamma=(A,C,R_{\Delta_2\circ\Gamma}) $$
   　 であり、
   $$ R_{\Delta_2\circ\Gamma} = \{(a,c)\in A\times C\mid \exists b\in B\ ((a,b)\in R\land(b,c)\in Q_2)\} $$
   　 である。
   対応のグラフの定義より、
   $$ G(\Delta_1\circ\Gamma)=R_{\Delta_1\circ\Gamma} $$
   かつ
   $$ G(\Delta_2\circ\Gamma)=R_{\Delta_2\circ\Gamma} $$
   である。
   $ $
2. したがって、
   $$ R_{\Delta_1\circ\Gamma}\subseteq R_{\Delta_2\circ\Gamma} $$
   を示せばよい。任意に
   $$ (a,c)\in R_{\Delta_1\circ\Gamma} $$
   をとる。
   合成対応のグラフの定義より、
   $$ (a,c)\in A\times C $$
   かつ、ある $b\in B$ が存在して、
   $$ (a,b)\in R\land(b,c)\in Q_1 $$
   が成り立つ。
   仮定より、
   $$ Q_1\subseteq Q_2 $$
   であるから、
   $$ (b,c)\in Q_2 $$
   である。したがって、
   $$ (a,b)\in R\land(b,c)\in Q_2 $$
   が成り立つ。
   ゆえに、合成対応のグラフの定義より、
   $$ (a,c)\in R_{\Delta_2\circ\Gamma} $$
   である。よって、
   $$ R_{\Delta_1\circ\Gamma}\subseteq R_{\Delta_2\circ\Gamma} $$
   が成り立つ。
   したがって、
   $$ G(\Delta_1\circ\Gamma)\subseteq G(\Delta_2\circ\Gamma) $$
   である。

-ゆえに、対応の包含の定義より、
$$ \Delta_1\circ\Gamma\subseteq\Delta_2\circ\Gamma $$
が成り立つ。
$$ \Box$$

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)\} $$
   である。
   したがって、再び合成対応の定義より、
   $$ \Theta\circ(\Delta\circ\Gamma) = (A,D,R_{\Theta\circ(\Delta\circ\Gamma)}) $$
   であり、
   $$ R_{\Theta\circ(\Delta\circ\Gamma)} = \{(a,d)\in A\times D\mid \exists c\in C\ ((a,c)\in R_{\Delta\circ\Gamma}\land(c,d)\in P)\} $$
   である。
   $ $
2. 一方、合成対応の定義より、
   $$ \Theta\circ\Delta=(B,D,R_{\Theta\circ\Delta}) $$
   であり、
   $$ R_{\Theta\circ\Delta} = \{(b,d)\in B\times D\mid \exists c\in C\ ((b,c)\in Q\land(c,d)\in P)\} $$
   である。
   したがって、再び合成対応の定義より、
   $$ (\Theta\circ\Delta)\circ\Gamma = (A,D,R_{(\Theta\circ\Delta)\circ\Gamma}) $$
   であり、
   $$ R_{(\Theta\circ\Delta)\circ\Gamma} = \{(a,d)\in A\times D\mid \exists b\in B\ ((a,b)\in R\land(b,d)\in R_{\Theta\circ\Delta})\} $$
   である。
   以上より、$\Theta\circ(\Delta\circ\Gamma)$ と $(\Theta\circ\Delta)\circ\Gamma$ はどちらも $A$ から $D$ への対応である。
   $ $
3. したがって、対応の相等の定義より、
   $$ R_{\Theta\circ(\Delta\circ\Gamma)} = R_{(\Theta\circ\Delta)\circ\Gamma} $$
   を示せばよい。
   外延性により、任意の順序対 $(a,d)$ に対して、
   $$ (a,d)\in R_{\Theta\circ(\Delta\circ\Gamma)} \Longleftrightarrow (a,d)\in R_{(\Theta\circ\Delta)\circ\Gamma} $$
   が成り立つことを示す。任意に $(a,d)$ をとる。
   $ $
4. まず、左辺を展開する。
   $$ \begin{align} (a,d)\in R_{\Theta\circ(\Delta\circ\Gamma)} &\Longleftrightarrow (a,d)\in A\times D\land \exists c\in C\ ((a,c)\in R_{\Delta\circ\Gamma}\land(c,d)\in P)\\ &\Longleftrightarrow (a,d)\in A\times D\land \exists c\in C\Bigl( \exists b\in B\ ((a,b)\in R\land(b,c)\in Q) \land(c,d)\in P \Bigr)\\ &\Longleftrightarrow (a,d)\in A\times D\land \exists c\in C\exists b\in B\ ((a,b)\in R\land(b,c)\in Q\land(c,d)\in P)\\ &\Longleftrightarrow (a,d)\in A\times D\land \exists b\in B\exists c\in C\ ((a,b)\in R\land(b,c)\in Q\land(c,d)\in P)\cdots① \end{align} $$
   である。
   ここで、存在記号の順序は入れ替えてよい( 証明はコチラ )。すなわち、
   $$ \exists c\in C\exists b\in B\ \Phi(b,c) \Longleftrightarrow \exists b\in B\exists c\in C\ \Phi(b,c) $$
   を用いた。
   $ $
5. 次に、右辺を展開する。
   $$ \begin{align} (a,d)\in R_{(\Theta\circ\Delta)\circ\Gamma} &\Longleftrightarrow (a,d)\in A\times D\land \exists b\in B\ ((a,b)\in R\land(b,d)\in R_{\Theta\circ\Delta})\\ &\Longleftrightarrow (a,d)\in A\times D\land \exists b\in B\Bigl( (a,b)\in R\land \exists c\in C\ ((b,c)\in Q\land(c,d)\in P) \Bigr)\\ &\Longleftrightarrow (a,d)\in A\times D\land \exists b\in B\exists c\in C\ ((a,b)\in R\land(b,c)\in Q\land(c,d)\in P)\cdots② \end{align} $$
   である。
   $ $
6. 式① と 式② より、
   $$ (a,d)\in R_{\Theta\circ(\Delta\circ\Gamma)} \Longleftrightarrow (a,d)\in A\times D\land \exists b\in B\exists c\in C\ ((a,b)\in R\land(b,c)\in Q\land(c,d)\in P) $$
   かつ
   $$ (a,d)\in R_{(\Theta\circ\Delta)\circ\Gamma} \Longleftrightarrow (a,d)\in A\times D\land \exists b\in B\exists c\in C\ ((a,b)\in R\land(b,c)\in Q\land(c,d)\in P) $$
   である。したがって、
   $$ (a,d)\in R_{\Theta\circ(\Delta\circ\Gamma)} \Longleftrightarrow (a,d)\in R_{(\Theta\circ\Delta)\circ\Gamma} $$
   が成り立つ。
   $(a,d)$ は任意であったから、外延性により、
   $$ R_{\Theta\circ(\Delta\circ\Gamma)} = R_{(\Theta\circ\Delta)\circ\Gamma} $$
   である。

-したがって、対応の相等の定義より、
$$ \Theta\circ(\Delta\circ\Gamma)=(\Theta\circ\Delta)\circ\Gamma $$
が成り立つ。
$$ \Box$$