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

^{В исчислении могут использоваться и символы, не входящие в его исходный («основной») алфавит; такие символы вводятся посредством определений, записанных в терминах исходных (и вообще ранее определенных) символов. Например, в наше исчисление можно ввести новый символ (константу) «·», обозначающий союз «и», определив его таким образом, чтобы запись «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ⁿ. Такой простой и компактный метод применим, очевидно, для получения гёделевского номера произвольной последовательности формул. Таким образом, любое выражение нашей системы — будь то элементарный символ, последовательность символов или последовательность таких последовательностей — может быть однозначно занумеровано посредством некоторого гёделевского номера.