集合の計算(5) - エレファント・コンピューティング調査報告

前回の議論を $f \in \mathfrak{P}(X \times Y)$ の場合について考えます。

$f \in \mathfrak{P}(X \times Y)$ 、 $A \subseteq X$ 、 $U \subseteq Y$ のとき

$\overline{f}(A) = \{ y \in Y \mid \exists x \in X (\langle x,y \rangle \in f \land x \in A) \}$
$\overline{f^{-1}}(U) = \{ x \in X \mid \exists y \in Y (\langle x,y \rangle \in f \land y \in U) \}$

と定義します。定義より $A \subseteq X$ 、 $B \subseteq X$ 、 $U \subseteq Y$ 、 $V \subseteq Y$ に対して

$A \subseteq B \implies \overline{f}(A) \subseteq \overline{f}(B)$
$U \subseteq V \implies \overline{f^{-1}}(U) \subseteq \overline{f^{-1}}(V)$

が成り立ちます。

$f \in \mathfrak{P}(X \times Y)$ 、 $a \in X$ 、 $x \in X$ 、 $A \subseteq X$ 、 $B \subseteq X$ 、 $u \in Y$ 、 $y \in Y$ 、 $U \subseteq Y$ 、 $V \subseteq Y$ とするとき
$\begin{eqnarray*} \overline{f}(\{a\}) & = & \{ y \in Y \mid \exists x \in X (\langle x,y \rangle \in f \land x \in \{a\}) \} \\ & = & \{ y \in Y \mid \langle a,y \rangle \in f \} \end{eqnarray*}$
$\begin{eqnarray*} \overline{f^{-1}}(\{u\}) & = & \{ x \in X \mid \exists y \in Y (\langle x,y \rangle \in f \land y \in \{u\}) \} \\ & = & \{ x \in X \mid \langle x,u \rangle \in f \} \end{eqnarray*}$
となって
$y \in \overline{f}(\{x\}) \iff \langle x,y \rangle \in f \iff x \in \overline{f^{-1}}(\{y\})$
が成り立ちます。

$f \in \mathcal{M}(X, Y)$ ( $f$ が写像)のときは
$\overline{f}(\{x\}) \subseteq \{y\} \iff \overline{f}(\{x\}) = \{y\} \iff \overline{f}(\{x\}) \supseteq \{y\}$
であることから
$\overline{f}(\{x\}) = \{y\} \iff x \in \overline{f^{-1}}(\{y\})$
となるので
$\begin{eqnarray*} \overline{f}(\{x\}) \subseteq U & \iff & \exists y \in U (\overline{f}(\{x\}) = \{y\}) \\ & \iff & \exists y \in U (x \in \overline{f^{-1}}(\{y\})) \\ & \iff & x \in \overline{f^{-1}}(U) \end{eqnarray*}$
が成り立ちます。

$A(\lambda)$ が $X$ の部分集合( $\lambda \in \Lambda$ )、 $p(\lambda)$ が $\lambda$ に関する条件のとき、 $\displaystyle \bigcup_{\lambda \in \Lambda} \{ x \in A(\lambda) \mid p(\lambda) \} = \{ x \in X \mid \exists \lambda \in \Lambda ( x \in A(\lambda) \land p(\lambda) ) \}$ を $\{ A(\lambda) \mid \mid p(\lambda) \}$ と書くことにします。

前回の (1) から (8) までを書き直します。

$f \in \mathfrak{P}(X \times Y)$ 、 $A \subseteq X$ 、 $B \subseteq X$ 、 $U \subseteq Y$ 、 $V \subseteq Y$ 、 $X$ の部分集合系 $(A_\lambda \mid \lambda \in \Lambda)$ 、 $Y$ の部分集合系 $(U_\mu \mid \mu \in M)$ に対して以下が成り立ちます。

(1) $\overline{f}(A \cap B) \subseteq \overline{f}(A) \cap \overline{f}(B)$

[証明]
$\begin{eqnarray*} & & (A \cap B \subseteq A) \land (A \cap B \subseteq B) \\ & \implies & (\overline{f}(A \cap B) \subseteq \overline{f}(A)) \land (\overline{f}(A \cap B) \subseteq \overline{f}(B)) \\ & \implies & \overline{f}(A \cap B) \subseteq \overline{f}(A) \cap \overline{f}(B) \\ \end{eqnarray*}$
[証明終わり]

(2) $\overline{f}(A \cup B) = \overline{f}(A) \cup \overline{f}(B)$

[証明]
$\begin{eqnarray*} \overline{f}(A \cup B) & = & \{ \overline{f}(x) \mid \mid x \in A \cup B \} \\ & = & \{ \overline{f}(x) \mid \mid x \in A \lor x \in B \} \\ & = & \{ \overline{f}(x) \mid \mid x \in A \} \cup \{ \overline{f}(x) \mid \mid x \in B \}\\ & = & \overline{f}(A) \cup \overline{f}(B) \\ \end{eqnarray*}$
[証明終わり]

