Решение. Неудачи связаны с принципиальной неосуществимостью намерений регистратора. Этот замечательный математический факт был открыт математиком Георгом Кантором. Предположим, что регистратору удалось присвоить всем клубам имена обитателей Вселенной с соблюдением всех правил (никакие два клуба не названы именем одного и того же обитателя Вселенной, и у каждого обитателя есть клуб, названный его именем). Назовем обитателя Вселенной неноминабельным, если он не является членом клуба, названного в его честь. Все неноминабельные обитатели Вселенной образуют хорошо определенное множество, а мы знаем, что члены каждого множества обитателей Вселенной состоят в своем особом клубе. Следовательно, должен существовать клуб неноминабельных обитателей Вселенной, что невозможно по причинам, изложенным в задаче 260 (этот клуб должен быть назван в честь одного из обитателей Вселенной, который не может быть ни номинабельным, ни неноминабельным, так как и то и другое приводит к противоречию).
267. Задача об учтенных множествах
Перед вами та же задача в новом одеянии. Некоторые из вводимых здесь понятий понадобятся нам в следующей главе.
У одного математика хранится «Книга множеств». На каждой ее странице дается описание какого-нибудь множества чисел (под множеством чисел мы понимаем подмножество множества целых положительных чисел 1, 2, 3, …, n, …). Любое множество, описанное на какой-нибудь странице книги, называется учтенным множеством. Страницы книги перенумерованы по порядку целыми положительными числами.
Назовите множество, описания которого нет ни на одной странице «Книги множеств».
Решение. Пусть n – любое целое положительное число. Назовем n экстраординарным числом, если n принадлежит множеству, описанному на n-й странице, и ординарным, если не принадлежит множеству, описанному на n-й странице.
Множество ординарных чисел не может быть описано ни на одной странице «Книги множеств». Действительно, если бы оно было перечислено на k-й странице, то число k не могло бы быть ни экстраординарным, ни ординарным, так как и в том и в другом случае мы пришли бы к противоречию.
XVI. Открытие Гёделя
А. ГЁДЕЛЕВЫ ОСТРОВА
Задачи этого раздела представляют собой адаптированные варианты знаменитого принципа, открытого Куртом Гёделем, работу которого по математической логике мы рассмотрим в конце главы.
264. Остров G
Население острова G составляют лишь рыцари, всегда говорящие только правду, и лжецы, которые всегда лгут. Кроме того, некоторых рыцарей называют «признанными рыцарями» (они проявили себя чем-то, подтвердив свое рыцарское звание), а некоторых лжецов (подтвердивших свою приверженность ко лжи) – «отъявленными лжецами». Обитатели острова G являются членами различных клубов. Каждый островитянин может быть членом нескольких клубов. Любой островитянин X утверждает относительно любого клуба С, что он либо является членом клуба С, либо не является членом клуба С.
Известно, что выполняются следующие четыре условия:
E1: Все признанные рыцари являются членами одного клуба.
Е2: Все отъявленные лжецы являются членами одного клуба.
С (условие дополнительности; С – от лат. complementum – дополнение). Все островитяне, не являющиеся членами любого клуба С, состоят в одном клубе. (Этот клуб называется дополнением клуба С и обозначается ~С.)
G (условие гёделевости). Для любого клуба С существует по крайней мере один островитянин, который утверждает, что является членом клуба С. (Разумеется, его утверждение о членстве в клубе С может быть ложным, так как островитянин может оказаться лжецом.)
264а (по Гёделю)
1) Докажите, что на острове G существует по крайней мере один непризнанный рыцарь.
2) Докажите, что на острове существует по крайней мере один неотъявленный лжец.
264б (по Тарскому)
1) Являются ли все лжецы острова G членами одного клуба?
2) Являются ли все рыцари острова членами одного клуба?
Решение задачи 264а. По условию Е1 все признанные рыцари острова (образующие множество Е) являются членами одного клуба. Следовательно, по условию С все островитяне, входящие в множество ∼Е непризнанных рыцарей, также являются членами одного клуба. Но тогда по условию G существует по крайней мере один островитянин, который утверждает, что является членом клуба Е (иначе говоря, он утверждает, что не принадлежит к множеству непризнанных рыцарей).
Лжец не мог бы утверждать, что он не признанный рыцарь (поскольку утверждение о том, что лжец – не признанный рыцарь, истинно). Следовательно, островитянин, высказавший это утверждение, должен быть рыцарем. Поскольку он рыцарь, то высказываемые им утверждения истинны, поэтому он непризнанный рыцарь. Значит, островитянин, высказавший это утверждение, – рыцарь, но не признанный рыцарь.
По условию Е2 все отъявленные лжецы являются членами одного клуба. Следовательно (по условию G), существует по крайней мере один островитянин, утверждающий, что он отъявленный лжец (он утверждает, что является членом клуба отъявленных лжецов). Этот островитянин не может быть рыцарем (так как рыцарь не мог бы утверждать, что он лжец). Значит, он лжец. Следовательно, его утверждение ложно, поэтому он не отъявленный лжец. Значит, он лжец, но не отъявленный лжец.
Решение задачи 264б. Если бы все лжецы являлись членами одного клуба, то по крайней мере один островитянин утверждал бы, что он лжец. Но ни рыцарь, ни лжец не могли бы высказать такое утверждение. Следовательно, все лжецы не являлись в одном клубе. Если бы все рыцари являлись членами одного клуба, то (по условию С) все лжецы также являлись бы членами одного клуба, что, как мы доказали, невозможно. Следовательно, все рыцари также не являются членами одного клуба.
Примечания. 1. Задача 264б дает еще одно решение задачи 264а. Хотя оно и неконструктивно, но тем не менее несколько проще предыдущего.
Если бы каждый рыцарь был признанным, то множество всех рыцарей совпадало бы с множеством признанных рыцарей, что невозможно, так как (по условию Е1) все признанные рыцари состоят в одном клубе, а все рыцари (как показано в решении задачи 264б) не состоят в одном клубе. Таким образом, предположение о том, что все рыцари признанные, приводит к противоречию. Следовательно, должен существовать по крайней мере один непризнанный рыцарь. Аналогично если бы все лжецы были отъявленными, то множество отъявленных лжецов совпадало бы с множеством всех лжецов, что невозможно, так как все отъявленные лжецы являются членами одного клуба, в то время как все лжецы не являются членами одного клуба.
В отличие от только что приведенного доказательства наше первое доказательство позволяет установить дополнительные подробности: всякий, кто утверждает, что он непризнанный рыцарь, должен быть непризнанным рыцарем, а всякий, кто утверждает, что он отъявленный лжец, должен быть неотъявленным лжецом.
