Document

離散数学
1. 集合
五島正裕
離散数学
集合
 現代数学すべての基本
 自然数も集合によって定義
離散数学
集合
 集合：
 「明確に定義された対象の集まり」
 要素 (element)
x∈A
 表現
 外延的表現 (extensional)

A = {1, 2, 3}
 内包的表現 (intentional)

A = {x | x は 1≦x≦3 を満たす整数}
離散数学
 空集合 (empty set)
 φ
 包含関係
 A ⊂ B, B ⊃ A
離散数学
集合の演算
 和集合 (union)
 A ∪ B = {x | x ∈ A または x ∈ B}
 積集合 (intersection)
 A ∩ B = {x | x ∈ A かつ x ∈ B}
 差集合 (difference)
 A － B = {x | x ∈ A かつ x ∈ B}
 補集合 (complement)
 ある集合 U の部分集合だけを問題とするとき
 A の上に横棒 = Ac = U － A
 直積 (direct product, Cartesian product)
 A × B = {(a, b) | a ∈ A, b ∈ B}
離散数学
濃度
 濃度 (potency, power)
 集合の大きさ

 |A|
有限集合の場合は要素数
離散数学
巾（べき）集合
 巾集合 (power set)
 集合 A の部分集合すべての集合
 2A
 A = {a, b, c} なら

2A = {{}, {a}, {b}, {c}, {a, b}, {b, c}, {c, a}, {a, b, c}}
 2A
 A → {0, 1} への写像全体の集合と同一視できる
 | 2A | = 2|A|
離散数学
代表的な無限集合の記法
 自然数：
N
 整数：
Z
 有理数：
Q
 実数：
R
離散数学
無限集合の濃度
 無限集合の濃度の比較
 全単射写像が存在すれば |A| = |B|
 A から B への単射が存在すれば |A| ≦ |B|
 全単射写像の作り方
 システマティックな数え上げの方法
離散数学
無限ホテル by ヒルベルト (1/2)
 無限の部屋があるホテルがあり，満室だった．
突然の客が来て，どうしても泊めて欲しいと言う．
 1号室の客は2号室へ，2号室の客は3号室へ，… ，と移ってもらうと，
1号室が空く．
離散数学
無限ホテル by ヒルベルト (2/2)
 無限の部屋があるホテルがあり，満室だった．
突然無限人の客が来て，どうしても泊めて欲しいと言う．
 1号室の客は2号室へ，2号室の客は4号室へ，… ，n 号室の客は 2n 号室へ
と移ってもらうと，無限の部屋が空く．
 自然数の濃度 = 奇数（偶数）の濃度！
離散数学
自然数と整数の濃度
 自然数 ⇔ 整数
0
1
2
3
4
5
…
0
1
−1
2
−2
3
…
離散数学
有理数の濃度
 自然数 → 有理数の単射は簡単
 有理数 → 自然数の単射は
1/1 1/2 1/3 1/4 ...
2/1 2/2 2/3 2/4 ...
3/1 3/2 3/3 3/4 ...
...
分子+分母をしだいに大きく
離散数学
実数の濃度
 自然数と実数の濃度は違う
 「対角線論法」
 実数全体 → (0, 1) の実数
 ex) シグモイド関数（ロジスティック関数）

y = 1/(1 + exp(−x))
y
1
O
x
離散数学
対角線論法 by カントール
{αi}：(0,1) の実数の集合と書けるとす
ると…
{αi}：(0,1) の実数の集合と書けるとす
ると…
α1 = 0. a11 a12 a13 … a1n …
α1 = 0. 127…2…
α2 = 0. a21 a22 a23 … a2n …
α2 = 0. 797…2…
α3 = 0. a31 a32 a33 … a3n …
α3 = 0. 722…2…
…
…
αn = 0. an1 an2 an3 … ann …
αn = 0. 727…7…
…
…
β = 0. b1 b2 b3 … bn …
β = 0. 727…2…
bi = 7 (0 ≤ ai ≤ 4)
bi = 7 (0 ≤ ai ≤ 4)
2 (5 ≤ ai ≤ 9)
2 (5 ≤ ai ≤ 9)
β ∈ {αi}？
β ∈ {αi}？
離散数学
‫א‬
 一般に |A| < |2A|
 自然数の濃度：
実

可算無限： ‫א‬0
数の濃度：非可算無限： ‫א‬
‫א‬
 アレフ
 ヘブライ語のアルファ
離散数学
どんな仕様のプログラムでも書けるか？
 あらゆるプログラム
 プログラム: 文字の有限長の並び
 文字コードでエンコードすれば有限長のビット列
→ 自然数と同じ濃度
 あらゆる仕様とは？たとえば：
 入力: 自然数
 出力: 0 または 1
というプログラムの仕様（入出力の関係）は:
 入力: 0 1 2 3 4 5 ...
 出力: 0 1 1 0 1 0 ...
という無限長の 0/1 列で表現できる.
離散数学
どんな仕様のプログラムでも書けるか？
 プログラムの実行結果の一覧表
0:
01101011...
1:
11011001...
2:
00110110...
...
対角線論法により，ここに出現しない仕様があるはず.
 入力の自然数には上限 (32b とか)があるが？
 入力を「任意長文字列」→「自然数」とすれば同じ
離散数学
Russel のパラドクス
 「集合の集合」も考えられる
 「自分自身を要素として持つような集合」

例: あらゆる集合の集合
 「自分自身を要素として持たない集合すべての集合」S
 S 自身は S の要素か?

Yes → S の定義に違反

No → S の定義から S は S の要素であるべき
離散数学
Russel のパラドクス
 ある村にはただ一人の理髪師がいて，自分で自分のヒゲを剃らない村人
全員のヒゲを剃るとする．この理髪師は，自分のヒゲを剃るか？
 ある図書館の図書目録のうちで，自分自身を載せていないものすべての
目録を作る．この目録自体は，この目録に載せるべき？
 自分の市に住んでいない市長のみを集めて「市長市」を作る．「市長
市」の市長には誰がなるか？
離散数学
自己言及のパラドクス
 クレタ人のパラドクス
 『クレタ人はいつもうそつき』とクレタ人が言った．
 「この文は真ではない．」
離散数学
昨年度の試験の問題
 Russel のパラドクスの例を作れ
 悩みがないのは悩み？
 矛と盾を売っている人がいて…
離散数学
素朴集合論の破綻
 素朴集合論 → 公理的集合論

Download Report