У интуиции есть своя логика. Гёдель. Теоремы о неполноте - [19]
"х — четное число" ↔ код 171.
Заметим, что "х — четное число" назначается код 171, в то время как высказыванию "2 — четное число" соответствует код 223. Коды разные, и это правильно, поскольку речь идет о разных лингвистических объектах. Точно так же "1 — четное число", "3 — четное число", "4 — четное число" имеют разные числа Гёделя.
Наконец, число Гёделя также назначается каждой конечной последовательности высказываний (которое вычисляется на основе кодов высказываний, образующих последовательность). Идея этого назначения в том, чтобы гарантировать, что каждое доказательство также можно будет идентифицировать по его коду. Например, следующему доказательству того, что "4 = 2 + 2" на основе аксиом "S(x + у) = х + S(y)" и "х + 1 = = S(x)":
S(x + y)=x + S(y) 173
S(2 + 1)-2+ S(1) 199
S(2 + 1) = 2+ 2 13
х + 1 = 5(х) 37
2 + 1 = 5(2) 83
2 + 1=3 7
S(3) = 2+ 2 251
4 = 2 + 2 67
может соответствовать (гипотетически) код 2414871965597, который мы вычислили как произведение кодов высказываний, его образующих (они указаны рядом с соответствующим высказыванием).
Как в действительности определяется нумерация Гёделя? Чтобы определить ее, каждое высказывание и каждая пропозициональная функция должны быть выражены с помощью символов формального языка. Ученый назначил каждому символу этого языка нечетное число.
=> 3
┐ 5
= 7
1 9
S 11
+ 13
· 15
( 17
) 19
x>1 21
х>2 23
х>3 25
Количество переменных потенциально бесконечно. Оставшимся (х>4, х>5, ...) соответствуют числа 27, 29 и так далее. Гёдель назначил коды высказываний и пропозициональных функций. Для большей ясности объясним метод на конкретном примере. Какой код соответствует, например, высказыванию "1 = 1"? Шаги для его вычисления следующие.
1. Сначала остановимся на кодах символов, образующих высказывание: 9, 7,9.
2. Поскольку есть три символа, теперь возьмем по порядку три первых простых числа: 2, 3, 5.
3. Тогда код следующий: 2>9 · З>7 · 5>9 = 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.
