Как устроено доказательство Гёделя

В 1931 году австрийский логик Курт Гёдель совершил одно из самых поразительных интеллектуальных достижений в истории науки.

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

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

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

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

Ниже — упрощённое, неформальное изложение того, как Гёдель доказал свои теоремы.

Нумерация Гёделя

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

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

Слегка модифицированная версия схемы Гёделя, представленная Эрнестом Нагелем и Джеймсом Ньюманом в их книге 1958 года «Доказательство Гёделя», начинается с 12 элементарных символов, служащих словарём для записи базовых аксиом. Например, утверждение «нечто существует» выражается символом ∃, а сложение — символом +. Важно, что символ s, обозначающий «следующее за», даёт способ задавать числа: например, ss0 означает 2.

Этим двенадцати символам присваиваются числа Гёделя от 1 до 12.

Далее буквы, обозначающие переменные — начиная с x, y и z, — отображаются на простые числа больше 12 (то есть 13, 17, 19 и так далее).

Затем любая комбинация этих символов и переменных — то есть любая арифметическая формула или последовательность формул, которую можно построить, — получает собственное число Гёделя.

Рассмотрим, например, 0 = 0. Три символа этой формулы соответствуют числам Гёделя 6, 5 и 6. Гёделю нужно превратить эту последовательность из трёх чисел в единственное уникальное число — такое, которое не сможет породить никакая другая последовательность символов. Для этого он берёт первые три простых числа (2, 3 и 5), возводит каждое в степень, равную числу Гёделя символа на соответствующей позиции последовательности, и перемножает результаты. Так 0 = 0 превращается в 2⁶ × 3⁵ × 5⁶, то есть 243 000 000.

Отображение работает потому, что никакие две формулы никогда не получат одинаковое число Гёделя. Числа Гёделя — целые числа, а целые числа раскладываются на простые множители единственным способом. Поэтому единственное разложение числа 243 000 000 на простые множители — это 2⁶ × 3⁵ × 5⁶, а значит, есть лишь один способ декодировать это число Гёделя: формула 0 = 0.

Гёдель пошёл ещё дальше. Математическое доказательство состоит из последовательности формул. Поэтому Гёдель присвоил уникальное число Гёделя и каждой последовательности формул. В этом случае он снова начинает со списка простых чисел — 2, 3, 5 и так далее, — возводит каждое простое число в степень, равную числу Гёделя формулы на соответствующей позиции последовательности (например, 2^{243 000 000} × …, если 0 = 0 стоит первым), и перемножает всё вместе.

Арифметизация метаматематики

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

Рассмотрим сначала формулу ~(0 = 0), означающую «ноль не равен нулю». Эта формула явно ложна. Тем не менее у неё есть число Гёделя: 2 в степени 1 (число Гёделя символа ~), умноженное на 3 в степени 8 (число Гёделя символа «открывающая скобка»), и так далее, что даёт 2¹ × 3⁸ × 5⁶ × 7⁵ × 11⁶ × 13⁹.

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

Рассмотрим утверждение: «Первый символ формулы ~(0 = 0) — тильда». Это (истинное) метаматематическое утверждение о ~(0 = 0) переводится в утверждение о числе Гёделя формулы — а именно, что первый показатель степени равен 1, числу Гёделя тильды. Другими словами, наше утверждение говорит, что 2¹ × 3⁸ × 5⁶ × 7⁵ × 11⁶ × 13⁹ содержит только один множитель 2. Если бы формула ~(0 = 0) начиналась с любого другого символа, кроме тильды, её число Гёделя содержало бы по меньшей мере два множителя 2. Точнее говоря: 2 является делителем 2¹ × 3⁸ × 5⁶ × 7⁵ × 11⁶ × 13⁹, а 2² — нет.

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

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

Точно так же в символы можно перевести и метаматематическое утверждение: «Существует некоторая последовательность формул с числом Гёделя x, которая доказывает формулу с числом Гёделя k» — или, короче, «Формула с числом Гёделя k доказуема». Возможность «арифметизировать» подобные утверждения подготовила почву для главного удара.

Сама формула G

Дополнительная идея Гёделя заключалась в том, что можно подставить собственное число Гёделя формулы в саму эту формулу — и это ведёт к неисчислимым последствиям.

Чтобы понять, как работает подстановка, рассмотрим формулу (∃x)(x = sy). Она читается как «существует некоторая переменная x, следующая за y», или короче — «у y есть следующий элемент». Как и у всех формул, у неё есть число Гёделя — некоторое большое целое число, которое обозначим m.

Теперь подставим m в формулу вместо символа y. Получится новая формула (∃x)(x = sm), означающая «у m есть следующий элемент». Как назвать число Гёделя этой новой формулы? Нужно передать три единицы информации: исходная формула имела число Гёделя m; в неё подставили m вместо символа y; согласно введённой ранее схеме отображения, символ y имеет число Гёделя 17. Обозначим число Гёделя новой формулы как sub(m, m, 17).

