真理は証明の外にある 〜ゲーデルの不完全性定理〜

20世紀を動かした五つの大定理

不完全性定理の流れを言語的に掴む

少し長くなるが、不完全性定理の説明を探していたので、引用。
外人の本の翻訳本なのでやや言い回しがわかりにくい点がところどころある。

イタリアのボローニャにおける１９２８年の国際数学者会議（ICM）において、著名なドイツの数学者ディビッド・ヒルベルトは、論理的に証明可能なものと実際に真であるものとの関係についての考え方を講義した。この講演で問題になったのは、数学的に正しいあらゆる言明が証明可能かどうか、という点だった。またヒルベルトが求めていたのは、考えうる数学的言明をすべて解決できる、というある種の真理機械だった。その機械の一端に言明を入れ、クランクを回して機械を動かすと、もう一方の端から答え（真または偽）がポンと出てくる、という。

しかし、ヒルベルトの講演から３年経たないうちに若きオーストラリアの論理学者クルト・ゲーデルがヒルベルトの愛してやまないその夢を覆す論文を発表し、数学界をびっくりさせた。彼は、『真だが証明不可能な数学的言明が存在すること』を示した。もう少し普通にいえば、証明できるものと真であるものとの間に、永遠の橋渡しができないギャップが存在するということだ。数学全体のために公理的枠組を設定しようとする構想（ヒルベルトが数学の第一目標と述べたもの）が、ゲーデルによる攻撃の出発点となった。

ゲーデルの定理の証明では、二つの極めて重要な概念がある。まず第一にゲーデル数である。次に日常での真理の概念を数学での証明の概念に置き換えることである。それとともに言葉で述べた論理上のパラドックスを算術の言明に移すのである。ヒルベルトを悩ませたそれら論理上のパラドックスは、すべて自己言及の概念に基づいている。そのひとつが、「うそつきのパラドックス」である。その一例が

この文章は偽である。

なぜこれがパラドックスなのか？
この文章は、自分自身が嘘だと言っている。もしこの主張が事実なら、この文章は真でなければならない。一方もし、この文章が真なら、その主張が事実と一致することを意味する。だが、この真の文章は自らが偽だと述べている。したがってこの文章は実際のところ、偽でなければならない。こうして、この文章を真と仮定しようが偽と仮定しようが、その反対の結論を出さざるを得なくなるのだ。

ゲーデルが行おうとしたのは、算術の枠組の内部でこうした矛盾した自己言及の言明を表現する方法を見つけることだった。それは、ヒルベルトの「すべての真の主張が形式的体系の中で証明可能であるべきだ」という命題に対する例外を示すためである。しかしながら、うそつきのパラドックスのような言明は真の概念を必要とする。論理学者のアルフレッド・タルスキが以前に指摘したように、それは形式的体系の範囲内では把握できない代物なのである。そこでゲーデルの偉大なアイデアその２に入ることにしよう。

永遠に掴みどころのない真という概念を使う代わりに、ゲーデルは「真」を何か形式化できるもので置き換えることを思いついた。それは証明可能性（provability）の概念である。こうしてゲーデルは、前のうそつきのパラドックスを次のゲーデル文に訂正した。

この言明は証明可能ではない

もしこの文章が証明可能と判明したら、ゲーデルによると真と証明の同一視によって、その証明は真でなければならない。したがって、その言明の主張は
真でなければならない。したがって、その言明の主張は真でなければならない。だが、ここで言明は自分自身が証明可能ではないと主張している。その結果、その言明とその否定の両方が証明可能となり、証明の論理的構成に矛盾を暗示することになる。すなわち、この言及は真だが証明できないことになる。こうして証明できない真の言明が存在することになる。これは、言明を証明するために用いている形式的体系が、不完全であることを暗示している。
　ゲーデルが示したことは、言葉で表した自己言及文を、算術の言明を証明する際に数学者が用いる形式的体系内での等価な言明に移す方法だった。これは、ぜひ覚えておいてほしい。こうして、矛盾と不完全について今しがた引き出した結果が、算術に関する数学上の仕掛け全体に当てはまることになる。すなわち、もし算術に用いる形式的体系が無矛盾であれば、それは必然的に不完全でなければならない。

