Хавьер Фресан - Том. 22. Сон разума. Математическая логика и ее парадоксы

Приведем простейший пример. Напомним, что число Гёделя для второй аксиомы Пеано равно

2 3·3 5·5 11·7 3·11 5·13 13·17 7·19 13·23 6·29 2·31 11·37 8.

Так как определяющее свойство аксиом гласит, что они являются доказательством самих себя, то если мы подставим вышеприведенное число вместо х и z в D( х , z), результат будет истинным: последовательность формул для числа Гёделя z , состоящая в этом случае лишь из второй аксиомы Пеано, является доказательством формулы, которой соответствует число х — это вновь вторая аксиома Пеано! Однако если мы введем в качестве значения z число 2 3·3 5·5 11·7 7·11 2·13 11·17 6·19 1·23 8, механизм D( х, z ) выдаст результат «ложь», так как формула, соответствующая этому числу, не является доказательством второй аксиомы Пеано. Тот факт, что формула для числа Гёделя х доказуема, означает, что существует число z такое, что после довательность формул, соответствующая z , является доказательством формулы, связанной с х . Иными словами, существует z такое, что высказывание D( х, z ) является истинным. Как следствие, формула z D( х, z ), которую для краткости будем обозначать Dem ( х ), гласит, что формула, соответствующая числу Гёделя х , доказуема. Вкратце повторим вышеизложенное: если бы существовала формула D , то благодаря «гёделизации» все тонкости доказуемости высказываний можно было бы свести к простому отношению между натуральными числами х и z . Какая же теория рассматривает подобные отношения? Арифметика!

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

z = p k1 · p k2 · p k3 ·…· р kn .

Итак, мы разложили число z на простые множители, возведенные в различные степени. Так как z соответствует последовательности формул, то каждый показатель степени будет числом Гёделя для одной из этих формул. Таким образом, мы можем определить числа Гёделя для всех формул последовательности, которые обозначим

k 1, k 2, k 3 … k n .

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

— первый шаг: последовательность формул с числами Гёделя k 1, k 2, k 3 … k n является доказательством, то есть каждому из этих чисел соответствует либо аксиома, либо высказывание, которое получено из предыдущих с помощью правил вывода;

— второй шаг: последняя формула последовательности — это формула, которую мы хотим доказать.

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

Теперь перейдем к первому этапу нашей гонки с препятствиями и рассмотрим формулы, которым соответствуют числа Гёделя k 1, k 2, … k n . Именно здесь обязательно должно выполняться условие рекурсивной перечислимости системы аксиом арифметики — ранее это условие казалось не более чем причудой. Напомним, что множество аксиом S является рекурсивно перечислимым, когда за конечное число шагов можно показать, является некоторое высказывание аксиомой или нет. Следовательно, в нашем распоряжении находится формула А(х) (А — по первой букве слова «аксиома»), которая для любого числа х позволяет определить, является ли соответствующее ему высказывание аксиомой. Достаточно вычислить А(k 1), А(k 2) … А(k n), и мы узнаем, какие из высказываний предполагаемого доказательства являются аксиомами. Первая формула, которой соответствует число Гёделя обязательно должна быть аксиомой, так как ей не предшествуют формулы, из которых ее можно было бы вывести. Следовательно, если результат А(k 1) случайно окажется ложным, дальнейшие действия не потребуются: z не является числом Гёделя, соответствующим доказательству. Предположим, что этого не произошло.