Задачи этого раздела представляют собой адаптированные варианты знаменитого принципа, открытого Куртом Гёделем, работу которого по математической логике мы рассмотрим в конце главы.

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

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

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

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

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

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

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

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

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

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

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

Лжец не мог бы утверждать, что он не признанный рыцарь (поскольку утверждение о том, что лжец – не признанный рыцарь, истинно). Следовательно, островитянин, высказавший это утверждение, должен быть рыцарем. Поскольку он рыцарь, то высказываемые им утверждения истинны, поэтому он непризнанный рыцарь. Значит, островитянин, высказавший это утверждение, – рыцарь, но не признанный рыцарь.

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

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

Примечания. 1. Задача 264б дает еще одно решение задачи 264а. Хотя оно и неконструктивно, но тем не менее несколько проще предыдущего.

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

В отличие от только что приведенного доказательства наше первое доказательство позволяет установить дополнительные подробности: всякий, кто утверждает, что он непризнанный рыцарь, должен быть непризнанным рыцарем, а всякий, кто утверждает, что он отъявленный лжец, должен быть неотъявленным лжецом.

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

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

Рассмотрим теперь любой остров, населенный рыцарями и лжецами, на котором имеются клубы. Предполагается, что, кроме рыцарей и лжецов, на острове нет других обитателей. Назовем остров гёделевым, если выполняется условие G, то есть если для любого клуба С найдется по крайней мере один островитянин, утверждающий, что является членом этого клуба.

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

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

Крэг не знал, находится ли он на гёделевом острове, до тех пор, пока не обнаружил, что культурная жизнь на острове удовлетворяет некоторому условию, которое мы назовем условием Н.

Н: Для любого клуба С существует другой клуб D, такой, что у каждого члена клуба D по крайней мере один друг является членом клуба С, а у каждого не члена клуба D по крайней мере один друг не является членом клуба С.

Из условия Н Крэг вывел заключение относительно того, гёделев ли тот остров, на котором он находился. К какому заключению пришел инспектор Крэг?

Решение. Остров гёделев. Выберем любой клуб С. Пусть D – клуб, заданный условием Н. Клуб D носит имя какого-нибудь островитянина, например островитянина по имени Джон. Сам Джон либо является, либо не является членом клуба D.

Предположим, что Джон является членом клуба D. Тогда у него есть друг (назовем его Джек) в клубе С, который подтверждает, что Джон номинабелен. Поскольку Джон не является членом клуба D, то Джон действительно номинабелен. Значит, Джек рыцарь. Следовательно, Джек рыцарь и является членом клуба С, поэтому Джек утверждает, что является членом клуба С.

Предположим, что Джон не является членом клуба D. Тогда у Джона есть друг (назовем его Джим), не состоящий в клубе С и подтверждающий, что Джон номинабелен. Поскольку Джон не является в клубе D, то Джон в действительности неноминабелен. Значит, Джим лжец. Итак, Джим лжец и не является членом клуба С, поэтому Джим солгал бы и утверждал бы, что является членом клуба С. Следовательно, независимо от того, является или не является Джон членом клуба D, существует островитянин, утверждающий, что он является членом клуба С.

Примечание. Объединяя решения задач 264 и 265, можно утверждать, что на любом острове, удовлетворяющем условиям Е₁, Е₂, С и Н, заведомо найдется непризнанный рыцарь и неотъявленный лжец. Этот результат в действительности представляет собой замаскированную форму знаменитой теоремы Гёделя о неполноте, к которой мы еще вернемся в разделе В этой главы.

Если вы хотите предложить одному из ваших друзей действительно трудную задачу, задайте ему задачу 264 для острова, удовлетворяющего условиям Е₁, Е₂, С и Н (об условии G пока умолчите). Выведет ли ваш приятель самостоятельно условие G?

Задачи этого раздела представляют более специальный интерес, и ознакомление с ними можно отложить до прочтения раздела В.

Под дважды гёделевыми островами мы будем понимать острова рыцарей и лжецов, объединенные в клубы, удовлетворяющие условию CG.

CG: для любых двух клубов С₁, С₂ найдутся островитяне А, В, о которых известно следующее: А утверждает, что В является членом клуба С₁, а В утверждает, что А является членом клуба С₂.