Подстановка — сердцевина доказательства Гёделя.

Гёдель рассмотрел метаматематическое утверждение примерно такого вида: «Формула с числом Гёделя sub(y, y, 17) не может быть доказана». Вспоминая только что введённое обозначение: формула с числом Гёделя sub(y, y, 17) — это та, что получена из формулы с числом Гёделя y (некоторая неизвестная переменная) подстановкой этой же переменной y везде, где встречается символ с числом Гёделя 17 (то есть везде, где стоит y).

Дальше становится ещё более головокружительно, но тем не менее наше метаматематическое утверждение — «Формула с числом Гёделя sub(y, y, 17) не может быть доказана» — обязательно переводится в формулу с уникальным числом Гёделя. Назовём его n.

Теперь последний раунд подстановки: Гёдель создаёт новую формулу, подставляя число n везде, где в предыдущей формуле стоит y. Новая формула звучит так: «Формула с числом Гёделя sub(n, n, 17) не может быть доказана». Назовём эту новую формулу G.

Естественно, у G есть собственное число Гёделя. Каково его значение? И вот сюрприз: это число — sub(n, n, 17). По определению, sub(n, n, 17) — это число Гёделя формулы, получаемой из формулы с числом Гёделя n подстановкой n везде, где стоит символ с числом Гёделя 17. А G — это в точности такая формула! Благодаря единственности разложения на простые множители теперь видно: формула, о которой говорит G, — не что иное, как сама G.

G утверждает о самой себе, что она недоказуема.

Но можно ли доказать G? Если бы это было так, значило бы, что существует последовательность формул, доказывающая формулу с числом Гёделя sub(n, n, 17). Но это противоположно тому, что утверждает G, — а именно, что такого доказательства не существует. Противоположные утверждения, G и ~G, не могут быть одновременно истинными в непротиворечивой аксиоматической системе. Значит, истинность G должна быть неразрешимой.

Однако, хотя G неразрешима, она явно истинна. G утверждает: «Формула с числом Гёделя sub(n, n, 17) не может быть доказана», — и именно это мы и обнаружили! Поскольку G истинна, но неразрешима в рамках аксиоматической системы, использованной для её построения, эта система неполна.

Можно подумать, что достаточно постулировать какую-то дополнительную аксиому, использовать её для доказательства G и разрешить парадокс. Но это невозможно. Гёдель показал, что расширенная аксиоматическая система позволит построить новую истинную формулу G′ (по схожей схеме), которую нельзя доказать уже в новой, расширенной системе. Стремясь к полной математической системе, невозможно поймать собственный хвост.

Невозможность доказать непротиворечивость

Итак, если набор аксиом непротиворечив, то он неполон. Это первая теорема Гёделя о неполноте. Вторая теорема — о том, что ни один набор аксиом не может доказать собственную непротиворечивость, — легко из неё следует.

Что означало бы, если бы набор аксиом мог доказать, что он никогда не приведёт к противоречию? Это означало бы существование последовательности формул, построенных из этих аксиом, которая доказывает формулу, метаматематически означающую «этот набор аксиом непротиворечив». Согласно первой теореме, такой набор аксиом тогда обязательно оказался бы неполным.

Но утверждение «набор аксиом неполон» равносильно утверждению «существует истинная формула, которую нельзя доказать». Это утверждение эквивалентно нашей формуле G. А мы знаем, что аксиомы не могут доказать G.

Так Гёдель выстроил доказательство от противного: если бы набор аксиом мог доказать собственную непротиворечивость, мы могли бы доказать G. Но это невозможно. Следовательно, ни один набор аксиом не может доказать собственную непротиворечивость.

Доказательство Гёделя похоронило поиски непротиворечивой и полной математической системы. Смысл неполноты «до сих пор не осмыслен полностью», писали Нагель и Ньюман в 1958 году. Это остаётся верным и сегодня.

^*Для любопытствующих: утверждение звучит так: «Существует такое целое число x, что x, умноженное на 2, равно 2¹ × 3⁸ × 5⁶ × 7⁵ × 11⁶ × 13⁹, и не существует такого целого числа x, что x, умноженное на 4, равно 2¹ × 3⁸ × 5⁶ × 7⁵ × 11⁶ × 13⁹». Соответствующая формула:

(∃x)(x × ss0 = sss … sss0) ⋅ ~(∃x)(x × ssss0 = sss … sss0)

где sss … sss0 означает 2¹ × 3⁸ × 5⁶ × 7⁵ × 11⁶ × 13⁹ копий символа-преемника s. Символ ⋅ означает «и» и является сокращением более длинного выражения из базового словаря: p ⋅ q — это сокращение для ~(~p ∨ ~q).