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

Главная идея доказательства состоит в том, чтобы получить высказывание G, в котором будет говориться: "G недоказуемо". Другими словами, G может быть записано так: "Это утверждение недоказуемо".

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

Для начала заметим, что 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 — четное число".

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