普通, 公理を 集合 存在を仮定, 別 （ 基本的 考 ）公 理 , 公理を 集合 存在を証明 , 集合を N¯ 書 . 2.(iii)を 数学的帰納法 公理 .
定理 1.8.3 (数学的帰納法). P(n)をN¯ 元 関 述語 , 次 成 立 . 1. P(0) 真.
2. P(n) 真 P(n+ 1) 真.
, 任意 n∈N¯ 対 , P(n) 真 .
証明. P(n) 真 n∈N¯ 全体をN . N ={
n∈N¯ P(n)}
条件1 0∈N . 条件2 ,n∈N suc(n)∈N, suc(N)⊂N
. 数学的帰納法 公理 N = ¯N.
自然数 性質 全 公理 1.8.2 導 . （[5]等参照.）例 次 示 .
命題 1.8.4. Im suc =N.
n∈N 対 , suc−1(n)をn−1 書 .
定理 1.8.5. N¯ , n <suc(n)（ n < n+ 1） 任意 n∈N¯ 対 成 立 順序 存在 . , 順序 次を .
1. 順序 全順序 .
2. suc 順序を保 . （ m≤n m+ 1≤n+ 1 .）
3. m < n suc(m)≤n. （ m < n m+ 1≤n .）
m 直後 元 m+ 1 , m 直前 元 m−1 .
4. 0 = min ¯N.
問 43. 全順序集合 , 直後（直前） 元 , 存在 一意的.
以下 議論 , 命題 1.8.4, 定理 1.8.5 断 用 .
使 , 集合[n]を定義 . 定義 1.8.6. n∈N¯ 対 , ¯N 部分集合[n]を
[n] :={
m∈N¯ m < n}
1.8 濃度 73 定 .
, [n]を順序集合 考 , 断 N¯ 入 順序を入 .
補題 1.8.7. 1. [0] =∅. 2. [n+ 1] = [n]∪ {n}.
3. min[n+ 1] = 0, max[n+ 1] =n.
証明.（2016年度 ） 1. 0 = min ¯N .
2. m < n+ 1 ⇔ m ≤ n 成 立 . ⇐ n < n+ 1 明 . ⇒ , m > n
m≥n+ 1 , ¯N 順序 全順序 . [n+ 1] = [n]∪ {n}.
3. 0 = min ¯N 0≤n+ 1. n+ 1∈Im suc̸∋0 0̸=n+ 1. 0< n+ 1 0∈[n+ 1]. 0 = min[n+ 1].
n < n+ 1 n ∈ [n+ 1]. m ∈ [n+ 1] m < n+ 1 m ≤ n.
n= max[n+ 1].
.
補題 1.8.8. A⊂[n] , m∈N¯, m≤ n 存在 , A [m] 順序同型 :
A ∼= [m]. , A [n] 入 順序を入 .
証明. n 関 帰納法. n= 0 [0] =∅ A=∅ ∼= [0] O.K.
n 成立 , A ⊂ [n+ 1] = {0, . . . , n} = [n]∪ {n} を考 . n ̸∈ A A ⊂ [n] 帰納法 仮定 O.K. n ∈ A A\ {n} ⊂ [n]
, 帰納法 仮定 , m ∈ N¯, m ≤ n 存在 順序同型 f: A \ {n} →
[m] = {0,1, . . . , m−1} 存在 . m ≤ n m+ 1 ≤ n+ 1 . 写像 f¯: A→[m+ 1] = [m]∪ {m}を
f(l) =¯ {
f(l), l̸=n m, l=n 定 明 f¯ 順序同型 .
系 1.8.9. n∈N¯ . 任意 ∅ ̸=A⊂[n] 対 , minA 存在 .
証明. ∅ ̸= A⊂[n] . m≤n 順序同型g: [m]→A 存在 . A ̸=∅ m >0 0 = min[m]. 明 g(0) = minA.
定義 1.8.10. 順序集合(X,≤) 任意 空 部分集合 最小元を持 , 順序
≤を整列順序(well-order) , (X,≤)を整列集合(well-ordered set) .
上 見 , 任意 n∈N¯ 対 , [n] 整列集合 . 次 分 .
定理 1.8.11. N¯ 数 大小関係 順序を 整列集合 .
証明. A ⊂ N¯, A ̸= ∅ . n ∈Aを一 . An :={a ∈A a≤n}= A∩[n+ 1]
An ⊂ [n+ 1] , n ∈ An An ̸= ∅. 系 1.8.9 An 最
小元 存在 . m := minAn m = minA . 実際, m ∈ An ⊂ A
m∈ A. a∈ A . a ≤n , a ∈An a≥ minAn =m. a ≥n , n∈An 注意 , a≥n≥minAn =m a≥m.
注意 . 上 証明 N¯ 順序 全順序 を用 （ ?）. 話 持
行 方 , 整列順序 を示 , 全順序 を導
場合 .
命題 1.8.12. 整列順序 全順序 .
証明. (X,≤)を整列集合 . x, y ∈X min{x, y} 存在 . min{x, y}= x x≤y, min{x, y}=y y≤x .
命題 1.8.13. 整列集合 全射 切断を持 . , X 整列集合,f: X →Y
全射 , 写像s: Y →X f ◦s= idY 存在 .
, 任意 n∈N¯ 対 , [n] 全射 切断を持 .
証明. Y ̸=∅ 場合を考 . 写像s: Y →X をs(y) = minf−1(y) 定 .（f 全射 任意 y ∈ Y 対 f−1(y)̸= ∅ , X 整列集合 minf−1(y) 存在 . ）s(y)∈f−1(y) f◦s = idY.
1.8.2 有限集合
有限集合 言葉を 使 , 定義 基本的
性質を与 .
定義 1.8.14. 集合X 有限集合(finite set)
⇔def 非負整数n∈N¯ 存在 , X [n] 対等 .
注意 . 有限集合 定義 仕方 流儀 . 適当 仮定
同値 . 述 定義 最 思 , 一番標準的
.
補題 1.8.8 次 分 .
系 1.8.15. 有限集合 部分集合 有限集合 .
1.8 濃度 75 証明. X を有限集合, A ⊂ X . 定義 n ∈N¯ 全単射f: X → [n] 存在
. f A 制限 A ∼=f(A)⊂[n] . m∈N¯ 存在 f(A)∼= [m]
A∼= [m].
系 1.8.16. X を有限集合,Y を集合 . 全射X →Y 存在 ,Y 有限集合 .
証明. Y ̸=∅ . [n]∼=X ,全射X →Y 合成f: [n]−→∼= X →Y を考
f 全射 . 命題 1.8.13 f 切断s: Y → [n]を持 . s(Y) ⊂ [n]
s(Y) 有限集合. f◦s = idY s 単射. Y ∼=s(Y) 有限集合.
補題 1.8.8 ん 同様 示 , 次 補題 1.8.17 元 個数を考 上 基本的
.
補題 1.8.17. m, n∈N¯ . 次 成 立 . 1. 単射f: [m]→[n] 存在 ⇔m≤n.
2. 全射 単射f: [m]→[n] 存在 ⇔m < n.
証明. 1,2 ⇐ 包含写像を考 明 .
（2016年度 ） ⇒を示 .
1. n 関 帰納法 示 . n= 0 [0] =∅ 写像f: [m]→[0] 存在
[m] =∅, m= 0 . 成立.
n 成立 仮定 . f: [m]→[n+ 1] = [n]∪ {n}を単射 . n ̸∈f([m]) 場 合. f([m])⊂[n] f [m]−→f [n],→[n+ 1] 分解 . 帰納法 仮定 m≤n.
m≤n+ 1 O.K. n∈f([m]) 場合. f([m])̸=∅ , [m]̸=∅ m >0. l∈[m],f(l) =n . σ: [m]→[m]をl m−1 互換,
σ(k) =
m−1, k=l l, k=m−1 k, k̸=l, m−1
与 全単射 , 合成f′: [m−1],→[m]−→σ [m]−→f [n+ 1] を考 . f′ 単射 合成 単射 , n̸∈f′([m−1]) . 前半 議論 m−1≤n ,m≤n+ 1 .
2. 単射f: [m]→[n] 全射 . l∈[n]\f([m])を一 . 写像f′: [m+ 1] = {0, . . . , m} →[n]を
f′(k) =
{f(k), k < m l, k=m
定 明 f 単射. 1 m+ 1≤n m < n.
.
系 1.8.18. m, n ∈N .
1. 全射f: [m]→[n] 存在 ⇔m≥n.
2. 単射 全射f: [m]→[n] 存在 ⇔m > n.
証明. ⇐ . （m > n 単射[m]→[n] 存在 注意.）
（2016 年度 ） ⇒を示 . f: [m] → [n]を全射 . 命題 1.8.13 , f 切断
g: [n]→[m]を持 . f◦g= id[n] g 単射. n≤m.
f 単射 g 全射 . n < m. （g 全（単）射
f （全）単射 , g 作 方 .） . 注意 . ⇒ m= 0 n= 0 正 .
問 44. m, n ∈N,m≥n . 全射[m]→[n]を作 . 系 1.8.19. X ∼=Y X ∼= [n] Y ∼= [m] m=n.
証明. 仮定 [m] ∼= [n] . 単射[m] → [n], [n] → [m] 存在
m≤n n≤m m=n.
定義 1.8.20. X を有限集合 . X ∼= [n] , n∈ N¯ をX 元 個数
濃度 (cardinality) , ♯X, |X|等 表 . 系 1.8.19をX = Y 場合 使 ,
n X 対 一意 定 .
系 1.8.21. X, Y を有限集合 . X ∼=Y ⇔ |X|=|Y|. 問 45. を示 .
系 1.8.22. X, Y を|X|=|Y| 有限集合 , f: X →Y を写像 . 次 同値. 1. f 単射.
2. f 全射. 3. f 全単射.
X 有限集合 , 写像f: X →X 対 同値.
問 46. を示 . ( : X =Y = [n] （ ?）. X = Y = [n] 場合
補題 1.8.17 2, 系1.8.18 2 分 .)
系 1.8.23. X を有限集合, A⊂X . , A∼=X ⇔A =X.
, 有限集合 真部分集合 対等 . 証明. ⇐ 明 .
1.8 濃度 77
⇒を示 . A ∼= X . |A| = |X| . i: A → X を包含写像
, i 単射 , 系 1.8.22 i 全射. 包含写像 全射 A =X.
系 1.8.24. X を集合, Y を有限集合 . 1. 次 同値.
(i) X 有限集合 |X| ≤ |Y|.
(ii) X Y 単射 存在 .
2. 次 同値.
(i) X 有限集合 |X|=|Y|.
(ii) X Y 全単射 存在 .
(iii) X Y 単射 Y X 単射 存在 .
3. 次 同値.
(i) X 有限集合 |X|<|Y|.
(ii) X Y 単射 存在 , X Y 全単射 存在 .
(iii) X Y 単射 存在 , Y X 単射 存在 .
証明. １ 系 1.8.15, 補題 1.8.17 明 .
２ １ 系 1.8.21 明 . 3 1,2 明 .
系 1.8.25. X ̸=∅を集合, Y を有限集合 . 次 同値.
1. X Y 単射 存在 .
2. Y X 全射 存在 .
証明. 系 1.8.15, 系1.8.16, 補題 1.8.17 系1.8.18 明 . 有限集合 濃度 関 基本的 性質を挙 .
定理 1.8.26. X, Y を有限集合 . ,
1. X⨿Y 有限集合 |X ⨿Y|=|X|+|Y|. 2. X×Y 有限集合 |X×Y|=|X||Y|. 3. YX 有限集合 |YX|=|Y||X|.
直感的 明 . , ん 証明 ,自然数 和, 積,
冪乗を 定義 必要 . 講義 定理 証明
述 . （[5]等参照.）
系 1.8.27. X を有限集合 , P(X) 有限集合 |P(X)|= 2|X|.
証明. P(X)∼= 2X.
系 1.8.28. A, B を有限集合 . |A∪B|=|A|+|B| − |A∩B|. 証明.
A∪B = (A\B)⨿(A∩B)⨿(B\A) A = (A\B)⨿(A∩B)
B = (B\A)⨿(A∩B).
問 47. 1. A, B, Cを有限集合 .
|A∪B∪C|=|A|+|B|+|C| − |A∩B| − |B∩C| − |C∩A|+|A∩B∩C|. 2. A0, A1, . . . , An−1 を有限集合 . ,
∪
i∈[n]
Ai
= ∑
I⊂[n]
|I|is odd
∩
i∈I
Ai
− ∑
∅̸=I⊂[n]
|I|is even
∩
i∈I
Ai
.
注意 . ∩
i∈∅Ai =∪
i∈[n]Ai 約束 （1.5節 注意参照）上 式
∑
I⊂[n]
|I|is even
∩
i∈I
Ai
= ∑
I⊂[n]
|I|is odd
∩
i∈I
Ai
書 .
問 48. X ̸=∅を順序集合, A⊂X を有限部分集合 .
1. A 有界 例 挙 .
2. X 全順序集合 , A̸=∅ , maxA, minA 存在 を,A 元 個数 関 帰納法を用 示 .
3. X 全順序集合 , A 有限部分集合 , A 有界 を示 .
1.8.3 無限集合
定義 1.8.29. 集合X 無限集合(infinite set)
⇔def X 有限集合 .
1.8 濃度 79 例 1.8.30. N 無限集合 . 実際,f: N→Nをf(n) =n+ 1 定 , f 単射
全射 . 系1.8.22 N 有限集合 .
定義 1.8.31. 集合X Y 同 濃度(cardinality)を持
⇔def X Y 対等（X ∼=Y） .
|X|=|Y| 書 .
注意 . 定義 |X|=|Y| X ∼=Y 他 . ん本来 , 集合X 対 , （有限集合 場合 元 個数 ）|X| 「量」を定義
, を濃度 , X Y 濃度 等 X ∼=Y 同値 を示
正 態度 .
教科書[6] , 対等 同値「関係」 X 「同値類」を|X| 定 最 自然 考 方 , 一般 , 集合X 対等 集合全体 集合 .
有限集合 場合, |X|=n 集合 代表 [n]を考 . 同 , 無限 集合 場合 , 濃度 等 集合 中 一 標準的 を構成 , （ 対等
同値関係 完全代表系を一 構成 , ） を濃度 定義 標準的考 方
. , 準備 多 必要 講義 .
例 1.8.32. |N|¯ =|N|. 実際, ¯N→N, n7→n+ 1 全単射を与 .
例 1.8.33. 開区間 (0,1) ⊂ R 半開区間 (0,1] ⊂ R 濃度 等 . 実際, 写像 f: (0,1]→(0,1)を
f(x) = { 1
n+1, ∃n∈N:x= n1
x, 他
定 f 全単射 .
例 1.8.34. 開区間 (0,1) ⊂ R R>0 = {x ∈R x >0} 濃度 等 . 実際, 写像 f: (0,1)→R>0をf(x) =x/(1−x) 定 f 全単射.
問 49. 次 R 部分集合 対 , 全単射を具体的 構成 濃度 等 を示 . 1. 開区間(0,1) 閉区間[0,1].
2. 開区間(0,1) R.
定義 1.8.35. X, Y を集合 . X Y 単射 存在 , |X| ≤ |Y| 書 .
|X| ≤ |Y| |X| ̸=|Y| （ , X Y 単射 存在 全単射 存在 ）, |X|<|Y| 書 , X 濃度 Y 濃度 小 .
注意 . 系 1.8.24 , 有限集合 対 , 濃度 大小 数 大小 一致 . 任意 集合 対 , 大 濃度を持 集合 存在 .
定理 1.8.36 (Cantor). 任意 集合X 対 , |X|<|P(X)|.
証明. X =∅ P(X) ={∅} 明 .
X ̸= ∅ . singleton map s: X → P(X), s(x) = {x} 単射 |X| ≤
|P(X)|. , X P(X) 全射 存在 を示 . f: X → P(X) を写像 .
A ={x∈X x̸∈f(x)} ∈ P(X)
A ̸∈ Imf . 実際, 任意 y ∈ X 対 , y ∈ f(y) 場合 y ̸∈ A f(y)̸=A, y̸∈f(y) 場合 y∈A f(y)̸=A.
証明 論法（A 構成）を対角線論法(diagonal argument) （定 理 1.8.53, 1.10.20 参照）.
濃度 大小関係 「順序」 .
補題 1.8.37. X, Y を集合, f: X → Y, g: Y → X を写像 . , 部分集合 A ⊂X, B⊂Y , f(A) =B, g(Bc) =Ac 存在 .
証明. S ⊂X 対 F(S)⊂ X をF(S) =g(f(S)c)c ⊂X 定 . F(A) =A 集合A ⊂Xを B=f(A) .
F: P(X)→ P(X) 順序を保 , , S, T ⊂X 対 , S ⊂T ⇒F(S)⊂F(T)
成 立 . 実際
S ⊂T ⇒f(S)⊂f(T)
⇒f(S)c ⊃f(T)c
⇒g(f(S)c)⊃g(f(T)c)
⇒g(f(S)c)c ⊂g(f(T)c)c. X 部分集合族
A={S ∈ P(X) S ⊂F(S)} ⊂ P(X) を考 .
（証明 使 ）明 ∅ ⊂F(∅) ∅ ∈ A. A ̸=∅ . A=∪
S∈AS . (例 1.7.30 見 A= supA .)
1.8 濃度 81 F(A) =Aを示 .
明 , 任意 S ∈ A 対 S ⊂A 注意 . 1. 任意 S ∈ A 対 S ⊂F(A).
実際S ∈ A , S ⊂ A , F 順序を保 F(S) ⊂ F(A).
S ∈ A S ⊂F(S). S ⊂F(A).
2. A∈ A, A ⊂F(A) .
実際, 1 S ∈ A S ⊂F(A) , A =∪
S∈AS ⊂F(A).
3. 任意 S ∈ A 対 F(S)∈ A.
実際, S ∈ A S ⊂F(S) , F 順序を保 F(S)⊂F(F(S)).
4. F(A)⊂A.
実際, 2 A ∈ A , 3 F(A)∈ A. A 定 方F(A)⊂A.
2, 4 , F(A) =A.
問 50 (Tarski’s fixed point theorem). P を順序集合, f: P → P を順序を保 写像 .
A ={a∈P a≤f(a)}
上限を持 , α = supA . α = maxA 及 , f(α) = α
を以下 順 示 .
1. f(α) A 上界 , ∀a∈A :a≤f(α).
2. α ∈A, α≤f(α). α = maxA.
3. ∀a∈A :f(a)∈A.
4. f(α)≤α.
5. f(α) =α.
問 51. X, Y を集合, f:X →Y, g: Y →X を写像 . A ={S ⊂X S ⊃F(S)}
. 次を示 .
1. A ̸=∅ . 2. A=∩
S∈AS F(A) =A .
具体的 写像 対 補題 1.8.37 証明 方法 F(A) =A Aを求 一般 難 （ 思 ）. f g 単射 場合, 次 求
. , （X = Y, f, g 恒等写像を考 分 ）
A 一意的 定 . 補題 1.8.37 定 , 部分集 合 最大 , 上 exe. 定 最小 .
問 52. X, Y を集合, f: X → Y, g: Y →X を写像 . F: P(X) → P(X)を F(S) = g(f(S)c)c 定 , i∈N¯ 対 Fi(S)を帰納的 , F0(S) =S, Fi+1(S) = F(Fi(S)) 定 . {Sλ}λ∈ΛをX 部分集合 族 . Λ̸=∅ .
1. g 単射 . 次を示 .
(i) F(∪
λSλ) =∪
λF(Sλ) (ii) A =∪∞
i=0Fi(∅) F(A) =A.
2. f 単射 . 次を示 .
(i) F(∩
λSλ) =∩
λF(Sλ).
(ii) A =∩∞
i=0Fi(X) F(A) =A.
注意! . 何度 注意 , 念 為. ∪∞
i=0Fi(∅) ∪
i∈N¯Fi(∅)
. F∞(∅) 集合を考 .
系 1.8.38 ( , Bernstein). X, Y を集合 . 次 同値.
1. X ∼=Y.
2. X Y 単射 , Y X 単射 存在 .
証明. 2⇒1 を示 . f: X → Y, g: Y → X を単射 . 補題 1.8.37 ,
A ⊂X, B⊂Y f(A) =B, g(Bc) =Ac . f, g 単射
f|A: A −→∼= B, g|Bc: Bc −→∼= Ac . h: X →Y を
h(x) = {
f(x), x ∈A (g|Bc)−1(x), x ̸∈A 定 h 全単射.
系 1.8.39. 濃度 大小関係 次を . X, Y, Zを集合 . 1. |X| ≤ |X|.
2. |X| ≤ |Y| |Y| ≤ |X| |X|=|Y|. 3. |X| ≤ |Y| |Y| ≤ |Z| |X| ≤ |Z|.
証明. 1 明 . ２ Bernstein 定理. ３ 単射 合成 単射 明
.
1.8 濃度 83 系 1.8.40. X, Y を集合 . 次 同値
1. |X|<|Y|.
2. X Y 単射 存在 , X Y 全単射 存在 .
3. X Y 単射 存在 , Y X 単射 存在 .
系 1.8.41. X, Y, Z を集合 .
|X|<|Y| |Y| ≤ |Z| |X|<|Z|.
|X|<|Y| Y ⊂Z |X|<|Z|. 問 53. を示 .
系 1.8.42. X, Y, Z を集合 .
|X| ≤ |Y| |Y| ≤ |Z| |X|=|Z| |X|=|Y|=|Z|.
系 1.8.43. X を集合, A ⊂ X , A ∼=X . , A ⊂ B ⊂X B ∼=X.
証明. 包含写像 単射.
例 1.8.44. 問 49 見 (0,1)∼= R . (0,1)⊂ (0,1]⊂ [0,1]⊂ R 濃度 全 等 .
一般 , a, b ∈ R, a < b 存在 (a, b) ⊂A ⊂R A ∼= R .
（ , 逆 正 . , A ∼= R A ⊂R , A 開区間を含
存在 . 時間 都合 思 有名 集合
(Cantor set) .）
問 52を用 全単射(0,1)→ (0,1]を作 . f: (0,1) →(0,1]を包含写像 , g: (0,1]→(0,1)をg(x) =x/2 定 , 単射.
f(∅)c = (0,1]
g(f(∅)c) = (0,1/2] F(∅) = (1/2,1) f(F(∅))c = (0,1/2]∪ {1}
g(f(F(∅))c) = (0,1/4]∪ {1/2} F2(∅) = (1/4,1/2)∪(1/2,1) f(F2(∅))c = (0,1/4]∪ {1/2} ∪ {1}
g(f(Fc(∅))c) = (0,1/8]∪ {1/4} ∪ {1/2} F3(∅) = (1/8,1/4)∪(1/4,1/2)∪(1/2,1) . . .
全単射 組
(0,1)⊃A=
∪∞ i=0
(1/2i+1,1/2i)−−−→f=id∼
=
∪∞ i=0
(1/2i+1,1/2i) =B⊂(0,1]
(0,1)⊃Ac ={
1/2i i≥1} g−1=2×
−−−−−→∼
=
{1/2i i≥0}
=Bc ⊂(0,1]
を得 . h: (0,1)→(0,1]を
h(x) = {
x, x∈A 2x, x̸∈A 定 h 全単射.
g: (0,1]→(0,1) g(x) =x/(x+ 1)を使 同 構成を 例1.8.33 全単 射（ 逆写像） 得 .
1.8.4 可算集合 , 連続体 濃度
定義 1.8.45. N 濃度 等 集合を可算集合(countable set) . X 可算集 合 , X 濃度 可算無限濃度 , |X|=ℵ0（ ） 表 .
X 可算集合 , 直観的 言 X 元全 , 重 順 番号を
1,2,3, . . . 付 （X N 全単射 ）, X 元を順
並 (N X 全単射 ) .
定義 1.8.46. 集合 X 可算集合 有限集合 , 高々可算 (at most
countable) .
注意 . 高々可算 集合を可算集合 . （有限 ）可算 集合を可算無限集合(countably infinite set) .
例 1.8.47. 正 偶 数 全 体 Neven = {
n∈N n 偶数}
, 正 奇 数 全 体 Nodd = {n∈N n 奇数}
可 算 集 合 . 実 際, Neven = {2,4,6, . . .}, Nodd = {1,3,5, . . .} 並 . 具体的 式 書 f: N → Neven, f(n) = 2n, g: N→Nodd, g(n) = 2n−1 全単射.
1.8 濃度 85 例 1.8.48. 整数全体Z 可算集合 . 実際, Z ={0,1,−1,2,−2,3,−3, . . .} 並
, Z 元
. . . −3
7
−2
5
−1
3
''0
1
))1
2
uu 2
4
vv 3
6
. . .
番号を付 . 具体的 式 書 , f: N→Zを f(n) =
{−n−21 n 奇数,
n
2, n 偶数
定 f 全単射 , g: Z→Nを g(l) =
{−2l+ 1, l ≤0, 2l, l >0 定 g f 逆写像.
例 1.8.49. N×N 可算集合 . |N×N|=|N|=ℵ0. 実際, N×N 元
図 番号を .
1 2 3 4
1
1 //
3
((
6
%%
10
$$
2 2
`` 5
`` 9
``
3 4
`` 8
``
4 7
``
問 54. 例 1.8.48 図 対応を与 写像N×N→Nを式 書 .
問 55. f: N×N→ Nをf(l, m) = 2l−1(2m−1) 定 f 全単射 を 示 .
例 1.8.50. 有理数全体Q 可算集合 .
実際,f: Q→Z×Nをr ∈Q 既約分数 p/q,q ∈N 表 f(r) = (p, q)
定 （ f(0) = (0,1) ） f 単射 . （ρ: Z× N → Q を
ρ(l, m) =l/m 定 ρ◦f = idQ.） |Q| ≤ |Z×N|. Z∼=N Z×N∼=N×N , 上 見 N×N∼=N |Z×N|=ℵ0. |Q| ≤ ℵ0.
N⊂Q ℵ0 ≤ |Q|. |Q|=ℵ0.
具体的 有理数を順 並 , 例 r ∈ Q を既約分数 p/q 表
|p|+|q| 小 順 , |p|+|q| 同 分母 大 順 , 正負交互 並 . 見 正 有理数
1
|{z}1
p+q=2
, 1 2,2
|{z}1
p+q=3
, 1 3,3
|{z}1
p+q=4
,1 4,2
3, 3 2,4
| {z }1
p+q=5
, . . .
具合.
可算無限濃度 濃度 大小 関 極小 , 可算無限 小 無限濃度 . （後 述 選択公理を仮定 最小 示 .）
定理 1.8.51. 可算集合 部分集合 高々可算集合 .
証明. N 部分集合A ⊂N 高々可算 を示 , 例 A 元を小
方 順 .
少 厳密 , 次 . ∅ ̸=A ⊂ N . a ∈A 対 Aa ⊂A をAa ={l ∈A l ≤a} 定 , a ∈Aa ⊂ [a+ 1] Aa 空 有限集合
. 写像c: A→Nをc(a) =|Aa| 定 .
a, b∈ A, a < b Aa ⊊Aa∪ {b} ⊂ Ab c(a)< c(b) . c 順 序を保 単射 .
c 順序を保 c(Aa) ⊂ {1, . . . , c(a)} . 実際, l ∈ Aa , l ≤ a c(l) ≤ c(a). c(l) ∈ {1, . . . , c(a)}. |Aa| = c(a) = |{1,· · · , c(a)}|
, c: Aa → {1, . . . , c(a)} 単射 系 1.8.22 c(Aa) = {1, . . . , c(a)}. ,
m∈N , a ∈A 存在 m≤c(a) , m∈c(A) .
c 全射 . m ̸∈c(A)を一 . c(A) ⊂[m] , A 有限
集合. （(∃a∈A :c(a)≥m)⇒m∈c(A).）
c 全射 c: A→N 全単射 A 可算集合.
問 56. 上 定 c: A →N 単射 を確 .
1.8 濃度 87 定理 1.8.52. Xを可算集合, Y を高々可算 集合 .
1. X∪Y 可算集合.
2. Y ̸=∅ X×Y 可算集合.
証明. 1. X∪Y =X∪(Y \X), X∩(Y \X) =∅ , 系1.8.15, 定理 1.8.51
Y \X 高々可算. , X∩Y =∅ 場合を考 . Y 有限集合
場合 . Y 可算 場合を考 . f: N−→∼= X, g: N −→∼= Y を全単射 . h: N→X∪Y を
h(n) = {
f(n+12 ), n 奇数, g(n2), n 偶数 定 h 全単射.
2. Y 有限集合 場合 . Y 可算集合 場合X ×Y ∼=N×N∼=N.
問 57. X を可算集合, Y を有限集合 .
1. X∩Y =∅ . X∪Y 可算集合 を示 .
2. Y ̸=∅ X×Y 可算集合 を示 .
定理 1.8.53 (Cantor). 実数全体R 可算集合 .
証明. 1 小 非負 実数 , 少数 表 各桁 0 1 全体をB .
B={
x∈R x = 0.a1a2. . . ( ∀n∈N:an∈ {0,1})}
= {
x∈R x =
∑∞ n=1
an10−n ( ∀n∈N:an ∈ {0,1}) }
. ℵ0 <|B|を示 .
写像i: N→Bをi(n) = 10−n 定 明 i 単射 ℵ0 ≤ |B|.
N B 全 射 存 在 を 示 . f: N → B を 写 像 , f(1), f(2), . . . を順 並 .
f(1) = 0.a11a12a13. . . f(2) = 0.a21a22a23. . . f(3) = 0.a31a32a33. . .
. . .
n∈N 対 bn ∈ {0,1}を
bn = {
0, ann = 1, 1, ann = 0 定 ,
b= 0.b1b2b3· · ·=
∑∞ n=1
bn10−n∈B
を考 . 任意 n∈N 対 ann̸=bn f(n)̸=b. f 全射 . 注意 . 証明 元々 対角線論法 .
j: 2N →B ⊂Rをj(a) =∑∞
n=1a(n)10n 定 明 j 全単射
|P(N)|=|2N|=|B| ≤ |R|
, 証明 |N| < |P(N)| |N| < |2N| を示
, 見 分 , 議論 1.8.36 X = N , 定
理 1.10.20 X =N, Y = [2], τ =¬: [2]→[2] 他 .
定義 1.8.54. 集合 X 実数全体 R 濃度 等 , X 濃度 連続体 濃度
(cardinality of continuum) , |X|=ℵ 表 .
上 注意 |2N| ≤ ℵ , 実 等 .
定理 1.8.55. ℵ=|2N|.
証明. ℵ ≤ |2N|を示 . 写像 f: R → P(Q)をf(x) ={r ∈Q r ≤x} 定 . x, y ∈ R, x < y x < r < y r ∈ Q 存在 r ∈ f(y)\f(x)
f(x)̸= f(y). f 単射. （ Q R 稠密性を用 . Rを
Dedekind 切断 構成 立場 f 包含写像 他 .）Q ∼= N
P(Q)∼= 2Q ∼= 2N. 系 1.8.56. |R2|=|RN|=ℵ.
証明. 単射R→R2, R2 →RN を構成 .
|R|=|RN|を示 , 定理 1.8.55 見 R∼= 2N , N×N∼=N
定理 1.4.41 ,
RN ∼=(
2N)N ∼= 2N×N ∼= 2N ∼=R.
1.8 濃度 89 問 58. 単射R→R2,R2 →RN を .
例 1.8.57. p: (0,1]→ S1 ={z ∈C |z|= 1}をp(θ) = e2πiθ 定 p 全単射 . (0,1]∼=I = [0,1]∼=R
S1 ∼=I ∼=R∼=R×R∼=I×I ∼=S1×I ∼=S1×S1 連続体 濃度を持 .