対応 ⑧

Prop&Proof

外延性により、任意の $x$ に対して、
$$ x\in\operatorname{dom}(\widetilde{\Gamma})\cap A \Longleftrightarrow x\in\operatorname{dom}(\Gamma) $$
が成り立つことを示せば十分である。

1. 任意に $x$ をとる。
   まず、定義域の定義より、
   $$ \operatorname{dom}(\widetilde{\Gamma}) = \{x\in A'\mid \exists b\in B\ ((x,b)\in\widetilde R)\} $$
   である。
   したがって、共通部分の定義と定義域の定義より、
   $$ \begin{align} x\in\operatorname{dom}(\widetilde{\Gamma})\cap A &\Longleftrightarrow x\in\operatorname{dom}(\widetilde{\Gamma})\land x\in A\\ &\Longleftrightarrow (x\in A'\land \exists b\in B\ ((x,b)\in\widetilde R))\land x\in A \end{align} $$
   である。
   ここで、$A\subseteq A'$ であるから、$x\in A$ ならば $x\in A'$ である。
   よって、
   $$ x\in\operatorname{dom}(\widetilde{\Gamma})\cap A \Longleftrightarrow x\in A\land \exists b\in B\ ((x,b)\in\widetilde R) $$
   である。
   ここで、$x\in A$ かつ $b\in B$ ならば、
   $$ (x,b)\in A\times B $$
   である。
   したがって、$x\in A$ のもとで、任意の $b\in B$ に対して、
   $$ (x,b)\in\widetilde R \Longleftrightarrow (x,b)\in\widetilde R\cap(A\times B) $$
   が成り立つ。
   さらに、$\widetilde{\Gamma}$ は $\Gamma$ の $A'$ への拡張であるから、
   $$ \widetilde R\cap(A\times B)=R $$
   である。
   ゆえに、$x\in A$ のもとで、任意の $b\in B$ に対して、
   $$ (x,b)\in\widetilde R \Longleftrightarrow (x,b)\in R $$
   が成り立つ。
   したがって、
   $$ \begin{align} x\in\operatorname{dom}(\widetilde{\Gamma})\cap A &\Longleftrightarrow x\in A\land \exists b\in B\ ((x,b)\in\widetilde R)\\ &\Longleftrightarrow x\in A\land \exists b\in B\ ((x,b)\in R) \end{align} $$
   である。
   $ $
2. 一方、定義域の定義より、
   $$ \operatorname{dom}(\Gamma) = \{x\in A\mid \exists b\in B\ ((x,b)\in R)\} $$
   であるから、
   $$ x\in\operatorname{dom}(\Gamma) \Longleftrightarrow x\in A\land \exists b\in B\ ((x,b)\in R) $$
   である。

-以上より、
$$ x\in\operatorname{dom}(\widetilde{\Gamma})\cap A \Longleftrightarrow x\in\operatorname{dom}(\Gamma) $$
が成り立つ。
$x$ は任意であったから、外延性により、
$$ \operatorname{dom}(\widetilde{\Gamma})\cap A = \operatorname{dom}(\Gamma) $$
を得る。
$$ \Box$$

任意に
$$ b\in\operatorname{ran}(\Gamma) $$
をとる。
値域の定義より、
$$ \operatorname{ran}(\Gamma) = \{b\in B\mid \exists a\in A\ ((a,b)\in R)\} $$
であるから、
$$ b\in B \quad\text{かつ}\quad \exists a\in A\ ((a,b)\in R) $$
が成り立つ。
したがって、ある $a\in A$ が存在して、
$$ (a,b)\in R $$
である。
また、$A\subseteq A'$ であるから、
$$ a\in A' $$
である。
ここで、$\widetilde{\Gamma}$ は $\Gamma$ の $A'$ への拡張であるから、
$$ \widetilde R\cap(A\times B)=R $$
である。
したがって、$(a,b)\in R$ より、
$$ (a,b)\in\widetilde R\cap(A\times B) $$
である。ゆえに、
$$ (a,b)\in\widetilde R $$
である。
さらに、$a\in A'$ かつ $b\in B$ であるから、値域の定義より、
$$ b\in\operatorname{ran}(\widetilde{\Gamma}) $$
である。
以上より、任意の $b\in\operatorname{ran}(\Gamma)$ に対して、
$$ b\in\operatorname{ran}(\widetilde{\Gamma}) $$
が成り立つ。
したがって、
$$ \operatorname{ran}(\Gamma)\subseteq\operatorname{ran}(\widetilde{\Gamma}) $$
である。
$$ \Box$$

対応のグラフの定義より、
$$ G(\Gamma)=R $$
であり、
$$ G(\widetilde{\Gamma})=\widetilde R $$
である。
また、$\widetilde{\Gamma}$ は $\Gamma$ の $A'$ への拡張であるから、拡張の定義より、
$$ \widetilde R\cap(A\times B)=R $$
である。
ここで、一般に共通部分は各成分の部分集合であるから、
$$ \widetilde R\cap(A\times B)\subseteq \widetilde R $$
が成り立つ( 証明はコチラ )。
したがって、
$$ R\subseteq \widetilde R $$
である。ゆえに、
$$ G(\Gamma)\subseteq G(\widetilde{\Gamma}) $$
が成り立つ。
$$ \Box$$

1. $\widetilde{\Gamma}$ が $\Gamma$ の $A'$ への拡張であるならば、条件を満たす対応 $\Lambda$ が存在することを示す。
   $\widetilde{\Gamma}$ が $\Gamma$ の $A'$ への拡張であると仮定する。
   拡張の定義より、
   $$ \widetilde R\cap(A\times B)=R $$
   である。ここで、
   $$ L:=\widetilde R\cap((A'\setminus A)\times B) $$
   と定め、
   $$ \Lambda:=(A'\setminus A,B,L) $$
   とおく。このとき、
   $$ L\subseteq (A'\setminus A)\times B $$
   である( 証明はコチラ )から、$\Lambda$ は $A'\setminus A$ から $B$ への対応である。
   任意に $x\in A'$ をとる。
   i) $x\in A$ の場合。
   　 任意の $b\in B$ に対して、$x\in A$ かつ $b\in B$ であるから、
   $$ (x,b)\in A\times B $$
   　 である。したがって、
   $$ (x,b)\in\widetilde R \Longleftrightarrow (x,b)\in\widetilde R\cap(A\times B) $$
   　 である。
   　 拡張の定義より、
   $$ \widetilde R\cap(A\times B)=R $$
   　 であるから、
   $$ (x,b)\in\widetilde R \Longleftrightarrow (x,b)\in R $$
   　 である。ゆえに、
   $$ \begin{align} \widetilde{\Gamma}(x) &= \{b\in B\mid (x,b)\in\widetilde R\}\\ &= \{b\in B\mid (x,b)\in R\}\\ &= \Gamma(x) \end{align} $$
   　 である。
   $ $
   ii) $x\in A'\setminus A$ の場合。
   　 任意の $b\in B$ に対して、$x\in A'\setminus A$ かつ $b\in B$ であるから、
   $$ (x,b)\in (A'\setminus A)\times B $$
   　 である。したがって、
   $$ (x,b)\in\widetilde R \Longleftrightarrow (x,b)\in\widetilde R\cap((A'\setminus A)\times B) $$
   　 である。$L$ の定義より、
   $$ L=\widetilde R\cap((A'\setminus A)\times B) $$
   　 であるから、
   $$ (x,b)\in\widetilde R \Longleftrightarrow (x,b)\in L $$
   　 である。ゆえに、
   $$ \begin{align} \widetilde{\Gamma}(x) &= \{b\in B\mid (x,b)\in\widetilde R\}\\ &= \{b\in B\mid (x,b)\in L\}\\ &= \Lambda(x) \end{align} $$
   　 である。
   以上より、任意の $x\in A'$ に対して、
   $$ \widetilde{\Gamma}(x) = \begin{cases} \Gamma(x) & x\in A\\ \Lambda(x) & x\in A'\setminus A \end{cases} $$
   が成り立つ。
   $ $
2. 逆に、条件を満たす対応 $\Lambda$ が存在するならば、$\widetilde{\Gamma}$ が $\Gamma$ の $A'$ への拡張であることを示す。
   ある対応
   $$ \Lambda=(A'\setminus A,B,L) $$
   が存在して、任意の $x\in A'$ に対して
   $$ \widetilde{\Gamma}(x) = \begin{cases} \Gamma(x) & x\in A\\ \Lambda(x) & x\in A'\setminus A \end{cases} $$
   が成り立つと仮定する。
   $\widetilde{\Gamma}$ が $\Gamma$ の $A'$ への拡張であることを示すには、拡張の定義より、
   $$ \widetilde R\cap(A\times B)=R $$
   を示せばよい。
   i) まず、
   $$ \widetilde R\cap(A\times B)\subseteq R $$
   　 を示す。
   　 任意に $(x,b)\in\widetilde R\cap(A\times B)$ をとる。
   　 このとき、
   $$ (x,b)\in\widetilde R \quad\text{かつ}\quad (x,b)\in A\times B $$
   　 である。したがって、
   $$ x\in A \quad\text{かつ}\quad b\in B $$
   　 である。
   　 また、$(x,b)\in\widetilde R$ より、対応の値の定義から
   $$ b\in\widetilde{\Gamma}(x) $$
   　 である。仮定より、$x\in A$ に対して
   $$ \widetilde{\Gamma}(x)=\Gamma(x) $$
   　 であるから、
   $$ b\in\Gamma(x) $$
   　 である。
   　 対応の値の定義より、
   $$ (x,b)\in R $$
   　 である。ゆえに、
   $$ \widetilde R\cap(A\times B)\subseteq R $$
   　 が成り立つ。
   ii) 次に、
   $$ R\subseteq\widetilde R\cap(A\times B) $$
   　 を示す。任意に $(x,b)\in R$ をとる。
   　 $\Gamma=(A,B,R)$ は $A$ から $B$ への対応であるから、
   $$ R\subseteq A\times B $$
   　 である。したがって、
   $$ (x,b)\in A\times B $$
   　 である。特に、
   $$ x\in A \quad\text{かつ}\quad b\in B $$
   　 である。
   　 また、$(x,b)\in R$ より、対応の値の定義から
   $$ b\in\Gamma(x) $$
   　 である。
   　 仮定より、$x\in A$ に対して
   $$ \widetilde{\Gamma}(x)=\Gamma(x) $$
   　 であるから、
   $$ b\in\widetilde{\Gamma}(x) $$
   　 である。
   　 対応の値の定義より、
   $$ (x,b)\in\widetilde R $$
   　 である。さらに、
   $$ (x,b)\in A\times B $$
   　 であるから、
   $$ (x,b)\in\widetilde R\cap(A\times B) $$
   　 である。ゆえに、
   $$ R\subseteq\widetilde R\cap(A\times B) $$
   　 が成り立つ。
   以上より、
   $$ \widetilde R\cap(A\times B)=R $$
   である。
   したがって、$\widetilde{\Gamma}$ は $\Gamma$ の $A'$ への拡張である。

-以上より、$\widetilde{\Gamma}$ が $\Gamma$ の $A'$ への拡張であることと、ある対応
$$ \Lambda=(A'\setminus A,B,L) $$
が存在して、任意の $x\in A'$ に対して
$$ \widetilde{\Gamma}(x) = \begin{cases} \Gamma(x) & x\in A\\ \Lambda(x) & x\in A'\setminus A \end{cases} $$
が成り立つことは同値である。
$$ \Box$$