Чтение онлайн

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 следует, что множество номеров истинных высказываний также не является учтенным множеством.

270. Теорема Гёделя.

Предыдущая задача представляет собой не что иное, как упрощенный вариант знаменитой теоремы Гёделя о полноте.

В 1931 г. Курт Гёдель совершил поразительное открытие. Он установил, что математическую истину в некотором смысле нельзя формализовать полностью. Гёдель доказал, что в математической системе, принадлежащей широкому классу систем, всегда найдется утверждение, недоказуемое (то есть невыводимое из аксиом системы), несмотря на свою истинность! Следовательно, ни одной аксиоматической системы, сколь бы остроумно она ни была устроена, не достаточно для доказательства всех математических истин.

Гёдель впервые доказал свою теорему для системы "Principia Mathematica" Уайтхеда и Расселла, но предложенное им доказательство, как я уже говорил, допускает перенос и на многие другие системы. Во всех этих системах существует вполне определенное множество выражений, называемых предложениями, которые подразделяются на истинные и ложные. Некоторые истинные предложения приняты за аксиомы системы. Точный перечень правил вывода позволяет доказывать (выводить из аксиом) одни предложения и опровергать другие.

Помимо предложений система содержит имена различных множеств (целых и положительных) чисел. Любое множества чисел, наделенное в рассматриваемой системе именем, можно назвать именуемым, или определимым, множеством системы (в предыдущей задаче такие множества скрывались под псевдонимом "учтенные множества"). Весьма существенно, что все предложения можно перенумеровать, а все определимые множества перечислить по порядку. Это означает, что математическая система удовлетворяет условиям E1, E2, C и H нашей задачи. (Номер, присваиваемый каждому предложению, - в задаче мы называли его просто номером - в математической логике известен подназванием гёделевого номера предложения.) Доказать, что система удовлетворяет условиям C и H, очень просто. Доказательство того, что система удовлетворяет условиям E1 и E2, в принципе несложно /* Напомним условие H. Для любого числа n существует высказывание, утверждающее, что n - экстраординарное число. Это высказывание (как и всякое другое предложение)

имеет гёделев номер. Обозначим его n*. Оказывается, что для любого определимого множества A множество B всех чисел n, для которых n* принадлежит A, также определимо.

Поскольку геделев номер n* сопряжен с числом n, то тем самым условие H выполнено.*/, но довольно громоздко. Коль скоро доказано, что система удовлетворяет всем четырем условиям, они позволяют построить предложение, которое истинно, но недоказуемо (невыводимо) в данной системе.

Это предложение можно представлять себе как некоторое предложение X, содержащее утверждение о своей недоказуемости. Такое предложение действительно должно быть истинно, но недоказуемо (подобно тому как житель острова G, утверждавший, что он непризнанный рыцарь, действительно был рыцарем, но не был признанным рыцарем).