　普通の算術に関するすべての言明を十分表現できる無矛盾などんな形式的体系に対しても、そのようなゲーデル文が存在する。これをゲーデルは示すことができた。その結果、形式化というのは不完全とならざるを得ない。そして最終的に明らかになったのは、整数の関係をすべて表現できる無矛盾などんな形式的体系においても、その体系の規則を用いて証明できない言明が存在するというということだ。にもかかわらず、その言明は数についての真の主張を表現しており、その体系の外に飛び出せば真だと了解できる言明である。

以上のさまざまな概念をまとめると最終的に次の定理に至る。

ゲーデルの定理（形式論理版）

あらゆる無矛盾な算術の形式化に対して、その形式的体系の内部では証明することができない算術上の真理が存在する。

ゲーデルの驚くべき結論に至るステップは、論理的に扱いにくく複雑に入り組んでいるので、表の道筋に沿って主要な流れをかいつまんで一覧表に要約しておこう。

ゲーデル証明の主な道筋

○ゲーデル数
「プリンキピア・マテマティカ」（バートランド・ラッセルとアルフレッド・ノース・ホワイトヘッドによる代表作。）でのあらゆる論理式と証明の系列を、自然数による「鏡像」的言明へ移すためのコード化方式の開発。

↓

○ウソつきのパラドックス
「真」の概念を、「証明可能性」の概念で置き換え、それによってウソつきのパラドックスを『この言明は証明できない』という主張に移す。

↓

○ゲーデル文
「この言明は証明できない」という文章が、考えうるすべての算術の形式化において、算術に対応するもの、すなわち、そのゲーデル文Gを持つことを示す。

↓

○不完全性
もしその形式的体系が無矛盾ならば、そのゲーデル文Gは真だが証明できないことを示す。

↓

○免れぬ条項
Gを証明可能となる新しい体系を形成するために、たとえ公理を追加したとしても、その追加公理を持つ新しい体系自身が、その体系内で証明できないゲーデル文を持つことを示す。

↓

○無矛盾性
「算術は無矛盾である」と主張する算術上の言明Aを作る。この算術上の言明が証明可能ではないことを示し、こうして形式的体系としての算術があまりにも弱く、それ自身の無矛盾性を証明できないことを示す。

ここまで論じたとき、チューリングとゲーデルの結果の間に、著しい類似性があることに気づく。二つの定理の本質を再び述べると、

ゲーデルの定理
算術の全言明を解決する（すなわち証明するか反証する）ことを目的とする、どんな無矛盾な形式的体系Fに対しても、この体系内に証明も反証もできない算術上の命題が存在する。それゆえ、形式的体系Fは不完全である。

停止定理
すべてのチューリング・マシンのプログラムについて、それが停止するかしないかを決めることを目的とする、どんなチューリング・マシンのプログラムHに対しても、入力データIを処理しているときにプログラムPが停止するかどうか、そのプログラムHが決定できないような、PとIが存在する

こんなふうに述べてみるとかなり明らかになると思うが、停止定理というのはたんに、論理演繹体系の言語の代わりに計算機械とプログラムの言葉で表現した、ゲーデルの定理にほかならない。

ゲーデルの示したのは、真だとはわかるが、論理的推論のつながりを追うことは証明できない、算術についての言明が存在するということである。別の言い方をするとどんな規則の集合も、算術について考えうる真の言明のすべてを「囲い込む」ことはできない。
すなわち、真理は証明の及ばないところにも確かに存在するのだ。

（ある哲学者たちはこれを人間の知性力が演繹推論の力をどういうわけか凌駕するあかしと考えた。この立場から、人間の知性と同じ力をもつ計算機をつくれないと結論するまではほんの小さなステップにすぎない。）