1. 集合 五島 正裕.

Presentation on theme: "1. 集合 五島 正裕."— Presentation transcript:

1 1. 集合 五島 正裕

2 集合 現代数学すべての基本 自然数も集合によって定義

3 集合 集合： 「明確に定義された対象の集まり」 要素 (element) x ∈ A 表現 外延的表現 (extensional)
内包的表現 (intentional) A = {x | x は 1≦x≦3 を満たす整数}

4 空集合 (empty set) φ 包含関係 A ⊂ B, B ⊃ A

5 集合の演算 和集合 (union) A ∪ B = {x | x ∈ A または x ∈ B} 積集合 (intersection)
差集合 (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}

6 濃度 濃度 (potency, power) 集合の大きさ 有限集合の場合は要素数 |A|

7 巾（べき）集合 巾集合 (power set) 集合 A の部分集合すべての集合 2A A = {a, b, c} なら
2A = {{}, {a}, {b}, {c}, {a, b}, {b, c}, {c, a}, {a, b, c}} A → {0, 1} への写像全体の集合と同一視できる | 2A | = 2|A|

8 代表的な無限集合の記法 自然数： N 整 数： Z 有理数： Q 実 数： R

9 無限集合の濃度 無限集合の濃度の比較 全単射写像が存在すれば |A| = |B| A から B への単射が存在すれば |A| ≦ |B|
全単射写像の作り方 システマティックな数え上げの方法

10 無限ホテル by ヒルベルト (1/2) 無限の部屋があるホテルがあり，満室だった． 突然の客が来て，どうしても泊めて欲しいと言う．
1号室の客は2号室へ，2号室の客は3号室へ，… ，と移ってもらうと， 1号室が空く．

11 無限ホテル by ヒルベルト (2/2) 無限の部屋があるホテルがあり，満室だった． 突然 無限人の客が来て，どうしても泊めて欲しいと言う．
1号室の客は2号室へ，2号室の客は4号室へ，… ，n 号室の客は 2n 号室へと移ってもらうと，無限の部屋が空く． 自然数の濃度 = 奇数（偶数）の濃度！

12 自然数と整数の濃度 自然数 ⇔ 整数 1 2 3 4 5 … −1 −2

13 有理数の濃度 自然数 → 有理数の単射は簡単 有理数 → 自然数の単射は 　1/1 1/2 1/3 1/ 　2/1 2/2 2/3 2/ 　3/1 3/2 3/3 3/ 　... 分子+分母をしだいに大きく

14 実数の濃度 自然数と実数の濃度は違う 「対角線論法」 実数全体 → (0, 1) の実数 ex) シグモイド関数（ロジスティック関数）
y = 1/(1 + exp(−x)) y 1 O x

15 対角線論法 by カントール {αi}：(0,1) の実数の集合 と書けるとすると… α1 = 0. a11 a12 a13 … a1n … α2 = 0. a21 a22 a23 … a2n … α3 = 0. a31 a32 a33 … a3n … … αn = 0. an1 an2 an3 … ann … β = 0. b1 b2 b3 … bn … bi = 7 (0 ≤ ai ≤ 4) 2 (5 ≤ ai ≤ 9) β ∈ {αi}？ {αi}：(0,1) の実数の集合 と書けるとすると… α1 = …2… α2 = …2… α3 = …2… … αn = …7… β = …2… bi = 7 (0 ≤ ai ≤ 4) 2 (5 ≤ ai ≤ 9) β ∈ {αi}？

16 א 一般に |A| < |2A| 自然数 の濃度： 可算無限： א0 実 数 の濃度： 非可算無限： א א アレフ
自然数 の濃度： 　可算無限： א0 実　数 の濃度： 非可算無限： א א アレフ ヘブライ語のアルファ

17 どんな仕様のプログラムでも書けるか？ あらゆるプログラム プログラム: 文字の有限長の並び 文字コードでエンコードすれば有限長のビット列
→ 自然数と同じ濃度 あらゆる仕様とは？ たとえば： 入力: 自然数 出力: 0 または 1 というプログラムの仕様 （入出力の関係） は: 入力: 出力: という無限長の 0/1 列で表現できる.

18 どんな仕様のプログラムでも書けるか？ プログラムの実行結果の一覧表 0: : : 対角線論法により，ここに出現しない仕様があるはず. 入力の自然数には上限 (32b とか)があるが？ 入力を「任意長文字列」→「自然数」とすれば同じ

19 Russel のパラドクス 「集合の集合」も考えられる 「自分自身を要素として持つような集合」 例: あらゆる集合の集合
Yes → S の定義に違反 No → S の定義から S は S の要素であるべき

20 Russel のパラドクス ある村にはただ一人の理髪師がいて，自分で自分のヒゲを剃らない村人全員のヒゲを剃るとする．この理髪師は，自分のヒゲを剃るか？ ある図書館の図書目録のうちで，自分自身を載せていないものすべての目録を作る．この目録自体は，この目録に載せるべき？ 自分の市に住んでいない市長のみを集めて「市長市」を作る．「市長市」の市長には誰がなるか？

21 自己言及のパラドクス クレタ人のパラドクス 『クレタ人はいつもうそつき』とクレタ人が言った． 「この文は真ではない．」

22 昨年度の試験の問題 Russel のパラドクスの例を作れ 悩みがないのは悩み？ 矛と盾を売っている人がいて…

23 素朴集合論の破綻 素朴集合論 → 公理的集合論