集合の濃度，可算集合について

「集合の大きさ」とは？（１）有限集合
「離散数学」補足資料
集合の濃度，可算集合について
• 有限集合の場合，「集合の大きさ」は，元の個数 |A|
• 性質1
(1) A⊆B ⇒ |A| ≦ |B|
(2) A⊆B ⇒ |A| ≦ |B|
芝浦工業大学工学部情報工学科
杉本徹
• 性質2
(1) 単射 A→B が存在する ⇔ |A| ≦ |B|
(2) 全射 A→B が存在する ⇔ |A| ≧ |B|
(3) 全単射 A→B が存在する ⇔ |A| = |B|
• 発展的な内容（試験には出ない）
• しかし，理系の教養として知っておくとよい
「集合の大きさ」とは？（２）無限集合
• 無限集合の場合は，有限集合の時ほど明確でない
• 例：整数全体の集合を Z,
偶数全体の集合を E = { 2n｜n∈Z } とする時，
Q：集合 Z と E はどちらが大きい？
A1： E⊆Z だから，Zの方が大きい
A2：どちらの集合も大きさ「無限」だから同じ
集合の「濃度」（大きさの尺度）
• （有限または無限）集合 A の濃度 |A| を次のように
定める
(1) 集合A, Bの濃度の間の順序関係を次のように定める
• 単射 A→B が存在する ⇔ |A| ≦ |B|
• 全射 A→B が存在する ⇔ |A| ≧ |B|
• 全単射 A→B が存在する ⇔ |A| = |B|
(2) 有限集合 A に関しては，今まで通り
濃度 |A| は A の元の個数を表すとする
⇒ 現代の数学から見ると，どちらの説明も適切ではない！
無限集合の濃度の比較（１）
可算集合
• 次のような全単射 f: Z→E が存在するので，|Z| = |E|
f(x) = 2・x
Z: … -4 -3 -2 -1 0 1 2 3 4 …
E: … -4
-2
0
2
4 …
• 次のような全単射 f: N→Z が存在するので，|N| = |Z|
f(x) =
x/2
－(x+1)
N:
（xが偶数のとき）
/ 2 （xが奇数のとき）
0 1 2 3 4 5 6 …
• 自然数の集合 N との間に全単射が存在する（つま
り濃度が等しい）集合を可算（可付番，countable），
または可算無限であると言う．
• 言い換えれば，可算集合とは，すべての元に 0, 1, 2,
… という番号を付けることができる集合である．
– 例：集合 Z と E の全要素に対する番号付け
番号（N)
Z
E
0
0
0
1
-1
-2
2
1
2
3
-2
-4
4
2
4
5
-3
-6
6
3
6
…
…
…
Z: … -4 -3 -2 -1 0 1 2 3 4 …
1
無限集合の濃度の比較（２）
• 有理数の集合 Q が可算集合であることの証明
• 方針：
– 恒等写像 idN: N→Q は単射なので，|N|≦|Q|
– Q が可算集合であること（|N| = |Q|）を証明するには，あと
|N|≧|Q| であること，つまり全射 N→Q が存在することを
示せばよい．
• 次のような全射 f: N→Q が存在する
N
Q
0
0
N
Q
1
2
3
4
5
6
7
8
9
-1/1 1/1 -1/2 1/2 -2/1 2/1 -1/3 1/3 -2/2
10 11 12 13 14 15 16 17 18
2/2 -3/1 3/1 -1/4 1/4 -2/3 2/3 -3/2 3/2
…
…
無限集合の濃度の比較（３）
• 実数の集合 R と開区間 (0, 1) = { x∈R｜0<x<1 }の
濃度は等しい
– tan(x/π + 1/2) は (0, 1) から R への全単射
• 実数の集合 R と複素数の集合 C の濃度は等しい
– 明らかに |C| = |R×R| であるから，上の結果を踏まえると
（0, 1)×(0, 1) → (0, 1) という全単射の存在を示せば十分
– x, y∈(0, 1) の10進小数表示をそれぞれ
x = 0.d1 d2 d3 …
y = 0. e1 e2 e3 …
とするとき，これらから z = 0. d1 e1 d2 e2 d3 e3 … という
小数を作ることができる．(x, y) に z に対応付ける関数は，
(0, 1)×(0, 1)→(0, 1) の全単射となる．
1/1
1/2
1/3
1/4
1/5
1/6
2/1
2/2
2/3
2/4
2/5
2/6
3/1
3/2
3/3
3/4
3/5
3/6
4/1
4/2
4/3
4/4
4/5
4/6
5/1
5/2
5/3
5/4
5/5
5/6
6/1
6/2
6/3
6/4
6/5
6/6
…
…
…
…
このような順番で番号付けすれば，あらゆる有理数を網羅できる
無限集合の濃度の比較（４）
• 実数の集合Rは可算集合ではない |N| ≠ |R|
• 証明（カントールの対角線論法）
全射 f: N→(0, 1) が存在すると仮定し，矛盾を導く（背理法）
n∈N に対する f(n)∈(0, 1) の10進小数表示を
f(n) = 0. dn1 dn2 dn3 …
とする．このとき次のような小数 x を考えることができる．
x = 0. e1 e2 e3 …
ここでei = dii + 1 （ただし dii=9 の場合は ei = 0 とする）
このような x は (0, 1) の元であるが，どんな n を取っても
f(n) = x とならない．これは f が全射という前提に反する．
矛盾が生じたので，全射 N→(0, 1) の存在が間違っていた
ことになる．よって |N| ≠ |R| であることが証明された．
まとめ
• 例：
f(1)
f(2)
f(3)
f(4)
f(5)
…
=
=
=
=
=
0.
0.
0.
0.
0.
3
2
7
1
3
5
6
2
8
1
2
8
0
5
4
1
0
9
2
1
4
6
9
6
9
6
5
4
0
7
7…
1…
5…
3…
8…
• …
とすると，x = 0. 4 7 1 3 0 …
• 濃度 |A| ：集合の大きさを表す尺度
• 集合の大きさによる分類
有限集合（|A| は元の個数）
可算集合（N, Z, E, Q など）
無限集合
その他（可算より大，R, C など）
• 参考：さらに勉強するためのキーワード「連続体仮説」
2

Download Report