Алиса в стране смекалки - Смаллиан Р.М.
Скачать (прямая ссылка):
Решение. Неудачи связаны с принципиальной неосуществимостью намерений регистратора. Этот замечательный математический факт был открыт математиком Георгом Кантором. Предположим, что регистратору удалось присвоить всем клубам имена обитателей Вселенной с
Ше:Шу4 _5иблиотека_КОЛХОЗ/Ыхо3^зс05/М_МАТНЕМ/МРОР_РОР/15.5МтШт (11 о? 13)19.01.2004 16:56:33
"Как же называется эта книга?" - 15
соблюдением всех правил (никакие два клуба не названы именем одного и того же обитателя Вселенной, и у каждого обитателя есть клуб, названный его именем). Назовем обитателя Вселенной неноминабельным, если он не состоит членом клуба, названного в его честь. Все неноминабильные обитатели Вселенной образуют хорошо определенное множество, а мы знаем, что члены каждого множества обитателей Вселенной состоят в своем особом клубе. Следовательно, должен существовать клуб неноминабельных обитателей Вселенной, что невозможно по причинам, изложенным в задаче 260 (этот клуб должен быть назван в честь одного из обитателей Вселенной, который не может быть ни номинабельным, ни неноминабельным, так как и то и другое приводит к противоречию).
263. Задача об учтенных множествах.
Перед вами та же задача в новом одеянии. Некоторые из вводимых здесь понятий понадобятся нам в следующей главе.
У одного математика хранится "Книга множеств". На каждой ее странице дается описание какого-нибудь множества чисел (под множеством чисел мы понимаем подмножество множества целых положительных чисел 1, 2, 3,..., п,...). Любое множество, описанное на какой-нибудь странице книги, называется учтенным множеством. Страницы книги перенумерованы по порядку целыми положительными числами. Назовите множество, описания которого нет ни на одной странице "Книги множеств".
Решение. Пусть п - любое целое положительное число.
Назовем п экстраординарным числом, если п принадлежит множеству, описанному на п-й странице, и ординарным, если не принадлежит множеству, описанному на п-й странице.
Множество ординарных чисел не может быть описано ни на одной странице "Книги множеств". Действительно, если бы оно было перечислено на к-й странице, то число к не могло бы быть ни экстраординарным, ни ординарным, так как и в том и в другом случае мы пришли бы к противоречию.
Наверх
Ше:Шу4 _Ьиблиотека_КОЛХОЗ/коІхо3^І5с05/М_МАТНЕМ/МРОР_РОР/15.5ІіїтІМт (12оБ 13)19.01.2004 16:56:33
"Какже называется эта книга?" -15
Спонсирование и хостинг проекта осуществляет компания "Зенон Н.С.П."
Ше:Шу4 _Библиотека_КОЛХОЗ/Ыхо3^с05/М_МАТНЕМ/МРОР_РОР/15.зМтШт (13оБ 13)19.01.2004 16:56:33
"Как же называется эта книга?" - 16
Рэймонд Смаллиан "Как же называется
эта книга?" - 16
Открытие Гёделя
А. - Геделевы острова
Задачи этого раздела представляют собой адаптированные варианты знаменитого принципа, открытого Куртом Гёделем, работу которого по математической логике мы рассмотрим в конце главы.
264. Остров G.
Население острова G составляют лишь рыцари, всегда говорящие только правду, и лжецы, которые всегда лгут. Кроме того, некоторых рыцарей называют "признанными рыцарями" (они проявили себя чем-то, подтвердив свое рыцарское звание), а некоторых лжецов (подтвердивших свою приверженность ко лжи) - "отъявленными лжецами".
Обитатели острова G состоят членами различных клубов. Каждый островитянин может быть членом нескольких клубов. Любой островитянин X утверждает относительно любого клуба С, что он либо состоит членом клуба С, либо не состоит членом клуба С.
Известно, что выполняются следующие четыре условия:
Е1: Все признанные рыцари состоят членами одного клуба.
Е2: Все отъявленные лжецы состоят членами одного клуба.
С (условие дополнительности; С - от лат. сотр1етеп^т - дополнение). Все островитяне, не состоящие членами любого клуба С, состоят в одном
Ше:Шу4 _Ьиблиотека_КОЛХОЗ/ко1хо3^с05/М_МАТНЕМ/МРОР_РОР/16.511Ш1Мт (1 о? 19)19.01.2004 16:56:35
"Какже называется эта книга?" -16
клубе. (Этот клуб называется дополнением клуба С и обозначается С.)
G (условие гёделевости). Для любого клуба С существует по крайней мере один островитянин, который утверждает, что состоит членом клуба С. (Разумеется, его утверждение о членстве в клубе С может быть ложным, так как островитянин может оказаться лжецом.)
264 а (по Гёделю).
1) Докажите, что на острове G существует по крайней мере один непризнанный рыцарь.
2) Докажите, что на острове существует по крайней мере один неотъявленный лжец.
264 б (по Тарскому).
1) Состоят ли все лжецы острова членами одного клуба?
2) Состоят ли все рыцари острова членами одного клуба?
Решение задачи 264 а.
По условию Е1 все признанные рыцари острова (образующие множество Е) состоят членами одного клуба. Следовательно, по условию С все островитяне, входящие в множество Е непризнанных рыцарей, также состоят членами одного клуба. Но тогда по условию G существует по крайней мере один островитянин, который утверждает, что состоит членом клуба Е (иначе говоря, он утверждает, что принадлежит к множеству непризнанных рыцарей). Лжец не мог бы утверждать, что он не признанный рыцарь (поскольку утверждение о том, что лжец - не признанный рыцарь, истинно). Следовательно, островитянин, высказавший это утверждение, должен быть рыцарем. Поскольку он рыцарь, то высказываемые им утверждения истинны, поэтому он не признанный рыцарь. Значит, островитянин, высказавший это утверждение - рыцарь, но не признанный рыцарь.
