1. 集合五島正裕 DATE : 集合  現代数学すべての基本  自然数も集合によって定義集合  集合：  「明確に定義された対象の集まり」  要素 (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} への写像全体の集合と同一視できる  A = {a, b, c} なら  {{000}, {100}, {010}, {001}, {110}, {011}, {1010}, {111}}  | 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) の実数の集合とすると… α1 = 0. a11 a12 a13 … a1n … α2 = 0. a21 a22 a23 … a2n … α3 = 0. a31 a32 a33 … a3n … … αn = 0. an1 an2 an3 … ann … … {αi}：(0,1) の実数の集合とすると… α1 = 0. 127…2… α2 = 0. 797…2… α3 = 0. 722…2… … αn = 0. 727…7… … β = 0. b1 b2 b3 … bn … bi = 7 (0 ≤ ai ≤ 4) 2 (5 ≤ ai ≤ 9) β = 0. 727…2… bi = 7 (0 ≤ ai ≤ 4) 2 (5 ≤ ai ≤ 9) β ∈ {αi}？ β ∈ {αi}？対角線論法 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 … … {αi}：(0,1) の実数の集合とすると… α1 = 0. 100…1… α2 = 0. 101…0… α3 = 0. 100…0… … αn = 0. 101…1… … β = 0. b1 b2 b3 … bn … bi = 0 (ai = 1) 1 (ai = 0) β = 0. 011…0… bi = 0 (ai = 1) 1 (ai = 0) β ∈ {αi}？ β ∈ {αi}？ ‫א‬  可算・非可算無限  自然数の濃度 |N|：可算無限： ‫א‬0  実数の濃度 |R|：非可算無限： ‫א‬  ‫א‬  アレフ  ヘブライ語のアルファ |A| < |2A|  一般に |A| < |2A|  対角線論法を用いて証明せよどんなプログラムでも書けるか？ (1/2)  あらゆるプログラム  プログラム: 文字の有限長の並び  文字コードでエンコードすれば有限長のビット列 → 自然数と同じ濃度  あらゆる仕様とは？たとえば：  入力：自然数  出力： 0 または 1 というプログラムの仕様（入出力の関係）は:  入力: 0 1 2 3 4 5 ...  出力: 0 1 1 0 1 0 ... という無限長の 0/1 列で表現できる. どんなプログラムでも書けるか？ (2/2)  仕様の一覧表：仕様 0: 01101011... 仕様 1: 11011001... 仕様 2: 00110110... ... 対角線論法により，ここに出現しない仕様がある.  入力の自然数には上限 (32b とか) があるが？  入力を「任意長文字列」→「自然数」とすれば同じ Russel のパラドクス  「集合の集合」も考えられる  「自分自身を要素として持つような集合」  例: あらゆる集合の集合  「自分自身を要素として持たない集合すべての集合」S  S 自身は S の要素か?  Yes → S の定義に違反  No → S の定義から S は S の要素であるべき Russel のパラドクス  ある村にはただ一人の理髪師がいて，自分で自分のヒゲを剃らない村人全員のヒゲを剃るとする．この理髪師は，自分のヒゲを剃るか？  ある図書館の図書目録のうちで，自分自身を載せていないものすべての目録を作る．この目録自体は，この目録に載せるべき？  自分の市に住んでいない市長のみを集めて「市長市」を作る．「市長市」の市長には誰がなるか？自己言及のパラドクス  クレタ人のパラドクス  『クレタ人はいつもうそつき』とクレタ人が言った．  「この文は真ではない．」昨年度の試験の問題  Russel のパラドクスの例を作れ  ？悩みがないのは悩み？  × 矛と盾を売っている人がいて… 素朴集合論の破綻  素朴集合論 → 公理的集合論