Как же называется эта книга?

Что касается первой половины задачи, то ее можно решить двумя способами. Первый из них проще того способа, которым мы только что решили вторую часть задачи, зато второй способ более поучительный.

Первый способ. Так как все рыцари не являются членами одного клуба, а все признанные рыцари являются членами одного клуба, то множество всех рыцарей не совпадает с множеством всех признанных рыцарей. Следовательно, не все рыцари признанные. Аналогично не все лжецы отъявленные.

Второй способ. Так как все признанные рыцари являются членами одного клуба, то все островитяне, не принадлежащие к числу признанных рыцарей, также являются членами одного клуба. Если эти клубы выбрать в качестве клубов C₁, C₂, то (по условию CG) найдутся островитяне А, В, высказывающие следующие утверждения:

А: В – признанный рыцарь.

В: А – не признанный рыцарь.

Предоставляем читателю самостоятельно убедиться в том, что по крайней мере один из островитян А, В должен быть признанным рыцарем (точнее говоря, требуется доказать, что если А – рыцарь, то он не признанный рыцарь, а если А – лжец, то В должен быть непризнанным рыцарем). Установить, кто из островитян А, В непризнанный рыцарь, мы не можем, хотя и знаем, что кто-то из них непризнанный рыцарь. (С точно такой же ситуацией мы уже сталкивались в задаче 134 (о паре шкатулок, изготовленных Беллини и Челлини): одна из шкатулок заведомо должна быть работы Беллини, но установить, какую из двух шкатулок изготовил Беллини, невозможно.) Аналогичным образом, так как все отъявленные лжецы являются членами одного клуба, то все островитяне, не принадлежащие множеству отъявленных лжецов, также являются членами одного клуба. Следовательно (по условию CG), непременно найдутся островитяне А, В, высказывающие следующие утверждения:

А: В – отъявленный лжец,

В: А – не отъявленный лжец.

Отсюда мы заключаем, что если В – лжец, то он не отъявленный лжец, а если В – рыцарь, то А – не отъявленный лжец (доказательство этого утверждения мы также предоставляем читателю). Итак, в любом случае либо А, либо В – не отъявленный лжец, но мы не знаем, кто именно. (По существу эта задача ничем не отличается от задачи 135 о двух шкатулках, изготовленных Беллини и Челлини.)

267. Остров S¹

Однажды мне удалось открыть еще один дважды гёделев остров S¹, который показался мне еще более интересным, чем остров S. Для острова S¹ выполнены оба условия E₁, Е₂, но неизвестно, выполняется ли условие С. (Напомним, что, согласно этому условию, все островитяне, не являющиеся членами клуба С, являются членами одного клуба.)

По-видимому, невозможно доказать, что на острове S¹ непременно есть непризнанный рыцарь или что на том же острове есть неотъявленный лжец. Невозможно, по-видимому, доказать также, что все рыцари не являются членами одного клуба или что все лжецы не являются членами одного клуба. Но следующие утверждения доказать можно:

а) На острове S¹ найдется либо непризнанный рыцарь, либо неотъявленный лжец.

б) Не может быть, чтобы все рыцари являлись членами одного клуба и все лжецы являлись членами одного клуба.

Решение. Докажем сначала утверждение (б). Предположим, что все рыцари являются членами одного клуба и все лжецы являются членами одного клуба. Тогда найдутся островитяне А, В, о которых известно следующее: А утверждает, что В – лжец, а В утверждает, что А – рыцарь. Но это, как мы уже знаем, невозможно (см. предыдущую задачу или задачу 259 в предыдущей главе). Итак, невозможно, чтобы все рыцари являлись членами одного клуба и все лжецы также являлись членами одного клуба. Значит, либо все рыцари не являются членами одного клуба, либо все лжецы не являются членами одного клуба. Если все рыцари не являются членами одного клуба, то непременно найдется по крайней мере один непризнанный рыцарь (поскольку все признанные рыцари являются членами одного клуба). Если все лжецы не являются членами одного клуба, то непременно найдется по крайней мере один неотъявленный лжец. Но какой именно случай представится на острове, мы не знаем. Итак, утверждение (а) доказано.

Альтернативное (и более интересное) доказательство того, что непременно найдется непризнанный рыцарь или неотъявленный лжец, состоит в следующем.

Так как признанные рыцари состоят в одном клубе и отъявленные лжецы состоят в одном клубе, то найдутся островитяне А, В, высказывающие следующие утверждения:

А: В – отъявленный лжец.

В: А – признанный рыцарь.

Предположим, что А – рыцарь. Тогда его утверждение истинно. Значит, В – отъявленный лжец, поэтому его утверждение ложно. Следовательно, А – непризнанный рыцарь. Значит, А – не признанный рыцарь. Если же А – лжец, то высказанное В утверждение ложно, поэтому В – лжец. Высказанное А утверждение также ложно, поэтому В – неотъявленный лжец. Следовательно, В – отъявленный лжец.

Итак, либо А – не признанный рыцарь, либо В – не отъявленный лжец (но мы опять не знаем, какая из двух альтернатив истинна).