はじめに
先日、kindleの割引セールのときに購入し、積読状態になっていた「イラストで学ぶ 離散数学」を少しずつ読み始める。
数学的に厳密ではなく、フワッと理解すれば十分なので、覚書です。
数学本をまともに読んだの、5年ぶりくらいかなぁ。
9章
例題9.1
任意の正整数 $n$ に対して、$n$ と互いに素な整数が無限に存在することを示せ。
- $n$ の素因数を考える
正整数 $n$ を素因数分解すると、いくつかの素数から成り立っている。
これらの素因数を $p_1, p_2, \dots, p_k$ とする。
2. 互いに素な数とは？
$n$ と互いに素であるとは、$n$ の素因数（ここでは $p_1, p_2, \dots, p_k$）を一つも持たない数。
3. 他の素数を考える
素数は無限に存在する。したがって、$p_1, p_2, \dots, p_k$ 以外にも無限に多くの素数が存在する。
4. 結論
$p_1, p_2, \dots, p_k$ 以外の素数はすべて $n$ と互いに素。
これらの素数を使えば、$n$ と互いに素な整数を無限個作ることができる。
よって、$n$ と互いに素な整数は無限に存在する。
ふわっふわだけど、私にとってはこれで十分よ。
定義9.4
集合の濃度について
- 濃度の定義
集合の「濃度（cardinality）」とは、集合の大きさ（要素の数）を表す概念。集合 $A$ の濃度を $|A|$ と表す。
2. 有限集合の場合
集合が有限の場合、その濃度は単純に集合の要素数と等しいとする。
例: $A = {1, 2, 3}$ の場合、$|A| = 3$。
3. 無限集合の場合
無限集合では、要素数を数えることができないため、濃度を次のように定義する
- 単射による比較
無限集合 $A$ から無限集合 $B$ への**単射（injective function）**が存在する場合、$|A| \leq |B|$ とする。
（単射とは、$A$ の異なる要素が $B$ の異なる要素に対応する関数。）
- 全単射による等しさ
無限集合 $A$ から無限集合 $B$ への**全単射（bijective function）**が存在する場合、$|A| = |B|$ とする。
（全単射とは、$A$ のすべての要素が $B$ のすべての要素と一対一に対応する関数。）
ポイント
- 無限集合同士でも「大きさ」を比較できる。
- 単射が存在すれば「片方の集合はもう片方以下」とみなせる。
- 全単射が存在すれば「二つの集合は同じ大きさ」とみなせる。
イメージ例
- 自然数全体の集合 $\mathbb{N} = {1, 2, 3, \dots}$ と整数全体の集合 $\mathbb{Z} = {\dots, -2, -1, 0, 1, 2, \dots}$ はどちらも無限だが、全単射を構成できるため、$|\mathbb{N}| = |\mathbb{Z}|$ といえる。(補足1)
- 自然数全体の集合 $\mathbb{N}$ と実数全体の集合 $\mathbb{R}$ を比べると、実数全体には自然数からの単射しか作れず、全単射は作れない。このため、$|\mathbb{N}| < |\mathbb{R}|$ となる。
補足1
次のような関数 $f: \mathbb{N} \to \mathbb{Z}$ を考える。
$$
f(n) =
\begin{cases}
-\frac{n}{2}, & \text{if } n \text{ is even (偶数)}, \
\frac{n+1}{2}, & \text{if } n \text{ is odd (奇数)}.
\end{cases}
$$
- 偶数の自然数 $n = 2, 4, 6, \dots$ に対して、$f(n)$ は負の整数 $-1, -2, -3, \dots$ に対応する。
- 奇数の自然数 $n = 1, 3, 5, \dots$ に対して、$f(n)$ は非負の整数 $0, 1, 2, \dots$ に対応する。
例題9.2
正の偶数の集合 $E = \{2, 4, 6, \ldots\}$ と正整数の集合 $\mathbb{N} = \{1, 2, 3, \ldots\}$ の間に全単射 $f : \mathbb{N} \to E$ が存在することを示せ。
解説
全単射とは？
全単射とは、次の2つの条件を満たす写像（関数）のこと
- 単射：異なる入力が異なる出力に対応する（1対1である）。
- 全射：出力側（集合 $E$）のすべての要素に対応する入力が存在する。
つまり、全単射が存在すれば、2つの集合 $\mathbb{N}$ と $E$ の要素が完全に1対1で対応していることを意味する。
提案された写像
問題文では、次の写像 $f$ を提案している。
$ f(i) = 2i $ここで、$i$ は正整数（つまり $i \in \mathbb{N}$）となる。この写像が全単射であるかを確認する。
(1) 単射であることの証明
単射であるとは、異なる入力に対して異なる出力が得られることを意味する。
- 任意の $i_1, i_2 \in \mathbb{N}$ について、$f(i_1) = f(i_2)$ を仮定する。
- このとき、$2i_1 = 2i_2$ が成り立つ。
- 両辺を 2 で割ると、$i_1 = i_2$ が得られる。
したがって、異なる正整数 $i_1, i_2$ に対して $f(i_1) \neq f(i_2)$ となるため、この写像は単射です。
(2) 全射であることの証明
全射であるとは、出力側（集合 $E$）の任意の要素に対応する入力が存在することを意味する。
- 任意の正の偶数 $y \in E$ を取る。偶数であるため、$y = 2k$ （ただし $k \in \mathbb{N}$）と書ける。
- このとき、$f(k) = 2k = y$ が成り立つ。
- よって、任意の偶数 $y \in E$ に対応する正整数 $k \in \mathbb{N}$ が存在する。
したがって、この写像は全射となる。
結論
写像 $f(i) = 2i$ は単射かつ全射であるため、全単射である。
この結果から、正整数の集合 $\mathbb{N}$ と正の偶数の集合 $E$ の要素は完全に1対1対応しており、これらの集合は同じ「濃度」（要素数）を持つことが分かる。
定理9.5
整数の集合 $ \mathbb{Z} $ と有理数の集合 $ \mathbb{Q} $ の間には、全単射（1対1対応）$ f_{9.5} : \mathbb{Z} \to \mathbb{Q} $ が存在する。
証明
まず、正整数の集合 $ \mathbb{Z}_ + $ と正の有理数の集合 $ \mathbb{Q}_ + $ の間に全単射 $ g : \mathbb{Z}_ + \to \mathbb{Q}_ + $ を構成する。
任意の正の有理数 $ q \in \mathbb{Q}_ + $ は、互いに素な正整数 $ m, n \in \mathbb{Z}_ + $ を用いて次の形で表すことができる。
$q = \frac{m}{n}$
ここで、分母 $ n $ を固定したとき、その分子 $ m $ の値を昇順に並べることで列を作る。
$m_{n,1}, m_{n,2}, m_{n,3}, \dots$
ただし、各 $ m_{n,i} $ は $ m_{n,i} $ と $ n $ が互いに素であるように選ぶ。
具体例
-
$ n = 2 $ の場合
- $ m = 1 $：1 と 2 は互いに素なので、$ m_{2,1} = 1 $。
- $ m = 2 $：2 と 2 は互いに素ではないので、この場合は除外。
- $ m = 3 $：3 と 2 は互いに素なので、$ m_{2,2} = 3 $。
このようにして、任意の正整数 $ n \in \mathbb{Z}_ + $ に対して、無限に多くの $ m_{n,i} $ が存在します（例題 9.1 を参照）。
次に、このような $ m_{n,i} / n $ の形で表される正の有理数を図や表形式で配置する。
例えば以下のような表になる。
| $ n = 1 $ | $ n = 2 $ | $ n = 3 $ | ... | |
|---|---|---|---|---|
| 1行目 | $ 1/1 $ | $ 1/2 $ | $ 1/3 $ | ... |
| 2行目 | $ 3/2 $ | $ 2/3 $ | ... | |
| 3行目 | $ 4/3 $ | ... |
この表にはすべての正の有理数が一度だけ現れることが保証される。
この構成によって、正整数の集合 $ \mathbb{Z}_ + $ と正の有理数の集合 $ \mathbb{Q}_ + $ の間の全単射 $ g : \mathbb{Z}_ + →\mathbb{Q}_ + $ が得られる。
次に、この対応を利用して、整数全体の集合 $ \mathbb{Z} = { ..., -3, -2, -1, 0, 1, 2, 3, ... } $ と有理数全体の集合 $ \mathbb{Q} = { ..., -\frac{3}{2}, -\frac{1}{2}, 0, +\frac{1}{2}, +\frac{3}{2}, ... } $ の間の全単射を構成する。
具体的には以下のように定義する。
- 正整数部分：$ g(n) (n > 0) $ をそのまま利用して正の有理数に対応させる。
- 負整数部分：$ g(n)(n > 0) $ を負符号付きで対応させる。
- ゼロ：$ f(0) = 0$。
このようにして、全単射 $ f_{9.5} :\mathbb{Z} →\mathbb{Q} $ が得られる。
定理9.7(2025年2月18日脱落ポイント)
正整数の集合 $ \mathbb{N}^ + $（1, 2, 3, ...）から区間 $ (0,1] $（0より大きく1以下の実数）への全射関数は存在しない。
「全射」とは、関数 $ f: \mathbb{N}^ + \to (0,1] $ がすべての $ r \in (0,1] $ に対して、ある $ i \in \mathbb{N}^ + $ を用いて $ f(i) = r $ を満たす場合を指す。
つまり、「$ (0,1] $ のすべての要素が関数 $ f $ によって表される」ということ。
この定理は、「正整数の集合（可算無限集合）では、$ (0,1] $ のような実数区間（非可算無限集合）の全てを網羅することはできない」という事実を示している。
証明の概要
仮定
全射関数 $ f : \mathbb{N}^ + \to (0,1] $ が存在すると仮定する。
この場合、任意の $ r \in (0,1] $ は、ある正整数 $ i \in \mathbb{N}^ + $ を用いて $ r = f(i) $ と表せる。
三進数表記について
$ (0,1] $ の任意の実数 $ r $ は、三進数（3進法）で次のように表現できる。
$ r = 0.d_1 d_2 d_3 d_4 \dots $
ここで、各桁 $ d_k $ は 0, 1, 2 のいずれかになる。
- 無限小数として表記する（例えば、1 は $ 0.222\ldots $ と書く）。
- 各実数は、この方法で一意的に表される。
例えば：
- $ r = 0.12 = 0.11222\ldots $
- $ r = 1 = 0.222\ldots $
この三進数表記を使うことで、$ (0,1] $ の任意の実数を扱えるようになる。
矛盾する要素の構成
仮定によれば、関数 $ f : \mathbb{N}^ + \to (0,1] $ は全射なので、各正整数 $ i \in \mathbb{N}^ + $ に対して対応する値 $ f(i) = r_i = 0.d_1^{(i)} d_2^{(i)} d_3^{(i)}\dotsb $ が存在する。
ここで：
- $ d_k^{(i)} $ は、$ f(i) $ の三進数表記における第 $ k $ 桁目を意味する。
次に、この三進数表記を利用して、新しい実数 $ r_f = 0.e_1 e_2 e_3 e_4\dotsb \in (0,1] $ を次のように構成する。
$$
e_k =
\begin{cases}
1 & (d_k^{(k)} = 2 の場合), \
2 & (d_k^{(k)} = 1 の場合), \
1 & (d_k^{(k)} = 0 の場合).
\end{cases}
$$
つまり：
- 第 $ k $ 桁目 $ e_k $ は、$ f(k) = r_k = 0.d_1^{(k)} d_2^{(k)} d_3^{(k)}\dotsb $ の第 $ k $ 桁目 $ d_k^{(k)} $ と異なる数字になるように選ぶ。
このようにして構成された実数 $ r_f = 0.e_1 e_2 e_3\dotsb \in (0,1] $ は、「どの $ f(i) = r_i $ にも一致しない」ことが保証される。
なぜなら：
- 仮に一致するとすると、ある正整数 $ i' \in \mathbb{N}^ + $ が存在して $ r_f = f(i') = r_{i'} = 0.d_1^{(i')} d_2^{(i')} d_3^{(i')}\dotsb$ が成り立つはず
- 上記の構成法では、$ r_f $ の第 $ i' $桁目が必ず対応する三進数字と異なるため、この等式は成立しない。
矛盾
このようにして構成された実数 $ r_f \in (0,1] $ は、「どの正整数にも対応しない」ため、$ f : \mathbb{N}^+ → (0,1]$ 」が全射である」という仮定に矛盾する。
結論
したがって、「正整数から区間 $$ (0,1] 」への全射関数は存在しない」ということが証明された。
うーーーむ。2025年2月18日時点、ここで脱落。