その１の続きです。
さて、いよいよ本題の解説に入ってゆく。
この回を読めば、もうあなたも、「ゲーデルは神が存在しないことを証明した」などという恥ずかしい発言をしなくて済むようになるはずである。
もしそれが正しいのなら、後述するように、ゲンツェンは神が存在することを証明したことになってしまう。
不完全性を説明するために、まずは完全性とは何かを説明しなければならない。
順を追って説明しよう。
数学は厳密なルールにより成り立っている。最初に設定されるルールは公理と呼ばれる。
この公理からさまざまな定理や命題を導き出してゆくことが、基本的な数学という取り組みである。
定理を与えられた公理などから導くことを証明という。
ここで、ある公理が定められた数学体系があるとして、それをMと呼ぼう。
このM内において考えられるすべての式、命題、定理が証明、または反証（否定の証明）ができるならば、Mは完全であるという。
最初に設定するルールは当然、矛盾していてはいけない。矛盾するルールで行うゲームは良いゲームとは言えないだろう。
数学の矛盾とは、ある命題Pがあったとすると、「P」と「Pでない」が両方証明できてしまうことを言う。
ヒルベルトなどが目指したのはまさに、数学という体系が、無矛盾かつ完全であるということを示そうということだった。
そして、ゲーデルの第一不完全性定理は、これが破綻することを突きつけた。
彼は、数学のルールが無矛盾であるとき、必ず証明も反証もできない命題を作れてしまうことを示したのだ。
すなわち、無矛盾な数学体系は、完全ではないのだ。
一つ謝っておきたいのは、厳密にはゲーデルの定理では、単なる無矛盾ではなくω無矛盾という種類の無矛盾性を仮定している点である。
ω無矛盾とは、自然数n（n＝１、２、３、…）に対応する命題A(x)があったとして、個々の命題A(1)、A(2)、A(3)…は全部証明できるが、すべてのnに一般化したA(n)は証明できない、と言う制約のある無矛盾性である。
ゲーデル自身は普通の無矛盾性から不完全性を導くことができず、弱い形でのω無矛盾性を用いたのだが、のちにジョン・バークリー・ロッサーと言う数学者によって完成された。
しかしこういう説明が出てくると文系は振り落とされてしまうので、今回はただの無矛盾性とさせてもらう。
それでは、おまちかねの「証明も反証もできない命題」を作っていこう。
まずゲーデル数についての記法を定めよう。
まず、例えば変数を一個だけ持つ論理式K(x)があるとする。
その１で紹介したように、この論理式にただ一つの自然数（ゲーデル数）を割り当てることができる。
ゲーデル数を作る時は＃記号をつけることにしよう。
そしてK(x)のゲーデル数、記号で表すと＃K(x)の具体的な数を小文字でkと表そう。
＃K(x)＝k
この変数xにはkを代入することもできる。そうしてできた論理式K(k)にも対応するゲーデル数があるはずだ。
言葉で言えば、「自身のゲーデル数を変数に代入した式のゲーデル数」だ。
このようなゲーデル数は、あらゆる一変数論理式で考えられる。
一般化されたそれをS(x)と表記しよう。
上記の場合、#K(k)＝S(k)である。
それでは、「ゲーデル数を変数にもつ論理式が、数学体系Mで証明できる」と言う命題を考えてみよう。これをPf(x)とする。（proofからとっている）
そこで次のような論理式G(x)を用意する。
G(x)＝¬Pf(S(x))
この¬とはnot、つまり否定を表す。
言葉で説明すれば、G(x)は「「自身のゲーデル数を変数に代入した式のゲーデル数」を代入したこの論理式は数学体系Mで証明できない」を意味する。
ついてこれているだろうか。
さて、ここでさらにややこしいことをする。このG(x)にも対応するゲーデル数があるはずだ。もうお分かりかもしれないが、それをG(x)に代入する。
＃G(x)＝gとすると、
G(g)= ¬Pf(S(g))
S(x)について思い出せば、
G(g)=¬Pf(＃G(g))
と変換できることがわかるだろう。
ここでこの式の意味を考えてもらいたい。
言葉で表すならば、
G(g)＝「「G(x)のゲーデル数を自身に代入した式のゲーデル数」を代入したこの論理式は数学体系Mで証明できない」
よく見てみると「Gのゲーデル数を自身に代入した式」の部分が、この式の右側全体とイコールになるのである。
つまり、
「この式」＝「「この式」のゲーデル数を代入したこの論理式は証明できない」
「のゲーデル数を代入したこの論理式」は大したこと言っていないので省略すれば、
「この式」＝「「この式」は証明できない」
と言っているのである！
こんな感じで入れ子状態の関係式を作ることができたと言うわけだ。
（さっきから式と言っているが、文でも命題でも構わない）
右辺全体を「この式」に代入すると、
「この式」＝「「「この式」は証明できない」は証明できない」
さらに、
「この式」＝「「「「この式」は証明できない」は証明できない」は証明できない」
と無限に続けることができる。
このような式のことを、ゲーデル式、またはゲーデル文と言う。
何を食ったらこれが思いついたのかは定かではないが、とにかくゲーデルはこれを思いついたのだ。
さて数学体系Mの中で、
①「この式」つまりゲーデル文が証明できるならば、
「この式」が証明できる
↔︎「「この式」は証明できない」が証明できる
と言うことになってしまう。よって矛盾が発生する。
②逆に、ゲーデル文が反証できる、つまり否定が証明できるなら、
「「この式」は証明できない」の否定すなわち「「この式」が証明できる」が証明できることになる。
すると
「「この式」が証明できる」が証明できる
↔︎「「この式」は証明できない」が証明できる」が証明できる
となり、①が証明できてしまうことになってしまうので矛盾である。
こうして、矛盾を許さないのなら、ゲーデル分は証明も反証もできないことがわかる。
数学体系Mは無矛盾ならば、不完全である……（第一不完全性定理）
上の証明と反証のところは、どこかで見覚えがあるかもしれない。
これは「嘘つきのパラドックス」と同じ構造をしているのだ。
「この式」を「私」に置き換えれば、私が「私は証明できない」と発言しているのである。
「私は嘘つきである」は、私が嘘つきなら嘘つきでないことに、嘘つきでないなら嘘をついていることになる。
ゲーデルの定理が文系に愛される理由は、このように自然言語との類似性があるからだろう。
数学もまた、嘘をつくのだと。やった、数学は完全じゃないんだ！文系の勝利だ！理系は自分たちが論理的だとか金輪際抜かすんじゃねえ！神は存在しないんだ…！
さて、ここまで来たら、第二不完全性定理も目前である。
ヒルベルトの夢のうち、第一不完全性定理で完全性を否定してみせた。
では無矛盾性はどうだろうか。
これは背理法で示していく。
仮にゲーデル文が証明、または反証ができるとしよう
数学体系Mが完全であるなら、Mの中で矛盾を証明できることになる。
Mが完全である→Mの中で矛盾を証明できる
これの対偶をとってみよう。
Mの中で矛盾を証明できない→Mが不完全、つまり、「「この式」は証明できない」が証明できない
ヒルベルトが望むように、もしMの無矛盾性を証明したいのであれば、「M内で矛盾が証明できない」を証明する必要がある。矛盾が証明できてしまっては困るからだ。
何やら雲行きが怪しくなってきた。
上記を言い換えると、「「「この式」は証明できない」が証明できない」を証明する必要がある。
しかし、これは第一不完全性定理に抵触する。
Mが無矛盾なら、「この式」は証明できない」の反証もできないのだった。
つまり、Mの無矛盾性が証明できると言う仮定は間違っていたのだ。
数学体系Mが無矛盾のとき、Mは自身の無矛盾性を証明できない……（第二不完全性定理）
これは小話であるが、ゲーデルは第一不完全性定理を発表した時、すでに第二不完全性定理にも気づいていた。
しかし、数学会の反応を少し見守ろうと、第二不完全性定理の発表のタイミングを待っていた。
その間に、第一不完全性定理から即座に第二不完全性定理を導いたパウル・ベルナイスによって、先に発表されてしまった。
とにかくこの二つ実に驚くべき結果である。
数学という厳密なルールブックは、その無矛盾性ゆえに、自身の無矛盾性も完全性も、示すことができないのだ。
なんだ、もう数学は終わったのか……。
そんなことは全くない。前にも記述した通り、ゲーデルの仕事を経て、コンピュータの理論が開拓された。
また、数理論理学はこれを機にさらに発展していった。ゲーデルから新たな数学が始まったと言っても良い。
また、超越的な方法を使って（ある種、無限に長い証明なるものを考えることによって）、無矛盾性を証明できることが、ゲルハルト・ゲンツェンによって示されたりした。
（ああホッとした、やはり神は存在したのか……）
他にも、グレゴリー・チャイティンによってゲーデルのものと等価な証明が発見されたりもした。
アラン・チューリングはゲーデルからヒントを得たあと、有名な『停止問題』を示した。
実はこれは不完全性定理と本質的に同じことを言っているのだ。
チューリングは論理式をプログラムと捉え、そのプログラムをデータ＝数字で表すことができることを示した。これはゲーデル数のアイデアと等価である。
このように、計算理論、計算複雑性へと理論は発展していき、ミレニアム問題の一つであるN≠NP予想にも繋がってゆく。
その話もいずれ話すとして、次回ではこのチューリングの停止問題を、図解で一発で理解させて見せよう。
お楽しみに。
コメント