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