不完全性定理は「現代科学の限界」なるものを示してはいない（その１）

数学

これまでのお話

第一不完全性定理は「真であるが証明できないことが存在する」ではない

今日、第一不完全性定理として知られている定理は、次のものです。


体系 T が以下の三条件をみたしているとする。
  1. T は PA を含む。
  2. T は帰納的に記述できる。
  3. T は無矛盾である。
このとき、T の文(自由変数をもたない論理式) G が存在して、G も¬G も T で証明可能でない。
ここで、¬G は Gの否定を表します。


前提にも結論にも、論理式や体系の真偽に関する条件は含まれていません。つまり、第一不完全性定理のステートメントには真偽概念は含まれていないのです。

前提の三条件を少し詳しく見て、真偽概念が含まれていないことを確認しましょう。

体系 T が体系 t を含むとは、体系 t の論理式 A を体系 T の論理式 A* に翻訳し、さらに、A に t での証明 Π があれば体系 T における A* の証明 Π* に翻訳する、翻訳手続き * が存在することです。

PAは一階ペアノ算術の略称で、自然数論の体系の一つです。コンピュータで計算できる関数はすべて定義でき、さらに多くの関数が定義でき、数学的帰納法は自由に使えますが、無限集合は扱えない程度のものです。

前提の条件1に真偽概念が含まれていないことがわかりました。

帰納的に記述できるというのは、次の二条件が成り立つことです。

  1. 論理式 A が与えられたとき、A が公理であるかどうかを判定する手続きが存在する。
  2. 論理式 A1, …, An, B が与えられたとき、A1, …, An から B を導くことが推論規則の正しい適用であるかどうかを判定する手続きが存在する。
形式的体系における証明とは、公理から出発して推論規則の適用を有限回行なうことですから、この二条件は、その体系のための証明検証系（証明らしいものが与えらたとき、それが正しい証明であるかどこかに間違いがあるかを検証するプログラム）を、（原理的には）書くことができることと、同値です。自動証明系（定理を与えるとその証明を構成するプログラム）を書くことができる必要はありません。

前提の条件2に真偽概念が含まれていないことがわかりました。

なお、PA も帰納的に記述できる体系です。実用的な体系の多くは帰納的に記述できます。帰納的に記述できない体系も存在します。

体系が矛盾するとは、ある論理式 A とその否定 ¬A がどちらも証明できることです。体系が無矛盾であるとは、矛盾しないことです。

前提の条件3に真偽概念が含まれていないことがわかりました。

そういえば、「証明できる」の説明があとまわしになりましたね。論理式 C が証明できるとは、証明 Π が存在して、C は Π の最後に出現する論理式であることです。

注意しなくてはならないのは、論理式の否定とは、元の式の前に記号 ¬ を加えて得られる式のことであって、それが真偽を反転させる意味でのいわゆる「否定」であるともないともいっていないことです。すなわち、論理式を否定するとは、単に記号をひとつ加えるだけのことであって、真偽概念と関係なく実行できる操作です。

結論に真偽概念が含まれていないことがわかりました。

結局、前提の三条件も結論も、ソフトウェアの言葉でいえば記号処理のみで定義できる条件であることがわかります。数理論理学の言葉では、いずれも構文論的な条件であるといいます。第一不完全性定理は、純粋に構文論的に記述できる定理であり、体系の真偽には依存しないことがわかるはずです。

ちなみに、ゲーデルの原論文で証明されている定理では、今回紹介したものよりも強い前提をおいています。つまり、オリジナルはこれよりも弱い定理です。この形になったのは、他の何人かの貢献が加わった結果です。また、実は、これよりもさらに前提を弱めることが可能であることも知られています。しかし、そのことは今回の議論には影響しません。ゲーデルの原論文の定理にも、より強い第一不完全性定理にも、今回の議論は修正なく適用できます。

(次回は「第二不完全性定理は『体系は自身の正しさを証明できない』ではない」)