対応 ③

Prop&Proof

対応の定義域の定義より、
$$ \operatorname{dom}(\Gamma) = \{a\in A\mid \Gamma(a)\ne\varnothing\} $$
である。
任意に $x\in\operatorname{dom}(\Gamma)$ をとる。
このとき、内包表記の定義より、
$$ x\in A\land \Gamma(x)\ne\varnothing $$
が成り立つ。
したがって、特に
$$ x\in A $$
である。
ゆえに、任意の $x\in\operatorname{dom}(\Gamma)$ に対して $x\in A$ が成り立つ。
したがって、部分集合の定義より、
$$ \operatorname{dom}(\Gamma)\subseteq A $$
である。
$$ \Box$$

対応の値域の定義より、
$$ \operatorname{ran}(\Gamma) = \{b\in B\mid \exists a\in A\ ((a,b)\in R)\} $$
である。
$\operatorname{ran}(\Gamma)\subseteq B$ を示す。任意に $x\in\operatorname{ran}(\Gamma)$ をとる。
このとき、値域の定義より、
$$ x\in B\land \exists a\in A\ ((a,x)\in R) $$
が成り立つ。
したがって、特に
$$ x\in B $$
である。
ゆえに、任意の $x\in\operatorname{ran}(\Gamma)$ に対して $x\in B$ が成り立つ。
したがって、部分集合の定義より、
$$ \operatorname{ran}(\Gamma)\subseteq B $$
である。
$$ \Box$$

対応の値域の定義より、
$$ \operatorname{ran}(\Gamma) = \{b\in B\mid \exists a\in A\ ((a,b)\in R)\} $$
である。
また、集合の像の定義より、
$$ \Gamma(A) = \{b\in B\mid \exists a\in A\ ((a,b)\in R)\} $$
である。
したがって、両者は同じ集合であるから、
$$ \operatorname{ran}(\Gamma)=\Gamma(A) $$
が成り立つ。
$$ \Box$$

1. $\operatorname{ran}(\Gamma)=\varnothing\Longrightarrow\operatorname{dom}(\Gamma)=\varnothing$ を示す。
   $\operatorname{ran}(\Gamma)=\varnothing$ と仮定する。$\operatorname{dom}(\Gamma)=\varnothing$ を示す。
   背理法で示すために、
   $$ \operatorname{dom}(\Gamma)\ne\varnothing $$
   と仮定する。
   このとき、対応の定義域の定義より、ある $a\in A$ が存在して、
   $$ \Gamma(a)\ne\varnothing $$
   が成り立つ。
   したがって、ある $b$ が存在して、
   $$ b\in\Gamma(a) $$
   が成り立つ。
   対応の値の定義より、
   $$ b\in\Gamma(a) \Longleftrightarrow b\in B\land (a,b)\in R $$
   であるから、
   $$ b\in B\land (a,b)\in R $$
   が成り立つ。
   よって、値域の定義より、
   $$ b\in\operatorname{ran}(\Gamma) $$
   である。これは、
   $$ \operatorname{ran}(\Gamma)=\varnothing $$
   に矛盾する。したがって、
   $$ \operatorname{dom}(\Gamma)=\varnothing $$
   である。
   $ $
2. $\operatorname{dom}(\Gamma)=\varnothing\Longrightarrow\operatorname{ran}(\Gamma)=\varnothing$ を示す。
   $\operatorname{dom}(\Gamma)=\varnothing$ と仮定する。$\operatorname{ran}(\Gamma)=\varnothing$ を示す。
   背理法で示すために、
   $$ \operatorname{ran}(\Gamma)\ne\varnothing $$
   と仮定する。
   このとき、$\operatorname{ran}(\Gamma)\ne\varnothing$ より、ある $b$ が存在して、
   $$ b\in\operatorname{ran}(\Gamma) $$
   が成り立つ。値域の定義より、
   $$ b\in B\land \exists a\in A\ ((a,b)\in R) $$
   が成り立つ。
   したがって、ある $a\in A$ が存在して、
   $$ (a,b)\in R $$
   が成り立つ。
   したがって、対応の値の定義より、
   $$ b\in\Gamma(a) $$
   である。ゆえに、
   $$ \Gamma(a)\ne\varnothing $$
   である。
   よって、対応の定義域の定義より、
   $$ a\in\operatorname{dom}(\Gamma) $$
   である。これは、
   $$ \operatorname{dom}(\Gamma)=\varnothing $$
   に矛盾する。したがって、
   $$ \operatorname{ran}(\Gamma)=\varnothing $$
   である。

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

