Teopeмa Гёделя

Нагель Эрнст

^{Читатель, конечно, помнит, что формальное доказательство мы определяли выше как конечную последовательность формул, каждая из которых есть либо аксиома, либо выводима из предыдущих формул этой последовательности по правилам вывода данного исчисления. Согласно этому определению приведенная пара формул доказательством не является (первая ее формула — не аксиома) — это лишь «кусок» доказательства, на примере которого мы столь же понятно (но далеко не так громоздко) поясним идею нумерации, как и на целом доказательстве.}

Выше мы уже определили гёделевский номер первой из этих формул — мы обозначили его тогда через m. Пусть гёделевским номером второй формулы является число n. Как и выше, мы хотим сопоставить нашей последовательности не пару чисел m и n, а некоторое единственным образом определенное натуральное число. Для этого нам достаточно взять в качестве такого гёделевского номера число, являющееся произведением степеней первых двух

простых чисел (т. е. чисел 2 и 3), причем первый сомножитель будет входить в это произведение в степени, показатель которой равен гёделевскому номеру первой формулы, и аналогично для второго сомножителя (а также для третьего и других, если мы имеем дело с последовательностью, состоящей более чем из двух формул). Обозначим это число через k: k = 2^m x 3ⁿ. Такой простой и компактный метод применим, очевидно, для получения гёделевского номера произвольной последовательности формул. Таким образом, любое выражение нашей системы — будь то элементарный символ, последовательность символов или последовательность таких последовательностей — может быть однозначно занумеровано посредством некоторого гёделевского номера.

Теперь уже полная «арифметизация» нашего формального исчисления не представит никакого труда. Такая «арифметизация» попросту сводится к устанорлению некоторого взаимно-однозначного соответствия между выражениями, входящими в исчисление, и некоторым подмножеством натурального ряда.

^{Не всякое натуральное число есть гёделевский номер константы, переменной или формулы; предоставляем читателю придумать и разобрать примеры на различные возможные случаи.}

Если нам дано какое-нибудь выражение, мы без труда напишем его гёделевский номер. Это, однако, лишь полдела. Важно то, что когда нам дано какое-либо натуральное число, то мы можем установить, является ли это число гёделевским номером, а если да — то можем точно «восстановить» обозначаемое этим номером выражение. Если данное число не превосходит 10, то это, как мы знаем, просто номер некоторой константы. Если же данное число больше 10, то его можно разложить, причем единственным образом (в этом состоит так называемая основная теорема арифметики), на простые сомножители. Если оно оказалось простым, квадратом простого или кубом простого числа, то это — гёделевский номер переменной.

Если данное число оказалось произведением степеней первых последовательных простых чисел, то оно может (хотя, конечно, и не обязано) быть гёделевским номером формулы или последовательности формулы.

И в таком случае выражение, которому соответствует данный номер, может быть точно определено.

Следуя намеченной программе, мы можем для любого данного числа совершенно единообразным методом («как машина») проверить, является ли оно гёделевским номером, а если да — то какого выражения [14] . Пусть, например, нам дано число 243 000 000. Разложим его (оно, очевидно, составное) на простые сомножители: 243 000 000 = 64 x 243 x 15 625 = 2⁶ x 3⁵ x 5⁶. Вспомнив, что 6 есть гёделевский номер константы «0», а 5 — гёделевский номер знака «=», рисуем схему:

14

После чего уже совсем нетрудно проверить, является ли данное выражение формулой или доказательством нашего исчисления (ср. предыдущее примечание). — Прим. перев.

6 5 6

V V V

0 = 0

Теперь видно, что число «243 миллиона» действительно есть гёделевский номер некоторой формулы, а именно, формулы «0 = 0» (т. е. «нуль равен нулю»).

7.2. Арифметизация метаматематики

Следующим шагом, который проделал Гёдель, было чрезвычайно остроумное применение описанного выше «кодирования» («гёделевской нумерации»). Он показал, что все метаматематические высказывания о структурных свойствах выражений, входящих в рассматриваемое исчисление, можно изобразить (причем взаимно-однозначным образом) в самом этом исчислении. В основе этой процедуры лежит следующая идея. Поскольку каждому выражению нашего исчисления приписан некоторый (гёделевский) номер, то каждое метаматематическое высказывание о выражениях исчисления и отношениях, имеющих место между ними, можно рассматривать и как высказывание о соответствующих (гёделевских) номерах и отношениях между ними. Таким путем метаматематика оказывается полностью «арифметизированной».

