Теорема Гёделя

Элементарные символы, составляющие алфавит системы, бывают двух сортов: константы и переменные. Мы будем считать, что у нас есть ровно десять символов-констант, которым мы припишем в качестве гёделевских номеров числа от 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. Точно таким же образом мы можем приписать в качестве гёделевского номера единственное вполне определенное натуральное число каждой конечной последовательности элементарных символов, в частности каждой формуле, причем число простых сомножителей такого числа всегда будет равно числу вхождений элементарных символов в обозначаемой формуле.