対応 ⑦

Prop&Proof

空集合は任意の集合の部分集合である( 証明はコチラ )から、
$$ \varnothing\subseteq A $$
である。
したがって、対応の制限の定義より、$\Gamma$ の $\varnothing$ への制限を考えることができる。
制限の定義より、
$$ R|_{\varnothing} = R\cap(\varnothing\times B) $$
であり、
$$ \Gamma|_{\varnothing} = (\varnothing,B,R|_{\varnothing}) $$
である。ここで、
$$ \varnothing\times B=\varnothing $$
である( 証明はコチラ )から、
$$ R|_{\varnothing} = R\cap\varnothing = \varnothing $$
である( 証明はコチラ )。したがって、
$$ \Gamma|_{\varnothing} = (\varnothing,B,\varnothing) $$
である。

1. $\operatorname{dom}(\Gamma|_{\varnothing})=\varnothing$ を示す。
   $\Gamma|_{\varnothing}=(\varnothing,B,\varnothing)$ であるから、定義域の定義より、
   $$ \operatorname{dom}(\Gamma|_{\varnothing}) = \{x\in\varnothing\mid \exists b\in B\ ((x,b)\in\varnothing)\} $$
   である。
   右辺は $\varnothing$ の部分集合であるから、
   $$ \operatorname{dom}(\Gamma|_{\varnothing})\subseteq\varnothing $$
   である。
   また、空集合は任意の集合の部分集合である( 証明はコチラ )から、
   $$ \varnothing\subseteq\operatorname{dom}(\Gamma|_{\varnothing}) $$
   である。
   ゆえに、両包含より、
   $$ \operatorname{dom}(\Gamma|_{\varnothing})=\varnothing $$
   である。
   $ $
2. $\operatorname{ran}(\Gamma|_{\varnothing})=\varnothing$ を示す。
   $\Gamma|_{\varnothing}=(\varnothing,B,\varnothing)$ であるから、値域の定義より、
   $$ \operatorname{ran}(\Gamma|_{\varnothing}) = \{b\in B\mid \exists x\in\varnothing\ ((x,b)\in\varnothing)\} $$
   である。
   任意に $b\in\operatorname{ran}(\Gamma|_{\varnothing})$ をとる。
   このとき、値域の定義より、
   $$ \exists x\in\varnothing\ ((x,b)\in\varnothing) $$
   が成り立つ。
   しかし、$\varnothing$ には元が存在しないため、これは矛盾である。
   したがって、$\operatorname{ran}(\Gamma|_{\varnothing})$ には元が存在しない( 証明はコチラ )。
   ゆえに、
   $$ \operatorname{ran}(\Gamma|_{\varnothing})\subseteq\varnothing $$
   である。
   また、空集合は任意の集合の部分集合である( 証明はコチラ )から、
   $$ \varnothing\subseteq\operatorname{ran}(\Gamma|_{\varnothing}) $$
   である。
   ゆえに、両包含より、
   $$ \operatorname{ran}(\Gamma|_{\varnothing})=\varnothing $$
   である。
   $ $
3. $G(\Gamma|_{\varnothing})=\varnothing$ を示す。
   $\Gamma|_{\varnothing}=(\varnothing,B,\varnothing)$ であるから、対応のグラフの定義より、
   $$ G(\Gamma|_{\varnothing})=\varnothing $$
   である。

-以上より、
$$ \operatorname{dom}(\Gamma|_{\varnothing})=\varnothing, \quad \operatorname{ran}(\Gamma|_{\varnothing})=\varnothing, \quad G(\Gamma|_{\varnothing})=\varnothing $$
が成り立つ。
$$ \Box$$

1. $S\subseteq A$ であるから、
   $$ S\times B\subseteq A\times B $$
   である( 証明はコチラ )。
   また、$\Gamma=(A,B,R)$ は $A$ から $B$ への対応であるから、
   $$ R\subseteq A\times B $$
   である。
   制限の定義より、
   $$ R|_S:=R\cap(S\times B) $$
   であり、
   $$ \Gamma|_S=(S,B,R|_S) $$
   である。このとき、
   $$ R|_S\subseteq S\times B $$
   であるから、$\Gamma|_S$ は $S$ から $B$ への対応である。
   $ $
2. 対応のグラフの定義より、
   $$ G(\Gamma)=R $$
   であり、
   $$ G(\Gamma|_S)=R|_S $$
   である。
   したがって、
   $$ \begin{align} G(\Gamma|_S) &=R|_S\\ &=R\cap(S\times B)\\ &=G(\Gamma)\cap(S\times B) \end{align} $$
   である。

-ゆえに、
$$ G(\Gamma|_S)=G(\Gamma)\cap(S\times B) $$
が成り立つ。
$$ \Box$$

