У интуиции есть своя логика. Гёдель. Теоремы о неполноте. - Gustavo Pineiro

Для начала заметим, что G либо истинно, либо ложно. Если бы G было ложно, в связи с тем, что в G говорится о самом себе, можно было бы сделать вывод, что G доказуемо. Следовательно, G было бы одновременно ложным и доказуемым, но это невозможно (ведь мы сказали, что исходя из истинных аксиом можно доказать только истинные высказывания). Следовательно, G не может быть ложным.

Следовательно, G истинно, и согласно тому, что оно говорит о самом себе, оно недоказуемо. Так мы делаем вывод, что G — истинное и недоказуемое высказывание (см. схему).

Предыдущая идея, хотя и правильная в целом, имеет одну проблему: G должно быть арифметическим утверждением. Но арифметические высказывания относятся к свойствам натуральных чисел, в них не говорится о других высказываниях и тем более о самих себе. Как мы можем преодолеть это ограничение и сделать так, чтобы арифметическое высказывание относилось к другому высказыванию? Если в высказываниях говорится о числах, а нам надо, чтобы в них говорилось о других утверждениях, то нужно приравнять числа к утверждениям:

Числа ↔ Утверждения.

Требуется связать с каждым арифметическим высказыванием какое-нибудь натуральное число так, чтобы замечание об этом числе было равносильно замечанию о соответствующем утверждении. Например, если бы утверждению соответствовало число 457, мы могли бы считать, что в любом высказывании, в котором речь идет о 457, одновременно речь идет о Р.

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

"4 = 2 + 2" ↔ код 67

"2 — четное число" ↔ код 223

"162 делится на 18" ↔ код 103

"4 — нечетное число" ↔ код 149

"171 — четное число" ↔ код 61.

Мы настаиваем: коды не назначаются наугад или произвольно. Напротив, существует алгоритм, который при заданном высказывании позволяет точно вычислить его код. Также существует обратный алгоритм, который при заданном коде может восстановить высказывание, которому он соответствует. Более того, в действительности коды, если их правильно вычислить, могут содержать десятки цифр. Например, при реальном вычислении утверждению "1 = 1" соответствует код 2187000000000.

Заметим, что в нашем примере два последних высказывания ложны. Это показывает, что числа Гёделя назначаются всем высказываниям, как истинным, так и ложным. С технической целью числа Гёделя также назначаются общим выражениям, таким как "х — четное число" или "х делится на 18". Они относятся не к конкретному числу, а к переменному числу х. Эти выражения Бертран Рассел называл пропозициональными функциями.

Сами по себе пропозициональные функции не являются высказываниями, поскольку высказывание по определению должно быть истинным или ложным, в то время как истинность или ложность фразы "х — четное число" зависит от значения х. Каждый раз, когда мы заменяем х конкретным числом, мы получаем высказывание, которое будет истинным или ложным в зависимости от выбранного числа. Например, если в "х — четное число" заменить х числом 8, то мы получим истинное высказывание "8 — четное число". Наоборот, если заменить х числом 3, мы получим ложное высказывание "3 — четное число".

Мы уже сказали, что каждой пропозициональной функции также назначается число Гёделя (как и для высказываний, эти коды вычисляются с помощью установленного алгоритма). Например, мы можем представить, что:

"х делится на 18" ↔ код 162

"х — четное число" ↔ код 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, который мы вычислили как произведение кодов высказываний, его образующих (они указаны рядом с соответствующим высказыванием).

Как в действительности определяется нумерация Гёделя? Чтобы определить ее, каждое высказывание и каждая пропозициональная функция должны быть выражены с помощью символов формального языка. Ученый назначил каждому символу этого языка нечетное число.

 1

=> 3

┐ 5

= 7

1 9

S 11

+ 13

· 15

( 17

) 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 берутся по порядку коды высказываний, образующих последовательность, а на последнем шаге они становятся показателями степеней простых чисел.

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

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

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

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

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