単射・全射・全単射の演習問題 35 問（解答付き）

2020/05/182020/09/09

今日の目標

単射・全射・全単射の扱いに慣れる。演習問題で証明を書けるようになる。

この記事で使う記号や用語

集合 $X$ のべき集合を $P (X)$ で表す。
写像 $f : X \to Y$ に対し、 $X$ の部分集合 $A$ の $f$ による像を $f (A)$ と書く。
$N$ を非負整数全体の集合とする。
$N_{+}$ を正整数全体の集合とする。
$Z$ を整数全体の集合とする。
$Q$ を有理数全体の集合とする。
$Q_{+}$ を正の有理数全体の集合とする。
$R$ を実数全体の集合とする。
$N [X]$ を非負整数係数 $1$ 変数多項式全体の集合とする。
$Z [X]$ を整数係数 $1$ 変数多項式全体の集合とする。

単射・全射に関する演習問題をいっぱい解こう

ちなみに「有限集合」と「単射・全射」との関係については
↓ の記事をどうぞ

鳩ノ巣原理を証明する｜有限集合の定義

有限集合の基本性質の証明は意外と複雑

定義の確認

定義（単射・全射・全単射）

$f : X \to Y$ とする。

単射性

$f$ が単射であるとは、各 $x_{1}, x_{2} \in X$ に対し $f (x_{1}) = f (x_{2}) ⟹ x_{1} = x_{2}$ が成り立つこと。

全射性

$f$ が全射であるとは、 $f (X) = Y$ が成り立つこと。

全単射性

$f$ が全単射であるとは、 $f$ が単射でも全射でもあること。

f : X \to Y

の全射性を示したいときは

f (X) \subseteq Y

は自明だから

Y \subseteq f (X)

を示せばいい

つまり終域

Y

の要素

y

を任意に取って

y \in f (X)

であること
つまり

y = f (x)

となる

x \in X

が存在することを言えばいい

定義（包含写像・恒等写像）

集合 $X$ とその部分集合 $A$ に対し、写像 $ι : A \to X, ι (a) = a$ を $A$ から $X$ への包含写像と呼ぶ。

特に $X$ から $X$ への包含写像を $X$ 上の恒等写像と呼び、 ${id}_{X}$ と書く。すなわち ${id}_{X} : X \to X, {id}_{X} (x) = x$ である。

定義（合成写像）

$f : X \to Y$ と $g : Y \to Z$ に対し、写像 $g \circ f : X \to Z$ を $(g \circ f) (x) = g (f (x))$ によって定める。これを $f$ と $g$ との合成写像と呼ぶ。

例題（単射であることを示す）

写像 $f : [- 1, 0] \to R$ を $f (x) = | x |$ と定めたとき、 $f$ が単射であることを示せ。

解答例

始域 $[- 1, 0]$ に属する二元 $x_{1}, x_{2}$ が $f (x_{1}) = f (x_{2})$ を満たすとする。このとき $| x_{1} | = | x_{2} |$ なので $- x_{1} = - x_{2}$ であり、したがって $x_{1} = x_{2}$ である。よって $f$ は単射である。

例題（単射でないことを示す）

写像 $f : [- 1, 2] \to R$ を $f (x) = | x |$ と定めたとき、 $f$ が単射でないことを示せ。

解答例

始域 $[- 1, 2]$ に属する二元として $x_{1} = - 1$ と $x_{2} = 1$ を取る。このとき $f (x_{1}) = | - 1 | = 1$ $f (x_{2}) = | 1 | = 1$ より $f (x_{1}) = f (x_{2})$ である。しかし $x_{1} \neq x_{2}$ である。よって $f$ は単射ではない。

例題（全射であることを示す）

写像 $f : [- 1, 0] \to [0, 1]$ を $f (x) = | x |$ と定めたとき、 $f$ が全射であることを示せ。

解答例

終域 $[0, 1]$ に属する元 $y$ を任意に取る。このとき始域 $[- 1, 0]$ に属する元 $x$ として $x = - y$ を取ると、 $f (x) = | - y | = y$ となる。よって $f$ は全射である。

例題（全射でないことを示す）

写像 $f : [- 1, 0] \to [0, 2]$ を $f (x) = | x |$ と定めたとき、 $f$ が全射でないことを示せ。

解答例

終域 $[0, 2]$ に属する元として $y = 2$ を取る。このとき始域 $[- 1, 0]$ に属する任意の元 $x$ に対し $f (x) = | x | \leq 1 < 2 = y$ となるので $f (x) \neq y$ である。よって $f$ は全射ではない。

演習問題

問題１（包含写像は単射）

