Пропозициональные функции получили это название, потому что они похожи на функции, но ставят в соответствие не числа, а высказывания. Например, пропозициональная функция "х — четное число" сопоставляет числу 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, поскольку 20 = 1):
25 = 24+23+1.
И запишем также каждый показатель степени как сумму степеней числа 2:
25 = 22² +22+1 + 1.
Второй член последовательности получается, если заменить каждое 2 на 3 в выражении 222 + 22+1 +1 и затем вычесть 1:
(З3³ + З3+1 +1) - 1 = З3³ + З3+1 = 7625597485068
Второе число последовательности Гудстейна для числа 25 — это 7625597485068. Для получения третьего числа заменяем каждое 3 на 4 в З3³ + З3+1 и вычитаем 1. Получается 44⁴ + 44+1 - 1, операция, которая в результате дает число из 155 цифр. Прежде чем перейти к следующему шагу, надо записать 44⁴ + 44+1 - 1 как сумму степеней числа 4, в которой каждая степень появляется самое большое 3 раза и в которой показатели степени также являются суммой степеней числа 4. Заметьте, что 44⁴ + 44+1 - 1 не записано таким образом, поскольку присутствует вычитание. Правильная запись:
44⁴ + 44 + 44 + 44 + 41+1+1 + 41+1+1 + 41+1+1 + 41+1 + 41+1 + 41+1 + 4 + 4 + 4 + 1 + 1 + 1.
Чтобы получить четвертое число, заменим каждое 4 на 5 и вычтем 1. То есть:
55⁵ + 55 + 55 + 55 + 51+1+1 + 51+1+1 + 51+1+1 + 51+1 + 51+1 + 51+1 + 5 + 5 + 5 + 1 + 1.
Результат последнего вычисления состоит из более чем 2000 цифр. Для получения следующего числа заменим каждое 5 на 6 и вычтем 1, и так далее. Кажется, что последовательность растет до бесконечности. Однако в теореме Гудстейна, доказанной им около 1950 года, утверждается, что вне зависимости от исходного числа последовательность всегда за конечное количество шагов достигнет 0. В доказательстве Гудстейна были использованы понятия теории множеств и оставалась открытой возможность того, что оно неосуществимо на основе аксиом Пеано. Это было подтверждено в 1982 году Лори Кирби и Джеффом Пэрисом, которые доказали, что теорема Гудстейна действительно недоказуема на основе аксиом Пеано с помощью рассуждений, проверяемых алгоритмически.
Посмотрим внимательно на последний шаг: d(423) — это код "d(423) — четное". То есть "d(423) — четное число" может читаться как самореферентное высказывание, говорящее о своем собственном коде следующее: "мой код — четное число". Если бы у "d(423) — четное число" кодом было 503, то высказывание можно было бы записать как "503 — четное число" и в нем бы ложно утверждалось, что его собственный код — четное число.
Метод самореференции говорит, что эта процедура может применяться к любому арифметическому свойству Р Возьмем пропозициональную функцию "х выполняет свойство Р" и трансформируем ее в "d(x) выполняет свойство Р". Если код последнего выражения — число я, то "d(n) выполняет свойство Р" может быть прочитано посредством кодификации Гёделя как самореферентное высказывание, гласящее: "мой код выполняет свойство Р". Теперь посмотрим, как этот метод приведет нас в итоге к искомому высказыванию G.
Мы уже сказали, что "быть кодом доказуемого высказывания" — это свойство, которое можно выразить в терминах сумм, произведений и логических операций. Очевидно, что то же самое происходит и с его отрицанием. Следовательно, мы можем записать пропозициональную функцию:
"x: не является кодом доказуемого высказывания", что, как говорится в методе самореференции, превращается в: "d(x) не является кодом доказуемого высказывания". Если его код — число т, то:
G: "d(m) не является кодом доказуемого высказывания"
имеет в качестве кода число d(m) и может рассматриваться как самореферентное высказывание, говорящее о своем коде следующее: "мой собственный код не соответствует доказуемому высказыванию". Другими словами, в G говорится:
"G недоказуемо".
Как мы видели в начале доказательства, это высказывание является истинным и одновременно недоказуемым (вспомним, что "доказуемый" всегда означает "доказуемый на основе предложенных аксиом"). Мы доказали, что существует высказывание G, являющееся истинным и недоказуемым, и описали шаги, необходимые для того, чтобы записать его. Этим завершается доказательство первой теоремы Гёделя о неполноте.
ПАРАДОКС ЛЖЕЦА
Один из самых древних известных парадоксов — это так называемый парадокс лжеца. Он возникает, если поставить вопрос, является ли утверждение "это предложение ложное" истинным или ложным. Если утверждение истинно, то, судя по его смыслу, оно оказывается ложным. Но если оно ложно, то оно получается истинным. Так мы сталкиваемся с бессмыслицей, порочным кругом, который снова и снова приводит нас от истинности к ложности и от ложности к истинности. В своей статье 1931 года Гёдель объяснил, что его доказательство найдено под влиянием парадокса лжеца, только вместо того чтобы написать высказывание, говорящее о собственной ложности, Гёдель написал высказывание, говорящее о собственной недоказуемости. Высказывание "это предложение ложно" — парадоксальная бессмыслица. Но высказывание "это предложение недоказуемо на основе предложенных аксиом" — недоказуемая истина.
Важное пояснение: рассуждение, которое мы провели, на самом деле не является формальным доказательством первой теоремы Гёделя о неполноте. Это только введение, полезное для понимания основных идей, но не объясняющее специфических деталей того, как эти идеи применяются на практике. Если читателя заинтересовали детали, он может углубиться в технические работы по математической логике.
Как выглядело бы высказывание G в нашем гипотетическом примере? Вспомним, что в этом примере свойство, характеризующее коды доказуемых высказываний, — это "быть простым числом, которое может быть записано как сумма или разность трех последовательных простых чисел". Возьмем пропозициональную функцию "х не является простым числом, которое может быть записано как сумма или разность трех последовательных простых чисел" и трансформируем ее в "d(x) не является простым числом, которое может быть записано как сумма или разность трех последовательных простых чисел". Предположим, что последнему выражению соответствует число 909.