エレファントな整数論(22) - エレファント・コンピューティング調査報告

写像の性質の続き

前回の議論では足りないところがあるので追加していきます。証明はまとめることができると思うのですが、できませんでした。集合論の中の自然数論のような話題だと思うので、まとめて書かれているところがあると思うのですが、見つけることはできませんでしたので必要と思われるものを書いていきます。

全射・単射

$X, Y$ を集合、 $f: X \to Y$ を写像とします。任意の $x_1, x_2 \in X$ に対して $f(x_1) = f(x_2)$ ならば $x_1 = x_2$ であるとき、 $f$ を単射と呼びます。任意の $y \in Y$ に対して $y = f(x)$ となる $x \in X$ が存在するとき、 $f$ を全射と呼びます。 $f$ が全射かつ単射であるとき全単射と呼びます。

$f: X \to Y$ に対して $\overline{f^{-1}}: Y \to \mathfrak{P}(X)$ を $\overline{f^{-1}}(y) = \{x \in X \mid f(x) = y\}$ とおきます( $\mathfrak{P}(X)$ は $X$ の部分集合全体の集合)。

(MP1) $f \ は単射 \iff 任意の \ y \in Y \ に対して \ \#\overline{f^{-1}}(y) \le 1$
(MP2) $f \ は全射 \iff 任意の \ y \in Y \ に対して \ \#\overline{f^{-1}}(y) \ge 1$
(MP3) $f \ は全単射 \iff 任意の \ y \in Y \ に対して \ \#\overline{f^{-1}}(y) = 1$

となります。ここで $\#\overline{f^{-1}}(y)$ は $\overline{f^{-1}}(y)$ の元の個数を表します。ここでは $0$ 、 $1$ 、 $2$ 以上の場合に分けるためにこの記法を使います。(後で自然数を定義するので自然数の全体は使いません)

逆写像

$f$ が全単射であるとき、任意の $y \in Y$ に対して $\overline{f^{-1}}(y)$ の元の個数が $1$ なので、 $y$ に $\overline{f^{-1}}(y)$ の元を対応させる写像 $f^{-1}: Y \to X$ を定義することができます。

任意の $x \in X$ に対して $f^{-1}(f(x)) \in \overline{f^{-1}}(f(x)) = \{x\}$ となるので $f^{-1} \circ f$ は $X$ の恒等写像となります。

任意の $y \in Y$ に対して $f^{-1}(y) \in \overline{f^{-1}}(y)$ となるので
$f^{-1}(y) \in \overline{f^{-1}}(y) \iff f(f^{-1}(y)) = y$
であることから $f \circ f^{-1}$ は $Y$ の恒等写像となります。

$f^{-1}$ を $f$ の逆写像と呼びます。

以上の議論から

(MP4) $f$ が全単射ならば $f$ の逆写像が存在します。

集合 $X, Y$ に対して全単射 $f: X \to Y$ が存在するとき $X \sim Y$ と表し、 $X$ と $Y$ は濃度が等しいといいます。上の議論より $\sim$ は同値関係となります。

全射・単射の性質

$f: X \to Y$ を単射、 $g, h: Z \to X$ は $f \circ g = f \circ h$ を満たす写像とします。 $z \in Z$ とすると $f(g(z)) = f(h(z))$ となり、 $f$ は単射なので $g(z) = h(z)$ となります。よって $g = h$ となります。よって

(MP5) $f: X \to Y$ が単射、 $g, h: Z \to X$ が $f \circ g = f \circ h$ を満たす写像ならば $g = h$ となります。

$f: X \to Y$ を全射、 $g, h: Y \to Z$ は $g \circ f = h \circ f$ を満たす写像とします。 $y \in Y$ とすると $f$ は全射なので $f(x) = y$ となる $x \in X$ が存在します。 $g(f(x)) = h(f(x))$ となり、 $g(y) = h(y)$ となります。よって $g = h$ となります。よって

(MP6) $f: X \to Y$ が全射、 $g, h: Y \to Z$ が $g \circ f = h \circ f$ を満たす写像ならば $g = h$ となります。

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

