ゲーデルの定理-1.1- ２種類の定理

　専門外の人達にもその名が広く知られていることではアインシュタインの相対性理論やダーウィンの進化論にも匹敵すると言われるゲーデルの不完全性定理ですが、前記両理論以上に誤解にまみれているとも言われます。相対性理論には特殊相対性理論と一般相対性理論があることは意外に知られていないように、ゲーデルの不完全性定理にも第一と第二があることはあまり知られていません。それより何より、「ゲーデルの完全性定理」という関連深い定理もあることもあまり知られておらず、知っている人はあたかも矛盾する定理が共に証明されたかのような戸惑いを覚えてしまいます。

　戸惑いの原因は「完全性」という概念にいくつもの意味や表現があり混同されやすいことです。実はそれを正しく理解し不完全性定理を深く知るためには、完全性定理と共に学ぶのが良いのです。不完全性定理についてだけ書かれた本のみを読んでいても、なかなか理解は難しいものです。さて、当分の間は第二不完全性定理については無視して不完全性定理と言えば第一不完全性定理のことを指すことにします。

　とはいえ、ひとまずこれらの定理をなるべく誤解の余地が少なそうな表現で述べておきましょう。以下の表現はRef-1のものを参考にしています。以下の表現自体に説明の必要な専門用語が色々出てきますが、その説明は後ほどとします。


述語論理系の完全性定理
　述語論理の形式的体系Ｌにおける恒真式は全て、その形式的体系Ｌの中で証明できる

一般的体系の完全性定理
　一般的数学公理系Ｓにおいて、Ｓを満たすモデルの全てにおいて正しい解釈を与える論理式は述語論理Ｌに公理系Ｓを加えた形式的体系の中で証明できる

ゲーデルの第一不完全性定理
　自然数の公理系を含む形式的体系Ｚが無矛盾であれば、Ｐもその否定￢ＰもＺの中では証明できないような論理式Ｐが存在する

ゲーデルの第二不完全性定理
　自然数の公理系を含む形式的体系Ｚの中で「Ｚが無矛盾である」という意味を表す論理式Consisを作ることができて、もしＺが無矛盾ならば論理式ConsisはＺの中では証明できない
　簡略表現; Ｚがもし無矛盾ならば、Ｚの無矛盾性をＺの中で証明することは不可能である(p259)

　上記の定義からわかることは、完全性定理と不完全性定理では対象とする形式的体系が異なることです。不完全性定理は「自然数の公理系を含む」ものに限定されており、完全性定理はより一般的な体系を対象とします。
　また不完全性定理は「論理式が証明できるか否か」という性質だけに着目していますが、完全性定理は「恒真式」や「正しい解釈を与える」といった証明可能性以外の性質にも着目しています。

　ということで、まずは「完全性」という概念について整理していきます。

　なお、形式的体系では排中律(Ｐ∨￢Ｐ)を採用するのが普通ですが、排中律はＰが証明できることは保証しません。つまり排中律と不完全性定理は矛盾しません。

次回へ続く

－－－－－－－－－－－－－－
References
1) 野崎昭弘『不完全性定理―数学的体系のあゆみ(ちくま学芸文庫)』筑摩書房(2006/05)
2) 日本数学会『岩波数学辞典-第3版』岩波書店(1985/12) [71.記号論理]の項
3) 前原昭二『数学基礎論入門』朝倉書店(1977)