1. $\Gamma|_S\text{ が全域的}\Longrightarrow S\subseteq\operatorname{dom}(\Gamma)$ を示す。
   $\Gamma|_S$ が全域的であると仮定する。
   任意に $x\in S$ をとる。
   制限の定義より、
   $$ \Gamma|_S=(S,B,R|_S) $$
   であるから、$\Gamma|_S$ の始集合は $S$ である。
   $\Gamma|_S$ は全域的であるから、全域的対応の定義より、
   $$ \operatorname{dom}(\Gamma|_S)=S $$
   である。
   したがって、$x\in S$ より、
   $$ x\in\operatorname{dom}(\Gamma|_S) $$
   である。
   定義域の定義より、
   $$ x\in S \quad\text{かつ}\quad \exists b\in B\ ((x,b)\in R|_S) $$
   が成り立つ。
   ゆえに、ある $b\in B$ が存在して、
   $$ (x,b)\in R|_S $$
   である。制限の定義より、
   $$ R|_S=R\cap(S\times B) $$
   であるから、
   $$ (x,b)\in R $$
   が成り立つ。
   また、$x\in S\subseteq A$ であるから、
   $$ x\in A $$
   である。よって、定義域の定義より、
   $$ x\in\operatorname{dom}(\Gamma) $$
   である。
   $x\in S$ は任意であったから、
   $$ S\subseteq\operatorname{dom}(\Gamma) $$
   が成り立つ。
   $ $
2. $S\subseteq\operatorname{dom}(\Gamma)\Longrightarrow\Gamma|_S\text{ が全域的}$ を示す。
   $$ S\subseteq\operatorname{dom}(\Gamma) $$
   と仮定する。
   $\Gamma|_S$ が全域的であることを示すには、全域的対応の定義より、
   $$ \operatorname{dom}(\Gamma|_S)=S $$
   を示せばよい。
   i) まず、$\Gamma|_S=(S,B,R|_S)$ は $S$ から $B$ への対応であるから、
   $$ \operatorname{dom}(\Gamma|_S) = \{x\in S\mid \exists b\in B\ ((x,b)\in R|_S)\} $$
   　 である。したがって、
   $$ \operatorname{dom}(\Gamma|_S)\subseteq S $$
   　 である。
   $ $
   ii) 次に、
   $$ S\subseteq\operatorname{dom}(\Gamma|_S) $$
   　 を示す。
   　 任意に $x\in S$ をとる。仮定より、
   $$ x\in\operatorname{dom}(\Gamma) $$
   　 である。
   　 定義域の定義より、
   $$ x\in A \quad\text{かつ}\quad \exists b\in B\ ((x,b)\in R) $$
   　 が成り立つ。
   　 したがって、ある $b\in B$ が存在して、
   $$ (x,b)\in R $$
   　 である。
   　 また、$x\in S$ かつ $b\in B$ であるから、
   $$ (x,b)\in S\times B $$
   　 である。ゆえに、
   $$ (x,b)\in R\cap(S\times B) $$
   　 である。
   　 制限の定義より、
   $$ R|_S=R\cap(S\times B) $$
   　 であるから、
   $$ (x,b)\in R|_S $$
   　 である。
   　 したがって、定義域の定義より、
   $$ x\in\operatorname{dom}(\Gamma|_S) $$
   　 である。
   　 $x\in S$ は任意であったから、
   $$ S\subseteq\operatorname{dom}(\Gamma|_S) $$
   　 が成り立つ。
   以上より、
   $$ \operatorname{dom}(\Gamma|_S)=S $$
   である。
   したがって、$\Gamma|_S$ は全域的である。

-以上より、
$$ \Gamma|_S\text{ が全域的} \Longleftrightarrow S\subseteq\operatorname{dom}(\Gamma) $$
が成り立つ。
$$ \Box$$

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

1. 制限の定義より、
   $$ \Gamma|_S=(S,B,R|_S) $$
   であり、
   $$ R|_S=R\cap(S\times B) $$
   である。
   したがって、定義域の定義より、
   $$ x\in\operatorname{dom}(\Gamma|_S) \Longleftrightarrow x\in S\land \exists b\in B\ ((x,b)\in R|_S) $$
   である。
   ここで、$R|_S=R\cap(S\times B)$ であるから、
   $$ x\in\operatorname{dom}(\Gamma|_S) \Longleftrightarrow x\in S\land \exists b\in B\ ((x,b)\in R\cap(S\times B)) $$
   である。
   さらに、$x\in S$ かつ $b\in B$ ならば、
   $$ (x,b)\in S\times B $$
   である。
   したがって、
   $$ x\in S\land \exists b\in B\ ((x,b)\in R\cap(S\times B)) \Longleftrightarrow x\in S\land \exists b\in B\ ((x,b)\in R) $$
   が成り立つ。
   $ $