(MP7) 、が単射ならばは単射
- [証明] $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$
(MP8) が単射ならばは単射
- [証明] $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$
(MP9) 、が全射ならばは全射
- [証明] $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$
(MP10) が全射ならばは全射
- [証明] $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$
(MP11) が単射、が全単射ならばは単射
- [証明] $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$
(MP12) が全射、が全単射ならばは全射
- [証明] $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$

$f: X \to Y$ に対して $f(X) = \{ f(x) \mid x \in X \}$ ( $f$ の像)とすると、全射 $\tilde{f}: X \to f(X)$ 、 $\tilde{f}(x) = f(x)$ が存在します。 $X/f = \{ \overline{f^{-1}}(y) \mid y \in Y \}$ ( $f$ に関する同値類全体の集合)とすると、単射 $\bar{f}: X/f \to Y$ 、 $\bar{f}(\overline{f^{-1}}(y)) = y$ が存在します。

$X \xrightarrow{f_1} X/f \xrightarrow{f_2} f(X) \xrightarrow{f_3} Y$ を

$x \in \overline{f^{-1}}(y))$ のとき $f_1(x) = \overline{f^{-1}}(y))$
$f_2(\overline{f^{-1}}(y)) = y$
$f_3(y) = y$

とすると

$\tilde{f} = f_2 \circ f_1$ は全射なので $f_2$ は全射
$\bar{f} = f_3 \circ f_2$ は単射なので $f_2$ は単射

となります。よって $f_2$ は全単射、 $f_1$ は全射、 $f_3$ は単射となります。よって

(MP13) $X \xrightarrow{f_1} X/f \xrightarrow{f_2} f(X) \xrightarrow{f_3} Y$ とすると $f_2$ は全単射、 $f_1$ は全射、 $f_3$ は単射となります。
(MP14) が単射ならばが恒等写像となるが存在する
- [証明] $f$ が単射ならば $f_1$ は単射、したがって全単射となります。よって $f_2 \circ f_1$ の逆写像 $f_1^{-1} \circ f_2^{-1}: f(X) \to X$ が存在します。 $g: Y \to X$ を $f_1^{-1} \circ f_2^{-1}$ を拡張する写像とすると $g \circ f$ が恒等写像となります。
(MP15) が全射ならばが恒等写像となるが存在する
- [証明] $f$ が全射ならば $f_3$ は全射、したがって全単射となります。よって $f_3 \circ f_2$ の逆写像 $f_2^{-1} \circ f_3^{-1}: Y \to X/f$ が存在します。 $h: X/f \to X$ を $S \in X/f$ に対して $S$ を $X$ の部分集合としたときの $S$ の元の一つに対応させる写像とすると、 $f_1 \circ h$ は $X/f$ の恒等写像となります。 $g = h \circ f_2^{-1} \circ f_3^{-1}: Y \to X$ とすると $g \circ f$ が恒等写像となります。

(MP16) 集合 $X, Y$ に関する以下の条件(FS1)、(FS2)は同値となります。

(FS1*) 任意の写像 $f: X \to Y$ に対して $f$ が単射ならば $f$ は全射である
(FS2*) 任意の写像 $g: Y \to X$ に対して $g$ が全射ならば $g$ は単射である

[証明] $(FS1*) \Longrightarrow (FS2*):$ (FS1*)を仮定し、 $g: Y \to X$ を全射とします。 $f: X \to Y$ を $f(x) \in g^{-1}(x)$ となるように定義することができます。 $f$ は単射となり、(FS1*)より全単射となります。よって $g = f^{-1}$ は全単射となります。

$(FS2*) \Longrightarrow (FS1*):$ (FS2*)を仮定し、 $f: X \to Y$ を単射とします。 $g: Y \to X$ を $y \in f(X)$ のとき $g(y) \in f^{-1}(y)$ となるように定義することができます。 $y \notin f(X)$ のときは $g(y)$ 任意の $X$ の元とします。 $g$ は全射となり、(FS2*)より全単射となります。よって $f = g^{-1}$ は全単射となります。[証明終わり]

有限集合

上の議論より集合 $X$ に対して以下の条件(FS1)、(FS2)は同値となります。これらの条件が成り立つとき、 $X$ を有限集合と呼びます。有限集合でないとき無限集合と呼びます。

