to mock a mockingbirdを読む(42)17章

ゲーデルの森

Craigは次の森にやってきた。そこでこの森の鳥類学者Giuseppe Baritoniにこの森で成り立つ法則をきいた。
この森では以下の法則が成り立つ。

law 1.この森の全てのナイチンゲールは歌う
law 2.x'yはxyが歌わないときに限り、歌う
law 3.x*yはx(yy)が歌うときに限り、歌う
law 4.Nxはxがナイチンゲールであるときに限り歌う

この森ではナイチンゲールが歌うのしかきいたことがないが
ナイチンゲール以外に歌うとりはいるのかとCraigがきくと
その答えはまだ分かっていないとBaritoniは答えた。
Craigはしばらく考えたのち、ナイチンゲール以外に歌う鳥Gがいることを突き止めた。
注：文字の読みがわからないためGとしています

Problem 1

どのようにしてCraigは鳥Gがいることを突き止め、二人はどうやって
それを見つけたのか

解

NについてN'*を考え、これをAとする
AA、つまりN'*N'*がナイチンゲールではない歌う鳥Gであることを示す。

鳥Aは任意の鳥xについてxxがナイチンゲールでないときに限りAxが歌うという属性を持つ。これを示す。
N'*はN'(xx)が歌うときに限り歌う(law 3)。
N'(xx)はN(xx)が歌わないときに限り歌う。これはxxがナイチンゲールでないときに限り真である(law 4)
これらより、N'*はxxがナイチンゲールでないときに限り歌う。よって上の属性が示される。

xにAをあてはめると、AAはAAがナイチンゲールでないときに限り歌う。
これは、AAがナイチンゲールでなく歌うか、AAは歌わないがナイチンゲールであるかのどちらかであるが
law 1より後者は起こり得ない
よってAAはナイチンゲールではないが歌う鳥Gである。

Problem 2 A Follow-up

Gとは違う鳥でナイチンゲールではないが歌う鳥G1を見つけよ

解

N*'(N'*ではない)をA1とおく。
前問と類似の考察によって、A1A1=G1はナイチンゲールではないが歌う鳥G1である

Problem 3 The Bird Societies

まず、言葉の定義を行う。
鳥Aが鳥の集合Sをrepresentするとは、Sに含まれる各鳥xについて
Axが歌う鳥であり、Sに含まれない各鳥xについて
Axが歌わない鳥であることである。
言い換えると、各鳥xについて、AxはxがSのメンバーであるときにのみ歌う。

鳥の集合は、それが何かの鳥にrepresentされているときsocietyと呼ぶ。
例えばナイチンゲールの集合はsocietyを構成する。
なぜならその集合はNによってrepresentされるからである。

問題：全ての歌う鳥の集合はsocietyを形成するだろうか

解

まず、law3の基礎の上に、societyは歌う鳥が属するか、歌わない鳥が属さないことを証明する。
任意のsociety Sをとる。Sはなんらかの鳥Aによってrepresentされる。
ここでA*を考える。任意の鳥xについてA*xはA(xx)が歌うときのみに歌う。(law 3)
またA(xx)はxxがSのメンバーであるときにのみ歌う。なぜならAはSをrepresentするから。
よってA*xはxxがSのメンバーであるときにのみ歌う。
特にA*A*はA*A*がSのメンバーであるときにのみ歌う。
よって、歌うA*A*はSのメンバーであるか、歌わないA*A*はSに含まれないかのどちらかである

ここで、全ての歌う鳥がsocietyを作るとすると次の矛盾が導かれる。
全ての歌う鳥の集合は何らかの鳥Aによってrepresentされる。
law 2よりA'は全ての歌わない鳥の集合をrepresentする。
これより歌わない鳥の集合はsocietyを作るがこれは不可能である。
なぜなら、この集合は歌う鳥を含むか、歌わない鳥が存在してはならないからである。
よって全ての歌う鳥はsocietyを作らないことが導かれる