2. 一方、$\Gamma=(A,B,R)$ の定義域の定義より、
   $$ x\in\operatorname{dom}(\Gamma) \Longleftrightarrow x\in A\land \exists b\in B\ ((x,b)\in R) $$
   である。
   また、$S\subseteq A$ であるから、$x\in S$ ならば $x\in A$ である。
   ゆえに、
   $$ x\in S\land \exists b\in B\ ((x,b)\in R) \Longleftrightarrow x\in S\land x\in\operatorname{dom}(\Gamma) $$
   が成り立つ。
   したがって、
   $$ x\in S\land x\in\operatorname{dom}(\Gamma) \Longleftrightarrow x\in S\cap\operatorname{dom}(\Gamma) $$
   である。

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

外延性により、任意の $b$ に対して、
$$ b\in\operatorname{ran}(\Gamma|_S) \Longleftrightarrow b\in\Gamma(S) $$
が成り立つことを示せば十分である。
任意に $b$ をとる。

1. 制限の定義より、
   $$ \Gamma|_S=(S,B,R|_S) $$
   であり、
   $$ R|_S=R\cap(S\times B) $$
   である。
   したがって、値域の定義より、
   $$ \begin{align} b\in\operatorname{ran}(\Gamma|_S) &\Longleftrightarrow b\in B\land\exists x\in S\ ((x,b)\in R|_S)\\ &\Longleftrightarrow b\in B\land\exists x\in S\ ((x,b)\in R\cap(S\times B)) \end{align} $$
   である。
   ここで、$x\in S$ かつ $b\in B$ ならば、
   $$ (x,b)\in S\times B $$
   である。
   したがって、
   $$ b\in B\land\exists x\in S\ ((x,b)\in R\cap(S\times B)) \Longleftrightarrow b\in B\land\exists x\in S\ ((x,b)\in R) $$
   が成り立つ。
   $ $
2. 一方、集合の像の定義より、
   $$ \Gamma(S) = \{b\in B\mid \exists x\in S\ ((x,b)\in R)\} $$
   である。
   したがって、
   $$ b\in\Gamma(S) \Longleftrightarrow b\in B\land\exists x\in S\ ((x,b)\in R) $$
   である。

-以上より、
$$ b\in\operatorname{ran}(\Gamma|_S) \Longleftrightarrow b\in\Gamma(S) $$
が成り立つ。
$b$ は任意であったから、外延性により、
$$ \operatorname{ran}(\Gamma|_S)=\Gamma(S) $$
を得る。
$$ \Box$$

まず、$T\subseteq S\subseteq A$ より、$T\subseteq A$ である。
したがって、$\Gamma$ の $T$ への制限 $\Gamma|_T$ も定義できる。
$ $
制限の定義より、
$$ \Gamma|_S=(S,B,R|_S) $$
であり、
$$ R|_S=R\cap(S\times B) $$
である。

1. また、$T\subseteq S$ であるから、さらに制限をとることができ、
   $$ (\Gamma|_S)|_T=(T,B,(R|_S)|_T) $$
   である。
   ここで、制限の定義より、
   $$ (R|_S)|_T=R|_S\cap(T\times B) $$
   である。
   したがって、
   $$ \begin{align} (R|_S)|_T &= R|_S\cap(T\times B)\\ &= \bigl(R\cap(S\times B)\bigr)\cap(T\times B) \end{align} $$
   である。
   $ $
2. 一方、$T\subseteq S$ であるから、
   $$ T\times B\subseteq S\times B $$
   が成り立つ( 証明はコチラ )。
   ゆえに、
   $$ (S\times B)\cap(T\times B)=T\times B $$
   である。
   したがって、共通部分の結合法則( 証明はコチラ )と交換法則( 証明はコチラ )より、
   $$ \begin{align} (R|_S)|_T &= \bigl(R\cap(S\times B)\bigr)\cap(T\times B)\\ &= R\cap\bigl((S\times B)\cap(T\times B)\bigr)\\ &= R\cap(T\times B) \end{align} $$
   である。
   また、制限の定義より、
   $$ R|_T=R\cap(T\times B) $$
   である。
   したがって、
   $$ (R|_S)|_T=R|_T $$
   が成り立つ。

-以上より、
$$ (\Gamma|_S)|_T = (T,B,(R|_S)|_T) = (T,B,R|_T) = \Gamma|_T $$
である。ゆえに、
$$ (\Gamma|_S)|_T=\Gamma|_T $$
が成り立つ。
$$ \Box$$