Насколько мне известно, из условия CG не следует условие G, а из условия G не следует условие CG. Оба условия выглядят совершенно независимыми, поэтому (насколько мне известно) дважды гёделевы острова не обязательно должны быть гёделевыми островами.

Изучение дважды гёделевых островов – мой конек. Задачи, связанные с ними, имеют такое же отношение к парадоксу Журдэна с двусторонней карточкой (см. задачу 254 в предыдущей главе), какое задачи о гёделевых островах имеют к парадоксу лжецов.

Однажды мне посчастливилось открыть дважды гёделев остров S, для которого выполняются условия Е₁, Е₂ и С острова G.

а) Можно ли определить, найдется ли на острове S хоть один непризнанный рыцарь? Что можно сказать о неотъявленном лжеце?

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

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

А: В – лжец.

В: А – рыцарь.

Как показано в решении задачи 259 в предыдущей главе, это невозможно. Следовательно, все рыцари не могут являться членами одного клуба, и все лжецы не могут являться членами одного клуба.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Эта задача очень напоминает одну из задач о парах шкатулок (задачу 136 из гл. 9), в которой одна из двух шкатулок (какая именно – неизвестно) изготовлена либо Беллини, либо Челлини (но кем именно – опять-таки неизвестно).

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

Я уже говорил о том, что, насколько мне известно, ни одно из условий G, CG не следует из другого. Удастся ли вам доказать (или опровергнуть, что я считаю маловероятным) мою гипотезу? Для этого вам необходимо «построить» остров, для которого выполняется условие G, но не выполняется условие CG, а также остров, для которого выполняется условие CG, но не выполняется условие G. Построить остров означает в данном случае указать, кем он населен, кто из его обитателей рыцари и кто лжецы, какие обитатели являются и какие не являются членами одного клуба. (Кто из рыцарей обладает правом называться признанным рыцарем и кого из лжецов следует называть отъявленными лжецами, для решения этой задачи значения не имеет.)

Можете ли вы доказать (или опровергнуть) мою гипотезу о том, что на острове S¹ не обязательно должны быть непризнанные рыцари и неотъявленные лжецы (хотя непременно должны быть рыцари и лжецы)? Иначе говоря, можете ли вы построить остров, удовлетворяющий условиям Е₁, Е₂ и CG, на котором есть рыцари, но нет непризнанных рыцарей? Можете ли вы построить остров, на котором есть лжецы, но нет неотъявленных лжецов? (На этот раз при построении островов необходимо указать не только кто из его обитателей называется рыцарем или лжецом и состоит в том или ином клубе, но и указать, каких рыцарей следует считать признанными и каких лжецов – отъявленными.)

Предположим, что все острова, о которых говорится в предыдущих задачах, допускают построение (интуитивно я убежден в том, что построить эти острова можно, хотя и не могу этого доказать). Какова минимальная численность населения каждого острова? Можете ли вы доказать, что при меньшей численности населения какое-то из условий будет нарушено?

У одного логика хранится «Книга высказываний». Страницы книги перенумерованы последовательными натуральными числами, и на каждой странице записано ровно одно высказывание. Ни одно высказывание не занимает более одной страницы. Номер страницы, на которой записано высказывание X, назовем номером высказывания X.

Разумеется, каждое высказывание, внесенное в «Книгу высказываний», либо истинно, либо ложно. Некоторые из истинных высказываний настолько очевидны логику, у которого хранится книга, что он принял их за аксиомы своей логической системы. Помимо аксиом, в эту систему входят правила вывода, позволяющие доказывать истинные высказывания, сводя их к ранее доказанным истинным высказываниям и аксиомам, и опровергать ложные высказывания. Логик совершенно уверен в своей непротиворечивости (то есть в том, что всякое высказывание, доказуемое в его системе, действительно истинно, а каждое высказывание, опровергаемое в его системе, действительно ложно), но сомневается в ее полноте (то есть в том, что в системе все истинные высказывания доказуемы, а все ложные опровержимы). Все ли истинные высказывания доказуемы в его системе? Все ли ложные высказывания опровержимы в его системе? На эти вопросы логик хотел бы получить ответ.

