ゲーデルの不完全性定理

ゲーデルの定理は「知ったかぶり」がどのようなものかを腑に落ちる仕方でわかるための格好の例。この定理をわかるには実際に途中を省略せずに証明してみることだが、それが意外に厄介で、証明の多くの部分は「できる筈、そうなる筈」という妥当な推測に基づいて進められる。できるだけ省略せずに自ら証明を実行することが「知ること」とはどのような行為(計算)かを知ることになるが、それを教えてくれるのが不完全性定理の証明である。したがって、当然ながら以下の説明は典型的な「知ったかぶりの説明=説明擬き」。読者はこれで不完全性定理がわかったなどと妄想しないことが肝要で、定理の概要に過ぎないことを肝に銘ずべし、ということになる。>

f:id:huukyou:20160724144534j:plain

 数学界の巨匠ヒルベルトは「数学理論には矛盾は一切無く、どんな問題でも真偽の判定が可能である」ことを数学的に証明しようと、全数学者に一致協力するように呼びかけた。これは「ヒルベルトプログラム」と呼ばれ、数学の論理的な完成を目指す一大プロジェクトとして、当時世界中から注目を集めた。
 そこに若きゲーテルが登場し、「算術を含む数学理論は不完全であり、決して完全にはなりえない」ことを数学的に証明し、ヒルベルトプログラムは挫折することになった。ゲーデル不完全性定理とは算術を含む理論について次のように主張する。

1)第1不完全性原理
 「ある矛盾の無い理論体系の中に、肯定も否定もできない証明不可能な命題が、必ず存在する」

2)第2不完全性原理
 「ある理論体系は自分自身が無矛盾であれば、矛盾が無いことをその理論体系の中で証明できない」

*より正確に表現すれば次のようになる。
第1不完全性定理自然数論を含む帰納的に記述できる公理系が、ω無矛盾であれば、証明も反証もできない命題が存在する。
第2不完全性定理自然数論を含む帰納的に記述できる公理系が、無矛盾であれば、自身の無矛盾性を証明できない。

 その要点を簡単に述べてみよう。たとえば、私が、「私は嘘つきだ」と言ったとする。もしこの言葉が「真実」であれば、私は「嘘つきである」ことになるが、そうすると「嘘つきなのに、真実を言った」ことになってしまい、おかしなことになる。一方、この言葉が「嘘」だとすれば、私は「正直者である」という事になるが、そうすると、「正直者なのに、嘘を言った」ことになってしまい、おかしなことになる。結局、私の言葉が、真実でも、嘘でも、おかしなことが起こってしまうのだ。これは、「自分自身について真偽を確かめようとするときに起こってしまうパラドックス」であることから、一般に「自己言及のパラドックス」といわれている。ちなみに、「私は正直者だ」と言った場合でも、似たようなことになる。まず、この言葉が「真実」だった場合、正直者が「自分は正直者だ」と真実を言ったことになるので、問題なく成り立つわけだが、この言葉が「嘘」だった場合でも、嘘つきが「自分は正直者だ」と嘘を言ったことになるので、これまた問題なく成り立ってしまうのである。つまり、「私は正直者だ」という命題は、真でも偽でも、どちらでも成り立ってしまい、結局、真とも偽とも決められないのである。要するに、「おれって正直者(嘘つき)なんだよねー」と、自分で自分のことを言及したところで自分では、その言葉の正しさを絶対に証明できない、ということになる。
 このような「自己言及パラドックス」が、数学においても、同様に起こることが証明されたのである。それは、すなわち、一見すると、完全無欠に見える数学理論の中にも、「真とも偽とも決められない命題」「証明も反証もできない命題」が含まれていることを意味する(第1不完全性原理)。そして、数学理論において、証明不能な命題を含むということは、「正しいとも、間違っているとも言えない不明な領域」が数学理論の中にあるということなのだから、数学理論が「自らの理論体系は完璧に正しい」と証明することはそもそも不可能なのである(第2不完全性原理)。
 これがゲーデル不完全性定理についての知ったかぶりの説明擬きである。