А: В – отъявленный лжец,
В: А – не отъявленный лжец.
Отсюда мы заключаем, что если В – лжец, то он не отъявленный лжец, а если В – рыцарь, то А – не отъявленный лжец (доказательство этого утверждения мы также предоставляем читателю). Итак, в любом случае либо А, либо В – не отъявленный лжец, но мы не знаем, кто именно. (По существу эта задача ничем не отличается от задачи 135 о двух шкатулках, изготовленных Беллини и Челлини.)
Однажды мне удалось открыть еще один дважды гёделев остров S1, который показался мне еще более интересным, чем остров S. Для острова S1 выполнены оба условия E1, Е2, но неизвестно, выполняется ли условие С. (Напомним, что, согласно этому условию, все островитяне, не являющиеся членами клуба С, являются членами одного клуба.)
По-видимому, невозможно доказать, что на острове S1 непременно есть непризнанный рыцарь или что на том же острове есть неотъявленный лжец. Невозможно, по-видимому, доказать также, что все рыцари не являются членами одного клуба или что все лжецы не являются членами одного клуба. Но следующие утверждения доказать можно:
а) На острове S1 найдется либо непризнанный рыцарь, либо неотъявленный лжец.
б) Не может быть, чтобы все рыцари являлись членами одного клуба и все лжецы являлись членами одного клуба.
Решение. Докажем сначала утверждение (б). Предположим, что все рыцари являются членами одного клуба и все лжецы являются членами одного клуба. Тогда найдутся островитяне А, В, о которых известно следующее: А утверждает, что В – лжец, а В утверждает, что А – рыцарь. Но это, как мы уже знаем, невозможно (см. предыдущую задачу или задачу 259 в предыдущей главе). Итак, невозможно, чтобы все рыцари являлись членами одного клуба и все лжецы также являлись членами одного клуба. Значит, либо все рыцари не являются членами одного клуба, либо все лжецы не являются членами одного клуба. Если все рыцари не являются членами одного клуба, то непременно найдется по крайней мере один непризнанный рыцарь (поскольку все признанные рыцари являются членами одного клуба). Если все лжецы не являются членами одного клуба, то непременно найдется по крайней мере один неотъявленный лжец. Но какой именно случай представится на острове, мы не знаем. Итак, утверждение (а) доказано.
Альтернативное (и более интересное) доказательство того, что непременно найдется непризнанный рыцарь или неотъявленный лжец, состоит в следующем.
Так как признанные рыцари состоят в одном клубе и отъявленные лжецы состоят в одном клубе, то найдутся островитяне А, В, высказывающие следующие утверждения:
А: В – отъявленный лжец.
В: А – признанный рыцарь.
Предположим, что А – рыцарь. Тогда его утверждение истинно. Значит, В – отъявленный лжец, поэтому его утверждение ложно. Следовательно, А – непризнанный рыцарь. Значит, А – не признанный рыцарь. Если же А – лжец, то высказанное В утверждение ложно, поэтому В – лжец. Высказанное А утверждение также ложно, поэтому В – неотъявленный лжец. Следовательно, В – отъявленный лжец.
Итак, либо А – не признанный рыцарь, либо В – не отъявленный лжец (но мы опять не знаем, какая из двух альтернатив истинна).
Эта задача очень напоминает одну из задач о парах шкатулок (задачу 136 из гл. 9), в которой одна из двух шкатулок (какая именно – неизвестно) изготовлена либо Беллини, либо Челлини (но кем именно – опять-таки неизвестно).
Я придумал несколько задач о гёделевых и дважды гёделевых островах, но решить их так и не собрался. Думаю, что читателю будет приятно испробовать свои силы на работе, сулящей неожиданности и, быть может, даже открытия.
Я уже говорил о том, что, насколько мне известно, ни одно из условий G, CG не следует из другого. Удастся ли вам доказать (или опровергнуть, что я считаю маловероятным) мою гипотезу? Для этого вам необходимо «построить» остров, для которого выполняется условие G, но не выполняется условие CG, а также остров, для которого выполняется условие CG, но не выполняется условие G. Построить остров означает в данном случае указать, кем он населен, кто из его обитателей рыцари и кто лжецы, какие обитатели являются и какие не являются членами одного клуба. (Кто из рыцарей обладает правом называться признанным рыцарем и кого из лжецов следует называть отъявленными лжецами, для решения этой задачи значения не имеет.)
Можете ли вы доказать (или опровергнуть) мою гипотезу о том, что на острове S1 не обязательно должны быть непризнанные рыцари и неотъявленные лжецы (хотя непременно должны быть рыцари и лжецы)? Иначе говоря, можете ли вы построить остров, удовлетворяющий условиям Е1, Е2 и CG, на котором есть рыцари, но нет непризнанных рыцарей? Можете ли вы построить остров, на котором есть лжецы, но нет неотъявленных лжецов? (На этот раз при построении островов необходимо указать не только кто из его обитателей называется рыцарем или лжецом и состоит в том или ином клубе, но и указать, каких рыцарей следует считать признанными и каких лжецов – отъявленными.)
Предположим, что все острова, о которых говорится в предыдущих задачах, допускают построение (интуитивно я убежден в том, что построить эти острова можно, хотя и не могу этого доказать). Какова минимальная численность населения каждого острова? Можете ли вы доказать, что при меньшей численности населения какое-то из условий будет нарушено?
У одного логика хранится «Книга высказываний». Страницы книги перенумерованы последовательными натуральными числами, и на каждой странице записано ровно одно высказывание. Ни одно высказывание не занимает более одной страницы. Номер страницы, на которой записано высказывание X, назовем номером высказывания X.
Разумеется, каждое высказывание, внесенное в «Книгу высказываний», либо истинно, либо ложно. Некоторые из истинных высказываний настолько очевидны логику, у которого хранится книга, что он принял их за аксиомы своей логической системы. Помимо аксиом, в эту систему входят правила вывода, позволяющие доказывать истинные высказывания, сводя их к ранее доказанным истинным высказываниям и аксиомам, и опровергать ложные высказывания. Логик совершенно уверен в своей непротиворечивости (то есть в том, что всякое высказывание, доказуемое в его системе, действительно истинно, а каждое высказывание, опровергаемое в его системе, действительно ложно), но сомневается в ее полноте (то есть в том, что в системе все истинные высказывания доказуемы, а все ложные опровержимы). Все ли истинные высказывания доказуемы в его системе? Все ли ложные высказывания опровержимы в его системе? На эти вопросы логик хотел бы получить ответ.
У нашего логика помимо «Книги высказываний» есть еще «Книга множеств». Ее страницы также перенумерованы последовательными натуральными числами, и на каждой странице приведено описание некоторого множества чисел. (Под числами мы понимаем здесь целые положительные, или натуральные, числа 1, 2, …, n, …). Любое множество, внесенное в «Книгу множеств», мы будем называть учтенным множеством.
Если задано натуральное число n, то может случиться, что множество, записанное на n-й странице «Книги множеств», содержит число n. В этом случае мы будем называть n экстраординарным числом. Кроме того, назовем число h сопряженным с числом n, если в высказывании, записанном на n-й странице «Книги высказываний», утверждается, что n – экстраординарное число.
Известно, что выполняются следующие четыре условия:
Е1: Множество номеров всех доказуемых высказываний – учтенное множество.
Е2: Множество номеров всех опровержимых высказываний – учтенное множество.
С: Для любого учтенного множества А множество ~А, состоящее из всех чисел, которые не принадлежат множеству А, – учтенное множество.
Н: Для любого учтенного множества А существует другое учтенное множество В, такое, что каждое число из В имеет сопряженное, принадлежащее А, и каждое число, не принадлежащее В, имеет сопряженное, не принадлежащее А.
Этих четырех условий достаточно, чтобы ответить на вопросы логика: «Каждое ли истинное высказывание доказуемо в его системе? Каждое ли ложное высказывание опровержимо в его системе?» Кроме того, можно определить, является ли множество номеров всех истинных высказываний учтенным множеством, а также является ли учтенным множеством множество номеров всех ложных высказываний.
Как это сделать?
Решение. Перед вами не что иное, как гёделев остров из раздела А, но в ином «одеянии». Номера истинных высказываний играют роль рыцарей, номерам ложных высказываний отведена роль лжецов, доказуемые высказывания соответствуют признанным рыцарям, опровержимые – отъявленным лжецам. Учтенные роли заменяют собой клубы. Понятие множества, записанного на странице с заданным номером, играет роль клуба, названного по имени одного из обитателей острова. Экстраординарные числа – это не что иное, как номинабельные члены общины, а сопряженные числа являются аналогами друзей.
Чтобы решить задачу, прежде всего необходимо доказать аналог условия G.
Условие G. Для любого учтенного множества А найдется высказывание, истинное в том и только в том случае, если его номер принадлежит А.
Чтобы доказать условие G, выберем любое учтенное множество А. Пусть В – множество, заданное условием Н, n – номер страницы, на котором записано В в «Книге множеств». По условию Н если число n принадлежит В, то у него имеется сопряженное число h, принадлежащее множеству А, а если n не принадлежит В, то у него есть сопряженное число h, не принадлежащее А. Мы утверждаем, что высказывание X на h-й странице и есть то самое