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

Джеймс Рой Ньюмен

7

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

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

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

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

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

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

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