У нашего логика помимо «Книги высказываний» есть еще «Книга множеств». Ее страницы также перенумерованы последовательными натуральными числами, и на каждой странице приведено описание некоторого множества чисел. (Под числами мы понимаем здесь целые положительные, или натуральные, числа 1, 2, …, n, …). Любое множество, внесенное в «Книгу множеств», мы будем называть учтенным множеством.

Если задано натуральное число n, то может случиться, что множество, записанное на n-й странице «Книги множеств», содержит число n. В этом случае мы будем называть n экстраординарным числом. Кроме того, назовем число h сопряженным с числом n, если в высказывании, записанном на n-й странице «Книги высказываний», утверждается, что n – экстраординарное число.

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

Е₁: Множество номеров всех доказуемых высказываний – учтенное множество.

Е₂: Множество номеров всех опровержимых высказываний – учтенное множество.

С: Для любого учтенного множества А множество ^~А, состоящее из всех чисел, которые не принадлежат множеству А, – учтенное множество.

Н: Для любого учтенного множества А существует другое учтенное множество В, такое, что каждое число из В имеет сопряженное, принадлежащее А, и каждое число, не принадлежащее В, имеет сопряженное, не принадлежащее А.

Этих четырех условий достаточно, чтобы ответить на вопросы логика: «Каждое ли истинное высказывание доказуемо в его системе? Каждое ли ложное высказывание опровержимо в его системе?» Кроме того, можно определить, является ли множество номеров всех истинных высказываний учтенным множеством, а также является ли учтенным множеством множество номеров всех ложных высказываний.

Как это сделать?

Решение. Перед вами не что иное, как гёделев остров из раздела А, но в ином «одеянии». Номера истинных высказываний играют роль рыцарей, номерам ложных высказываний отведена роль лжецов, доказуемые высказывания соответствуют признанным рыцарям, опровержимые – отъявленным лжецам. Учтенные роли заменяют собой клубы. Понятие множества, записанного на странице с заданным номером, играет роль клуба, названного по имени одного из обитателей острова. Экстраординарные числа – это не что иное, как номинабельные члены общины, а сопряженные числа являются аналогами друзей.

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

Условие G. Для любого учтенного множества А найдется высказывание, истинное в том и только в том случае, если его номер принадлежит А.

Чтобы доказать условие G, выберем любое учтенное множество А. Пусть В – множество, заданное условием Н, n – номер страницы, на котором записано В в «Книге множеств». По условию Н если число n принадлежит В, то у него имеется сопряженное число h, принадлежащее множеству А, а если n не принадлежит В, то у него есть сопряженное число h, не принадлежащее А. Мы утверждаем, что высказывание X на h-й странице и есть то самое высказывание, которое требуется найти.

Высказывание X утверждает, что n – экстраординарное число, то есть что n принадлежит множеству В (так как множество В занесено на n-ю страницу «Книги множеств»). Если X истинно, то число n действительно принадлежит множеству В. Следовательно, h принадлежит А. Итак, если X истинно, то его номер (число h) принадлежит множеству А. Предположим теперь, что X ложно. Тогда число n не принадлежит В. Следовательно, сопряженное число h не принадлежит А. Итак, X истинно в том и только в том случае, если его номер принадлежит множеству А.

После того как условие G доказано, ответить на вопросы логика уже нетрудно. Дано, что множество номеров А всех доказуемых высказываний – учтенное множество. Следовательно, по условию С множество ^~А всех чисел, не совпадающих с номерами доказуемых высказываний, также учтенное множество. Значит (по условию G), существует высказывание X, которое истинно в том и только в том случае, если его номер принадлежит множеству ^~А. Но если номер высказывания X принадлежит множеству ^~А, то он не принадлежит множеству А, то есть высказывание X недоказуемо (так как множество А состоит из номеров доказуемых высказываний). Итак, X истинно в том и только в том случае, если X недоказуемо. Это означает, что либо X истинно и недоказуемо, либо X ложно и доказуемо. По условиям задачи ни одно ложное высказывание не доказуемо в системе. Следовательно, X должно быть истинным и недоказуемым в системе.

