2011/06/05

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

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

「正直者は誰?」という問題が載っていました。以下がこの問題です。
正直者は誰?
A1「ここに、嘘つきは1人いる」
A2「ここに、嘘つきは2人いる」
A3「ここに、嘘つきは3人いる」
A4「ここに、嘘つきは4人いる」
A5「ここに、嘘つきは5人いる」
ここでの「正直者」は常に本当のことを言い、逆に「嘘つき」は常に嘘をつきます。

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

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



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

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

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

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

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

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


『数学ガール』では、一般化させた問題に発展させます。
正直者は誰?(一般化)
B1「ここに、嘘つきは1人いる」
B2「ここに、嘘つきは2人いる」
B3「ここに、嘘つきは3人いる」
B4「ここに、嘘つきは4人いる」
B5「ここに、嘘つきは5人いる」

Bn-1「ここに、嘘つきは(n-1)人いる」
Bn「ここに、嘘つきはn人いる」
ここでのnは自然数。
Bn-1が正直者です。

しかし、おかしなことが生じます。n=1のときはどうなるのか?
正直者は誰?(n=1のとき)
C1「ここに、嘘つきは1人いる」
C1は正直者なのか、それとも嘘つきなのか?

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

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

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


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

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

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

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

また、自己言及だけではなく、2人の場合でも起こりえます。
D1「D2は嘘つきだ」
D2「D1は正直者だ」

「矛盾」という言葉も「何でも突き通す矛(ほこ)」と「何でも防ぐ盾(たて)」の話からつくられた言葉です。
「では、何でも突き通す矛で、何でも防ぐ盾を突いたらどうなりますか?」
自己言及性から生じるパラドックス。

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