7.1. Гёделевская нумерация

Гёдель прежде всего описал некоторое формализованное исчисление, средствами которого можно выразить все обычные арифметические понятия и установить известные арифметические соотношения.

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

Формулы этого исчисления строятся исходя из некоторого запаса элементарных символов, образующих алфавит системы. В этом исчислении, как обычно, выделено некоторое множество исходных формул (аксиом) и точно перечислены правила преобразования (правила вывода), посредством которых из аксиом выводятся теоремы.

Гёдель показал, что каждому элементарному символу, каждой формуле (т. е. цепочке элементарных символов) и каждому доказательству (конечной последовательности формул) можно однозначным образом приписать некоторый номер (натуральное число). Такой номер, служащий своего рода значком, ярлыком, указывающим на отмечаемый им объект — символ, формулу или доказательство — формальной системы, мы будем называть «гёделевским номером» этого символа, формулы или доказательства[13].

Элементарные символы, составляющие алфавит системы, бывают двух сортов: константы и переменные. Мы будем считать, что у нас есть ровно десять символов-констант, которым мы припишем в качестве гёделевских номеров числа от 1 до 10. Почти все эти символы читателю уже известны: «~» (сокращение для «не»), «?» («или»), «?» («если…, то…»), «=» («равно»), «0» (цифровой знак, изображающий число «нуль»), а также три «знака препинания»: левая скобка «(», правая скобка «)» и запятая «,». Кроме того, нам понадобятся еще два символа: перевернутая буква «?» (читаемая как «существует» и называемая «квантором существования») и строчная латинская буква «s», обозначающая числовой оператор, сопоставляющий каждому натуральному числу непосредственно следующее за ним число. Пример: формулу «? x (x = s0)» можно прочесть как «существует такое x, что x непосредственно следует за числом 0». Выпишем все используемые нами символы-константы (под ними указаны соответствующие гёделевские номера):

~ ? ? ? = 0 s ( ) ,

1 2 3 4 5 6 7 8 9 10

Кроме элементарных символов-констант, в алфавит нашего исчисления входят еще переменные, причем переменные трех сортов: числовые переменные «x», «y», «z» и т. д. (вместо них можно подставлять «цифры» и составленные из них (и числовых переменных) «арифметические выражения», выражающие натуральные числа); пропозициональные переменные «p», «q», «r» и т. д. (вместо них можно подставлять «формулы», выражающие высказывания); и, наконец, предикатные переменные «P», «Q», «R» и т. д. (вместо них можно подставлять арифметические «предикаты», выражающие такие свойства и отношения, как «больше чем», «простое (число)» и т. п.). Переменным также сопоставляются гёделевские номера, причем делается это в соответствии со следующими соглашениями:

1) различным числовым переменным приписываются различные простые числа, большие 10;

2) различным пропозициональным переменным приписываются квадраты различных простых чисел, больших 10;

3) различным предикатным переменным приписываются кубы различных простых чисел, бОльших 10.

_{* Кавычки (добавленные при переводе) означают здесь, что подставить можно не само написанное в правом столбце слово, а его формальную запись на языке нашего исчисления. — Прим. перев.}

Возьмем какую-нибудь формулу нашей системы, например

? x (x = sy)

(которую можно прочесть как «существует такое x, что x непосредственно следует за y» и которая выражает то обстоятельство, что для каждого числа есть непосредственно следующее за ним число). Выпишем под каждым из входящих в нее символов его (символа) гёделевский номер:

? x ( x = s у )

? ? ? ? ? ? ? ?

4 11 8 11 5 7 13 9

Конечно, нам бы хотелось сопоставить каждой формуле не набор номеров (как пока получилось), а один-единственный определенный номер. Но это очень легко сделать. А именно: сопоставим этой формуле произведение первых восьми простых чисел в порядке их величины, причем каждое из них в степени, показатель которой равен гёделевскому номеру соответствующего элементарного символа:

2⁴ ? 3¹¹ ? 5⁸ ? 7¹¹ ? 11⁵ ? 13⁷ ? 17¹³ ? 9⁹.

Обозначим это число, скажем, через m. Точно таким же образом мы можем приписать в качестве гёделевского номера единственное вполне определенное натуральное число каждой конечной последовательности элементарных символов, в частности каждой формуле, причем число простых сомножителей такого числа всегда будет равно числу вхождений элементарных символов в обозначаемой формуле.

^{В исчислении могут использоваться и символы, не входящие в его исходный («основной») алфавит; такие символы вводятся посредством определений, записанных в терминах исходных (и вообще ранее определенных) символов. Например, в наше исчисление можно ввести новый символ (константу) «·», обозначающий союз «и», определив его таким образом, чтобы запись «p·q» воспринималась как сокращение записи «~(~p?~q)». Какой гёделевский номер сопоставить введенному таким образом символу? Ответ станет совершенно очевидным, когда мы заметим, что из выражений, содержащих дополнительные (введенные определениями) символы, эти новые символы можно исключить, заменив их обозначаемыми ими выражениями, составленными исключительно из исходных символов (для этого мы просто читаем соответствующие определения «справа налево»); для последних же гёделевеcкие номера мы строить умеем. Поэтому нам достаточно условиться считать гёделевским номером формулы «p·q» гёделевский номер эквивалентной ей формулы «~(~p?~q)», гёделевским номером «формулы» «2 ? 3» — номер заменяемой ею «настоящей» формулы «~(ss0=sss0)» и т. п., условившись, конечно (что совсем нетрудно), об однозначном порядке таких «расшифровок».}

Рассмотрим, наконец, какую-нибудь последовательность формул (могущую быть в частном случае доказательством), например последовательность

? x (x = sy),

? x (x = s0).

Вторая формула последовательности, читаемая как «существует число, непосредственно следующее за нулем», — выводимая из первой формулы посредством подстановки цифры 0 вместо числовой переменной.

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

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

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

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

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

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

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

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

6 5 6

? ? ?

0 = 0

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