Рассмотрим такой популярный пример. При входе в большие универсальные магазины покупателям иногда выдают билетики с номерами, определяющими порядок дальнейшего обслуживания покупателей. Достаточно бывает посмотреть на эти номера, чтобы ответить на вопросы, сколько покупателей уже обслужено, сколько ожидает своей очереди, кто за кем стоит, сколько всего покупателей было с утра в магазине и т. п. Если, скажем, миссис Смит имеет номер 37, а миссис Браун — номер 53, то вместо того чтобы объяснить миссис Браун, что она должна пропустить вперед миссис Смит, достаточно обратить ее внимание на то, что 37 меньше, чем 53.

В метаматематике дело обстоит в точности, как в этом магазине. Каждое метаматематическое высказывание кодируется теперь вполне однозначным образом посредством некоторой арифметической формулы; отношения же,

имеющие место между метаматематическими высказываниями, и логические зависимости между ними также однозначно переводятся в некоторые числовые соотношения и зависимости между соответствующими арифметическими формулами. И здесь, как и раньше, числовое кодирование облегчает рассмотрение всех достаточно сложных соотношений. Изучение метаматематических вопросов сводится к исследованию арифметических соотношений и свойств некоторых чисел.

Проиллюстрируем все эти общие замечания одним элементарным примером. Возьмем первую аксиому исчисления высказываний, являющуюся, кстати, аксиомой и рассматриваемого сейчас логико-арифметического исчисления: «(p p) p». Ее гёделевский номер, равный, как легко убедиться, числу 2⁸ x 3¹¹ x 5² x 7^{11^2} x 11⁹ x 13⁸ x 17¹¹ мы обозначим буквой а. Рассмотрим теперь формулу «(p p)», гёделевский номер которой, равный числу 2⁸ x 3^{11^2} x 5² x 7^{11^2} x 11⁹, обозначим через b. Сформулируем теперь метаматематическое утверждение, гласящее, что формула «(p p)» есть начальная «подформула» (т. е. часть формулы, сама также являющаяся формулой) выбранной аксиомы. Какой арифметической формуле рассматриваемой формальной системы соответствует это утверждение? Очевидно, что более короткая формула «(p p)» является начальной подформулой более длинной формулы «(p p) p» в том и только в том случае, если (гёделевский) номер b, соответствующий первой из этих формул, есть делитель (гёделевского) номера a, соответствующего второй формуле. В предположении, что термин «делитель» определен некоторым подходящим образом в формализованной арифметической системе арифметической формулой, однозначным образом соответствующей упомянутому выше метаматематическому утверждению о том, что первая аксиома начинается с подформулы «(p p)», является формула «b есть делитель a». Более того, если эта последняя формула истинна, т. е. если b действительно является делителем a, то верно и то, что «(p p)» есть начальная подформула формулы «(p p) p».

Рассмотрим теперь повнимательнее следующее метаматематическое высказывание: «Последовательность формул, имеющая гёделевский номер x, является доказательством формулы, имеющей гёделевский номер z». Высказывание кодируется (изображается) посредством некоторой вполне определенной формулы арифметического исчисления, выражающей некоторое чисто арифметическое отношение между числами x и z. (Некоторое представление о том, насколько сложным является такое отношение, читатель получит, вспомнив приводившийся выше пример, в котором конец доказательства (а не все доказательство!) некоторой формулы, имеющей гёделевский номер, n, получал гёделевский номер k = 2^m x 3ⁿ. Самый беглый анализ приводит нас к выводу, что здесь вводится вполне определенное, хотя и далеко не простое, арифметическое отношение между k (будем для простоты считать его номером всего доказательства) и n — гёделевским номером заключения этого доказательства.) Мы будем записывать отношение между числами x и z посредством формулы «Dem(x, z)» [15] напоминающей нам самим своим обликом о том метаматематическом утверждении, которому она соответствует (а именно, об утверждении «Последовательность формул, имеющая гёделевский номер x, является доказательством формулы, имеющей гёделевский номер z»).

15

От англ. demonstration (доказательство). — Прим. перев.

^{Читатель должен твердо уяснить себе, что хотя «Dem(x, z)» кодирует некоторое метаматематическое утверждение, сама эта запись является формулой арифметического исчисления. Формула эта в более привычных обозначениях может быть записана в виде f(x, z) = 0, где буква f обозначает некоторый довольно-таки сложный комплекс арифметических операций над числами. Однако эта более привычная запись не «подсказывает» сразу своей метаматематической интерпретации, почему мы и предпочли запись, приведенную в тексте.}