集合の計算(1) - エレファント・ビジュアライザー調査記録

前回の「多重集合・自由可換モノイド(7)」では数式の変形について考えましたが、これをわかりやすくするために図解する方法について考えていきます。

前回は「ある数式があって、その数式のある部分に写像を適用することによって集合の包含関係が得られる」ということの繰り返しによって求める包含関係を得る、ということをやっていました。「数式のある部分に写像を適用する」ということをビジュアル・プログラミングのような操作で行って、求める包含関係を得た後には、その操作の過程を見ることができるようにします。そのためにできるだけ集合の包含関係と写像で数式の変形を書くことができるようにします。

「エレファントな整数論(22)」で写像の性質について議論しました。これの図解のための議論をやってみたいと思います。これは以前もやろうと思っていたことですけどやっていないので、できるかどうかはわかりませんがやってみます。

論理式の記法

論理式については『論理と集合から始める数学の基礎』、『公理と証明証明論への招待 (ちくま学芸文庫)』を参照してください。また、『記号論理、命題論理入門：覚えるべき論理記号（否定、かつ、または、ならば、同値）とは | 趣味の大学数学』、『述語論理、量化子とは：全称記号（∀）と存在記号（∃）、数学における例と否定 | 趣味の大学数学』のサイトを参照してください。

以下の記法を使います。

$\land$ (かつ)
$\lor$ (または)
$\neg$ (否定)
$\implies$ (ならば)
$\iff$ (同値)
$\top$ (真)
$\bot$ (偽)
$\forall x (p(x))$ (変数 $x$ 、述語 $p(x)$ に対して「任意の $x$ に対して $p(x)$ が成り立つ」)
$\exists x (p(x))$ (変数 $x$ 、述語 $p(x)$ に対して「 $x$ が存在して $p(x)$ が成り立つ」)

集合の記法

以下の記法を使います。

$\cap$ (共通部分)
$\cup$ (和集合)
$\setminus$ (差集合)
$\in$ (元)
$\subseteq$ (部分集合)
$\varnothing$ (空集合)
$\mathfrak{P}(X)$ (集合 $X$ のべき集合)
$\times$ (集合の直積。 $X$ 、 $Y$ を集合とするとき、 $X \times Y$ は $X$ の元 $x$ と $Y$ の元 $y$ の組 $\langle x, y \rangle$ 全体の集合)
$+$ (集合の直和。 $X$ 、 $Y$ を集合とするとき、 $X + Y$ は $X$ と $Y$ の共通部分が空集合のとき $X$ の元 $x$ と $Y$ の元 $y$ 全体の集合)

これらの記法は集合に対してだけではなく、前回の「多重集合・自由可換モノイド(7)」で扱った「ある条件を満たす半環の全体」のようなものもこの記法を使ってもよいとします。このときの議論は公理的集合論ZFCに従うとします。

公理的集合論については『数学基礎論 Math＆Science (ちくま学芸文庫)』、『新装版集合とはなにか―はじめて学ぶ人のために (ブルーバックス)』を参照してください。また、『公理的集合論をわかりやすく解説：ZFC公理系を例に | 趣味の大学数学』のサイトを参照してください。

以下の記法も使います。

$\forall x \in X (p(x))$ (「任意の $x \in X$ に対して $p(x)$ が成り立つ」)
$\exists x \in X (p(x))$ (「 $x \in X$ が存在して $p(x)$ が成り立つ」)
$\bigcap_{x \in X} Y(x) = \{y \mid \forall x \in X (y \in Y(x))\}$ ( $Y(x)$ は変数 $x$ を含む式で書かれた集合)
$\bigcup_{x \in X} Y(x) = \{y \mid \exists x \in X (y \in Y(x))\}$ ( $Y(x)$ は変数 $x$ を含む式で書かれた集合)

写像

集合 $X, Y$ に関する「対応の規則」で、任意の $x \in X$ に対して $y \in Y$ が一意的に決まるものを集合 $X$ から集合 $Y$ への写像と呼びます。この「対応の規則」を $f$ とするとき $y$ を $f(x)$ と書きます。 $f$ が集合 $X$ から集合 $Y$ への写像であるとき $f: X \to Y$ と書きます。

これだけだと「対応の規則」とは何かというと写像のことなので、これを写像の定義と考えると定義が循環していて少しわかりにくいです。この状態を避けるためにまず「対応の規則」を $X \times Y$ の部分集合として定義しているものがあり、そのような本があったと思うのですが見つかりません。以下のようになります。

$X, Y$ を集合、 $f \subseteq X \times Y$ とします。任意の $x \in X$ に対して $\langle x,y \rangle \in f$ を満たす $y \in Y$ が一意的に決まるものを集合 $X$ から集合 $Y$ への写像と呼びます。この $y$ を $f(x)$ と書きます。 $f$ が集合 $X$ から集合 $Y$ への写像であるとき $f: X \to Y$ と書きます。集合 $X$ から集合 $Y$ への写像の全体を $\mathcal{M}(X,Y)$ とします。