1. $\Gamma(S)=\varnothing\Longrightarrow S\subseteq A\setminus\operatorname{dom}(\Gamma)$ を示す。
   $\Gamma(S)=\varnothing$ と仮定する。$S\subseteq A\setminus\operatorname{dom}(\Gamma)$ を示す。
   任意に $a\in S$ をとる。$S\subseteq A$ であるから、
   $$ a\in A $$
   である。次に、
   $$ a\notin\operatorname{dom}(\Gamma) $$
   を示す。
   背理法のために、
   $$ a\in\operatorname{dom}(\Gamma) $$
   と仮定する。
   対応の定義域の定義より、
   $$ \Gamma(a)\ne\varnothing $$
   である。
   したがって、ある $b$ が存在して、
   $$ b\in\Gamma(a) $$
   が成り立つ。対応の値の定義より、
   $$ b\in B\land (a,b)\in R $$
   である。いま $a\in S$ であるから、
   $$ \exists x\in S\ ((x,b)\in R) $$
   が成り立つ。
   したがって、集合の像の定義より、
   $$ b\in\Gamma(S) $$
   である。しかし、仮定より、
   $$ \Gamma(S)=\varnothing $$
   であるから、
   $$ b\in\varnothing $$
   となる。これは矛盾である。
   したがって、
   $$ a\notin\operatorname{dom}(\Gamma) $$
   である。ゆえに、
   $$ a\in A\setminus\operatorname{dom}(\Gamma) $$
   である。
   $a\in S$ は任意であったから、
   $$ S\subseteq A\setminus\operatorname{dom}(\Gamma) $$
   が成り立つ。
   $ $
2. $S\subseteq A\setminus\operatorname{dom}(\Gamma)\Longrightarrow \Gamma(S)=\varnothing$ を示す。
   $S\subseteq A\setminus\operatorname{dom}(\Gamma)$ と仮定する。$\Gamma(S)=\varnothing$ を示す。
   背理法のために、
   $$ \Gamma(S)\ne\varnothing $$
   と仮定する。このとき、ある $b$ が存在して、
   $$ b\in\Gamma(S) $$
   が成り立つ。集合の像の定義より、
   $$ b\in B\land \exists a\in S\ ((a,b)\in R) $$
   である。
   したがって、ある $a\in S$ が存在して、
   $$ (a,b)\in R $$
   が成り立つ。また、$S\subseteq A$ であるから、
   $$ a\in A $$
   である。よって、$a\in A$、$b\in B$、$(a,b)\in R$ であるから、
   対応の値の定義より、
   $$ b\in\Gamma(a) $$
   である。したがって、
   $$ \Gamma(a)\ne\varnothing $$
   である。
   また、$a\in S$ かつ $S\subseteq A$ であるから、
   $$ a\in A $$
   である。よって、対応の定義域の定義より、
   $$ a\in\operatorname{dom}(\Gamma) $$
   である。
   一方、$a\in S$ かつ $S\subseteq A\setminus\operatorname{dom}(\Gamma)$ であるから、
   $$ a\in A\setminus\operatorname{dom}(\Gamma) $$
   である。したがって、
   $$ a\notin\operatorname{dom}(\Gamma) $$
   である。これは、
   $$ a\in\operatorname{dom}(\Gamma) $$
   に矛盾する。したがって、
   $$ \Gamma(S)=\varnothing $$
   である。

-以上より、
$$ \Gamma(S)=\varnothing \Longleftrightarrow S\subseteq A\setminus\operatorname{dom}(\Gamma) $$
が成り立つ。
$$ \Box$$

対応の定義域の定義より、
$$ \operatorname{dom}(\Gamma)\subseteq A $$
であり(冒頭でも証明済み)、$S\subseteq A$ であるから、
$$ S\cap\operatorname{dom}(\Gamma)\subseteq A $$
である。したがって、$\Gamma(S\cap\operatorname{dom}(\Gamma))$ は定義される。

1. $\Gamma(S)\subseteq\Gamma(S\cap\operatorname{dom}(\Gamma))$ を示す。
   任意に $b\in\Gamma(S)$ をとる。
   集合の像の定義より、
   $$ b\in B\land\exists a\in S\ ((a,b)\in R) $$
   である。
   したがって、ある $a\in S$ が存在して、
   $$ (a,b)\in R $$
   が成り立つ。
   また、$S\subseteq A$ であるから、
   $$ a\in A $$
   である。
   いま、$b\in B$ かつ $(a,b)\in R$ であるから、
   定義域の定義より、
   $$ a\in\operatorname{dom}(\Gamma) $$
   である。したがって、
   $$ a\in S\cap\operatorname{dom}(\Gamma) $$
   である。
   よって、集合の像の定義より、
   $$ b\in\Gamma(S\cap\operatorname{dom}(\Gamma)) $$
   である。ゆえに、
   $$ \Gamma(S)\subseteq\Gamma(S\cap\operatorname{dom}(\Gamma)) $$
   である。
   $ $