(FS1) 集合 $X$ が、任意の写像 $f: X \to X$ に対して $f$ が単射ならば $f$ は全射である
(FS2) 集合 $X$ が、任意の写像 $f: X \to X$ に対して $f$ が全射ならば $f$ は単射である

(FM1) $Y$ が有限集合、 $f: X \to Y$ が単射ならば、 $X$ は有限集合となります。

[証明] $g: X \to X$ を単射とします。

$y \in f(X)$ とすると $\overline{f^{-1}}(y)$ は空ではないので、その一つの元をとる写像を $h: f(X) \to X$ とします。 $f$ を $X$ から $f(X)$ への写像と見たものを $\tilde{f}: X \to f(X)$ とすると、 $\tilde{f} \circ h$ は $f(X)$ の恒等写像となります。よって $h$ は単射となり、 $\tilde{f} \circ g \circ h: f(X) \to f(X)$ は単射となります。

$g': Y \to Y$ を
$g'(y) = \begin{cases} \tilde{f}(g(h(y))) & (y \in f(X)) \\ y & (y \notin f(X)) \end{cases}$
とおくと単射となります。 $Y$ が有限集合なので $g'$ は全単射となります。

よって $\tilde{f} \circ g \circ h$ も全単射となり、 $\tilde{f}$ は全単射なので $g$ は全射となります。よって $X$ は有限集合となります。[証明終わり]

(FM2) $X$ が有限集合、 $f: X \to Y$ が全射ならば、 $Y$ は有限集合となります。

[証明] $g: Y \to Y$ を単射とします。

$y \in Y$ とすると $\overline{f^{-1}}(y)$ は空ではないので、その一つの元をとる写像を $h: Y \to X$ とします。 $h$ は単射となり、 $h$ を $Y$ から $h(Y)$ への写像と見たものを $\tilde{h}: Y \to h(Y)$ とすると、 $\tilde{h}$ は全単射となります。よって $\tilde{h} \circ g \circ \tilde{h}^{-1}: h(Y) \to h(Y)$ は単射となります。

$g': X \to X$ を
$g'(x) = \begin{cases} \tilde{h}(g(\tilde{h}^{-1}(x))) & (x \in h(Y)) \\ x & (x \notin h(Y)) \end{cases}$
とおくと単射となります。 $X$ が有限集合なので $g'$ は全単射となります。

よって $\tilde{h} \circ g \circ \tilde{h}^{-1}$ も全単射となり、 $\tilde{h}$ は全単射なので $g$ は全射となります。よって $Y$ は有限集合となります。[証明終わり]

(FM3) $X$ が有限集合ならば $X$ の任意の部分集合は有限集合となります。

[証明] (FM1)より成り立ちます。[証明終わり]

(FM4) $X$ が有限集合ならば $X$ の任意の同値類全体の集合は有限集合となります。

[証明] (FM2)より成り立ちます。[証明終わり]

(FM5) $X$ が有限集合、 $X$ と $Y$ は濃度が等しいならば $Y$ は有限集合となります。

これは明らかに成り立ちます。

(FM6) $Z = X \cup Y$ 、 $X$ が有限集合、 $Y = \{y\}$ ならば $Z$ は有限集合となります。

[証明] $y \in X$ ならば $Z = X$ は有限集合となります。 $y \notin X$ とします。

$f: Z \to Z$ を単射とします。

$f(X) \subseteq X$ とすると $f$ の $X$ への制限は $X$ から $X$ への単射となり、 $X$ が有限集合であることから全射となります。 $f$ は単射なので $f(y) \notin X$ となって $f(y) = y$ となります。よって $f$ は全射となります。

$f(X) \not\subseteq X$ とします。 $f$ は単射なので $y \in f(X)$ となります。 $f$ は単射なので $y = f(x)$ となる $x \in X$ がただ一つ存在します。また、 $f$ は単射なので $f(y) \in X$ となります。 $g: X \to X$ を $g(x) = f(y)$ 、 $v \ne x$ のとき $g(v) = f(v)$ と定義することができ、 $g$ は単射となります。 $X$ が有限集合であることから $g$ は全射となります。