2. Доказывая, что все лжецы не являются членами одного клуба, мы использовали только условие G. Условия E1, Е2 и С нам не понадобились. Значит, из одного лишь условия G следует, что все лжецы не являются членами одного клуба. Более того, условие G эквивалентно утверждению, что все лжецы не являются членами одного клуба. Действительно, будем считать известным, что все лжецы не являются членами одного клуба. Тогда условие G можно вывести следующим образом.
Выберем любой клуб С. Так как все лжецы не является членами одного клуба, то С не множество всех лжецов. Следовательно, либо членом клуба С является какой-нибудь рыцарь, либо какой-нибудь лжец не является членом клуба С. Если какой-нибудь рыцарь является членом клуба С, то он заведомо утверждает, что является членом этого клуба (так как он всегда говорит только правду). Если бы какой-нибудь лжец не являлся членом клуба С, то он утверждал бы, что является членом этого клуба (так как он лжет). Следовательно, и в том и в другом случае кто-нибудь утверждает, что является членом клуба С.
265. Гёделевы острова в общем и целом
Рассмотрим теперь любой остров, населенный рыцарями и лжецами, на котором имеются клубы. Предполагается, что, кроме рыцарей и лжецов, на острове нет других обитателей. Назовем остров гёделевым, если выполняется условие G, то есть если для любого клуба С найдется по крайней мере один островитянин, утверждающий, что является членом этого клуба.
Как-то раз инспектор Крэг посетил такой остров, населенный рыцарями и лжецами, являющимися членами клубов. Крэгу (человеку с необычайно широким кругом интересов, теоретические познания которого не уступают его практической сметке) захотелось узнать, находится ли он на гёделевом острове. Ему удалось собрать следующие сведения.
Каждый клуб носит имя одного из островитян, и у каждого островитянина есть клуб, названный его именем. Островитянин не обязательно является членом клуба, носящего его имя. Островитянина, который является членом клуба, названного в его честь, называют номинабельным. Островитянина, который не является членом клуба, названного его именем, называют неноминабельным. Об островитянине X говорят, что он друг островитянина Y, если X подтверждает номинабельность островитянина Y.
Крэг не знал, находится ли он на гёделевом острове, до тех пор, пока не обнаружил, что культурная жизнь на острове удовлетворяет некоторому условию, которое мы назовем условием Н.
Н: Для любого клуба С существует другой клуб D, такой, что у каждого члена клуба D по крайней мере один друг является членом клуба С, а у каждого не члена клуба D по крайней мере один друг не является членом клуба С.
Из условия Н Крэг вывел заключение относительно того, гёделев ли тот остров, на котором он находился. К какому заключению пришел инспектор Крэг?
Решение. Остров гёделев. Выберем любой клуб С. Пусть D – клуб, заданный условием Н. Клуб D носит имя какого-нибудь островитянина, например островитянина по имени Джон. Сам Джон либо является, либо не является членом клуба D.
Предположим, что Джон является членом клуба D. Тогда у него есть друг (назовем его Джек) в клубе С, который подтверждает, что Джон номинабелен. Поскольку Джон не является членом клуба D, то Джон действительно номинабелен. Значит, Джек рыцарь. Следовательно, Джек рыцарь и является членом клуба С, поэтому Джек утверждает, что является членом клуба С.
Предположим, что Джон не является членом клуба D. Тогда у Джона есть друг (назовем его Джим), не состоящий в клубе С и подтверждающий, что Джон номинабелен. Поскольку Джон не является в клубе D, то Джон в действительности неноминабелен. Значит, Джим лжец. Итак, Джим лжец и не является членом клуба С, поэтому Джим солгал бы и утверждал бы, что является членом клуба С. Следовательно, независимо от того, является или не является Джон членом клуба D, существует островитянин, утверждающий, что он является членом клуба С.
Примечание. Объединяя решения задач 264 и 265, можно утверждать, что на любом острове, удовлетворяющем условиям Е1, Е2, С и Н, заведомо найдется непризнанный рыцарь и неотъявленный лжец. Этот результат в действительности представляет собой замаскированную форму знаменитой теоремы Гёделя о неполноте, к которой мы еще вернемся в разделе В этой главы.
Если вы хотите предложить одному из ваших друзей действительно трудную задачу, задайте ему задачу 264 для острова, удовлетворяющего условиям Е1, Е2, С и Н (об условии G пока умолчите). Выведет ли ваш приятель самостоятельно условие G?
Б. ДВАЖДЫ ГЁДЕЛЕВЫ ОСТРОВА
Задачи этого раздела представляют более специальный интерес, и ознакомление с ними можно отложить до прочтения раздела В.
Под дважды гёделевыми островами мы будем понимать острова рыцарей и лжецов, объединенные в клубы, удовлетворяющие условию CG.
CG: для любых двух клубов С1, С2 найдутся островитяне А, В, о которых известно следующее: А утверждает, что В является членом клуба С1, а В утверждает, что А является членом клуба С2.
Насколько мне известно, из условия CG не следует условие G, а из условия G не следует условие CG. Оба условия выглядят совершенно независимыми, поэтому (насколько мне известно) дважды гёделевы острова не обязательно должны быть гёделевыми островами.
Изучение дважды гёделевых островов – мой конек. Задачи, связанные с ними, имеют такое же отношение к парадоксу Журдэна с двусторонней карточкой (см. задачу 254 в предыдущей главе), какое задачи о гёделевых островах имеют к парадоксу лжецов.
266. Дважды гёделев остров S
Однажды мне посчастливилось открыть дважды гёделев остров S, для которого выполняются условия Е1, Е2 и С острова G.
а) Можно ли определить, найдется ли на острове S хоть один непризнанный рыцарь? Что можно сказать о неотъявленном лжеце?
б) Можно ли установить, состоят ли рыцари острова S членами одного клуба? А лжецы?
Решение. Начнем со второй части задачи. Если все рыцари острова являются членами одного клуба, то (по условию С) все лжецы также являются членами одного клуба, а если все лжецы острова S являются членами одного клуба, то (в силу того же условия С) рыцари также являются членами одного клуба. Следовательно, если представители одной из двух групп населения острова (либо рыцари, либо лжецы) являются членами одного клуба, то представители каждой из двух групп являются членами одного клуба. Итак, предположим, что все рыцари являются членами одного клуба и что все лжецы состоят членами одного клуба. Тогда по условию CG должны найтись островитяне А, В, высказывающие следующие утверждения:
А: В – лжец.
В: А – рыцарь.
Как показано в решении задачи 259 в предыдущей главе, это невозможно. Следовательно, все рыцари не могут являться членами одного клуба, и все лжецы не могут являться членами одного клуба.