$f \subseteq X \times Y$ 、 $g \subseteq X \times Y$ が写像のとき、任意の $x \in X$ に対して $f(x) = g(x)$ であることは $x = y$ であることと同値となります。

$\mathcal{S}^-(X) = \{S \in \mathfrak{P}(X) \mid \forall x \forall y (x \in S \land y \in S \implies x = y)\}$ ( $X$ の一元以下の部分集合の全体)
$\mathcal{S}^+(X) = \{S \in \mathfrak{P}(X) \mid \exists x (x \in S)\}$ ( $X$ の空ではない部分集合の全体)
$\mathcal{S}(X) = \mathcal{S}^-(X) \cap \mathcal{S}^+(X)$ ( $X$ の一元部分集合の全体)

とおきます。

$X, Y$ を集合とし、 $f \subseteq X \times Y$ 、 $S \subseteq X$ に対して $\overline{f}(S) = \bigcup_{x \in S} \{y \in Y \mid \langle x, y \rangle \in f\}$ と定義すると $\mathcal{M}(X,Y) = \{ f \in \mathfrak{P}(X \times Y) \mid \forall S \in \mathcal{S}(X) (\overline{f}(S) \in \mathcal{S}(Y)) \}$ が成り立ちます。

$\overline{f}(S)$ は通常 $f(S)$ と書くので今後は $f(S)$ と書くこともあります。

$\overline{f}: \mathfrak{P}(X) \to \mathfrak{P}(Y)$ となるので、 $\overline{f} \subseteq \mathfrak{P}(X) \times \mathfrak{P}(Y)$ と考えることができ、 $\overline{\overline{f}}: \mathfrak{P}(\mathfrak{P}(X)) \to \mathfrak{P}(\mathfrak{P}(Y))$ を作ることができます。 $\mathcal{M}(X,Y) = \{ f \in \mathfrak{P}(X \times Y) \mid \overline{\overline{f}}(\mathcal{S}(X)) \subseteq \mathcal{S}(Y) \}$ が成り立ちます。

$X = X_1 \times X_2 \times \cdots \times X_n$ のとき $f(\langle x_1, x_2, \cdots, x_n \rangle)$ を $f(x_1, x_2, \cdots, x_n)$ のように書くこともあります。

全射・単射・全単射

$X, Y$ が集合のとき、 $f \subseteq X \times Y$ に対して $f^{-1} = \{\langle y, x \rangle \in Y \times X \mid \langle x, y \rangle \in f\}$ とおきます。集合 $X, Y$ に対して

$\mathcal{B}^-(X,Y) = \{ f \in \mathfrak{P}(X \times Y) \mid \overline{\overline{f^{-1}}}(\mathcal{S}(Y)) \subseteq \mathcal{S}^-(X) \}$
$\mathcal{B}^+(X,Y) = \{ f \in \mathfrak{P}(X \times Y) \mid \overline{\overline{f^{-1}}}(\mathcal{S}(Y)) \subseteq \mathcal{S}^+(X) \}$
$\mathcal{B}(X,Y) = \{ f \in \mathfrak{P}(X \times Y) \mid \overline{\overline{f^{-1}}}(\mathcal{S}(Y)) \subseteq \mathcal{S}(X) \}$

と定義します。 $\mathcal{M}(X,Y) \cap \mathcal{B}^-(X,Y)$ の元を単射、 $\mathcal{M}(X,Y) \cap \mathcal{B}^+(X,Y)$ の元を全射、 $\mathcal{M}(X,Y) \cap \mathcal{B}(X,Y)$ の元を全単射と呼びます。

写像の合成

$f$ を $X$ から $Y$ への写像、 $g$ を $Y$ から $Z$ への写像とします。 $X$ から $Z$ への写像 $g \circ f$ を任意の $x \in X$ に対して $(g \circ f)(x) = g(f(x))$ と定義することができます。

$g \circ f$ を $g \circ f \in \mathfrak{P}(X \times Z)$ と考えると
$\begin{eqnarray*} g \circ f & = & \{ \langle x,z \rangle \in X \times Z \mid g(f(x)) = z \} \\ & = & \{ \langle x,z \rangle \in X \times Z \mid \exists y \in Y ( f(x) = y \land g(y) = z )\} \\ & = & \{ \langle x,z \rangle \in X \times Z \mid \exists y \in Y ( \langle x,y \rangle \in f \land \langle y,z \rangle \in g )\} \\ \end{eqnarray*}$
が成り立ちます。

恒等写像

$X$ から $X$ への写像で任意の $x \in X$ に $x$ を対応させるものを $X$ の恒等写像と呼び、 $1_X$ と書きます。任意の $x \in X$ に対して $1_X(x) = x$ となります。 $1_X \in \mathfrak{P}(X \times X)$ と考えたとき $1_X = \{\langle x,x \rangle \mid x \in X\} = \{ \langle x,x' \rangle \in X \times X \mid x = x' \}$ となります。

逆写像

$f$ が $X$ から $Y$ への全単射であるとき、 $f^{-1} \in \mathcal{M}(Y,X)$ が成り立ちます。 $f^{-1}$ を $f$ の逆写像と呼びます。

