(существование), = (равенство), открывающие и закрывающие скобки.
Мы также использовали переменные х, у, z для обозначения чисел. На первом этапе кодификации Гёдель предложил поставить в соответствие каждому из этих символов число от 1 до 8, переменным х, у, z — три первых числа, больших 8, как показано в таблице ниже.
После того как мы присвоили числа «основным идеям» арифметики, закодировать формулу очень просто: сначала нужно подсчитать число используемых в ней символов (с повторениями) и выбрать столько же простых чисел. Размеры формулы не имеют значения, так как простых чисел бесконечно много. Далее каждое простое число возводится в степень, соответствующую символу, согласно таблице, приведенной выше, после чего все множители перемножаются. Но вместо долгих объяснений рассмотрим один пример.
Третья аксиома Пеано гласит, что «0 не следует ни за каким натуральным числом», и записывается в виде Будем следовать инструкциям «гёделизации»: чтобы преобразовать эту формулу в число, сначала нужно подсчитать, сколько символов в ней используется. Их всего девять: ¬,, x, (, s, x, =, 0 и). Выберем первые девять простых чисел, а именно: 2, 3, 5, 7, 11, 13, 17, 19 и 23. Согласно таблице, ¬ отрицанию соответствует число 3, следовательно, нужно возвести простое число 2 в степень 3, то есть вычислить 23. Квантор существования обозначается числом 5, поэтому нужно возвести простое число 3 в пятую степень: 35.
Повторив аналогичные действия, получим 511, 77, 112, 1311, 176, 191 и 238. После того как мы перемножим эти числа, формула примет вид:
23·35·511·77·112·1311·176·191·238
Описанный нами метод позволяет представить любую формулу в виде числа, которое мы будем называть числом Гёделя. Никто не мешает нам выполнить аналогичные действия и для доказательств. Напомним, что доказательство — это не более чем конечная последовательность, состоящая, например, из п формул. Следовательно, можно сначала представить в виде числа каждую из этих формул, затем выбрать n простых чисел, возвести каждое из них в степень, равную числу Геделя для каждой из формул, после чего вычислить их произведение. Таким образом, любое арифметическое доказательство сводится к одному числу.
Ключевой момент здесь заключается в том, что «гёделизация» является обратимой. Те, кто немного знаком с химией, знают, что одной из важнейших задач в ней является определение того, какие реакции являются обратимыми. Например, при сжигании топлива оно превращается в водяной пар и диоксид углерода — знаменитый углекислый газ, являющийся причиной парникового эффекта. Однако из этих газов нельзя получить исходное топливо, в противном случае все энергетические проблемы человечества были бы решены. Другие химические реакции обратимы, как, например, реакция, происходящая при пропускании водяного пара над раскаленной железной пластиной: полученные в ее результате оксид железа и водород можно вновь превратить в железо и водяной пар.
Именно этот сценарий мы хотим восстановить в арифметике, так как числа никогда не смогли бы вести «двойную жизнь», как того хотел Гедель, если бы, играя одну роль, они навсегда забывали бы о другой. Благодаря основной теореме арифметики все «реакции» при «гёделизации» обратимы. Рассмотрим, почему это так.
Допустим, дано число
304 496 379 203 017 490 604 020 678 113 081 132 612 291 772 080 917 708 404 389 616 093 394 253 015 558 500 327 468 465 234 375 000,
которое мы записали специально для того, чтобы читатель представил себе наименьшие числа Гёделя. Основная теорема арифметики гарантирует, что это число можно разложить на простые множители. Если вы не хотите выполнять разложение вручную, что вполне объяснимо, то можете обратиться к веб-странице http://www.wolframalpha.com и записать в строке поиска слово «factor», а затем — это число.
Для разложения больших величин на простые множители компьютеру потребуется значительное время, однако важно другое: основная теорема арифметики гарантирует, что это разложение всегда существует и, более того, является единственным.
К счастью, наше число сравнительно невелико, поэтому его разложение на множители займет менее секунды:
23·35·511·73·115·1313·177·1913·236·292·3111·378.
Теперь осталось внимательно рассмотреть показатели степеней и восстановить исходные символы согласно таблице. Мы получим формулу которая гласит, что не существует натурального числа х такого, что для него не существует числа у такого, что у является числом, следующим за х. Переформулировав это высказывание, читатель убедится, что его можно записать в виде «число, следующее за натуральным, тоже есть натуральное число», а это есть не что иное, как вторая аксиома Пеано.
Разумеется, не все натуральные числа являются числами Гёделя для какой-либо формулы, но даже если кто-то скажет нам, что какое-либо число не соответствует никакой формуле арифметики, мы мгновенно сможем это проверить. Например, 15 = 3·5 не является числом Геделя для какой-либо формулы, так как по условиям «гёделизации» разложение числа на простые множители должно обязательно содержать первые простые числа без пропусков, а в разложении 15 отсутствует число 2. Число 1536 = 29·3 также не соответствует никакой формуле арифметики: хотя в его разложении присутствуют первые простые числа без пропусков, число 9 не соответствует ни одному из символов алфавита.
Подведем итог: описанная система кодификации позволяет сопоставить любой формуле (и любому доказательству) арифметики число, кодирующее всю ее структуру целиком. Кроме того, эта «математическая реакция» является обратимой в том смысле, что, разложив произвольное натуральное число N на простые множители, можно определить следующее.
1. Является ли N числом Гёделя для некоторой формулы.
2. Если число N соответствует некоторой формуле, то какой именно.
* * *
ГЁДЕЛЬ В ЛИТЕРАТУРЕ
В романе «Новые признания» (The new confessions) Уильяма Бойда главный герой снимает шедевр немого кино, однако его премьера остается незамеченной, так как в то же самое время появляются первые звуковые короткометражные фильмы. Лишь Курт Гёдель, который мимолетно появляется на страницах романа, признает талант режиссера.
В романе мексиканского писателя Хорхе Вольпи «В поисках Клингзора», опубликованном на десять лет позже, подруга главного героя, физика по имени Фрэнсис Бэкон, врывается на семинар Гёделя в Институте перспективных исследований и начинает кричать на него, обвиняя в неверности. Когда действие переносится в последние ряды аудитории, «профессор Гёдель объявляет, что не может продолжать занятия, и безудержно заливается слезами». Главным его конфликтом, объясняет автор устами фон Неймана, были не формально неразрешимые предложения, а «терзания от любви к проститутке — собственной жене». Эпизод «Новых признаний» выглядит правдоподобным, но сцена, описанная Вольпи, и жестока, и неправдоподобна.
Писатель Уильям Бойд сделал Курта Гёделя одним из героев своего романа «Новые признания».
* * *
Хотя мы уделили немало времени объяснениям гениального метода нумерации, на создание которого Гёделя вдохновили труды Лейбница, не следует забывать, что этот метод — лишь средство достижения цели: доказать, что в любой непротиворечивой и рекурсивно перечислимой системе аксиом существуют истинные, но недоказуемые высказывания. В начале этой главы мы указали, по какой схеме должно выполняться это доказательство: в парадоксе лжеца нужно заменить понятие истинности понятием доказуемости и получить самоотносимое утверждение, которое гласит: «я недоказуемо». Если противоречия не допускаются, то это утверждение должно быть истинным, следовательно, недоказуемым. Основная сложность, как мы уже указывали, заключается в том, чтобы найти арифметический эквивалент этого утверждения на метаязыке, в котором речь идет не о числах, а о математических теориях. Теперь в нашем распоряжении есть все необходимые методы, позволяющие это сделать. Далее мы попытаемся изложить важнейшие этапы доказательства Геделя максимально простым языком.
Нужно перевести на язык арифметики утверждение «я недоказуемо». Но что означает доказуемость утверждения в системе аксиом арифметики? Это означает, что существует доказательство, которое заканчивается нашим утверждением, то есть конечная последовательность формул, каждая из которых является либо аксиомой, либо получена из предыдущих формул с помощью правил вывода. Чтобы определить, является ли последовательность формул, которую мы обозначим Z, доказательством высказывания X, нужно показать, что Z строится по вышеуказанному правилу и что его последней формулой является именно X. Основная идея заключается в том, чтобы с помощью «гёделизации» сопоставить формулам X и Z числа Гёделя, которые мы будем обозначать строчными буквами х и z. Нам хотелось бы найти механизм D, который позволял бы для натуральных чисел х и z через определенное количество шагов дать ответ, является ли последовательность формул, соответствующая числу z, доказательством формулы с числом Гёделя х. Следовательно, высказывание D(х, z) будет истинным, если Z доказывает формулу X, и ложным — в противном случае.
Приведем простейший пример. Напомним, что число Гёделя для второй аксиомы Пеано равно
23·3