エレファント・ビジュアライザー調査記録

ビジュアルプログラミングで数式の変形を表すことを考えていくブロクです。

エレファントな整数論(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 の逆写像と呼びます。

以上の議論から

集合  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 となります。よって

 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 に対して

 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

とすると

となります。よって  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: X \to Y単射ならば  g \circ f が恒等写像となる  g: Y \to X が存在する
    • [証明]  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: X \to Y全射ならば  f \circ g が恒等写像となる  g: Y \to X が存在する
    • [証明]  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*) \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 を有限集合と呼びます。有限集合でないとき無限集合と呼びます。

(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全射となります。

任意の  w \in X に対して  w \ne f(y) ならば  w = g(v) = f(v) となる  v \in X が存在します。よって  f全射となり、 Z は有限集合となります。[証明終わり]

集合と位相(増補新装版)(数学シリーズ)

集合と位相(増補新装版)(数学シリーズ)