集合 $X$ とその部分集合 $A$ に対し、包含写像 $ι : A \to X$ は単射であることを示せ。

解答例

$ι (a_{1}) = ι (a_{2})$ となる $a_{1}, a_{2} \in A$ を取ると、 $a_{1} = ι (a_{1}) = ι (a_{2}) = a_{2}$ となるので、 $ι$ は単射である。

問題２（恒等写像は全単射）

集合 $X$ 上の恒等写像 ${id}_{X} : X \to X$ は全単射であることを示せ。

解答例

${id}_{X}$ は $X$ から $X$ への包含写像なので、問題１より単射である。

$x \in X$ を任意に取ると、 ${id}_{X} (x) = x$ より $x \in {id}_{X} (X)$ となるので ${id}_{X}$ は全射である。

問題３

始域と終域が等しい単射は常に全単射か？

解答例

そうとは限らない。反例として $f : N \to N$ を $f (n) = n + 1$ と定めると、 $f (n_{1}) = f (n_{2})$ となる $n_{1}, n_{2} \in N$ に対し、 $n_{1} + 1 = n_{2} + 1$ すなわち $n_{1} = n_{2}$ となるので $f$ は単射である。一方 $f (n) = 0$ となる $n \in N$ は存在せず $0 \notin f (N)$ なので $f$ は全射ではない。

問題４

写像 $f : X \to Y$ は全単射であるとする。このとき任意の $y \in Y$ に対し

$f (x) = y$ となる $x \in X$ が唯一つ存在する

ことを示せ。

解答例

$y \in Y$ を任意に取る。

f (x) = y

となる

x \in X

の存在性

$f$ が全射なので $y \in f (X)$ である。よって $f (x) = y$ となる $x \in X$ が存在する。

f (x) = y

となる

x \in X

の一意性

$f (x_{1}) = y$ かつ $f (x_{2}) = y$ となる $x_{1}, x_{2} \in X$ に対し $f (x_{1}) = f (x_{2})$ であり、 $f$ の単射性より $x_{1} = x_{2}$ となる。

問題５

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

$g \circ f$ は単射ならば $f$ は単射

であることを示せ。

解答例

$x_{1}, x_{2} \in X$ に対し $f (x_{1}) = f (x_{2})$ であるとすると、 $g (f (x_{1})) = g (f (x_{2}))$ すなわち $(g \circ f) (x_{1}) = (g \circ f) (x_{2})$ であり、 $g \circ f$ は単射なので $x_{1} = x_{2}$ である。

問題６

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

$g \circ f$ は全射ならば $g$ は全射

であることを示せ。

解答例

$z \in Z$ を任意に取る。このとき $g \circ f$ の全射性より $g (f (x)) = z$ となる $x \in X$ が存在し、 $z \in g (Y)$ となるので $g$ は全射である。

問題７

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

$g \circ f$ は単射ならば $g$ は単射

は一般に成り立つか？

解答例

一般には成り立たない。反例として $X = {0}, Y = {0, 1}, Z = {0}$ および $\begin{aligned} f (0) & = 0 & g (0) & = 0 & g (1) & = 0 \end{aligned}$ とすると $(g \circ f) (0) = 0$ であり、 $g \circ f$ は単射であるが $g$ は単射ではない。

問題８

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

$g \circ f$ は全射ならば $f$ は全射

は一般に成り立つか？

解答例

一般には成り立たない。問題７の解答例で用いた反例において、 $g \circ f$ は全射であるが $f$ は全射ではない。

問題９

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

$g \circ f = {id}_{X}$ ならば $f$ は単射かつ $g$ は全射

が成り立つことを示せ。

解答例１

f

の単射性

$f (x_{1}) = f (x_{2})$ なる $x_{1}, x_{2} \in X$ に対し $x_{1} = g (f (x_{1})) = g (f (x_{2})) = x_{2}$ なので $f$ は単射。

g

の全射性

$x \in X$ を任意に取る。このとき $g (f (x)) = x$ なので $x \in g (Y)$ である。

解答例２

問題２より

{id}_{X} : X \to X

は全単射なので、問題５より

f

は単射であり問題６より

g

は全射である。

問題１０

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

$g \circ f = {id}_{X}$ ならば $g$ は単射

は一般に成り立つか？

解答例１（素朴な反例）

一般には成り立たない。反例として $X = {0}, Y = {0, 1}$ とし、 $\begin{aligned} f (0) = 0 & g (0) = 0 & g (1) = 0 \end{aligned}$ とすると $(g \circ f) (0) = 0$ なので $g \circ f = {id}_{X}$ であるが $g$ は単射ではない。

解答例２（始域と終域が等しい反例）

