Хавьер Фресан - Том. 22. Сон разума. Математическая логика и ее парадоксы

Некоторые из следующих формул, которым соответствуют числа 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 = s 0. Предлагаем читателю убедиться, что число Гёделя для формулы 0 = 1 равно 255150. Следовательно, высказывание ¬ Dem (255150), переведенное на язык арифметики, гласит, что «формула, обозначаемая числом Гёделя 255150, недоказуема», то есть «формула 0 = 1 недоказуема», что равносильно высказыванию «арифметика непротиворечива». Высказывание ¬ Dem (х) позволяет убить сразу двух зайцев.

Важность выражения ¬ Dem(х) заключается в том, что это уже не высказывание на повседневном языке, а арифметическая формула, в которой используются только символы 0, s, ¬, V, =, (, )и некоторые переменные. Буквы «Dem» — это лишь сокращенный способ записи этого выражения, так как его полная запись очень сложна и занимает не одну страницу. Однако если мы захотим найти его полную запись, то сможем сделать это, используя исключительно символы алфавита арифметики. И ради этого мы потратили столько сил! У нас нет никаких сомнений, что теперь читатель знает, что нужно сделать всякий раз, когда ему встретится записанная в таком виде формула: ее нужно записать согласно гёделевской нумерации. Сопоставим выражению ¬ Dem(х) число Гёделя, которое обозначим d . Возможно, это число будет настолько большим, что во всем мире не хватит чернил, чтобы записать его, однако его размер совершенно не важен — главное, что это число будет конечным.

Вся структура высказывания «формула, обозначаемая числом Гёделя х , недоказуема», содержится в единственном числе d . Параметр х не фиксирован, он не равняется, например, 14 451937 500, а может принимать любые значения. Но если этот параметр может принимать любые значения, почему бы умышленно не принять х равным d ? В этом случае мы получим высказывание ¬ Dem(d) , которое гласит, что «формула, выражаемая числом Гёделя d , недоказуема», но так как d , в свою очередь, является числом Гёделя, обозначающим высказывание «формула, выражаемая числом Гёделя х , недоказуема», ¬ Dem (d) преобразуется в высказывание «формула „формула, выражаемая числом Геделя х, недоказуема" недоказуема». Нетрудно видеть, что это высказывание означает не что иное, как «я недоказуемо» [4] В этой книге мы не можем абсолютно точно привести формулы, описывающие свободные переменные, замены и обобщения, которые Гедель использовал в своей статье. Однако мы полагаем, что упомянули все основные элементы его доказательства. .