Goedel is the last name of Kurt...

エイプリルフール企画 解答編

結城浩

目次

結城の解答

解答

言えない。 反例は「NDSNDS」。

以下、NDSNDSのカードはスキャナを通らないが有効なカードであることを証明する。

ルール(d)により、

「NDSNDSが有効である」⇔「NDSNDSのカードがスキャナを通らない」

である。したがって、次の(A)(B)のいずれかが真となる。

ところで、(B)はルール(f)と矛盾する。 したがって(A)が成り立つ。

解説

意味論的に書いてみましょう。

つまりこのシステムでは、カードに書かれている文字列によって、 有効なカードは何であるかを記述できることになります。

「NDSNDS」というのは「NDSを2回繰り返したものがスキャナを通らない」という命題です。 つまり「自分はスキャナを通らない」という命題になっているのですね。 これはカントールの対角線論法や、計算機の停止問題と類似した考え方です。

ゲーデルはこれと似た議論を展開して不完全性定理を証明しました。 「あるカードがスキャナを通る」というのを「ある文が証明可能である」に置き換え、 「あるカードが有効である」というのを「ある文が真である」に置き換えます。 すると「真であるのに証明が不可能な文が存在する」ということが言えることになります。

以下余談。 KurtくんはLedeog Universityの研究者、と4月1日の日記で書きましたが、 LedeogというのはGoedelの逆綴りです。 また、Kurtというのはゲーデルの名前です。

鷲崎弘宜さんの解答

解答

「有効なカードはすべてこのスキャナを通る」とは言えない。
「有効なのにスキャナを通らないカード」として、
文字列 "NDSNDS" を持つカードが存在する。

この解答を得た過程を以下に示す。

[ルール]

以降において、カードが持つ文字列のタイプを「Card」と記述する。
ある文字列 c がスキャナを通るかどうかの真理値を示す式を「S(c)」と、
有効であるかどうかの真理値を示す式を「V(c)」と記述する。
記号「+」は文字列の連結を表す。

ルール(a) (∀c : Card |: S(c) ≡ V("S" + c) ) が成り立つ
ルール(b) (∀c : Card |: ¬S(c) ≡ V("NS" + c) ) が成り立つ
ルール(c) (∀c : Card |: S(c + c) ≡ V("DS" + c) ) が成り立つ
ルール(d) (∀c : Card |: ¬S(c + c) ≡ V("NDS" + c) ) が成り立つ
ルール(e) (∀c : Card | S(c) : V(c) ) 
= (∀c : Card |: S(c) ⇒ V(c) ) が成り立つ
ルール(f) (∀c : Card | ¬V(c) : ¬S(c) ) 
= (∀c : Card |: ¬V(c) ⇒ ¬S(c) ) 
= (∀c : Card |: S(c) ⇒ V(c) ) が成り立つ

つまり、(e) と (f) は同値。

[問題]

(q) (∀c : Card |: V(c) ⇒ S(c) ) が成り立つか?

[解答1]

以下に反例を示す。

(e) より、
(e') S("NDSNDS") ⇒ V("NDSNDS") が成り立つ。

(d) より、
(d'') ¬S("NDS" + "NDS") ≡ V("NDS" + "NDS") 
= ¬S("NDSNDS") ≡ V("NDSNDS") 
= S("NDSNDS") ≡ ¬V("NDSNDS") が成り立つ。

(e') より、
(e'') S("NDSNDS") ⇒ V("NDSNDS") 
= ¬V("NDSNDS") ⇒ V("NDSNDS") 
= ¬V("NDSNDS") ∧ V("NDSNDS") ≡ ¬V("NDSNDS") 
= V("NDSNDS") ≡ true
= S("NDSNDS") ≡ false が成り立つ。

従って、文字列 "NDSNDS" を持つカードは有効であるが
スキャナを通らない。 □

[解答2]

以下に (q) が成り立たないことを示す。

(q) が成り立つならば、(e) より
(q') (∀c : Card |: S(c) ≡ V(c) )
が成り立つ。

(q')が成り立つならば、
(q'') S("NDS" + "NDS") ≡ V("NDS" + "NDS")
が成り立つ。

一方、(d) より
(d') !S("NDS" + "NDS") ≡ V("NDS" + "NDS")
が成り立つ。

しかし (q'') と (d') は矛盾する。
従って (q) は成り立たない。 □

参考文献

今回のパズルの題材は以下の本から得ています。

豊かな人生のための四つの法則