263. Задача об учтенных множествах.
Перед вами та же задача в новом одеянии. Некоторые из вводимых здесь понятий понадобятся нам в следующей главе.
У одного математика хранится «Книга множеств». На каждой ее странице дается описание какого-нибудь множества чисел (под множеством чисел мы понимаем подмножество множества целых положительных чисел 1, 2, 3…, n…). Любое множество, описанное на какой-нибудь странице книги, называется учтенным множеством. Страницы книги перенумерованы по порядку целыми положительными числами. Назовите множество, описания которого нет ни на одной странице «Книги множеств».
Решение. Пусть n — любое целое положительное число. Назовем n экстраординарным числом, если n принадлежит множеству, описанному на n-й странице, и ординарным, если не принадлежит множеству, описанному на n-й странице.
Множество ординарных чисел не может быть описано ни на одной странице «Книги множеств». Действительно, если бы оно было перечислено на k-й странице, то число k не могло бы быть ни экстраординарным, ни ординарным, так как и в том и в другом случае мы пришли бы к противоречию.
XVI. Открытие Гёделя
А. Гёделевы острова
Задачи этого раздела представляют собой адаптированные варианты знаменитого принципа, открытого Куртом Гёделем, работу которого по математической логике мы рассмотрим в конце главы.
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.
265. Гёделевы острова в общем и целом.
Рассмотрим теперь любой остров, населенный рыцарями и лжецами, на котором имеются клубы. Предполагается, что, кроме рыцарей и лжецов, на острове нет других обитателей. Назовем остров гёделевым, если выполняется условие G, то есть если для любого клуба C найдется по крайней мере один островитянин, утверждающий, что состоит членом этого клуба.
Как-то раз инспектор Крэг посетил такой остров, населенный рыцарями и лжецами, состоящими членами клубов. Крэгу (человеку с необычайно широким кругом интересов, теоретические познания которого не уступают его практической сметке) захотелось узнать, находится ли он на гёделевом острове. Ему удалось собрать следующие сведения. Каждый клуб носит имя одного из островитян, и у каждого островитянина есть клуб, названный его именем. Островитянин не обязательно состоит членом клуба, носящего его имя. Островитянина, который состоит членом клуба, названного в его честь, называют номинабельным. Островитянина, который не состоит членом клуба, названного его именем, называют неноминабельным. Об островитянине X говорят, что он друг островитянина Y, если X подтверждает номинабельность островитянина Y.
Крэг не знал, находится ли он на гёделевом острове до тех пор, пока не обнаружил, что культурная жизнь на острове удовлетворяет некоторому условию, которое мы назовем условием H.
H: Для любого клуба C существует другой клуб D, такой, что у каждого члена клуба D по крайней мере один друг состоит членом клуба C, а у каждого не члена клуба D по крайней мере один друг не состоит членом клуба C.
Из условия H Крэг вывел заключение относительно того, гёделев ли тот остров, на котором он находился. К какому заключению пришел инспектор Крэг?
Решение. Остров гёделев. Выберем любой клуб C. Пусть D — клуб, заданный условием H. Клуб D носит имя какого-нибудь островитянина, например островитянина по имени Джон. Сам Джон либо состоит, либо не состоит членом клуба D. Предположим, что Джон состоит членом клуба D. Тогда у него есть друг (назовем его Джек) в клубе C, который подтверждает, что Джон номинабелен. Поскольку Джон состоит членом клуба D, то Джон действительно номинабелен. Значит, Джек рыцарь. Следовательно, Джек рыцарь и состоит членом клуба C, поэтому Джек утверждает, что состоит членом клуба C.
Предположим, что Джон не состоит членом клуба D. Тогда у Джона есть друг (назовем его Джим), не состоящий членом клуба C и подтверждающий, что Джон номинабелен. Поскольку Джон не состоит членом клуба D, то Джон в действительности неноминабелен. Значит, Джим лжец. Итак, Джим лжец и не состоит членом клуба C, поэтому Джим солгал бы и утверждал бы, что состоит членом клуба C.
Следовательно, независимо от того, состоит или не состоит Джон членом клуба D, существует островитянин, утверждающий, что он состоит членом клуба C.
Примечание. Объединяя решения задач 264 и 265, можно утверждать, что на любом острове, удовлетворяющем условиям E1, E2, C и H, заведомо найдется непризнанный рыцарь и неотъявленный лжец. Этот результат в действительности представляет собой «замаскированную» форму знаменитой теоремы Гёделя о неполноте, к которой мы еще вернемся в разделе В этой главы.
Если вы хотите предложить одному из ваших друзей действительно трудную задачу, задайте ему задачу 264 для острова, удовлетворяющего условиям E1, E2, C и H, (об условии G пока умолчите). Выведет ли ваш приятель самостоятельно условие G?
Б. Дважды гёделевы острова
Задачи этого раздела представляют более специальный интерес, и ознакомление с ними можно отложить до прочтения раздела B.
Под дважды гёделевыми островами мы будем понимать острова рыцарей и лжецов, объединенные в клубы, удовлетворяющие условию CG.
CG: для любых двух клубов C1, C2 найдутся островитяне A, B, о которых известно следующее: A утверждает, что B состоит членом клуба C1, а B утверждает, что A состоит членом клуба C2.
Насколько мне известно, из условия CG не следует условие G, а из условия G не следует условие CG. Оба условия выглядят совершенно независимыми, поэтому (насколько мне известно) дважды гёделевы острова не обязательно должны быть гёделевыми островами.
Изучение дважды гёделевых островов — мой «конек».
Задачи, связанные с ними, имеют такое же отношение к парадоксу Журдэна с двусторонней карточкой (см. задачу 254 в предыдущей главе), какое задачи о гёделевых островах имеют к парадоксу лжецов.
266. Дважды гёделев остров S.
Однажды мне посчастливилось открыть дважды гёделев остров S, для которого выполняются условия E1, E2 и C острова G.
а) Можно ли определить, найдется ли на острове S хоть один непризнанный рыцарь? Что можно сказать о неотъявленном лжеце?
б) Можно ли установить, состоят ли рыцари острова S членами одного клуба? A лжецы?
Решение. Начнем со второй части задачи. Если все рыцари острова состоят членами одного клуба, то (по условию C) все лжецы также состоят членами одного клуба, а если все лжецы острова S состоят членами одного клуба, то (в силу того же условия C) рыцари также состоят членами одного клуба. Следовательно, если представители одной из двух групп населения острова (либо рыцари, либо лжецы) состоят членами одного клуба, то представители каждой из двух групп состоят членами одного клуба. Итак, предположим, что все рыцари состоят членами одного клуба и что все лжецы состоят членами одного клуба. Тогда по условию CG должны найтись островитяне A, B, высказывающие следующие утверждения:
A: B — лжец.
B: A — рыцарь.
Как показано в решении задачи 259 в предыдущей главе, это невозможно. Следовательно, все рыцари не могут состоять членами одного клуба, и все лжецы не могут состоять членами одного клуба.
Что касается первой половины задачи, то ее можно решить двумя способами. Первый из них проще того способа, которым мы только что решили вторую часть задачи, зато второй способ более поучительный.
Первый способ. Так как все рыцари не состоят членами одного клуба, а все признанные рыцари состоят членами одного клуба, то множество всех рыцарей не совпадает с множеством всех признанных рыцарей. Следовательно, не все рыцари признанные. Аналогично не все лжецы отъявленные.
Второй способ. Так как все признанные рыцари состоят членами одного клуба, то все островитяне, не принадлежащие к числу признанных рыцарей, также состоят членами одного; клуба. Если эти клубы выбрать в качестве клубов C1, C2, то (по условию CG) найдутся островитяне A, B, высказывающие следующие утверждения:
A: B — признанный рыцарь.
B: A — не признанный рыцарь.
Предоставляем читателю самостоятельно убедиться в том, что по крайней мере один из островитян A, B должен быть признанным рыцарем (точнее говоря, требуется доказать, что если A — рыцарь, то он не признанный рыцарь, а если A — лжец, то B должен быть не признанным рыцарем. Установить, кто из островитян A, B не признанный рыцарь, мы не можем, хотя и знаем, что кто-то из них не признанный рыцарь.[11]
Аналогичным образом, так как все отъявленные лжецы состоят членами одного клуба, то все островитяне, не принадлежащие множеству отъявленных лжецов, также состоят членами одного клуба. Следовательно (по условию CG), непременно найдутся островитяне A, B, высказывающие следующие утверждения:
A: B — отъявленный лжец,
B: A — не отъявленный лжец.
Отсюда мы заключаем, что если B — лжец, то он не отъявленный лжец, а если B — рыцарь, то A — не отъявленный лжец (доказательство этого утверждения мы также предоставляем читателю). Итак, в любом случае либо A, либо B — не отъявленный лжец, но мы не знаем, кто именно. (По существу эта задача ничем не отличается от задачи 135 о двух шкатулках, изготовленных Беллини и Челлини.)
267. Остров S1.
Однажды мне удалось открыть еще один дважды гёделев остров S1, который показался мне еще более интересным, чем остров S. Для острова S1 выполнены оба условия E1, E2, но не известно, выполняется ли условие C. (Напомним, что, согласно этому условию, все островитяне, не состоящие членами клуба C, состоят членами одного клуба.) По-видимому, невозможно доказать, что на острове S1 непременно есть не признанный рыцарь или что на том же острове есть не отъявленный лжец. Невозможно, по-видимому, доказать также, что все рыцари не состоят членами одного клуба или что все лжецы не состоят членами одного клуба. Но следующие утверждения доказать можно:
а) На острове S1 найдется либо не признанный рыцарь, либо не отъявленный лжец.
б) Не может быть, чтобы все рыцари состояли членами одного клуба и все лжецы состояли членами одного клуба.
Решение. Докажем сначала утверждение (б). Предположим, что все рыцари состоят членами одного клуба и все лжецы состоят членами одного клуба. Тогда найдутся островитяне A, B, о которых известно следующее: A утверждает, что B — лжец, а B утверждает, что A — рыцарь. Но это, как мы уже знаем, невозможно (см. предыдущую задачу или задачу 259 в предыдущей главе). Итак, невозможно, чтобы все рыцари состояли членами одного клуба и все лжецы также состояли членами одного клуба. Значит, либо все рыцари не состоят членами одного клуба, либо все лжецы не состоят членами одного клуба. Если все рыцари не состоят членами одного клуба, то непременно найдется по крайней мере один не признанный рыцарь (поскольку все признанные рыцари состоят членами одного клуба). Если все лжецы не состоят членами одного клуба, то непременно найдется по крайней мере один не отъявленный лжец. Но какой именно случай представится на острове, мы не знаем. Итак, утверждение (а) доказано.
Альтернативное (и более интересное) доказательство того, что непременно найдется не признанный рыцарь или не отъявленный лжец, состоит в следующем. Так как признанные рыцари состоят в одном клубе и отъявленные лжецы состоят в одном клубе, то найдутся островитяне A, B, высказывающие следующие утверждения:
A: B — отъявленный лжец.
B: A — признанный рыцарь.
Предположим, что A — рыцарь. Тогда его утверждение истинно. Значит, B — отъявленный лжец, поэтому его утверждение ложно. Следовательно, A — не признанный рыцарь. Значит, A — не признанный рыцарь. Если же A — лжец, то высказанное B утверждение ложно, поэтому B — лжец. Высказанное A утверждение также ложно, поэтому B — не отъявленный лжец. Следовательно, B — не отъявленный лжец.
Итак, либо A — не признанный рыцарь, либо B — не отъявленный лжец (но мы опять не знаем, какая из двух альтернатив истинна).
Эта задача очень напоминает одну из задач о парах шкатулок (задачу 136 из гл. 9), в которой одна из двух шкатулок (какая именно — неизвестно) изготовлена либо Беллини, либо Челлини (но кем именно — опять-таки неизвестно).