一般には成り立たない。反例として $X = Y = N$ とし、 $f (x) = x + 1, g (x) = {\begin{cases} x - 1 & (x \geq 1 のとき) \\ 0 & (x = 0 のとき) \end{cases}$ とすると、各 $x \in R$ に対し $g (f (x)) = (x + 1) - 1 = x$ より $g \circ f = {id}_{X}$ であるが、 $g (0) = 0 = g (1), 0 \neq 1$ なので $g$ は単射ではない。

問題１１

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

$g \circ f = {id}_{X}$ ならば $f$ は全射

は一般に成り立つか？

解答例

一般には成り立たない。問題１０の解答例１（または解答例２）で用いた反例において、 $g \circ f = {id}_{X}$ であるが $f$ は全射ではない。

問題１２（逆関数の存在と一意性）

全単射写像 $f : X \to Y$ に対し、写像 $g : Y \to X$ で

(i)

g \circ f = {id}_{X}

(ii)

f \circ g = {id}_{Y}

をともに満たすものが唯一つ存在することを示せ。

解答例

(i), (ii) を満たす写像

g

の存在性

$f$ は全単射なので、問題４より各 $y \in Y$ に対し

$f (x) = y$ となる $x \in X$ が唯一つ存在する。

この $x$ に対し $g (y) = x$ と定めることで写像 $g : Y \to X$ を定義する。

(i)

g \circ f = {id}_{X}

が成り立つこと

$x_{0} \in X$ を任意に取る。このとき

$f (x) = f (x_{0})$ となる $x \in X$

として $x_{0}$ が該当するので、 $g$ の定義より $g (f (x_{0})) = x_{0}$ である。

(ii)

f \circ g = {id}_{Y}

が成り立つこと

各 $y \in Y$ に対し $f (g (y)) = y$ となることは $g$ の定義から自明。

(i), (ii) を満たす写像

g

の一意性

$g_{1}, g_{2} : Y \to X$ がともに (i),(ii) を満たすとする。 $y \in Y$ を任意に取ると $f$ の全射性より $f (x) = y$ なる $x \in X$ が存在し、 $g_{1} (y) = g_{1} (f (x)) = x = g_{2} (f (x)) = g_{2} (y)$ となる。よって $g_{1} = g_{2}$ である。

このような写像

g

を

f

の逆写像と呼んで

f^{- 1}

と書きます

そして問題９より

f^{- 1}

は全単射

問題１３（単射と単射の合成は単射）

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

$f$ も $g$ も単射ならば $g \circ f$ は単射

であることを示せ。

解答例

$x_{1}, x_{2} \in X$ が $(g \circ f) (x_{1}) = (g \circ f) (x_{2})$ すなわち $g (f (x_{1})) = g (f (x_{2}))$ であるとする。このとき $g$ の単射性より $f (x_{1}) = f (x_{2})$ であり、更に $f$ の単射性より $x_{1} = x_{2}$ である。よって $g \circ f$ は単射である。

問題１４（全射と全射の合成は全射）

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

$f$ も $g$ も全射ならば $g \circ f$ は全射

を示せ。

解答例

$z \in Z$ を任意に取る。このとき $g$ の全射性より $g (y) = z$ となる $y \in Y$ が存在し、 $f$ の全射性より $f (x) = y$ となる $x \in X$ が存在する。よって $(g \circ f) (x) = g (f (x)) = g (y) = z$ となるので $g \circ f$ は全射である。

よって

f

も

g

も全単射なら

g \circ f

も全単射

問題１５

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

$f$ が単射ならば $g \circ f$ は単射

は一般に成り立つか？

解答例

一般には成り立たない。反例として $X = {0, 1}, Y = {0, 1}, Z = {0}$ とし、 $\begin{aligned} f (0) & = 0 & f (1) & = 1 & g (0) & = 0 & g (1) & = 0 \end{aligned}$ とすると $\begin{aligned} (g \circ f) (0) & = 0 & (g \circ f) (1) & = 0 \end{aligned}$ であり、 $f$ は単射であるが $g \circ f$ は単射ではない。

問題１６

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

$g$ が単射ならば $g \circ f$ は単射

は一般に成り立つか？

解答例

一般には成り立たない。反例として $X = {0, 1}, Y = {0}, Z = {0}$ とし、 $\begin{aligned} f (0) & = 0 & f (1) & = 0 & g (0) & = 0 \end{aligned}$ とすると $\begin{aligned} (g \circ f) (0) & = 0 & (g \circ f) (1) & = 0 \end{aligned}$ であり、 $g$ は単射であるが $g \circ f$ は単射ではない。

問題１７

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

$f$ が全射ならば $g \circ f$ は全射

は一般に成り立つか？

解答例

一般には成り立たない。反例として $X = {0}, Y = {0}, Z = {0, 1}$ とし、 $\begin{aligned} f (0) & = 0, \end{aligned} \begin{aligned} g (0) & = 0 \end{aligned}$ とすると $(g \circ f) (0) = 0$ であり、 $f$ は全射であるが、 $g \circ f$ は全射ではない。

問題１８

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

$g$ が全射ならば $g \circ f$ は全射

は一般に成り立つか？

解答例

一般には成り立たない。反例として $X = {0}, Y = {0, 1}, Z = {0, 1}$ とし、 $\begin{aligned} f (0) & = 0 & g (0) & = 0 & g (1) & = 1 \end{aligned}$ とすると $(g \circ f) (0) = 0$ であり、 $g$ は全射であるが、 $g \circ f$ は全射ではない。

問題１９

空でない集合 $X$ と集合 $Y$ に対し、

$X$ から $Y$ への単射が存在するならば $Y$ から $X$ への全射が存在する

を示せ。

解答例

$X \neq \emptyset$ より、 $x_{0} \in X$ を一つ取れる。単射 $f : X \to Y$ を取ると、その終域を狭めた写像 $f : X \to f (X)$ は全単射であり、その逆写像 $g : f (X) \to X$ が存在する。そこで $h : Y \to X, h (y) = {\begin{cases} g (y) & (y \in f (X)) \\ x_{0} & (y \notin f (X)) \end{cases}$ を考える。 $x \in X$ を任意に取ると $g$ の全射性より $g (y) = x$ なる $y \in f (X)$ が存在し、 $h (y) = g (y) = x$ なので $h$ の全射性を得る。

ちなみに

X = \emptyset, Y \neq \emptyset

のときを考えると

\emptyset

から

Y

への単射は存在する（空関数）けど

Y

から

\emptyset

への全射は存在しない（そもそも写像がない）

詳しくはこちら↓

始域や終域が空集合の写像｜空関数と単射性と全射性

空関数（空写像）とは始域が空集合の写像のこと。写像の定義に従えば始域が空集合の写像は空集合そのも ...

https://sorai-note.com/math/empty-function/

問題２０

選択公理を仮定する。集合 $X, Y$ に対し、

$X$ から $Y$ への全射が存在するならば $Y$ から $X$ への単射が存在する

を示せ。

解答例

全射 $f : X \to Y$ を取ると、各 $y \in Y$ に対し、 ${x \in X | f (x) = y} \neq \emptyset$ であるので、選択公理より、関数 $g : Y \to X$ で

各 $y \in Y$ に対し $f (g (y)) = y$

となるものが存在する。このとき

g (a) = g (b)

となる

a, b \in Y

に対し

a = f (g (a)) = f (g (b)) = b

となるので

g

は単射である。

問題２１

$f_{1}, f_{2} : X \to Y$ と $g : Y \to Z$ に対し、

$g$ が単射かつ $g \circ f_{1} = g \circ f_{2}$ ならば $f_{1} = f_{2}$

であることを示せ。

解答例

$x \in X$ を任意に取る。 $g \circ f_{1} = g \circ f_{2}$ より $g (f_{1} (x)) = g (f_{2} (x))$ であり、 $g$ が単射なので $f_{1} (x) = f_{2} (x)$ を得る。

問題２２

$f_{1}, f_{2} : X \to Y$ と $g : Y \to Z$ に対し、

$g \circ f_{1} = g \circ f_{2}$ ならば $f_{1} = f_{2}$

は一般に成り立つか？

解答例

一般には成り立たない。反例として $X = {0}, Y = {0, 1}, Z = {0}$ とし、 $\begin{aligned} f_{1} (0) & = 0 & f_{2} (0) & = 1 & g (0) & = 0 & g (1) & = 0 \end{aligned}$ とすると、 $\begin{aligned} g (f_{1} (0)) = 0 & g (f_{2} (0)) = 0 \end{aligned}$ であり、 $f_{1} \neq f_{2}$ だが $g \circ f_{1} = g \circ f_{2}$ である。

問題２３

$f : X \to Y$ と $g_{1}, g_{2} : Y \to Z$ に対し、

$f$ が全射かつ $g_{1} \circ f = g_{2} \circ f$ ならば $g_{1} = g_{2}$

であることを示せ。

解答例

$y \in Y$ を任意に取る。 $f$ の全射性より $f (x) = y$ となる $x \in X$ が存在し、 $g_{1} \circ f = g_{2} \circ f$ より $g_{1} (f (x)) = g_{2} (f (x))$ であり、 $g_{1} (y) = g_{2} (y)$ を得る。

問題２４

$f : X \to Y$ と $g_{1}, g_{2} : Y \to Z$ に対し、

$g_{1} \circ f = g_{2} \circ f$ ならば $g_{1} = g_{2}$

は一般に成り立つか？

解答例

一般には成り立たない。反例として $X = {0}, Y = {0, 1}, Z = {0, 1, 2}$ とし、 $\begin{aligned} f (0) & = 0 & \begin{aligned} g_{1} (0) & = 0 \\ g_{1} (1) & = 1 \end{aligned} & \begin{aligned} g_{2} (0) & = 0 \\ g_{2} (1) & = 2 \end{aligned} \end{aligned}$ とすると $\begin{aligned} g_{1} (f (0)) = 0 & g_{2} (f (0)) = 0 \end{aligned}$ であり、 $g_{1} \neq g_{2}$ だが $g_{1} \circ f = g_{2} \circ f$ である。

問題２５

$N^{2}$ から $N$ への全単射が存在することを示せ。

解答例１（カントールの対関数）

写像 $f : N^{2} \to N$ を

$f (n, m) = a_{n + m} + n$ ただし $a_{k} = \sum_{i = 0}^{k} i$

で定め、この全単射性を示す。

f

の全射性

$ℓ \in N$ を任意に取る。 $a_{0} = 0$ であり、 ${a_{k}}_{k \in N}$ は狭義単調増加な自然数列なので、 $a_{k} \leq ℓ < a_{k + 1}$ となる $k \in N$ が取れる。 $n = ℓ - a_{k}$ および $m = k - n$ とする。ここで $0 \leq ℓ - a_{k} < a_{k + 1} - a_{k} = k + 1$ すなわち $0 \leq n \leq k$ であるので $n, m \in N$ であることに注意。したがって $f (n, m) = a_{k} + (ℓ - a_{k}) = ℓ$ である。

f

の単射性

自然数 $n, m, n^{'}, m^{'}$ が $f (n, m) = f (n^{'}, m^{'})$ を満たすとする。 $a_{n + m + 1} = a_{n} + n + m + 1$ であることに注意すると、 $a_{n + m} \leq f (n, m) < a_{n + m + 1}$ $a_{n^{'} + m^{'}} \leq f (n^{'}, m^{'}) < a_{n^{'} + m^{'} + 1}$ である。 $f (n, m) = f (n^{'}, m^{'})$ なので、 $a_{n + m} < a_{n^{'} + m^{'} + 1}$ であり、数列 ${a_{k}}_{k \in N}$ は単調増加なので $n + m < n^{'} + m^{'} + 1$ すなわち $n + m \leq n^{'} + m^{'}$ である。一方 $a_{n^{'} + m^{'}} < a_{n + m + 1}$ なので、同様に $n^{'} + m^{'} \leq n + m$ である。したがって $n + m = n^{'} + m^{'}$ である。ここで $0 = f (n, m) - f (n^{'}, m^{'}) = n - n^{'}$ より $n = n^{'}$ であり、したがって $m = m^{'}$ である。

動画で詳しく解説してます（Youtube）↓

解答例２（素因数分解を使用）

写像 $f : N^{2} \to N$ を $f (n, m) = 2^{n} (2 m + 1) - 1$ で定め、これが全単射であることを示す。

f

の全射性

$k \in N$ を任意に取る。正整数 $k + 1$ の素因数分解により、 $k + 1 = 2^{i} j$ となる自然数 $i$ と正奇数 $j$ が存在することがわかる。ここで $n = i$ および $m = \frac{j - 1}{2}$ とすると、 $n$ も $m$ も自然数で $f (n, m) = 2^{n} (2 m + 1) - 1 = 2^{i} j - 1 = (k + 1) - 1 = k$ である。

f

の単射性

自然数 $n, m, n^{'}, m^{'}$ が $f (n, m) = f (n^{'}, m^{'})$ を満たすとする。すなわち $2^{n} (2 m + 1) = 2^{n^{'}} (2 m^{'} + 1)$ とする。 $2 m + 1$ も $2 m^{'} + 1$ も $2$ を素因数に持たないので、素因数分解の一意性より $n = n^{'}$ であり、したがって $2 m + 1 = 2 m^{'} + 1$ すなわち $m = m^{'}$ である。

動画で詳しく解説してます（Youtube）↓

解答例３（ベルンシュタインの定理を使用）

ベルンシュタインの定理より、 $N$ から $N^{2}$ への単射と $N^{2}$ から $N$ への単射の存在を示せばよい。

N

から

N^{2}

への単射の存在

$f : N \to N^{2}, f (n) = (n, 0)$ とすればよい。

N^{2}

から

N

への単射の存在

$g : N^{2} \to N$ を $g (n, m) = 2^{n} 3^{m}$ とすると素因数分解の一意性より $g$ は単射。

解答例４（

d

進数表示を使用）

以下、自然数の「第 $i$ 桁目」とは「 $10$ 進数表示したときの第 $i$ 桁目」のこととする。

自然数 $n$ の第 $i$ 桁目を $n_{[i]}$ と書く（ $i$ が $n$ の桁数を超えるときは $n_{[i]} = 0$ ）。例えば $487_{[1]} = 7 487_{[2]} = 8 487_{[3]} = 4 487_{[4]} = 0 \dots$ である。ここで写像 $f : N \to N^{2}$ を $f (n) = (\sum_{i = 1}^{\infty} n_{[2 i - 1]} \cdot 10^{i - 1}, \sum_{i = 1}^{\infty} n_{[2 i]} \cdot 10^{i - 1})$ で定める。つまり自然数 $n$ の奇数桁だけを取り出した自然数と偶数桁だけを取り出した自然数との順序対を $f (n)$ とする。例えば $\begin{aligned} f (12345) & = (135, 24) & f (10101212) & = (22, 1111) \end{aligned}$ である。

f

の全射性

$(k, ℓ) \in N^{2}$ を任意に取る。このとき $n \in N$ を、 $n_{[2 i - 1]} = k_{[i]} n_{[2 i]} = ℓ_{[i]}$ となるように定めれば $f (n) = (k, ℓ)$ となる。これは $n = \sum_{i = 1}^{\infty} k_{[i]} \cdot 10^{(2 i - 1) - 1} + \sum_{i = 1}^{\infty} ℓ_{[i]} \cdot 10^{2 i - 1}$ とすればよい。

f

の単射性

$n \neq m$ とする。このとき $n$ と $m$ はある桁において異なる。つまり $n_{[i]} \neq m_{[i]}$ となる $i \geq 1$ が存在する。

$i$ が奇数のときは $f (n)$ の第 $1$ 成分において $\frac{i + 1}{2}$ 桁目が異なる。

$i$ が偶数のときは $f (n)$ の第 $2$ 成分において $\frac{i}{2}$ 桁目が異なる。

したがって $f (n) \neq f (m)$ である。

問題２６（整数全体の集合は可算集合）

$N$ から $Z$ への全単射が存在することを示せ。

解答例１

写像 $f : Z \to N$ を $f (n) = {\begin{cases} 2 n - 1 & (n \geq 1 のとき) \\ - 2 n & (n \leq 0 のとき) \end{cases}$ で定める。

f

の単射性

$f (n) = f (m)$ とする。

(i)

f (n)

が奇数のとき

$f (m)$ も奇数なので $2 n - 1 = 2 m - 1$ となり、 $n = m$ を得る。

(ii)

f (n)

が偶数のとき

$f (m)$ も偶数なので $- 2 n = - 2 m$ となり、 $n = m$ を得る。

f

の全射性

$m \in N$ を任意に取る。

(i)

m

が

1

以上の奇数のとき

$n = \frac{m + 1}{2}$ は $1$ 以上の整数であり $f (n) = 2 n - 1 = m$ である。

(ii)

m

が

0

以上の偶数のとき

$n = - \frac{m}{2}$ は $0$ 以下の整数であり $f (n) = - 2 n = m$ である。

よって全単射 $f^{- 1} : N \to Z$ が得られる。

解答例２（ベルンシュタインの定理を使用）

ベルンシュタインの定理より、 $N$ から $Z$ への単射と $Z$ から $N$ への単射の存在を示せばよい。

$N$ から $Z$ への単射が存在することは自明（ $N$ から $Z$ への包含写像）。

$Z$ から $N$ への単射としては、写像 $f : Z \to N$ を $f (n) = {\begin{cases} 2^{n} & (n \geq 0 のとき) \\ 3^{| n |} & (n < 0 のとき) \end{cases}$ で定めれば、 $n \neq m$ のとき素因数分解の一意性より $f (n) \neq f (m)$ となるので $f$ は単射である。

問題２７

$N_{+}$ から $Q_{+}$ への全単射が存在することを示せ。

解答例１

素数列を ${p_{n}}_{n \in N}$ とする（ $p_{0} = 2, p_{1} = 3, p_{2} = 5, \dots$ ）。写像 $f : N [X] \to N_{+}$ を $f (m_{0} + m_{1} X + \dots + m_{n} X^{n}) = p_{0}^{m_{0}} p_{1}^{m_{1}} \dots p_{n}^{m_{n}}$ で定めると、素因数分解の一意性より $f$ は全単射。また写像 $g : Z [X] \to Q_{+}$ を $g (k_{0} + k_{1} X + \dots + k_{n} X^{n}) = p_{0}^{k_{0}} p_{1}^{k_{1}} \dots p_{n}^{k_{n}}$ で定めると、素因数分解の一意性より $g$ も全単射。問題２６より全単射 $H : N \to Z$ が存在するので、これにより写像 $h : N [X] \to Z [X]$ を $\begin{aligned} h (m_{0} + m_{1} X + \dots + m_{n} X^{n}) \\ = H (m_{0}) + H (m_{1}) X + \dots + H (m_{n}) X^{n} \end{aligned}$ と定めると $h$ も全単射。よって $g \circ h \circ f^{- 1} : N_{+} \to Q_{+}$ は全単射。

解答例２（ベルンシュタインの定理を使用）

$N_{+}$ から $Q_{+}$ への単射が存在することは自明（包含写像）。

$q \in Q_{+}$ に対し $q$ の既約分数表示の分母を $D (q)$ と書き分子を $N (q)$ と書くことにする。このとき写像 $f : Q_{+} \to N_{+}$ を $f (q) = 2^{D (q)} 3^{N (q)}$ と定めると、素因数分解の一意性より $f$ は単射。

よってベルンシュタインの定理より、 $N_{+}$ から $Q_{+}$ への全単射が存在する。

問題２８（有理数全体の集合は可算集合）

$N$ から $Q$ への全単射が存在することを示せ。

解答例

問題２７より、全単射 $f : N_{+} \to Q_{+}$ が存在する。ここで写像 $F : N \to Q$ を $F (n) = {\begin{cases} f (n) & (n > 0 のとき) \\ 0 & (n = 0 のとき) \\ - f (| n |) & (n < 0 のとき) \end{cases}$ とすれば $F$ は全単射。

問題２９

集合 $X, Y, Z$ は $X \subseteq Y \subseteq Z$ を満たし、 $Z$ から $X$ への単射が存在するとする。

このとき $X$ から $Y$ への全単射、 $Y$ から $Z$ への全単射、 $X$ から $Z$ への全単射が存在することを示せ。

解答例

$X \subseteq Y \subseteq Z$ なので、包含写像を考えると

$X$ から $Y$ への単射が存在すること

$Y$ から $Z$ への単射が存在すること

$X$ から $Z$ への単射が存在すること

がわかる。一方 $Z$ から $X$ への単射が存在するという仮定を使って合成写像を考えると

$Y$ から $X$ への単射が存在すること

$Z$ から $Y$ への単射が存在すること

もわかる。以上により、ベルンシュタインの定理を用いて

$X$ から $Y$ への全単射が存在すること

$Y$ から $Z$ への全単射が存在すること

$Z$ から $X$ への全単射が存在すること

がわかる。

問題３０

半開区間 $(0, 1]$ から開区間 $(0, 1)$ への全単射が存在することを示せ。

解答例１（直接示す）

$(0, 1]$ の部分集合 $A$ と $(0, 1)$ の部分集合 $A^{'}$ を $\begin{aligned} A & = {1, \frac{1}{2}, \frac{1}{3}, \dots} = {\frac{1}{n} | n \in N_{+}} \\ A^{'} & = {\frac{1}{2}, \frac{1}{3}, \frac{1}{4}, \dots} = A ∖ {1} \end{aligned}$ とし、 $B = (0, 1] ∖ A$ とすると、 $\begin{aligned} (0, 1] & = A \cup B & A \cap B & = \emptyset \\ (0, 1) & = A^{'} \cup B & A^{'} \cap B & = \emptyset \end{aligned}$

となる。このとき

\begin{aligned} f : A & \to A^{'}, & f (\frac{1}{n}) & = \frac{1}{n + 1} \\ g : B & \to B, & g (x) & = x \end{aligned}

はどちらも全単射。よって写像

h : (0, 1] \to (0, 1)

を

h (x) = {\begin{cases} f (x) & (x \in A のとき) \\ g (x) & (x \in B のとき) \end{cases}

と定めれば

h

は全単射。

解答例２（ベルンシュタインの定理）

$(0, 1]$ から $(0, 1)$ への単射は $f (x) = \frac{x}{2}$ とすればよい。

$(0, 1)$ から $(0, 1]$ への単射は $g (x) = x$ とすればよい。

よってベルンシュタインの定理より、 $(0, 1]$ から $(0, 1)$ への全単射が存在する。

(a, b]

から

(a, b)

への全単射が欲しいときは

(0, 1]

から

(a, b]

への全単射や

(0, 1)

から

(a, b)

への全単射を作ればいい
具体的には

ℓ (x) = (b - a) x + a

閉区間

[a, b]

から開区間

(a, b)

への全単射が欲しいときは

a < c < b

となる

c

を取って
・

[a, c)

から

(a, c)

への全単射
・

{c}

から

{c}

への全単射
・

(c, b]

から

(c, b)

への全単射
を作って
場合分けを使って写像

[a, b] \to (a, b)

を定義すればいい

問題３１（カントールの定理）

$X$ を集合、 $P (X)$ を $X$ のべき集合とする。

(1)

X

から

P (X)

への全射が存在しないことを示せ。

(2)

P (X)

から

X

への単射が存在しないことを示せ。

※ したがって $X$ から $P (X)$ への全単射は存在しない。

解答例

(1)

全射 $f : X \to P (X)$ が存在するとして矛盾を導く。 $X$ の部分集合 $X_{0}$ を $X_{0} = {x \in X | x \notin f (x)}$ で定める。 $f$ の全射性より $X_{0} = f (y)$ となる $y \in X$ が存在する。

(i)

y \in X_{0}

のとき

$X_{0}$ の定義より $y \notin f (y)$ である一方 $y \in X_{0} = f (y)$ なので矛盾。

(ii)

y \notin X_{0}

のとき

$X_{0}$ の定義より $y \in f (y)$ である一方 $y \notin X_{0} = f (y)$ なので矛盾。

(2)

単射 $f : P (X) \to X$ が存在すると仮定すると、 $P (X) \neq \emptyset$ より始域と終域が逆の全射 $f : X \to P (X)$ が存在する（問題１９）が、これは (1) に矛盾。

(2) の別解答例（直接示す）

単射 $f : P (X) \to X$ が存在するとして矛盾を導く。 $X$ の部分集合 $X_{0}$ を $X_{0} = {x \in X | x = f (Y) \notin Y なる Y \in P (X) が存在}$ で定める。

(i)

f (X_{0}) \in X_{0}

のとき

$X_{0}$ の定義より $f (X_{0}) = f (Y) \notin Y$ となる $Y \in P (X)$ が存在する。このとき $f$ の単射性より $X_{0} = Y$ であり、 $f (Y) \notin Y$ より $f (X_{0}) \notin X_{0}$ となり、矛盾。

(ii)

f (X_{0}) \notin X_{0}

のとき

$f (X_{0}) = f (X_{0}) \notin X_{0}$ なので $X_{0}$ の定義より $f (X_{0}) \in X_{0}$ となり、矛盾。

これからカントールのパラドックス
「すべての集合からなる集合は存在しない」
を導ける

「任意の集合

X

に対し

X \in V

」となるような
集合

V

が存在すると仮定すると

P (V) \subseteq V

が成り立ち
包含写像を考えて

P (V)

から

V

への単射が構成できる
でもこれはカントールの定理（問題３１(2)）に矛盾

定義

写像 $f, g : N \to N$ に対し $f + g, f g : N \to N$ を $\begin{aligned} (f + g) (n) & = f (n) + g (n) \\ (f g) (n) & = f (n) g (n) \end{aligned}$ と定める。

問題３２

$f, g : N \to N$ とする。このとき

$f$ も $g$ も単射ならば $f + g$ も単射

は一般に成り立つか？

解答例

一般には成り立たない。反例として $\begin{aligned} f (n) = n & g (n) = {\begin{cases} 1 & (n = 0 のとき) \\ 0 & (n = 1 のとき) \\ n & (n \geq 2 のとき) \end{cases} \end{aligned}$ とすると $f$ も $g$ も単射だが、 $\begin{aligned} (f + g) (0) = 0 + 1 = 1 & (f + g) (1) = 1 + 0 = 1 \end{aligned}$ なので $f + g$ は単射ではない。

問題３３

$f, g : N \to N$ とする。このとき

$f$ も $g$ も単射ならば $f g$ も単射

は一般に成り立つか？

解答例

一般には成り立たない。問題３２の解答例で用いた反例において $\begin{aligned} (f g) (0) = 0 \cdot 1 = 0 & (f g) (1) = 1 \cdot 0 = 0 \end{aligned}$ なので $f g$ は単射ではない。

問題３４

$f, g : N \to N$ とする。このとき

$f$ も $g$ も全射ならば $f + g$ も全射

は一般に成り立つか？

解答例

一般には成り立たない。反例として $\begin{array}{r} f (n) = g (n) = n \end{array}$ とすると $f$ も $g$ も全射だが、 $\begin{array}{r} (f + g) (n) = 2 n \end{array}$ であり $(f + g) (n) = 1$ となる $n$ が存在しないので $f + g$ は全射ではない。