Построим теперь ложное высказывание, которое неопровержимо в системе. Пусть А – множество всех опровержимых высказываний. Воспользовавшись условием G, мы получим высказывание Y, истинное в том и только в том случае, если его номер совпадает с номером какого-нибудь опровержимого высказывания, то есть Y истинно в том и только в том случае, если Y опровержимо. Это означает, что Y либо истинно и опровержимо, либо ложно и неопровержимо. Первая альтернатива отпадает, так как опровержимое высказывание не может быть истинным. Следовательно, Y должно быть ложным, но неопровержимым в системе.

Перейдем теперь к остальным вопросам логики. Если бы множество номеров всех ложных высказываний было учтенным множеством, то существовало бы высказывание Z, которое было бы истинным в том и только в том случае, если бы его номер совпадал с номером какого-нибудь ложного высказывания. Иначе говоря, Z было бы истинным в том и только в том случае, если Z ложно, что невозможно. (Z напоминало бы высказывание «это высказывание ложно».) Следовательно, множество номеров всех ложных высказываний – неучтенное множество. Из условия С следует, что множество номеров истинных высказываний также не является учтенным множеством.

Предыдущая задача представляет собой не что иное, как упрощенный вариант знаменитой теоремы Гёделя о полноте.

В 1931 г. Курт Гёдель совершил поразительное открытие. Он установил, что математическую истину в некотором смысле нельзя формализовать полностью. Гёдель доказал, что в математической системе, принадлежащей широкому классу систем, всегда найдется утверждение, недоказуемое (то есть невыводимое из аксиом системы), несмотря на свою истинность! Следовательно, ни одной аксиоматической системы, сколь бы остроумно она ни была устроена, не достаточно для доказательства всех математических истин. Гёдель впервые доказал свою теорему для системы “Principia Mathematica” Уайтхеда и Расселла, но предложенное им доказательство, как я уже говорил, допускает перенос и на многие другие системы. Во всех этих системах существует вполне определенное множество выражений, называемых предложениями, которые подразделяются на истинные и ложные. Некоторые истинные предложения приняты за аксиомы системы. Точный перечень правил вывода позволяет доказывать (выводить из аксиом) одни предложения и опровергать другие. Помимо предложений система содержит имена различных множеств (целых и положительных) чисел. Любое множество чисел, наделенное в рассматриваемой системе именем, можно назвать именуемым, или определимым, множеством системы (в предыдущей задаче такие множества скрывались под псевдонимом «учтенные множества»). Весьма существенно, что все предложения можно перенумеровать, а все определимые множества перечислить по порядку. Это означает, что математическая система удовлетворяет условиям E₁, Е₂, С и Н нашей задачи. (Номер, присваиваемый каждому предложению, – в задаче мы называли его просто номером – в математической логике известен под названием гёделевого номера предложения.) Доказать, что система удовлетворяет условиям С и Н, очень просто. Доказательство того, что система удовлетворяет условиям E₁ и Е₂, в принципе несложно, но довольно громоздко. Коль скоро доказано, что система удовлетворяет всем четырем условиям, они позволяют построить предложение, которое истинно, но недоказуемо (невыводимо) в данной системе.

Это предложение можно представлять себе как некоторое предложение X, содержащее утверждение о своей недоказуемости. Такое предложение действительно должно быть истинно, но недоказуемо (подобно тому как житель острова G, утверждавший, что он непризнанный рыцарь, действительно был рыцарем, но не был признанным рыцарем).

Возможно, вы спросите: но если известно, что предложение X (содержащее утверждение о своей недоказуемости) истинно, то почему бы не принять его за новую аксиому? Разумеется, мы можем пополнить список аксиом системы еще одной аксиомой, но расширенная система также будет удовлетворять условиям E₁, Е₂, С и Н. Следовательно, в ней найдется другое предложение X1, которое будет истинным, но недоказуемым в расширенной системе. Таким образом, хотя расширенная система позволяет доказать больше истинных предложений, чем старая, тем не менее и в ней доказать все истинные предложения невозможно.

