ホーム

算術の不完全性

概 要

• 自然数論の形式的体系（以下，単に「算術」と呼びます）の不完全性を証明する一つの方法は計算不可能性の結果を利用することです．特に，MRDP定理（ディオファントス方程式に対する可解性判定問題の計算不可能性）を利用することによって， 各種記号列の符号化（ゲーデル数化）や対角線論法をMRDP定理の背後に隠蔽できるので， 不完全性の証明はぐっと簡単になります．これは，言うなれば，MRDP定理という窓を通して算術の世界を眺めるようなもので，算術の世界に足を踏み入れているとは言えないと思います．そのため，不完全性の深層にたどり着くことはないでしょう．でも，一般的な不完全性の証明が難しいと感じている筆者にとっては，深層へと向かうための端緒にはなり得ると感じています．
• このノートは，算術の不完全について，MRDP定理を通して理解したことを記録しています． 特に，不完全性をもたらす十分条件の間の関係性を理解することを目的にしています． なお，このノートは，第1階述語論理とチューリング機械に基づく計算理論に関する初歩的な知識を仮定しています．

目 次

1. 算術（自然数論の形式的体系）
2. MRDP定理
3. 不完全性の十分条件

参 考

• 以下の文献を参考にしています．
  • トルケル・フランセーン (著), 田中 一之 (翻訳) ：「ゲーデルの定理――利用と誤用の不完全ガイド」，みすず書房，2011年．
  • 菊池誠（著）：「不完全性定理」，共立出版，2014年．
  • Lev D. Beklemishev: "Gödel incompleteness theorems and the limits of their applicability. I", Russian Mathematical Surveys, Volume 65, Number 5, 2010.
    ※この文献については，著者自身がホームページ上で公開している ドラフト を参照しています．ちなみに，"II" は存在しないと思われます．おそらく，Gödelを真似ているのだろうと推察します．
• MathJax を利用しています． 奥村晴彦氏のMathJaxのページを参考にしています．