クレタ人と不完全性定理

世の中正直者と嘘つきしかいないとしよう。そしてアテネ人は正直者でクレタ人は嘘つきであるとしよう。さて「私はアテネ人でない」という人がいた場合、彼は正直者であるがアテネ人ではない。同様に「私はクレタ人だ」という人がいた場合、彼女は嘘つきであるがクレタ人ではない。

ある発言には、１．正直者の発言である２．うそつきの発言である３．アテネ人の発言である４．クレタ人の発言である という４つの性質の成立・非成立を議論できる。明らかなように（１と２）および（３と４）はそれぞれ同時に成立しないが、（１と２）と（３と４）の間には決定的な違いがある。つまり、「正直者でなければ嘘つきだ」が成立するのに対し「アテネ人でなければクレタ人だ」は必ずしも成立しない（例：スパルタ人がいるかもしれない）

数学や論理学においても文に対して１．真な文である２．偽な文である３．証明可能な文である４．反証可能な文である という４つの性質の成立・非成立を議論できる。（１と２）および（３と４）はそれぞれが同時に成立しないように数学を作るが、（１と２）と（３と４）の間には決定的な違いがある。つまり、「真でなければ偽である」が成立するのに対し「証明できなければ反証可能である」は必ずしも成立しない（例：証明も反証もできない文があるかもしれない）

数学で興味があるのは「証明できないが真である文」の存在だ。数学とは体系のルールに従って真なる証明可能な文を発見する行為とみなせるため、「証明できないが真である文」の存在があった場合、ルールの変更を検討する必要があるかもしれない。

冒頭の「私はアテネ人でない」すなわち「正直者の発言だがアテナ人の発言ではない」に対応する「真なる文だが証明できない文」は存在するのだろうか？に対してYesでありうるというのがゲーデルの第一不完全性定理となる。

「真なる文だが証明できない文」が存在する体系としないような体系の両方がある。簡単に言えば、整数や集合を扱うような体系にはそのようなイヤな文が存在するが、実数を扱うような体系にはそのようなイヤな文は存在しない。

最後に一言：「私はアテネ人でない」に対応する文は「証明可能でない文のゲーデル数の集合に対する対角化関数の逆像たる集合を定義する述語を対角化した文」であり、「私はクレタ人である」に対応する文は「反証可能な文のゲーデル数の集合に対する対角化関数の逆像たる集合を定義する述語を対角化した文」となる。

参考資料: スマリヤン『ゲーデルの不完全性定理』