Питер Эткинз - Десять великих идей науки. Как устроен наш мир.

Математическое доказательство состоит из строки предложений, которые выводятся одно из другого с помощью использования правил обращения с символами. Это означает, что мы можем приписать отдельный номер целому доказательству , отметив гёделевские номера всех входящих в него предложений. Если доказательство состоит из трех предложений с гёделевскими номерами 6, 8 и 2 (на практике эти номера были бы огромны), то всему доказательству приписывается номер 2 6× 3 8× 5 2= 10 497 600 (для более длинных доказательств ряд простых чисел 2, 3, 5 последовательно продолжают). Как вы можете вообразить, длинные доказательства, состоящие из сложных предложений, имеют астрономически большие гёделевские номера. И снова смыслом этой процедуры является то, что целые доказательства включаются в область арифметики. Мы можем использовать арифметические процедуры, чтобы, например, судить, используется ли одно доказательство в другом, определяя, входит ли гёделевский номер первого множителем в гёделевский номер второго, подобно тому, как 15 = 5 × 3 означает, что 5 и 3 являются компонентами 15.

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

Предположим, что у нас есть некоторое предложение относительно числа 0, мы назовем это предложение p 0(0) , и такое же предложение относительно числа 1, которое мы назовем p 0(1) , и так далее. Обозначим вообще это предложение относительно числа x как p 0(x) . Эти предложения могут быть истинными, а могут ложными. Например, предложение «квадратный корень из x равен 1» в случае p 0(0) ложно, поскольку утверждает, что √0 = 1, что неверно, но в случае p 0(1) оно истинно, так как √1 = 1. Каждое из этих предложений имеет гёделевский номер, который мы можем вычислить, и существует бесконечное число таких предложений относительно каждого из бесконечного числа натуральных чисел. Обозначим эти предложения как p 0(x), p 1(x) и так далее: некоторые из них являются мусором, некоторые верны. Организуем теперь все соответствующие им гёделевские номера в огромную таблицу (с астрономически большими номерами там, где мы подставили малые номера). Верхний левый фрагмент этой таблицы может быть чем-то вроде:

где каждое число во внутренних клетках таблицы есть (фальшивый) гёделевский номер соответствующего предложения. Так, фальшивый гёделевский номер предложения p 3(x) относительно числа 2 равен 11.

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

И здесь, как и в аргументах Тьюринга, нас ожидает провал. Рассмотрим следующее предложение:

«Диагональным членом» является предложение относительно собственного номера предложения, например, предложение p 2 относительно числа 2. Поскольку это утверждение является предложением, оно должно уже содержаться где-то в первоначальном исчерпывающем списке предложений. Для простоты давайте предположим, что оно оказывается Предложением 2. Коль это так, рассмотрим соответствующий диагональный гёделевский номер, который в этом случае равен 30. Этот гёделевский номер соответствует Предложению 2 относительно числа 2, которое гласит: