Kenneth Kunen を読む宇佐見大希2026年2月2日概要目次1このノートの目的 ........................................................................................... 121階命題論理 ............................................................................................ 22.1命題 ............................................................................................. 22.2論理式 ............................................................................................ 22.31階命題論理 ........................................................................................ 42.3.0.1含意 (→) ........................................................................... 52.3.0.2否定 (¬) ............................................................................ 52.3.0.3連言 (∧) ............................................................................ 52.3.0.4選言 (∨) ............................................................................ 52.3.0.5同値 (↔) ........................................................................... 52.3.0.6矛盾 (⊥) ........................................................................... 52.3.0.7全称量化 (∀) ......................................................................... 52.3.0.8存在量化 (∃) ......................................................................... 52.3.0.9その他 ............................................................................... 531階述語論理 ............................................................................................ 54集合論 ................................................................................................ 64.1ZFC 公理系 ....................................................................................... 64.2順序数と基数 ........................................................................................ 104.2.1順序数 ..................................................................................... 101 このノートの目的ここでやりたいことっていうのはこんなことです。1.述語論理を OS として使い、 ZFC というエンジンを動かして数学をする。(集合論)2.ZFC のエンジン上で述語論理という OS の仕様や性質を数学的に研究する。(モデル理論)このような手順で議論を進めていくと次のようなことができます。•ZFC 自身を ZFC 上で構築したりして、ZFC の無矛盾性を証明できないことを示せる (Gödel の不完全性定理)•連続体仮説はZFCの公理からは証明も反証もできない1•無限の厳密な議論ができるこの証明を理解するまでをまとめています。このノートでは集合論における次の名著を参考にしています。Kenneth Kunen, Set Theory (College Publications, 2011; corrected reprint 2013), ISBN-13:978-1848900509.2 1階命題論理2.1 命題命題とは客観的に真偽が決まる文のことです。例えば「富士山は日本で一番高い山である。」という命題は真です。この真偽を 1 0 という値として表すことにします。2.2 論理式Definition 2.1: 論理式 𝐴 は以下のように帰納的に定義される。1.命題 𝑃 は論理式である。2.論理式 𝐴 が論理式であるとき、 ¬𝐴 も論理式である。3.論理式 𝐴 と論理式 𝐵 が論理式であるとき、 𝐴∧𝐵 も論理式である。4.論理式 𝐴 と論理式 𝐵 が論理式であるとき、 𝐴∨𝐵 も論理式である。5.論理式 𝐴 と論理式 𝐵 が論理式であるとき、 𝐴→𝐵 も論理式である。6.論理式 𝐴 と論理式 𝐵 が論理式であるとき、 𝐴↔𝐵 も論理式である。𝑃¬𝑃1001𝑃𝑄𝑃∧𝑄𝑃∨𝑄𝑃→𝑄𝑃↔𝑄111111100100010110000011Theorem 2.2: 𝑃∨¬𝑃 は常に真であるProof:𝑃¬𝑃𝑃∨¬𝑃2101011∎Theorem 2.3: 𝑃∧¬𝑃 は常に偽であるProof:𝑃¬𝑃𝑃∧¬𝑃100010∎Theorem 2.4: (𝑃→𝑄)∧(𝑄→𝑃) は常に真であるProof:𝑃𝑄𝑃→𝑄𝑄→𝑃(𝑃→𝑄)∨(𝑄→𝑃)11111100110110100111∎Theorem 2.5: 𝑃→𝑄 は ¬𝑃∨𝑄 と同値であるProof:𝑃𝑄¬𝑃∨𝑄𝑃→𝑄1111100001110011∎3Theorem 2.6: 𝑃∧𝑄 は 𝑄∧𝑃 と同値であるProof:𝑃𝑄𝑃∧𝑄𝑄∧𝑃1111100001000001∎変数が増えていけばいくほど真偽値を使って証明するのは現実的ではなくなってきます。2.3 1階命題論理真偽値から脱却して論理的に証明することでもっと複雑な命題を扱えるようになります。 その真偽値に置き換わるものが推論規則です。推論規則Definition 2.7: 推論規則とは論理式から論理式を導く規則のことです。42.3.0.1 含意 (→)𝐴⋮𝐵→ I𝐴→𝐵𝐴→𝐵, 𝐴→ E𝐵2.3.0.2 否定 (¬)𝐴⋮⊥¬ I¬𝐴𝐴, ¬𝐴¬ E⊥2.3.0.3 連言 (∧)𝐴, 𝐵∧ I𝐴∧𝐵𝐴∧𝐵∧ E₁𝐴𝐴∧𝐵∧ E₂𝐵2.3.0.4 選言 (∨)𝐴∨ I₁𝐴∨𝐵𝐵∨ I₂𝐴∨𝐵𝐴∨𝐵, 𝐴 dots.v 𝐶, 𝐵 dots.v 𝐶∨ E𝐶2.3.0.5 同値 (↔)𝐴 dots.v 𝐵, 𝐵 dots.v 𝐴↔ I𝐴↔𝐵𝐴↔𝐵↔ E₁𝐴→𝐵𝐴↔𝐵↔ E₂𝐵→𝐴2.3.0.6 矛盾 (⊥)⊥⊥ E𝐴LEM𝐴∨¬𝐴2.3.0.7 全称量化 (∀)𝐴⋮(𝑥fresh)∀ I∀𝑥.𝐴∀𝑥.𝐴∀ E𝐴[𝑡𝑥]2.3.0.8 存在量化 (∃)𝐴[𝑡𝑥]∃ I∃𝑥.𝐴∃𝑥.𝐴, 𝐴⋮𝐶 (x not free in C)∃ E𝐶2.3.0.9 その他𝐴仮定𝐴𝐴→𝐵, 𝐵→𝐶三段論法𝐵図 1: 一階命題論理の推論規則3 1階述語論理論理記号意味∀全称記号∃存在記号∈属する∉属さない∧論理積∨論理和→含意↔同値¬否定5⊤真⊥偽⇒含意4 集合論ここでは ZFC 公理系を採用する。4.1 ZFC 公理系公理名式公理の意味集合の存在∃𝑥(𝑥=𝑥)集合は存在する。外延性公理∀𝐴∀𝐵(∀𝑥(𝑥∈𝐴↔𝑥∈𝐵)→𝐴=𝐵)全く同じ要素からなる 2 つの集合は等しい。内包性公理𝜑 は変数 𝑦 を自由変数として用いないとき ∃𝑦∀𝑥(𝑥∈𝑦↔𝑥∈𝑧∧𝜑)集合に対してある条件 𝜑 を満たしたものを集めた集合がある。対の公理∀𝑥∀𝑦∃𝑧(𝑥∈𝑧∧𝑦∈𝑧)2 つの集合があるときそれらを集めた集合も存在する。和集合の公理∀ℱ∃𝐴∀𝑌∀𝑥(𝑥∈𝑌∧𝑌∈ℱ→𝑥∈𝐴)集合族 ℱ に関する和集合が存在する。置換図式∀𝑥∈𝐴∃!𝑦𝜑(𝑥,𝑦)→∃𝑌∀𝑥∈𝐴∃𝑦∈𝑌𝜑(𝑥,𝑦)ある集合に対して論理式によって対応する集合がある。無限公理∃𝑥(0∈𝑥∧∀𝑦∈𝑥(𝑦∪{𝑦}∈𝑥))無限集合が存在する。冪集合公理∀𝐴∃𝐵∀𝑥(𝑥∈𝐵↔𝑥⊂𝐴)集合 𝐴 の冪集合が存在する。選択公理∀𝐴∃𝑅 (𝑅は𝐴を整列順序づけする)すべての集合に対して整列順序が存在する。これらの公理から次の定義を適当な順序で並べて語彙を一気に増やします。 これらの概念は知ってると思うので証明はせずさらっと流します。証明に必要な公理は提示したので気になる人は証明を考えてみてください。名前定義存在の証明内包性表記{𝑥∈𝑧|𝜑}内包性公理空集合 0∀𝑥(𝑥∉0)内包性公理, 集合の存在包含𝐴⊂𝐵≔∀𝑥(𝑥∈𝐴→𝑥∈𝐵)集合の存在, 外延性公理, 内包性公理2 元集合{𝑥,𝑦}≔{𝑣∈𝑧|𝑣=𝑥∨𝑣=𝑦}対の公理単集合{𝑥}≔{𝑥,𝑥}順序対⟨𝑥,𝑦⟩≔{{𝑥},{𝑥,𝑦}}対の公理和集合⋃ℱ≔{𝑥|∃𝑌∈ℱ(𝑥∈𝑌)}和集合の公理6共通部分 ℱ≠0 のとき⋂ℱ≔{𝑥|∀𝑌∈ℱ(𝑥∈𝑌)}和集合𝐴∪𝐵≔⋃{𝐴,𝐵}共通部分𝐴∩𝐵≔⋂{𝐴,𝐵}差集合𝐴∖𝐵≔{𝑥∈𝐴|𝑥∉𝐵}直積𝐴×𝐵≔{⟨𝑥,𝑦⟩|𝑥∈𝐴∧𝑦∈𝐵}置換図式×2定義域dom(𝑅)≔{𝑥|∃𝑦⟨𝑥,𝑦⟩∈𝑅}値域ran(𝑅)≔{𝑦|∃𝑥⟨𝑥,𝑦⟩∈𝑅}逆𝑅−1≔{⟨𝑦,𝑥⟩|⟨𝑥,𝑦⟩∈𝑅}関係 𝑅(𝑅−1)−1=𝑅𝑥𝑅𝑦⟨𝑥,𝑦⟩∈𝑅関数 𝑓∀𝑥∈dom(𝑓)∃!𝑦∈ran(𝑓)⟨𝑥,𝑦⟩∈𝑓 となる関係 𝑓関数 𝑓:𝐴→𝐵𝑓 が関数であり dom(𝑓)=𝐴∧ran(𝑓)⊂𝐵関数値 𝑓(𝑥)𝑓:𝐴→𝐵 かつ 𝑥∈𝐴 のとき ∃!𝑦⟨𝑥,𝑦⟩∈𝑓制限 𝑓|𝐶𝐶⊂𝐴 のとき 𝑓|𝐶≔𝑓∩(𝐶×𝐵)像 𝑓″𝐶𝑓″𝐶≔ran(𝑓|𝐶)={𝑓(𝑥):𝑥∈𝐶}単射 (1-1)𝑓:𝐴→𝐵 かつ 𝑓−1 が関数全射 (onto)𝑓:𝐴→𝐵 かつ ran(𝑓)=𝐵全単射単射かつ全射𝑅 が 𝐴 上で推移的∀𝑥,𝑦,𝑧∈𝐴(𝑥𝑅𝑦∧𝑦𝑅𝑧→𝑥𝑅𝑧)𝑅 が 𝐴 上で反対称的∀𝑥,𝑦∈𝐴(𝑥𝑅𝑦∧𝑦𝑅𝑥→𝑥=𝑦)trichotomy∀𝑥,𝑦∈𝐴(𝑥𝑅𝑦∨𝑦𝑅𝑥∨𝑥=𝑦)𝑅 が 𝐴 上で反射的∀𝑥∈𝐴(¬(𝑥𝑅𝑥))𝑅 が 𝐴 上の全順序𝑅 が推移的、非反射的、かつ trichotomy を満たす同型写像𝑓:𝐴→𝐵 が全単射かつ ∀𝑥,𝑦∈𝐴(𝑥𝑅𝑦↔𝑓(𝑥)𝑆𝑓(𝑦))同型 ⟨𝐴,𝑅⟩≅⟨𝐵,𝑆⟩同型写像 𝑓:𝐴→𝐵 が存在する整列順序 ⟨𝐴,𝑅⟩𝑅 が全順序かつ 𝐴 の任意の空でない部分集合が 𝑅 に関する最小元を持つ切片pred(𝐴,𝑥,𝑅)≔{𝑦∈𝐴:𝑦𝑅𝑥}7Theorem 4.1: すべての集合を集めた集合は存在しない。¬∃𝑦∀𝑥(𝑥∈𝑦)Proof: そのような集合 𝑧 が存在すると仮定すると内包性公理から次のような集合 𝑦 が存在する。∃𝑦∀𝑥(𝑥∈𝑦↔𝑥∈𝑧∧𝑥∉𝑥)∃𝑦∀𝑥(𝑥∈𝑦↔𝑥∉𝑥)∃𝑦(𝑦∈𝑦↔𝑦∉𝑦)この集合が存在してしまうと公理系が矛盾する。よって存在しない。これを Russell’s paradox と呼ぶ。∎Theorem 4.2: 順序対が等しければその要素が等しい。∀𝑥∀𝑦∀𝑥′∀𝑦′(⟨𝑥,𝑦⟩=⟨𝑥′,𝑦′⟩→𝑥=𝑥′∧𝑦=𝑦′)Proof: 外延性の公理より⟨𝑥,𝑦⟩=⟨𝑥′,𝑦′⟩{{𝑥},{𝑥,𝑦}}={{𝑥′},{𝑥′,𝑦′}}{𝑥}={𝑥′}∧{𝑥,𝑦}={𝑥′,𝑦′}→𝑥=𝑥′∧𝑦=𝑦′{𝑥}={𝑥′,𝑦′}∧{𝑥,𝑦}={{𝑥′,𝑦′},𝑦}=𝑥′∎Theorem 4.3: ⟨𝐴,𝑅⟩ が狭義全順序ならば, 任意の 𝐵⊂𝐴 について ⟨𝐵,𝑅⟩ は狭義全順序となる。Proof: 𝑅⊂dom(𝑅)×ran(𝑅) より集合に対して関係の集合は依存していない。また推移律, 三分律, 非反射律は存在を示している訳ではないので 𝐵 に対しても成立する。よって ⟨𝐵,𝑅⟩ は狭義全順序となる。∎Definition 4.4: 同型写像 集合と関係の対 𝑎𝑏<𝐴,𝑅>,𝑎𝑏<𝐵,𝑆> について 全単射 𝑓:𝐴𝑡𝑜𝐵 が存在し⟨𝐴,𝑅⟩≅⟨𝐵,𝑆⟩⇔∀𝑥,𝑦∈𝐴(𝑥𝑅𝑦↔𝑓(𝑥)𝑆𝑓(𝑦))𝑓 を同型写像と呼ぶ。整列順序全順序 ⟨𝐴,𝑅⟩ について 𝐴 の空でない任意の部分集合に必ず 𝑅-最小の要素があるとき, ⟨𝐴,𝑅⟩ が整列順序であるという。切片pred(𝐴,𝑥,𝑅)≔{𝑦∈𝐴|𝑦𝑅𝑥}8Theorem 4.5: ⟨𝐴,𝑅⟩ を整列順序とするとき, 任意の 𝑥𝑖𝑛𝐴 に対して ⟨𝐴,𝑅⟩≅⟨pred(𝐴,𝑥,𝑅),𝑅⟩ である。Proof: 𝑓:𝐴→pred(𝐴,𝑥,𝑅) が同型写像であると仮定すると, 集合 {𝑦∈𝐴|𝑓(𝑦)≠𝑦} の 𝑅-最小要素 𝑦 が。∎Theorem 4.6: ⟨𝐴,𝑅⟩,⟨𝐵,𝑆⟩ を互いに同型な整列順序とするとき, この間の同型写像は唯一つ存在する。Proof: 仮に2つの同型写像 𝑓,𝑔 が存在したとき 𝑓(𝑦)≠𝑔(𝑦) であるような 𝑦∈𝐴 のうち 𝑅-最小の 𝑦 を考えると矛盾。∎Theorem 4.7: ⟨𝐴,𝑅⟩,⟨𝐵,𝑆⟩ を整列順序とするとき, 次の3つの命題は互いに背反である。 (a) ⟨𝐴,𝑅⟩≅⟨𝐵,𝑆⟩ (b) ∃𝑦∈𝐵{⟨𝐴,𝑅⟩≅⟨pred(𝐵,𝑦,𝑆),𝑆>} (c) ∃𝑥∈𝐴{⟨pred(𝐴,𝑥,𝑅),𝑅>≅⟨𝐵,𝑆⟩}Proof: 次のように 𝑓 を定める。𝑓={⟨𝑣,𝑤⟩|𝑣∈𝐴∧𝑤∈𝐵∧⟨pred(𝐴,𝑣,𝑅),𝑅⟩≅⟨pred(𝐵,𝑤,𝑆),𝑆⟩}このとき, 𝑓 は 𝐴 のある切片から 𝐵 のある切片への同型写像となるが, これら二つの切片の両方が真の切片となることはありえない。∎𝑓(𝑥)={𝑦∈𝑏|(𝑥,𝑦)∈𝑓}𝑓[𝑎′]={𝑦∈𝑏|∃𝑥(𝑥∈𝑎′∧(𝑥,𝑦)∈𝑓)}𝑓{−1}={(𝑦,𝑥)∈𝑏×𝑎|(𝑥,𝑦)∈𝑓}𝑔○𝑓={(𝑥,𝑧)∈𝑎×𝑐|𝑓(𝑥)∩𝑔−1(𝑧)≠∅}Definition 4.8: 集合 𝑥 の任意の要素が同時に 𝑥 の部分集合でもあるとき 𝑥 が推移的であると呼ぶ。Definition 4.9: 推移的な集合 𝑥 が 𝑖𝑛 によって整列順序づけされるとき, 𝑥 を順序数と呼ぶ。Theorem 4.10: ¬∃𝑧∀𝑥(𝑥は順序数→𝑥∈𝑧)Proof: 仮に任意の順序数を含む集合 𝑧 があるとすると, 集合𝑂𝑁={𝑥|𝑥は順序数}が存在し, これは順序数となるが, 𝑂𝑁∈𝑂𝑁 となり, 整列順序付けできない為, 順序数ではない。よって矛盾し, そのような集合 𝑧 は存在しない。∎Theorem 4.11: 順序数の集合 𝐴 が ∀𝑥∈𝐴∀𝑦∈𝑥(𝑦∈𝐴) ならば 𝐴 は順序数である。Theorem 4.12: ⟨𝐴,𝑅⟩ が整列順序であれば, あるただ一つに定まる順序数 𝐶 について ⟨𝐴,𝑅⟩≅𝐶 となる。9Theorem 4.13: ⟨𝐴,𝑅⟩ が整列順序であれば, あるただ一つに定まる順序数 𝐶 について ⟨𝐴,𝑅⟩≅𝐶 となる。Proof: 定理(ref)(3)より唯一性はわかる。𝐵={𝑎∈𝐴|∃𝑥(𝑥は順序数∧𝑥≅⟨pred(𝐴,𝑎,𝑅),𝑅⟩)} とおくと, 置換公理より∀𝑎∈𝐵∃!𝑥(𝑥≅⟨pred(𝐴,𝑎,𝑅),𝑅⟩)\𝐶≔{𝑥:∃𝑎∈𝐵{𝑥≅⟨pred(𝐴,𝑎,𝑅),𝑅⟩}}となる 𝐶 が存在し, 関数 𝑓 を 𝑓:𝑎↦𝑥 とおくと 𝑓⊂𝐵×𝐶 となる。∎全射 (surjection)𝑓[𝑎]=𝑏単射 (injection)𝑓(𝑥)=𝑓(𝑦)→𝑥=𝑦全単射 (bijection) 全射かつ単射4.2 順序数と基数数も集合で定義できます。 例えば自然数を定義するには空集合 0 から始まり、 𝑛+1≔𝑆(𝑛)=𝑛∪{𝑛} と帰納的に定義することで表現できます。 ここに無限の公理を適用すると無限も扱えるようになり、無限同士で全単射が存在するならば大きさは同じというように捉えることでおもろい性質がたくさん出てきます。同値類 ON/∼ における法則を考えるのがここでの目的である。4.2.1 順序数Definition 4.14: 集合 𝑥 が推移的であるとは 𝑥 の任意の要素が 𝑥 の部分集合であることを言う。Example 4.15: 例えば次のような集合が推移的である。0,{0},{0,{0}},{0,{0},{0,{0}}},…𝑥={𝑥}Definition 4.16: 𝛼 が順序数であるとは 𝛼 が推移的かつ ∈ によって狭義全順序づけされていることを言う。Definition 4.17: 構成的定義𝑆(𝛼)≔𝛼∪{𝛼}1≔𝑆(0)={0}2≔𝑆(1)={0,1}={0,{0}}3≔𝑆(2)={0,1,2}={0,{0},{0,{0}}}4≔𝑆(3)={0,1,2,3}={0,{0},{0,{0}},{0,{0},{0,{0}}}}…𝑛≔𝑆(𝑛−1)={0,1,2,…,𝑛−1}…10Definition 4.18: ⟨𝛼,𝑅⟩ が整列順序であるとき type(𝛼,𝑅) を一意な順序数 𝐶 に対して ⟨𝛼,𝑅⟩≅𝐶 と定義する。Definition 4.19: 後続順序数 𝛽 が後続順序数であるとは 𝛽=𝑆(𝛼) となる順序数 𝛼 が存在することを言う。極限順序数 𝛽 が極限順序数であるとは 𝛽 が後続順序数でないことを言う。Definition 4.20: 加法𝛼+𝛽≔type(𝛼×{0}∪𝛽×{1},𝑅)𝑅={⟨⟨𝜉,0⟩,⟨𝜂,0⟩⟩|𝜉<𝜂<𝛼}∪{⟨⟨𝜉,1⟩,⟨𝜂,1⟩⟩|𝜉<𝜂<𝛽}∪[(𝛼×{0})×(𝛽×{1})]乗法𝛼⋅𝛽≔type(𝛽×𝛼,𝑅)⟨𝜉,𝜂⟩𝑅⟨𝜉′,𝜂′⟩↔(𝜉<𝜉′∨(𝜉=𝜉′∧𝜂<𝜂′))Theorem 4.21: 加法1.𝛼+0=𝛼2.𝛼+𝑆(𝛽)=𝑆(𝛼+𝛽)3.𝛽 が極限順序数のとき 𝛼+𝛽=sup{𝛼+𝜉,𝜉<𝛽}𝛽−1 とは後続順序数 𝛽=𝑆(𝛾) なら 𝛾, そうではないなら 𝛽 である。積1.𝛼⋅0=02.𝛼⋅𝑆(𝛽)=𝛼⋅𝛽+𝛼3.𝛽 が極限順序数のとき 𝛼⋅𝛽=sup{𝛼⋅𝜉,𝜉<𝛽}冪1.𝛼0=12.𝛼𝑆(𝛽)=𝛼⋅𝛼𝛽3.𝛽 が極限順序数のとき 𝛼𝛽=sup{𝛼𝜉,𝜉<𝛽}11