Сон разума. Математическая логика и ее парадоксы
Шрифт:
* * *
ГЁДЕЛЬ В ЛИТЕРАТУРЕ
В романе «Новые признания» (The new confessions) Уильяма Бойда главный герой снимает шедевр немого кино, однако его премьера остается незамеченной, так как в то же самое время появляются первые звуковые короткометражные фильмы. Лишь Курт Гёдель, который мимолетно появляется на страницах романа, признает талант режиссера.
В романе мексиканского писателя Хорхе Вольпи «В поисках Клингзора», опубликованном на десять лет позже, подруга главного героя, физика по имени Фрэнсис Бэкон, врывается на семинар Гёделя в Институте перспективных исследований и начинает кричать на него, обвиняя в неверности. Когда действие переносится в последние ряды аудитории, «профессор Гёдель объявляет, что не может продолжать занятия, и безудержно заливается слезами». Главным его конфликтом, объясняет автор устами фон Неймана, были не формально неразрешимые предложения, а «терзания от любви к проститутке — собственной жене». Эпизод «Новых признаний» выглядит правдоподобным, но сцена, описанная Вольпи, и жестока, и неправдоподобна.
Писатель Уильям
* * *
Хотя мы уделили немало времени объяснениям гениального метода нумерации, на создание которого Гёделя вдохновили труды Лейбница, не следует забывать, что этот метод — лишь средство достижения цели: доказать, что в любой непротиворечивой и рекурсивно перечислимой системе аксиом существуют истинные, но недоказуемые высказывания. В начале этой главы мы указали, по какой схеме должно выполняться это доказательство: в парадоксе лжеца нужно заменить понятие истинности понятием доказуемости и получить самоотносимое утверждение, которое гласит: «я недоказуемо». Если противоречия не допускаются, то это утверждение должно быть истинным, следовательно, недоказуемым. Основная сложность, как мы уже указывали, заключается в том, чтобы найти арифметический эквивалент этого утверждения на метаязыке, в котором речь идет не о числах, а о математических теориях. Теперь в нашем распоряжении есть все необходимые методы, позволяющие это сделать. Далее мы попытаемся изложить важнейшие этапы доказательства Геделя максимально простым языком.
Нужно перевести на язык арифметики утверждение «я недоказуемо». Но что означает доказуемость утверждения в системе аксиом арифметики? Это означает, что существует доказательство, которое заканчивается нашим утверждением, то есть конечная последовательность формул, каждая из которых является либо аксиомой, либо получена из предыдущих формул с помощью правил вывода. Чтобы определить, является ли последовательность формул, которую мы обозначим Z, доказательством высказывания X, нужно показать, что Z строится по вышеуказанному правилу и что его последней формулой является именно X. Основная идея заключается в том, чтобы с помощью «гёделизации» сопоставить формулам X и Z числа Гёделя, которые мы будем обозначать строчными буквами х и z. Нам хотелось бы найти механизм D, который позволял бы для натуральных чисел х и z через определенное количество шагов дать ответ, является ли последовательность формул, соответствующая числу z, доказательством формулы с числом Гёделя х. Следовательно, высказывание D(х, z) будет истинным, если Z доказывает формулу X, и ложным — в противном случае.
Приведем простейший пример. Напомним, что число Гёделя для второй аксиомы Пеано равно
23·35·511·73·115·1313·177·1913·236·292·3111·378.
Так как определяющее свойство аксиом гласит, что они являются доказательством самих себя, то если мы подставим вышеприведенное число вместо х и z в D(х, z), результат будет истинным: последовательность формул для числа Гёделя z, состоящая в этом случае лишь из второй аксиомы Пеано, является доказательством формулы, которой соответствует число х — это вновь вторая аксиома Пеано! Однако если мы введем в качестве значения z число 23·35·511·77·112·1311·176·191·238, механизм D(х, z) выдаст результат «ложь», так как формула, соответствующая этому числу, не является доказательством второй аксиомы Пеано. Тот факт, что формула для числа Гёделя х доказуема, означает, что существует число z такое, что после довательность формул, соответствующая z, является доказательством формулы, связанной с х. Иными словами, существует z такое, что высказывание D(х, z) является истинным. Как следствие, формула
Читатель уже наверняка понял, что наиболее трудоемкая часть работы Гёделя состояла в том, чтобы доказать, что механизм, обладающий описанными выше свойствами, действительно существует. Для этого Гёделю потребовалось 46 этапов, которые мы опишем лишь вкратце. Допустим, что дано некоторое натуральное число z, кодирующее некую последовательность формул. По основной теореме арифметики мы можем разложить z на простые множители:
z = pk1·pk2·pk3·…·рkn.
Итак, мы разложили число z на простые множители, возведенные в различные степени. Так
k1, k2, k3… kn.
Вновь повторим одно из основных утверждений этой книги: доказательство — это конечная последовательность формул, каждая из которых является либо аксиомой, либо получена из предыдущих формул с помощью правил вывода. Следовательно, нужно подтвердить следующее:
— первый шаг: последовательность формул с числами Гёделя k1, k2, k3… kn является доказательством, то есть каждому из этих чисел соответствует либо аксиома, либо высказывание, которое получено из предыдущих с помощью правил вывода;
— второй шаг: последняя формула последовательности — это формула, которую мы хотим доказать.
Начнем с последнего шага, который является наиболее простым: нам дана формула, которой соответствует число Гёделя х, и мы хотим узнать, оканчивается ли последовательность высказываний этой формулой, — простейшее требование, которое должно выполняться, если речь действительно идет о доказательстве. Вышеприведенные расчеты позволяют определить числа Гёделя для каждой формулы последовательности. Последней формуле соответствует число kn, поэтому достаточно проверить, что числа х и kn равны. Никто не усомнится в том, что проверить равенство чисел очень просто.
Теперь перейдем к первому этапу нашей гонки с препятствиями и рассмотрим формулы, которым соответствуют числа Гёделя k1, k2,… kn . Именно здесь обязательно должно выполняться условие рекурсивной перечислимости системы аксиом арифметики — ранее это условие казалось не более чем причудой. Напомним, что множество аксиом S является рекурсивно перечислимым, когда за конечное число шагов можно показать, является некоторое высказывание аксиомой или нет. Следовательно, в нашем распоряжении находится формула А(х) (А — по первой букве слова «аксиома»), которая для любого числа х позволяет определить, является ли соответствующее ему высказывание аксиомой. Достаточно вычислить А(k1), А(k2)… А(kn), и мы узнаем, какие из высказываний предполагаемого доказательства являются аксиомами. Первая формула, которой соответствует число Гёделя обязательно должна быть аксиомой, так как ей не предшествуют формулы, из которых ее можно было бы вывести. Следовательно, если результат А(k1) случайно окажется ложным, дальнейшие действия не потребуются: z не является числом Гёделя, соответствующим доказательству. Предположим, что этого не произошло.
Некоторые из следующих формул, которым соответствуют числа k2, k3,… kn будут аксиомами, другие — нет. Для тех, что не являются аксиомами, нужно показать, что они выводятся из предыдущих высказываний по допустимым правилам вывода. В своей скрупулезно выполненной работе Гёдель доказывает, что для каждого правила вывода существует формула I, которая для первых s чисел k1, k2,… ks возвращает результат «истина», если формула, обозначаемая числом Гёделя ks, выводится из формул, обозначаемых числами Гёделя k1, k2,… ks -1 (предшествующей формулы), по соответствующему правилу вывода. Например, I(k1, k2, k3, k4) будет истинной, если четвертая формула последовательности выводится из трех предыдущих по правилу вывода, обозначаемому формулой I. Таким образом, этот процесс можно выполнить для формул, которые не являются аксиомами, и если для каждой из них формула, обозначающая хотя бы одно из правил вывода, вернет значение «истина», то первый этап будет успешно завершен, и z будет числом Гёделя, обозначающим доказательство. Так как здесь нетрудно запутаться в технических деталях, выделим главное: нужно запомнить, что мы доказали существование процесса D(х, z), определяющего, является ли последовательность формул, обозначаемая числом z, доказательством высказывания, которому соответствует число Гёделя х.
Для этого достаточно выразить в виде отношений между числами правила, которым должно удовлетворять доказательство, что мы уже не раз повторили.
Отлично: в рамках арифметики мы сформулировали высказывание Dem (х), которое гласит: «формула, выражаемая числом Гёделя х, доказуема». Отрицанием этой формулы будет ¬ Dem (х), которая звучит так: «формула, выражаемая числом Гёделя х, недоказуема». Пока что все абсолютно понятно, но мы постепенно приближаемся к тому, чтобы совершить своеобразное сальто-мортале. Сначала следует напомнить, что высказывание «арифметика является непротиворечивой», которое фигурирует во второй теореме о неполноте, равносильно высказыванию «формула 0 = 1 недоказуема». Напомним также, что 1 является числом, следующим за нулем, то есть 1 = s0. Предлагаем читателю убедиться, что число Гёделя для формулы 0 = 1 равно 255150. Следовательно, высказывание ¬ Dem (255150), переведенное на язык арифметики, гласит, что «формула, обозначаемая числом Гёделя 255150, недоказуема», то есть «формула 0 = 1 недоказуема», что равносильно высказыванию «арифметика непротиворечива». Высказывание ¬ Dem (х) позволяет убить сразу двух зайцев.