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

続いて「エレファントな整数論(20)」(の前半)の議論について考えます。

集合と写像

$f \in \mathfrak{P}(X \times Y)$ 、 $A \subseteq B \subseteq X$ のとき
$\begin{eqnarray*} \overline{f}(A) & = & \{ y \in Y \mid \exists x \in A (\langle x,y \rangle \in f)\} \\ & = & \{ y \in Y \mid \exists x \in A (\langle x,y \rangle \in f) \land \forall x \in X(x \in A \implies x \in B)\} \\ & \subseteq & \{ y \in Y \mid \exists x \in B (\langle x,y \rangle \in f)\} \\ & = & \overline{f}(B) \\ \end{eqnarray*}$
が成り立ちます。

$f: X \to Y$ 、 $A, B \subseteq X$ 、 $U, V \subseteq Y$ とします。 $f(A)$ 、 $f^{-1}(U)$ について以下のことが成り立ちます(これらは上記の記法では $\overline{f}(A)$ 、 $\overline{f^{-1}}(U)$ となり、以下このように書くこともあります)。

$f(A) = \{ y \in Y \mid \exists a \in A ( x = f(a) ) \}$
$f^{-1}(U) = \{ x \in X \mid f(x) \in U \}$

上記の $f \in \mathfrak{P}(X \times Y)$ の場合の結果から以下のことが成り立ちます。

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

まず、集合の演算の定義から以下のことが成り立ちます。

$A \cap B \subseteq A$
$A \cap B \subseteq B$
$A \subseteq C, A \subseteq D \implies A \subseteq C \cap D$
$A \subseteq A \cup B$
$B \subseteq A \cup B$
$A \subseteq C, B \subseteq C \implies A \cup B \subseteq C$

よって

