269. Полна ли эта система?

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

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

Кроме того, назовем число h сопряженным с числом n, если в высказывании, записанном на n-й (Не уверен, но, IMHO, тут должно стоять …на h-й — SStas) странице «Книги высказываний», утверждается, что n — экстраординарное число.

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

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

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

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

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

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

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

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

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

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

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

Предположим теперь, что X ложно. Тогда число n не принадлежит B. Следовательно, сопряженное число h не принадлежит A. Итак, X истинно в том и только в том случае, если его номер принадлежит множеству A.

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

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

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