264. Остров G

Население острова G составляют лишь рыцари, всегда говорящие только правду, и лжецы, которые всегда лгут. Кроме того, некоторых рыцарей называют «признанными рыцарями» (они проявили себя чем-то, подтвердив свое рыцарское звание), а некоторых лжецов (подтвердивших свою приверженность ко лжи) — «отъявленными лжецами».

Обитатели острова G состоят членами различных клубов. Каждый островитянин может быть членом нескольких клубов. Любой островитянин X утверждает относительно любого клуба C, что он либо состоит членом клуба C, либо не состоит членом клуба C.

Известно, что выполняются следующие четыре условия:

E1: Все признанные рыцари состоят членами одного клуба.

E2: Все отъявленные лжецы состоят членами одного клуба.

C (условие дополнительности; C — от лат. complementum — дополнение). Все островитяне, не состоящие членами любого клуба C, состоят в одном клубе. (Этот клуб называется дополнением клуба C и обозначается ~C.)

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

264 а (по Гёделю).

1) Докажите, что на острове G существует по крайней мере один непризнанный рыцарь.

2) Докажите, что на острове существует по крайней мере один неотъявленный лжец.

264 б (по Тарскому).

1) Состоят ли все лжецы острова членами одного клуба?

2) Состоят ли все рыцари острова членами одного клуба?

Решение задачи 264 а.

По условию E1 все признанные рыцари острова (образующие множество E) состоят членами одного клуба. Следовательно, по условию C все островитяне, входящие в множество E непризнанных рыцарей, также состоят членами одного клуба. Но тогда по условию G существует по крайней мере один островитянин, который утверждает, что состоит членом клуба E (иначе говоря, он утверждает, что принадлежит к множеству непризнанных рыцарей). Лжец не мог бы утверждать, что он не признанный рыцарь (поскольку утверждение о том, что лжец — не признанный рыцарь, истинно). Следовательно, островитянин, высказавший это утверждение, должен быть рыцарем. Поскольку он рыцарь, то высказываемые им утверждения истинны, поэтому он не признанный рыцарь. Значит, островитянин, высказавший это утверждение — рыцарь, но не признанный рыцарь.

По условию E2 все отъявленные лжецы состоят членами одного клуба. Следовательно (по условию G), существует по крайней мере один островитянин, утверждающий, что он отъявленный лжец (он утверждает, что состоит членом клуба отъявленных лжецов). Этот островитянин не может быть рыцарем (так как рыцарь не мог бы утверждать, что он лжец). Значит, он лжец. Следовательно, его утверждение ложно, поэтому он не отъявленный лжец. Значит, он лжец, но не отъявленный лжец.

Решение задачи 264 б. Если бы все лжецы состояли членами одного клуба, то по крайней мере один островитянин утверждал бы, что он лжец. Но ни рыцарь, ни лжец не могли бы высказать такое утверждение. Следовательно, все лжецы не состоят в одном клубе. Если бы все рыцари состояли членами одного клуба, то (по условию C) все лжецы также состояли бы членами одного клуба, что, как мы доказали, невозможно. Следовательно, все рыцари также не состоят членами одного клуба.

Примечания:

1. Задача 264 б дает еще одно решение задачи 264 а. Хотя оно и неконструктивно, но тем не менее несколько проще предыдущего. Если бы каждый рыцарь был признанным, то множество всех рыцарей совпадало бы с множеством признанных рыцарей, что невозможно, так как (по условию E1) все признанные рыцари состоят в одном клубе, а все рыцари (как показано в решении задачи 264 6) не состоят в одном клубе. Таким образом, предположение о том, что все рыцари признанные, приводит к противоречию. Следовательно, должен существовать по крайней мере один непризнанный рыцарь. Аналогично если бы. все лжецы были отъявленными, то множество отъявленных лжецов совпадало бы с множеством всех лжецов, что невозможно, так как все отъявленные лжецы состоят членами одного клуба, в то время как все лжецы не состоят членами одного клуба. В отличие от только что приведенного доказательства наше первое доказательство позволяет установить дополнительные подробности: всякий; кто утверждает, что он непризнанный рыцарь, должен быть непризнанным рыцарем, а всякий, кто утверждает, что он отъявленный лжец, должен быть неотъявленным лжецом.

2. Доказывая, что все лжецы не состоят членами одного клуба, мы использовали только условие G. Условия E1, E2 и C нам не понадобились. Значит, из одного лишь условия G следует, что все лжецы не состоят членами одного клуба. Более того, условие G эквивалентно утверждению, что все лжецы не состоят членами одного клуба. Действительно, будем считать известным, что все лжецы не состоят членами одного клуба. Тогда условие G можно вывести следующим образом:

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