268в
Предположим, что все острова, о которых говорится в предыдущих задачах, допускают построение (интуитивно я убежден в том, что построить эти острова можно, хотя и не могу этого доказать). Какова минимальная численность населения каждого острова? Можете ли вы доказать, что при меньшей численности населения какое-то из условий будет нарушено?
В. ТЕОРЕМА ГЁДЕЛЯ
269. Полна ли эта система?
У одного логика хранится «Книга высказываний». Страницы книги перенумерованы последовательными натуральными числами, и на каждой странице записано ровно одно высказывание. Ни одно высказывание не занимает более одной страницы. Номер страницы, на которой записано высказывание 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-й странице и есть то самое высказывание, которое требуется найти.
Высказывание 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 напоминало бы высказывание «это высказывание ложно».) Следовательно, множество номеров всех ложных высказываний – неучтенное множество. Из условия С следует, что множество номеров истинных высказываний также не является учтенным множеством.
