| はじめに i |
| Part A.数理論理学入門 1 |
| 第1講 準備練習 3 |
| 1.1 論理について 3 |
| 1.2 集合について 6 |
| 1.3 再帰的定義と帰納法による証明 10 |
| 第2講 命題論理 13 |
| 2.1 トートロジー 13 |
| 2.2 命題論理の公理系 15 |
| 2.3 命題論理の完全性定理 20 |
| 第3講 述語論理 24 |
| 3.1 構造と言語 24 |
| 3.2 ゲーデルの完全性定理 29 |
| 3.3 完全性定理の応用1 35 |
| 3.4 完全性定理の応用2 36 |
| 第4講 再帰的関数 41 |
| 4.1 原始再帰的関数 41 |
| 4.2 原始再帰的集合 44 |
| 4.3 再帰的関数 46 |
| 4.4 再帰的関係とRE集合 51 |
| 4.5 β関数によるコード化 57 |
| 4.6 原始再帰法の消去 61 |
| パートA参考文献 64 |
| Part B.不完全性定理 65 |
| 第5講 算術の体系 67 |
| 5.1 ロビンソンの算術Q 67 |
| 5.2 ベアノ算術 69 |
| 5.3 Qの基本的な能力 71 |
| 5.4 Σ1完全性定理 73 |
| 5.5 表現可能性 76 |
| 第6講 第一不完全性定理 81 |
| 6.1 第一不完全性定理の主張(1) 81 |
| 6.2 ゲーデル数 82 |
| 6.3 第一不完全性定理の主張(2) 84 |
| 6.4 可証性述語 86 |
| 6.5 対角化定理 88 |
| 6.6 ゲーデルの第一不完全性定理 90 |
| 第7講 第一不完全性定理の拡張 93 |
| 7.1 ロッサーの不完全性定理 93 |
| 7.2 クレイグの手法 95 |
| 7.3 決定不能性に関するいくつかの結果 96 |
| 第8講 第二不完全性定理 99 |
| 8.1 第二不完全性定理の意義 99 |
| 8.2 可導性条件と第二不完全性定理 100 |
| 8.3 可証性述語のいくつかの性質 103 |
| 8.4 可証性述語と様相論理 105 |
| 第9講 可証性述語の詳細 108 |
| 9.1 β関数定理の形式化 108 |
| 9.2 可証性述語の定義 109 |
| 9.3 可導性条件D2の証明 113 |
| 9.4 Σ1完全性定理の形式化 114 |
| 9.5 クレイグの手法の形式化 119 |
| パートB参考文献 121 |
| Part C.組合せ的独立命題 123 |
| 第10講 順序数と急増加関数 125 |
| 10.1 ε0までの順序数と基本列 125 |
| 10.2 ヒドラ-ヘラクレス戦 129 |
| 10.3 グッドシュタイン列 131 |
| 10.4 急増加関数 133 |
| 第11講 パーソンズの定理(IΣ1と原始再帰的関数) 137 |
| 11.1 パーソンズの定理の応用 137 |
| 11.2 I*Σ1 138 |
| 11.3 カット消去定理 140 |
| 11.4 パーソンズの定理の証明 142 |
| 第12講 クライゼルの定理(PAと急増加関数) 146 |
| 12.1 クライゼルの定理の応用 146 |
| 12.2 PA∝ 147 |
| 12.3 カット消去定理 151 |
| 12.4 クライゼルの定理の証明 152 |
| 第13講 パリス-ハーリントンの独立命題 155 |
| 13.1 パリス-ハーリントンの命題PH 155 |
| 13.2 PHが真であること 157 |
| 13.3 PH(2)がIΣ1で証明できないこと 158 |
| 13.4 PHがPAで証明できないこと 160 |
| パートC参考文献 166 |
| Part D.算術の超準モデル 167 |
| 第14講 算術の超準モデル 168 |
| 14.1 算術の超準モデル 168 |
| 14.2 ペアノ算術 170 |
| 14.3 超準モデルの順序構造 172 |
| 14.4 始切片,終拡大 174 |
| 第15講 テンネンバウムの定理 177 |
| 15.1 テンネンバウムの定理 177 |
| 15.2 再帰的な超準モデルについて 181 |
| 第16講 モデルを用いた不完全性定理の証明 183 |
| 16.1 不完全性定理と超準モデル 183 |
| 16.2 完全性定理の算術化 184 |
| 16.3 モデルを用いた不完全性定理の証明 187 |
| 第17講 超準モデルと計算量理論 190 |
| 17.1 パリクの定理 190 |
| 17.2 P,NP,co-NP 192 |
| 17.3 ウィルキーの定理 194 |
| パートD参考文献 196 |
| 補講 不完全性定理を超えて 198 |
| ヒルベルトのプログラム 198 |
| 逆数学プログラム 199 |
| おわりに 201 |
| 索引 203 |
