Читать «Teopeмa Гёделя» онлайн - страница 33

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

Ǝ x (x = sy),

Ǝ x (x = s0).

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

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

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