$\overline{f^{-1}}(S)$ は通常 $f^{-1}(S)$ と書くので今後は $f^{-1}(S)$ と書くこともあります。

$f \in \mathcal{M}(X,Y)$ 、 $g \in \mathcal{M}(Y,Z)$ のとき
$\begin{eqnarray*} (g \circ f)^{-1} & = & \{ \langle z,x \rangle \in Z \times X \mid \langle x,z \rangle \in g \circ f\} \\ & = & \{ \langle z,x \rangle \in Z \times X \mid \exists y \in Y ( \langle x,y \rangle \in f \land \langle y,z \rangle \in g )\} \\ & = & \{ \langle z,x \rangle \in Z \times X \mid \exists y \in Y ( \langle y,x \rangle \in f^{-1} \land \langle z,y \rangle \in g^{-1} )\} \\ & = & f^{-1} \circ g^{-1} \end{eqnarray*}$
となります。

$\mathcal{M}^-(X,Y) = \{ f \in \mathfrak{P}(X \times Y) \mid \overline{\overline{f}}(\mathcal{S}(X)) \subseteq \mathcal{S}^-(Y) \}$
$\mathcal{M}^+(X,Y) = \{ f \in \mathfrak{P}(X \times Y) \mid \overline{\overline{f}}(\mathcal{S}(X)) \subseteq \mathcal{S}^+(Y) \}$

とおきます。

$f \in \mathcal{M}^+(X,Y)$ 、 $f^{-1} \in \mathcal{M}^-(Y,X)$ のとき
$\begin{eqnarray*} f^{-1} \circ f & = & \{ \langle x,x' \rangle \in X \times X \mid \exists y \in Y ( \langle x,y \rangle \in f \land \langle y,x' \rangle \in f^{-1} )\} \\ & = & \{ \langle x,x' \rangle \in X \times X \mid \exists y \in Y ( \langle x,y \rangle \in f \land \langle x',y \rangle \in f )\} \\ & = & \{ \langle x,x' \rangle \in X \times X \mid x = x' \} \\ & = & 1_X \\ \end{eqnarray*}$
となります。

$f \in \mathcal{M}^-(X,Y)$ 、 $f^{-1} \in \mathcal{M}^+(Y,X)$ のとき
$\begin{eqnarray*} f \circ f^{-1} & = & \{ \langle y,y' \rangle \in Y \times Y \mid \exists x \in X ( \langle y,x \rangle \in f^{-1} \land \langle x,y' \rangle \in f )\} \\ & = & \{ \langle y,y' \rangle \in Y \times Y \mid \exists y \in Y ( \langle x,y \rangle \in f \land \langle x,y' \rangle \in f )\} \\ & = & \{ \langle y,y' \rangle \in Y \times Y \mid y = y' \} \\ & = & 1_Y \\ \end{eqnarray*}$
となります。

全射・単射の性質

$f: X \to Y$ を単射、 $g, h: W \to X$ は $f \circ g = f \circ h$ を満たす写像とすると $g = f^{-1} \circ f \circ g = f^{-1} \circ f \circ h = h$ となって $g = h$ が成り立ちます。

$f: X \to Y$ を全射、 $g, h: Y \to Z$ は $g \circ f = h \circ f$ を満たす写像とすると $g = g \circ f \circ f^{-1} = h \circ f \circ f^{-1} = h$ となって $g = h$ が成り立ちます。

$f: X \to Y$ 、 $g: Y \to Z$ に対して

$f$ 、 $g$ が単射ならば $g \circ f$ は単射 [証明] $g \circ f \circ h_1 = g \circ f \circ h_2 \implies f \circ h_1 = f \circ h_2 \implies h_1 = h_2$
$g \circ f$ が単射ならば $f$ は単射 [証明] $f \circ h_1 = f \circ h_2 \implies g \circ f \circ h_1 = g \circ f \circ h_2 \implies h_1 = h_2$
$f$ 、 $g$ が全射ならば $g \circ f$ は全射 [証明] $h_1 \circ g \circ f = h_2 \circ g \circ f \implies h_1 \circ g = h_2 \circ g \implies h_1 = h_2$
$g \circ f$ が全射ならば $g$ は全射 [証明] $h_1 \circ g = h_2 \circ g \implies h_1 \circ g \circ f = h_2 \circ g \circ f \implies h_1 = h_2$
$g \circ f$ が単射、 $f$ が全単射ならば $g$ は単射 [証明] $g \circ h_1 = g \circ h_2 \implies g \circ f \circ f^{-1} \circ h_1 = g \circ f \circ f^{-1} \circ h_2 \\ \implies f^{-1} \circ h_1 = f^{-1} \circ h_2 \implies h_1 = h_2$
$g \circ f$ が全射、 $g$ が全単射ならば $f$ は全射 [証明] $h_1 \circ f = h_2 \circ f \implies h_1 \circ g^{-1} \circ g \circ f = h_2 \circ g^{-1} \circ g \circ f \\ \implies h_1 \circ g^{-1} = h_2 \circ g^{-1} \implies h_1 = h_2$