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

~ ˅ ﬤ Ǝ = 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)» и т. п., условившись, конечно (что совсем нетрудно), об однозначном порядке таких «расшифровок».}