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

Каждый шаг может осуществляться алгоритмически.

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

Наконец, делаем вывод, что выражение "существует некое у у являющееся кодом доказательства, заканчивающегося высказыванием с кодом х" также можно выразить арифметическими терминами. Фактически в этом утверждении говорится, что существует некое доказательство высказывания с кодом х удругими словами — что высказывание с кодом х доказуемо. Так мы приходим к выводу, что пропозициональную функцию "х — это код доказуемого высказывания" можно выразить арифметическими терминами.

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

Прежде чем продолжить, разберем это свойство. Простые числа — это числа, которые делятся только на единицу и на самих себя. Существует бесконечное число простых чисел: 2,3,5, 7,11,13,17, 19, 23,... (как уже говорилось в предыдущей главе, по техническим причинам число 1 не считается простым).

Число 23, например, простое и может быть записано как сумма или разность трех последовательных простых чисел, поскольку 23 =17 +19 -13 (заметим, что 13, 17 и 19 идут друг за другом в цепочке простых чисел, при выполнении операций их записали в другом порядке). В нашем примере мы можем убедиться, что 23 — это код доказуемого высказывания. Наоборот, 149 — это простое число, которое не может быть записано как сумма или разность трех последовательных простых чисел. Но 149 в нашем гипотетическом примере — это код высказывания "4 — нечетное число". Следовательно, говорить, что "149 не является простым числом, которое можно записать как сумму или разность трех последовательных простых чисел" равносильно тому, чтобы сказать: "высказывание о том, что 4 — нечетное число, является недоказуемым" (и действительно, оно недоказуемо, потому что мы предположили: аксиомы — это истинные высказывания, следовательно, всякое ложное высказывание недоказуемо). Повторим это понятие, поскольку это сердце доказательства Гёделя. Высказывание:

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

"высказывание о том, что 4 — нечетное число, является недоказуемым".

Существует два уровня прочтения "149 не является простым числом, которое можно записать как сумму или разность трех последовательных простых чисел". С одной стороны, чисто арифметически это дословный уровень, на котором мы истолковываем высказывание, выражая свойства числа 149. С другой стороны, у нас есть высший уровень прочтения, метаматематический, зависящий от нумерации Гёделя, и на нем мы истолковываем высказывание, говоря, что утверждение "4 — нечетное число" недоказуемо.

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

Предположим, что 101 — это код некоего высказывания Q. При таком предположении высказывание "101 — нечетное число" относится к Q и означает "код высказывания Q нечетный". Теперь представим себе, что мы ищем, какому высказыванию соответствует код 101 (то есть задаемся вопросом, что такое Q), и выясняем, что 101 — это число Гёделя для "101 — нечетное число". В этом случае "101 — нечетное число" действительно относится к самому себе и может быть переведено как "мой код — нечетное число".