Должен сказать, что мое изложение метода Гёделя отличается от первоначального доказательства теоремы, предложенного самим Гёделем. Основное отличие состоит в том, что я использую понятие истинности, отсутствующее у Гёделя. Действительно, в первоначальном виде теорема Гёделя не содержит утверждения о существовании в системе истинного, но недоказуемого (невыводимого) предложения. В ней говорится нечто иное: при некотором правдоподобном допущении относительно системы в ней непременно существует предложение (и Гёдель демонстрирует такое предложение), которое в рамках системы невозможно ни доказать, ни опровергнуть.

Понятие истинности было строго формализовано логиком Альфредом Тарским. Он доказал, что для математических систем, удовлетворяющих условиям теоремы Гёделя, множество гёделевых номеров истинных предложений неопределимо в системе. Иногда этот результат формулируют так: «Во всякой достаточно мощной системе истинность предложений системы неопределима в рамках самой системы».

Рассмотрим следующий парадокс:

Парадокс состоит в следующем. Если это предложение ложно, то неверно, что оно недоказуемо. Следовательно, оно доказуемо, а это означает, что оно истинно. Итак, предположив, что это предложение ложно, мы пришли к противоречию. Значит, оно должно быть истинно.

А теперь будьте внимательны! Я доказал, что предложение, набранное курсивом, истинно. Но в истинном предложении говорится о том, что есть на самом деле. Значит, оно недоказуемо. Как же мне удалось доказать его?

Где ошибка в приведенных мною рассуждениях? Ошибка в том, что понятие доказуемого предложения не вполне определенно. Одна из основных задач важного раздела современной математики, известного под названием «математической логики», состоит в придании точного значения понятию доказательства. Вполне строгого универсального определения доказательства, применимого к любым математическим системам, пока не существует. В современной математической логике принято говорить о доказуемости в рамках данной системы. Предположим, что у нас имеется система (назовем ее системой S), в которой строго определено, что такое доказуемость в рамках системы S. Предположим также, что система S непротиворечива, то есть что всякое доказуемое в S предложение действительно истинно. Рассмотрим следующее предложение:

Никакого парадокса теперь не возникает, хотя это предложение обладает одним довольно интересным свойством. Дело в том, что оно должно быть истинным, но недоказуемым в системе S. Оно представляет собой грубый аналог предложения X (содержащего утверждение о собственной недоказуемости не вообще, а в рамках системы S), построенного Гёделем в первоначальном варианте доказательства его знаменитой теоремы.

Несколько слов я хотел бы сказать о «дважды гёделевом» условии, которое мы анализировали в разделе Б. Дело в том, что полученный Гёделем результат справедлив не только для гёделевых систем (гёделевой я называю систему, в которой для любого определимого множества А найдется предложение, истинное в том и только в том случае, если его гёделев номер принадлежит А), но и для дважды гёделевых систем (дважды гёделевой я называю систему, в которой для любых определимых множеств А, В найдутся предложения X, Y, такие, что X истинно в том и только в том случае, если гёделев номер предложения Y принадлежит A, a Y истинно в том и только в том случае, если гёделев номер предложения X принадлежит В). Располагая дважды гёделевой системой, мы можем (используя условия E₁, Е₂ и С) построить два предложения X, Y, такие, что X будет содержать утверждение о доказуемости предложения Y (при этом я понимаю, что X истинно в том и только в том случае, если Y доказуемо), a Y будет содержать утверждение о недоказуемости предложения X. Одно из предложений (какое именно – неизвестно) X и Y должно быть истинно, но недоказуемо. Можно поступить иначе и построить два предложения X, Y, такие, что X будет содержать утверждение об опровержимости предложения Y, a Y будет содержать утверждение о неопровержимости предложения X. По крайней мере одно из предложений X, Y (какое именно – неизвестно) должно быть ложно, но неопровержимо. Возможен и еще один вариант. Не используя даже условие С, можно построить два предложения X, Y, такие, что X будет содержать утверждение о доказуемости Y, a Y – о неопровержимости X. Одно из них (какое именно – неизвестно) должно быть либо истинно, но недоказуемо, либо ложно, но неопровержимо (но каким именно набором из этих двух будет обладать предложение – неизвестно).

И последнее, о чем я хочу сказать вам, пока не забыл. Как же называется эта книга? Эта книга так и называется – «Как же называется эта книга?».