「正直者」と「嘘つき」の問題

引き続き、『数学ガール　ゲーデルの不完全性定理』より。

「正直者は誰？」という問題が載っていました。以下がこの問題です。

正直者は誰？
A₁「ここに、嘘つきは1人いる」
A₂「ここに、嘘つきは2人いる」
A₃「ここに、嘘つきは3人いる」
A₄「ここに、嘘つきは4人いる」
A₅「ここに、嘘つきは5人いる」

ここでの「正直者」は常に本当のことを言い、逆に「嘘つき」は常に嘘をつきます。

この問題での答えは、A₄。
A₄が正直者です。

場合分けして考えてみましょう。



まずは、正直者が0人、つまり嘘つきが5人と仮定します。

しかし、A₅は、「ここに、嘘つきは5人いる」と言っています。つまり、A₅は本当のことを言っている。そのため、矛盾が生じます。

次に、正直者が1人、嘘つきが4人とすると、A₄は「ここに、嘘つきは4人いる」と言っているので、A₄が正直者、残りが嘘つきです。

正直者が2人、嘘つきが3人とすると、A₃が「ここに、嘘つきは3人いる」と言っているので正直者。あとの4人は嘘つきとなりますが、仮定とは矛盾。

同様に、正直者が3人、4人、5人と考えても矛盾が生じます。

したがって、答えは「A₄が正直者」です。


『数学ガール』では、一般化させた問題に発展させます。

正直者は誰？（一般化）
B₁「ここに、嘘つきは1人いる」
B₂「ここに、嘘つきは2人いる」
B₃「ここに、嘘つきは3人いる」
B₄「ここに、嘘つきは4人いる」
B₅「ここに、嘘つきは5人いる」
…
B_n-1「ここに、嘘つきは(n-1)人いる」
B_n「ここに、嘘つきはn人いる」

ここでのnは自然数。
B_n-1が正直者です。

しかし、おかしなことが生じます。n=1のときはどうなるのか？

正直者は誰？（n=1のとき）
C₁「ここに、嘘つきは1人いる」

C₁は正直者なのか、それとも嘘つきなのか？

C₁が正直者だとすると、「ここに、嘘つきは1人いる」という発言は正しいということになります。しかし、ここではC₁1人しかいないので、C₁が嘘つきとなってしまいます。

逆にC₁が嘘つきだとすると、「ここに、嘘つきは1人いる」も嘘となります。つまりC₁が本当のことを言っていることになります。

「正直者」だとすると「嘘つき」になり、「嘘つき」だとすると「正直者」になる。
メビウスの輪のような状態です。


ゲーデルの不完全性定理に関する本を読むと、必ずと言っていいほど、このような「嘘つきのパラドックス」あるいは「クレタ人のパラドックス」の話が出てきます。不完全性定理の証明でのヒントとなっているようです。

「クレタ人のパラドックス」とは、「クレタ人の預言者が『クレタ人は嘘つきだ』と言った」という話です。

この種のパラドックスが生じることと「自己言及性」は密接な関係があります。n=1のときのC₁の発言は「ここに、嘘つきは1人いる」というものですが、このときの「1人」というのはC₁自身を指しています。クレタ人のパラドックスでも、自分自身を指しています。

しかし、自分自身を指しているからといって、全てが矛盾になるわけではありません。クレタ人の預言者が「クレタ人は正直者だ」と言ったら、別に矛盾も何もないのです。

また、自己言及だけではなく、2人の場合でも起こりえます。

D₁「D₂は嘘つきだ」
D₂「D₁は正直者だ」

「矛盾」という言葉も「何でも突き通す矛（ほこ）」と「何でも防ぐ盾（たて）」の話からつくられた言葉です。

「では、何でも突き通す矛で、何でも防ぐ盾を突いたらどうなりますか？」

自己言及性から生じるパラドックス。

不完全性定理の理解のためだけでなく、非常に興味があります。