(3) $f \in \mathcal{M}(X, Y) \implies \overline{f^{-1}}(U \cap V) = \overline{f^{-1}}(U) \cap \overline{f^{-1}}(V)$

[証明]
$\begin{eqnarray*} \overline{f^{-1}}(U \cap V) & = & \{ x \in X \mid \overline{f}(\{x\}) \subseteq U \cap V \} \\ & = & \{ x \in X \mid \overline{f}(\{x\}) \subseteq U \land \overline{f}(\{x\}) \subseteq V \} \\ & = & \{ x \in X \mid x \in \overline{f^{-1}}(U) \land x \in \overline{f^{-1}}(V) \} \\ & = & \overline{f^{-1}}(U) \cap \overline{f^{-1}}(V) \\ \end{eqnarray*}$
[証明終わり]

(4) $\overline{f^{-1}}(U \cup V) = \overline{f^{-1}}(U) \cup \overline{f^{-1}}(V)$

[証明]
$\begin{eqnarray*} \overline{f^{-1}}(U \cup V) & = & \{ \overline{f^{-1}}(y) \mid \mid y \in U \cup V \} \\ & = & \{ \overline{f^{-1}}(y) \mid \mid y \in U \lor y \in V \} \\ & = & \{ \overline{f^{-1}}(y) \mid \mid y \in U \} \cup \{ \overline{f^{-1}}(y) \mid \mid y \in V \}\\ & = & \overline{f^{-1}}(U) \cup \overline{f^{-1}}(V) \\ \end{eqnarray*}$
[証明終わり]

(5) $\displaystyle \overline{f}(\bigcap_{\lambda \in \Lambda} A_\lambda) \subseteq \bigcap_{\lambda \in \Lambda} \overline{f}(A_\lambda)$

[証明]
$\begin{eqnarray*} & & \forall \lambda \in \Lambda \left( \bigcap_{\lambda \in \Lambda} A_\lambda \subseteq A_\lambda \right) \\ & \implies & \forall \lambda \in \Lambda \left( \overline{f}(\bigcap_{\lambda \in \Lambda} A_\lambda) \subseteq \overline{f}(A_\lambda) \right) \\ & \implies & \overline{f}(\bigcap_{\lambda \in \Lambda} A_\lambda) \subseteq \bigcap_{\lambda \in \Lambda} \overline{f}(A_\lambda) \\ \end{eqnarray*}$
[証明終わり]

(6) $\displaystyle \overline{f}(\bigcup_{\lambda \in \Lambda} A_\lambda) = \bigcup_{\lambda \in \Lambda} \overline{f}(A_\lambda)$

[証明]
$\begin{eqnarray*} \overline{f}(\bigcup_{\lambda \in \Lambda} A_\lambda) & = & \left\{ \overline{f}(x) \middle\vert \middle\vert x \in \bigcup_{\lambda \in \Lambda} A_\lambda \right\} \\ & = & \{ \overline{f}(x) \mid \mid \exists \lambda \in \Lambda (x \in A_\lambda) \} \\ & = & \bigcup_{\lambda \in \Lambda} \{ \overline{f}(x) \mid \mid x \in A_\lambda \} \\ & = & \bigcup_{\lambda \in \Lambda} \overline{f}(A_\lambda) \\ \end{eqnarray*}$
[証明終わり]

(7) $\displaystyle f \in \mathcal{M}(X, Y) \implies \overline{f^{-1}}(\bigcap_{\mu \in M} U_\mu) = \bigcap_{\mu \in M} \overline{f^{-1}}(U_\mu)$

[証明]
$\begin{eqnarray*} \overline{f^{-1}}(\bigcap_{\mu \in M} U_\mu) & = & \left\{ x \middle\vert \overline{f}(\{x\}) \subseteq \bigcap_{\mu \in M} U_\mu \right\} \\ & = & \{ x \mid \forall \mu \in M (\overline{f}(\{x\}) \subseteq U_\mu) \} \\ & = & \{ x \mid \forall \mu \in M (x \in \overline{f^{-1}}(U_\mu)) \} \\ & = & \bigcap_{\mu \in M} \overline{f^{-1}}(U_\mu) \\ \end{eqnarray*}$
[証明終わり]

(8) $\displaystyle \overline{f^{-1}}(\bigcup_{\mu \in M} U_\mu) = \bigcup_{\mu \in M} \overline{f^{-1}}(U_\mu)$

[証明]
$\begin{eqnarray*} \overline{f^{-1}}(\bigcup_{\mu \in M} U_\mu) & = & \left\{ \overline{f^{-1}}(x) \middle\vert \middle\vert x \in \bigcup_{\mu \in M} U_\mu \right\} \\ & = & \{ \overline{f^{-1}}(x) \mid \mid \exists \mu \in M (x \in U_\mu) \} \\ & = & \bigcup_{\mu \in M} \{ \overline{f^{-1}}(x) \mid \mid x \in U_\mu \} \\ & = & \bigcup_{\mu \in M} \overline{f^{-1}}(U_\mu) \\ \end{eqnarray*}$
[証明終わり]