第一不完全性定理

前回のお話のおさらいです。何度でも書いておきますが、直観主義者は
「非可算無限を認めるとパラドックスが発生する。だから『非可算無限』という概念は排除すべきだ」
と主張しました。それに対して形式主義者は
「それだと排中律や一部の背理法も使えなくなってしまう。ならば非可算無限がちゃんと機能することを、可算無限の範囲内で証明できるよう、数学のシステムを構築しなおそうじゃないか」
と答えました。

少し補足しておきますと、「可算無限の範囲内での証明」というのは、基本的な式変形を有限回繰り返すこと、もう少し専門的に言うと、数学的帰納法の適用できる範囲での証明です。

こんな数学システムの構築を目指したヒルベルトに対して、若き天才・ゲーデルはこう言いました。
「可算無限の範囲内での証明って、それ、自然数論そのものじゃね？」

濃度の考え方を説明しましたとき、1対1でペアリングできるかどうかを調べる方法を紹介しましたが、ヒルベルトのこだわっている「可算無限の範囲内での証明」で使われる道具立て、すなわち基本的な式変形(と、それを延々と繰り返す操作)は、可算無限、つまり自然数の濃度にこだわり続ける限りにおいては、自然数と1対1にペアリングできるのではないか？

そう考えたゲーデルは、自然数論に出てくる式や証明を、全て数に変換する方法を見つけました。この「ゲーデル数化」という手順を踏むことで、自然数論の定理は全てある自然数として表現されることとなります。

例を挙げますと、
「4の倍数は必ず2で割り切れる」
という定理を表す自然数が必ず存在するのです。足し算や掛け算、等号や論理演算子(∧や∀など)、それらの式中での並び順、さらには数行にわたる式変形の過程までもが自然数に還元されてしまいます。

このようにして全てを自然数に還元しておいて、ゲーデルは「この定理は証明不可能だ」を表す自然数を表現してみせました。つまり、自然数論上の真理でありながら、自然数論という道具立てでは肯定も否定もできないような定理が存在することが証明され、さらには形式主義者が「可算無限の範囲での証明」にこだわり続ける限り、真理であるにもかかわらず、肯定も否定もできない定理が存在することが数学的に証明されてしまったのです。

真理であるにもかかわらず、その定理が証明できないような論理のシステム(公理系)のことを、「不完全な公理系」と呼びます。ゲーデルは自然数論や形式主義者の目指す公理系が不完全にならざるを得ないことを証明してみせたのです。