2. $\Gamma(S\cap\operatorname{dom}(\Gamma))\subseteq\Gamma(S)$ を示す。
   任意に $b\in\Gamma(S\cap\operatorname{dom}(\Gamma))$ をとる。
   集合の像の定義より、
   $$ b\in B\land\exists a\in S\cap\operatorname{dom}(\Gamma)\ ((a,b)\in R) $$
   である。
   したがって、ある $a\in S\cap\operatorname{dom}(\Gamma)$ が存在して、
   $$ (a,b)\in R $$
   が成り立つ。このとき、
   $$ a\in S\cap\operatorname{dom}(\Gamma) $$
   であるから、特に
   $$ a\in S $$
   である。
   よって、集合の像の定義より、
   $$ b\in\Gamma(S) $$
   である。したがって、
   $$ \Gamma(S\cap\operatorname{dom}(\Gamma))\subseteq\Gamma(S) $$
   である。

-以上より、
$$ \Gamma(S)\subseteq\Gamma(S\cap\operatorname{dom}(\Gamma)) \ \text{かつ}\ \Gamma(S\cap\operatorname{dom}(\Gamma))\subseteq\Gamma(S) $$
である。
したがって、外延性により、
$$ \Gamma(S)=\Gamma(S\cap\operatorname{dom}(\Gamma)) $$
が成り立つ。
$$ \Box$$

まず、対応の定義域の定義より、
$$ \operatorname{dom}(\Gamma)\subseteq A $$
である(冒頭でも証明済み)。
したがって、$\Gamma(\operatorname{dom}(\Gamma))$ は定義される。

1. $\operatorname{ran}(\Gamma)\subseteq\Gamma(\operatorname{dom}(\Gamma))$ を示す。
   任意に $b\in\operatorname{ran}(\Gamma)$ をとる。
   値域の定義より、
   $$ b\in B\land\exists a\in A\ ((a,b)\in R) $$
   である。
   したがって、ある $a\in A$ が存在して、
   $$ (a,b)\in R $$
   が成り立つ。
   いま、$b\in B$ であるから、定義域の定義より、
   $$ a\in\operatorname{dom}(\Gamma) $$
   である。よって、
   $$ b\in B\land\exists a\in\operatorname{dom}(\Gamma)\ ((a,b)\in R) $$
   が成り立つ。
   したがって、集合の像の定義より、
   $$ b\in\Gamma(\operatorname{dom}(\Gamma)) $$
   である。ゆえに、
   $$ \operatorname{ran}(\Gamma)\subseteq\Gamma(\operatorname{dom}(\Gamma)) $$
   である。
   $ $
2. $\Gamma(\operatorname{dom}(\Gamma))\subseteq\operatorname{ran}(\Gamma)$ を示す。
   任意に $b\in\Gamma(\operatorname{dom}(\Gamma))$ をとる。
   集合の像の定義より、
   $$ b\in B\land\exists a\in\operatorname{dom}(\Gamma)\ ((a,b)\in R) $$
   である。
   したがって、ある $a\in\operatorname{dom}(\Gamma)$ が存在して、
   $$ (a,b)\in R $$
   が成り立つ。
   また、$\operatorname{dom}(\Gamma)\subseteq A$ であるから、
   $$ a\in A $$
   である。よって、
   $$ b\in B\land\exists a\in A\ ((a,b)\in R) $$
   が成り立つ。
   したがって、値域の定義より、
   $$ b\in\operatorname{ran}(\Gamma) $$
   である。ゆえに、
   $$ \Gamma(\operatorname{dom}(\Gamma))\subseteq\operatorname{ran}(\Gamma) $$
   である。

-以上より、
$$ \operatorname{ran}(\Gamma)\subseteq\Gamma(\operatorname{dom}(\Gamma)) \ \text{かつ}\ \Gamma(\operatorname{dom}(\Gamma))\subseteq\operatorname{ran}(\Gamma) $$
である。
したがって、外延性により、
$$ \operatorname{ran}(\Gamma)=\Gamma(\operatorname{dom}(\Gamma)) $$
が成り立つ。
$$ \Box$$