Том 22. Сон разума. Математическая логика и ее парадоксы - страница 36
Некоторые из следующих формул, которым соответствуют числа k>2, k>3,… k>n будут аксиомами, другие — нет. Для тех, что не являются аксиомами, нужно показать, что они выводятся из предыдущих высказываний по допустимым правилам вывода. В своей скрупулезно выполненной работе Гёдель доказывает, что для каждого правила вывода существует формула I, которая для первых s чисел k>1, k>2,… k>s возвращает результат «истина», если формула, обозначаемая числом Гёделя k>s, выводится из формул, обозначаемых числами Гёделя k>1, k>2,… k>s -1 (предшествующей формулы), по соответствующему правилу вывода. Например, I(k>1, k>2, k>3, k>4) будет истинной, если четвертая формула последовательности выводится из трех предыдущих по правилу вывода, обозначаемому формулой I. Таким образом, этот процесс можно выполнить для формул, которые не являются аксиомами, и если для каждой из них формула, обозначающая хотя бы одно из правил вывода, вернет значение «истина», то первый этап будет успешно завершен, и z будет числом Гёделя, обозначающим доказательство. Так как здесь нетрудно запутаться в технических деталях, выделим главное: нужно запомнить, что мы доказали существование процесса D(х, z), определяющего, является ли последовательность формул, обозначаемая числом z, доказательством высказывания, которому соответствует число Гёделя х.
Для этого достаточно выразить в виде отношений между числами правила, которым должно удовлетворять доказательство, что мы уже не раз повторили.
Отлично: в рамках арифметики мы сформулировали высказываниеDem (х), которое гласит: «формула, выражаемая числом Гёделя х, доказуема». Отрицанием этой формулы будет ¬ Dem (х), которая звучит так: «формула, выражаемая числом Гёделя х, недоказуема». Пока что все абсолютно понятно, но мы постепенно приближаемся к тому, чтобы совершить своеобразное сальто-мортале. Сначала следует напомнить, что высказывание «арифметика является непротиворечивой», которое фигурирует во второй теореме о неполноте, равносильно высказыванию «формула 0 = 1 недоказуема». Напомним также, что 1 является числом, следующим за нулем, то есть 1 = s0. Предлагаем читателю убедиться, что число Гёделя для формулы 0 = 1 равно 255150. Следовательно, высказывание ¬Dem (255150), переведенное на язык арифметики, гласит, что «формула, обозначаемая числом Гёделя 255150, недоказуема», то есть «формула 0 = 1 недоказуема», что равносильно высказыванию «арифметика непротиворечива». Высказывание ¬Dem (х) позволяет убить сразу двух зайцев.
Важность выражения ¬ Dem (х) заключается в том, что это уже не высказывание на повседневном языке, а арифметическая формула, в которой используются только символы 0, s, ¬, V, =, (, ) и некоторые переменные. Буквы «Dem» — это лишь сокращенный способ записи этого выражения, так как его полная запись очень сложна и занимает не одну страницу. Однако если мы захотим найти его полную запись, то сможем сделать это, используя исключительно символы алфавита арифметики. И ради этого мы потратили столько сил! У нас нет никаких сомнений, что теперь читатель знает, что нужно сделать всякий раз, когда ему встретится записанная в таком виде формула: ее нужно записать согласно гёделевской нумерации. Сопоставим выражению ¬ Dem (х) число Гёделя, которое обозначим d. Возможно, это число будет настолько большим, что во всем мире не хватит чернил, чтобы записать его, однако его размер совершенно не важен — главное, что это число будет конечным.
Вся структура высказывания «формула, обозначаемая числом Гёделя х, недоказуема», содержится в единственном числе d. Параметр х не фиксирован, он не равняется, например, 14 451937 500, а может принимать любые значения. Но если этот параметр может принимать любые значения, почему бы умышленно не принять х равным d? В этом случае мы получим высказывание ¬Dem (d), которое гласит, что «формула, выражаемая числом Гёделя d, недоказуема», но так как
