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

Прежде чем продолжить, разберем это свойство. Простые числа — это числа, которые делятся только на единицу и на самих себя. Существует бесконечное число простых чисел: 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 — нечетное число" действительно относится к самому себе и может быть переведено как "мой код — нечетное число".

Да, так и есть, можно построить высказывание, относящееся к его собственному коду. В своей статье Гёдель изложил систематический метод, позволяющий записать арифметические высказывания, относящиеся к собственному коду. Если Р — это любое арифметическое свойство (такое, как "быть четным числом" или "быть простым числом"), то этот метод — метод самореференции — объясняет, как записать высказывание, которое может означать "мой код выполняет свойство Р". Основной инструмент этого метода — функция d(x), которую Гёдель назвал диагональной.

Функция — это правило, которое каждому числу х ставит в соответствие другое число. Оно может совпадать с х или отличаться, но вычисляется однозначно (одному и тому же х не могут соответствовать два разных числа). Правилами могут быть "умножить число х само на себя" или "прибавить 3 к числу х". Для числа 2 первая функция даст значение 4, а вторая — 5. В частности, нас интересуют функции, которые могут быть выражены в терминах сумм, произведений и логических операций.

Пропозициональные функции получили это название, потому что они похожи на функции, но ставят в соответствие не числа, а высказывания. Например, пропозициональная функция "х — четное число" сопоставляет числу 2 высказывание "2 — четное число".

В запись пропозициональных функций мы можем ввести числовые функции, если только они могут быть выражены в терминах сумм, произведений и логических операций. Так, мы можем записать: "х + 3 — простое число" или даже "х² делится на 18", и в обоих случаях это полноправные пропозициональные функции.

Теперь рассмотрим определение функции d(x), которая на самом деле вычисляется только для чисел, являющихся кодами пропозициональных функций. Поясним определение на примере. Возьмем код пропозициональной функции, например 171, который, как мы предположили, является числом Гёделя выражения "х — четное число". Далее в этой пропозициональной функции заменим х числом 171. Мы получим высказывание "171 — четное число". Код этого высказывания — d( 171), число, которое диагональная функция назначает числу 171:

171 → соответствует "х — четное число" → заменяем х на 171 → "171 — четное число" → d(171) — код "171 — четное число".

В первых примерах мы указали, что "171 — четное число" имеет код, равный 61. Следовательно, d(171) = 61. Диагональная функция сопоставляет числу 171 значение 61.

Во втором примере вычислим d(162), где 162 — это код "отделится на 18":

162 → соответствует "х делится на 18" → заменяем х на 162 → "162 делится на 18" → d(162) — это код "162 делится на 18".

Так как "162 делится на 18" имеет код 103, то d(162) = 103. Все шаги, определяющие диагональную функцию, могут быть вычислены алгоритмически, следовательно, ее определение можно выразить с помощью сумм, произведений и логических операций. Это обстоятельство дает нам право ввести числовую функцию d(x) в выражение пропозициональной функции, точно так же как в предыдущих примерах мы это делали с х² или х + 3. Таким образом мы можем рассмотреть выражение "d(x) — четное".

Предположим, что "d(x) — четное" соответствует код 423, и применим эту процедуру для вычисления d(423):

423 —> соответствует "d(x) — четное" -" заменяем х на 423 —" —" "d(423) — четное" —> d(423) — код "d(423) — четное".

Возьмем любое натуральное число, например 25. На его основе построим последовательность чисел, называемую последовательностью Гудстейна для числа 25 (названа в честь Рубена Луиса Гудстейна (1912-1985), английского математика, который впервые ее определил). Для получения второго числа последовательности запишем 25 как сумму степеней числа 2 так, чтобы каждая степень появлялась ровно один раз (1 — это тоже степень числа 2, поскольку 2⁰ = 1):

25 = 2⁴+2³+1.

И запишем также каждый показатель степени как сумму степеней числа 2:

25 = 2^2² +2²⁺¹ + 1.

Второй член последовательности получается, если заменить каждое 2 на 3 в выражении 222 + 2²⁺¹ +1 и затем вычесть 1:

(З^3³ + З³⁺¹ +1) - 1 = З^3³ + З³⁺¹ = 7625597485068

Второе число последовательности Гудстейна для числа 25 — это 7625597485068. Для получения третьего числа заменяем каждое 3 на 4 в З^3³ + З³⁺¹ и вычитаем 1. Получается 4^4⁴ + 4⁴⁺¹ - 1, операция, которая в результате дает число из 155 цифр. Прежде чем перейти к следующему шагу, надо записать 4^4⁴ + 4⁴⁺¹ - 1 как сумму степеней числа 4, в которой каждая степень появляется самое большое 3 раза и в которой показатели степени также являются суммой степеней числа 4. Заметьте, что 4^4⁴ + 4⁴⁺¹ - 1 не записано таким образом, поскольку присутствует вычитание. Правильная запись: