) 19

x1 21

х2 23

х3 25

Количество переменных потенциально бесконечно. Оставшимся (х4, х5, ...) соответствуют числа 27, 29 и так далее. Гёдель назначил коды высказываний и пропозициональных функций. Для большей ясности объясним метод на конкретном примере. Какой код соответствует, например, высказыванию "1 = 1"? Шаги для его вычисления следующие.

1. Сначала остановимся на кодах символов, образующих высказывание: 9, 7,9.

2. Поскольку есть три символа, теперь возьмем по порядку три первых простых числа: 2, 3, 5.

3. Тогда код следующий: 29 · З7 · 59 = 2187 000 000 000. (Заметьте, что простые числа — это основания степеней, а коды символов — показатели степеней.)

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

Конечно же, как и в предыдущих случаях, должен существовать механический способ, указывающий, как вычислить код последовательности высказываний, и другой, обратный способ, который при заданном коде позволил бы восстановить последовательность соответствующих ему высказываний. Наше правило вычисления кода последовательности как произведения индивидуальных кодов неверно, потому что игнорируется порядок высказываний (при перестановке высказываний местами код конечной последовательности остается тем же самым, но этого не должно происходить, так как при перестановке на самом деле получается другая последовательность). Однако, поскольку речь идет только о гипотетическом примере, мы не будем останавливаться на этом вопросе.

Коды, или числа Гёделя, приводят не только к тому, что арифметическое высказывание можно связать с другим высказыванием, но и к возможности говорить о доказуемости этого высказывания. Например, при заданном утверждении Р мы можем записать арифметическое высказывание, в котором говорилось бы, что "Р недоказуемо". Посмотрим, как достичь этой цели.

Как только выбрано множество аксиом, можно без ошибки определить, какие высказывания доказуемы, а какие нет (хотя это может быть и очень сложно на практике). Каждому доказуемому высказыванию, в свою очередь, соответствует число Гёделя. Итак, у нас есть множество чисел, образованное кодами доказуемых высказываний.

Гёдель доказал, что оно характеризуется четко определенным арифметическим свойством. Другими словами, "быть кодом доказуемого высказывания" — свойство, выраженное на языке арифметики (который использует в качестве базовых элементов сложение, умножение и логические операции). Другими словами, свойство "х — это код доказуемого высказывания" может сводиться к числовому свойству, выраженному в терминах сумм, произведений и логических операций. Как обычно говорят, понятие доказуемости можно выразить.

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

Все принципы математики сводятся к принципам логики.

Уиллард ван Орман Куайн. "С точки зрения логики"

Как Гёдель доказал, что понятие доказуемости можно выразить? Для начала он доказал, что любое числовое свойство, проверяемое алгоритмически (например, "быть простым числом", "быть четным" или "делиться на 9"), всегда можно выразить с помощью сумм, произведений и логических операций.

Итак, то, что высказывание Р доказуемо, означает, что существует доказательство (принимаемое программой Гильберта), в котором Р — это конечное высказывание. В качестве примера мы уже приводили доказательство того, что "4 = 2 + 2" на основе аксиом "S(x + у) = х + S(y)" и "х + 1 = S(x)". Вспомним, что этому доказательству, с учетом последовательности высказываний, соответствует число Гёделя 2414871965597. Вспомним также, что "4 = 2 + 2" соответствует число 67. В переводе на язык кодов доказуемость "4 = 2 + 2" означает, что существует конечная последовательность высказываний (ее код 2414871965597), являющаяся доказательством, в котором конечное высказывание имеет код 67.

"Быть кодом доказательства" — это свойство, проверяемое алгоритмически, поскольку при заданном коде для осуществления проверки компьютер сначала использовал бы программу, восстанавливающую последовательность высказываний, соответствующую этому коду, а затем применил бы к этой последовательности высказываний алгоритм, который определяет, идет ли речь о доказательстве:

Код последовательности -> Последовательность высказываний -> Это доказательство?