(1') $f(A \cap B) \subseteq f(A) \cap f(B)$
(2') $f(A \cup B) \supseteq f(A) \cup f(B)$
(3') $f^{-1}(U \cap V) \subseteq f^{-1}(U) \cap f^{-1}(V)$
(4') $f^{-1}(U \cup V) \supseteq f^{-1}(U) \cup f^{-1}(V)$

が成り立ちます。

$f: X \to Y$ 、 $X$ の部分集合系 $(A_\lambda \mid \lambda \in \Lambda)$ 、 $Y$ の部分集合系 $(U_\mu \mid \mu \in M)$ に対して集合の演算の定義から以下が成り立ちます。

$\displaystyle B \subseteq \bigcap_{\lambda \in \Lambda} A_\lambda \iff \forall \lambda \in \Lambda ( B \subseteq A_\lambda )$
$\displaystyle \bigcup_{\mu \in M} U_\mu \subseteq V \iff \forall \mu \in M ( U_\mu \subseteq V )$

よって

(5') $\displaystyle f(\bigcap_{\lambda \in \Lambda} A_\lambda) \subseteq \bigcap_{\lambda \in \Lambda} f(A_\lambda)$
(6') $\displaystyle f(\bigcup_{\lambda \in \Lambda} A_\lambda) \supseteq \bigcup_{\lambda \in \Lambda} f(A_\lambda)$
(7') $\displaystyle f^{-1}(\bigcap_{\mu \in M} U_\mu) \subseteq \bigcap_{\mu \in M} f^{-1}(U_\mu)$
(8') $\displaystyle f^{-1}(\bigcup_{\mu \in M} U_\mu) \supseteq \bigcup_{\mu \in M} f^{-1}(U_\mu)$

が成り立ちます。

ここで再び $f \in \mathfrak{P}(X \times Y)$ の場合を考えると
$\begin{eqnarray*} \overline{f}(\bigcup_{\lambda \in \Lambda} A_\lambda) & = & \left\{ y \in Y \middle\vert \exists x \in X \left( \langle x,y \rangle \in f \land x \in \bigcup_{\lambda \in \Lambda} A_\lambda \right) \right\} \\ & = & \{ y \in Y \mid \exists x \in X ( \langle x,y \rangle \in f \land \exists \lambda \in \Lambda (x \in A_\lambda) ) \} \\ & = & \{ y \in Y \mid \exists x \in X ( \exists \lambda \in \Lambda ( \langle x,y \rangle \in f \land x \in A_\lambda ) ) \} \\ & = & \{ y \in Y \mid \exists \lambda \in \Lambda ( \exists x \in X ( \langle x,y \rangle \in f \land x \in A_\lambda ) ) \} \\ & = & \bigcup_{\lambda \in \Lambda} \{ y \in Y \mid \exists x \in X ( \langle x,y \rangle \in f \land x \in A_\lambda ) \} \\ & = & \bigcup_{\lambda \in \Lambda} \overline{f}(A_\lambda) \\ \end{eqnarray*}$
が成り立ちます。

よって

(2) $f(A \cup B) = f(A) \cup f(B)$
(4) $f^{-1}(U \cup V) = f^{-1}(U) \cup f^{-1}(V)$
(6) $\displaystyle f(\bigcup_{\lambda \in \Lambda} A_\lambda) = \bigcup_{\lambda \in \Lambda} f(A_\lambda)$
(8) $\displaystyle f^{-1}(\bigcup_{\mu \in M} U_\mu) = \bigcup_{\mu \in M} f^{-1}(U_\mu)$

が成り立ちます。

$f \in \mathcal{B}^-(X, Y)$ とし $A \subseteq X$ と $y \in Y$ をとります。
$\langle x_0,y \rangle \in f$ を満たす $x_0 \in A$ が存在するとすると、
$\langle x,y \rangle \in f$ を満たす $x \in X$ をとると $f \in \mathcal{B}^-(X, Y)$ であるから $x = x_0$ となり $x \in A$ となります。
よって $f \in \mathcal{B}^-(X, Y)$ ならば
$\begin{eqnarray*} & & \{ y \in Y \mid \exists x \in X ( \langle x,y \rangle \in f \land x \in A ) \} \\ & \subseteq & \{ y \in Y \mid \forall x \in X ( \langle x,y \rangle \in f \implies x \in A ) \} \\ \end{eqnarray*}$
が成り立ちます。

$f \in \mathcal{B}^+(X, Y)$ とし $A \subseteq X$ と $y \in Y$ をとります。
$\langle x,y \rangle \in f$ を満たす $x \in X$ は $x \in A$ を満たすとします。
$f \in \mathcal{B}^+(X, Y)$ であるから $\langle x_0,y \rangle \in f$ を満たす $x_0 \in X$ が存在します。
$x_0 \in A$ となります。
よって $f \in \mathcal{B}^+(X, Y)$ ならば
$\begin{eqnarray*} & & \{ y \in Y \mid \exists x \in X ( \langle x,y \rangle \in f \land x \in A ) \} \\ & \supseteq & \{ y \in Y \mid \forall x \in X ( \langle x,y \rangle \in f \implies x \in A ) \} \\ \end{eqnarray*}$
が成り立ちます。

よって $f \in \mathcal{B}(X, Y)$ ならば
$\begin{eqnarray*} & & \{ y \in Y \mid \exists x \in X ( \langle x,y \rangle \in f \land x \in A ) \} \\ & = & \{ y \in Y \mid \forall x \in X ( \langle x,y \rangle \in f \implies x \in A ) \} \\ \end{eqnarray*}$
が成り立ちます。

よって
$\begin{eqnarray*} \overline{f}(\bigcap_{\lambda \in \Lambda} A_\lambda) & = & \left\{ y \in Y \middle\vert \exists x \in X \left( \langle x,y \rangle \in f \land x \in \bigcap_{\lambda \in \Lambda} A_\lambda \right) \right\} \\ & = & \left\{ y \in Y \middle\vert \forall x \in X \left( \langle x,y \rangle \in f \implies x \in \bigcap_{\lambda \in \Lambda} A_\lambda \right) \right\} \\ & = & \{ y \in Y \mid \forall x \in X ( \langle x,y \rangle \in f \implies \forall \lambda \in \Lambda (x \in A_\lambda) ) \} \\ & = & \{ y \in Y \mid \forall x \in X ( \forall \lambda \in \Lambda ( \langle x,y \rangle \in f \implies x \in A_\lambda) ) \} \\ & = & \{ y \in Y \mid \forall \lambda \in \Lambda ( \forall x \in X ( \langle x,y \rangle \in f \implies x \in A_\lambda) ) \} \\ & = & \bigcap_{\lambda \in \Lambda} \{ y \in Y \mid \forall x \in X ( \langle x,y \rangle \in f \implies x \in A_\lambda) \} \\ & = & \bigcap_{\lambda \in \Lambda} \{ y \in Y \mid \exists x \in X ( \langle x,y \rangle \in f \land x \in A_\lambda) \} \\ & = & \bigcap_{\lambda \in \Lambda} \overline{f}(A_\lambda) \\ \end{eqnarray*}$
が成り立ちます。

よって

(3) $f^{-1}(U \cap V) = f^{-1}(U) \cap f^{-1}(V)$
(7) $\displaystyle f^{-1}(\bigcap_{\mu \in M} U_\mu) = \bigcap_{\mu \in M} f^{-1}(U_\mu)$

が成り立ちます。

以上をまとめると以下のことが成り立ちます。(「集合と位相」定理5.2、問5.4 を参照)

(1) $f(A \cap B) \subseteq f(A) \cap f(B)$
(2) $f(A \cup B) = f(A) \cup f(B)$
(3) $f^{-1}(U \cap V) = f^{-1}(U) \cap f^{-1}(V)$
(4) $f^{-1}(U \cup V) = f^{-1}(U) \cup f^{-1}(V)$
(5) $\displaystyle f(\bigcap_{\lambda \in \Lambda} A_\lambda) \subseteq \bigcap_{\lambda \in \Lambda} f(A_\lambda)$
(6) $\displaystyle f(\bigcup_{\lambda \in \Lambda} A_\lambda) = \bigcup_{\lambda \in \Lambda} f(A_\lambda)$
(7) $\displaystyle f^{-1}(\bigcap_{\mu \in M} U_\mu) = \bigcap_{\mu \in M} f^{-1}(U_\mu)$
(8) $\displaystyle f^{-1}(\bigcup_{\mu \in M} U_\mu) = \bigcup_{\mu \in M} f^{-1}(U_\mu)$