Этот пример подтверждает, насколько удобно использовать системы кодов в различных областях, в том числе за пределами математики, преобразуя сложные выражения в цепочку простых символов. В предыдущей главе вы видели, как свойства натуральных чисел, записанные обычным языком, можно перевести на язык символов, описанный в «Началах математики». Так, аксиома «0 не следует ни за каким натуральным числом» в этой системе преобразуется в формулу Однако Гёделю требовалось сделать еще один шаг вперед: чтобы доказать теорему о неполноте, ему было недостаточно свести арифметику к формулам — требовалось свести любую формулу и даже любое доказательство к единственному числу.
И Гёдель вспомнил, что на семинарах по истории философии, которые он посещал во время учебы в Венском университете, профессор Теодор Гомперц рассказывал об издании Луи Кутюром отредактированных рукописей Лейбница в 1903 году.
Подобно своим гениальным предшественникам, Лейбниц потратил немало сил, чтобы положить конец вавилонскому смешению языков, которым Бог наказал людей за то, что они хотели построить башню высотой до самого неба. Для этого Лейбниц задумал универсальный язык, в котором все человеческие мысли вне зависимости от языка носителя сводились к каталогу первичных идей, каждой из которых ставилось в соответствие простое число. С помощью этой системы можно было найти числа, соответствующие производным идеям так, что всегда было возможным «извлечь базовые обозначения, их составляющие», подобно тому, как из простых чисел образуются составные. Если понятиям «вода» и «неподвижность» поставлены в соответствие, например, числа 3 и 5, то понятие «озеро» (неподвижная вода) можно выразить произведением 3·5. И напротив, если понятие озера обозначается числом 15, мы можем разложить 15 на простые множители, найти в энциклопедии основных идей те, что соответствуют числам 3 и 5, и сделать вывод, что озеро есть не более чем неподвижная вода. Так, чтобы узнать, является ли утверждение вида «А есть В» истинным, достаточно определить, делится ли число, обозначающее В, на число, обозначающее А, и «когда возникнет противоречие, необходимости в споре между двумя философами будет не более, чем между двумя математиками». Эта амбициозная программа Лейбница, открытая спустя двести лет после его смерти, никогда не была реализована, однако она подсказала Гёделю, как можно перевести метаязык на язык арифметики.
Напомним, что простые числа — это числа, которые делятся только на 1 и на самих себя: например, число 5 простое, так как не делится ни на 2, ни на 3, ни на 4, однако 6 не является простым, так как при делении на 2 дает 3. Первыми простыми числами являются 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31. Путем доказательства от противного, которое так не любили интуиционисты, можно установить, что этот перечень простых чисел можно продолжать бесконечно. Большинство усилий физиков второй половины XX века было направлено на определение элементарных частиц, из которых состоит материя и которые нельзя разделить на другие, более мелкие частицы. Математикам же со времен Евклида известно, что элементарными частицами арифметики являются натуральные числа. Действительно, для любого натурального n возможны два варианта: либо n является простым, либо существует число, отличное от 1 и n, которое является делителем этого числа. Если, например, n равно 23, то мы имеем дело с первым случаем, но если n равно 30, то его можно разделить на 2.
Следовательно, исходное число не является простым. Его можно представить в виде произведения: n = а·b (в нашем случае 30 = 2·15). Мы получили два числа, для которых повторим вышеописанные действия: если оба этих числа являются простыми, процесс на этом завершается, но если одно из них не является простым, мы вновь запишем его в виде произведения сомножителей. В нашем примере 2 является простым, однако 15 можно представить в виде произведения 15 = 3·5, таким образом, 30 = 2·3·5. Так как 2, 3 и 5 — простые числа, процесс на этом завершается. В общем случае мы либо находим простой сомножитель, либо найденные нами множители постепенно уменьшаются — это гарантирует, что описанный нами процесс рано или поздно завершится. Таким образом, мы доказали основную теорему арифметики, которая гласит, что любое число можно представить в виде произведения простых множителей, которые могут повторяться. Пример: 77220 = 2·2·3 x 3·3·5·11·13. В этом случае используется сокращенная запись: 77 220 = 22· З3 х 5·11·13, где показатели степеней указывают, сколько раз повторяется каждый сомножитель.
Основная теорема арифметики утверждает, что разложение на простые множители не только существует для любого натурального числа, но и является единственно возможным (порядок множителей при этом не имеет значения). Иными словами, мы можем записать число 77 220 другим способом, например 77 220 = 3· 22·11 x З3·13, однако и в новом разложении будут использоваться те же простые множители, возведенные в те же степени.
В предыдущей главе мы показали, что «алфавит» арифметики состоит из восьми символов: 0 (число ноль), s (функция следования), ¬ (отрицание), V (дизъюнкция «или»), (существование), = (равенство), открывающие и закрывающие скобки.
Мы также использовали переменные х, у, 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 простых чисел, возвести каждое из них в степень, равную числу Геделя для каждой из формул, после чего вычислить их произведение. Таким образом, любое арифметическое доказательство сводится к одному числу.
Ключевой момент здесь заключается в том, что «гёделизация» является обратимой. Те, кто немного знаком с химией, знают, что одной из важнейших задач в ней является определение того, какие реакции являются обратимыми. Например, при сжигании топлива оно превращается в водяной пар и диоксид углерода — знаменитый углекислый газ, являющийся причиной парникового эффекта. Однако из этих газов нельзя получить исходное топливо, в противном случае все энергетические проблемы человечества были бы решены. Другие химические реакции обратимы, как, например, реакция, происходящая при пропускании водяного пара над раскаленной железной пластиной: полученные в ее результате оксид железа и водород можно вновь превратить в железо и водяной пар.
Именно этот сценарий мы хотим восстановить в арифметике, так как числа никогда не смогли бы вести «двойную жизнь», как того хотел Гедель, если бы, играя одну роль, они навсегда забывали бы о другой. Благодаря основной теореме арифметики все «реакции» при «гёделизации» обратимы. Рассмотрим, почему это так.
