Для медленного чтения. Как работает доказательство Гёделя

Его теоремы о неполноте разгромили поиск математической теории всего. Почти сто лет спустя мы всё ещё пытаемся осмыслить последствия этого.

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

Математики той эпохи искали неколебимые основы математики: набор базовых фактов, аксиом, которые были бы непротиворечивыми и полными, играя роль строительных блоков всех математических истин.

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

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

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

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

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

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

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

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

Затем этим двенадцати символам назначаются номера Гёделя с 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² — не является.

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

Если вам интересно, то формулировка получается такая: существует такое целое х, что х, помноженное на 2, будет равно 2¹ × 3⁸ × 5⁶ × 7⁵ × 11⁶ × 13⁹, но не существует такого целого х, чтобы оно, помноженное на 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).

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

Преобразовать в символы можно и метаматематические утверждения. „Существует некая последовательность формул с номером Гёделя х, доказывающая формулу с номером Гёделя k“ – или, короче говоря, „формула с номером Гёделя k доказуема“. Именно возможность „арифметизировать“ подобные заявления и заложила основы переворота.
 

G само по себе

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

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

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

Подстановка формирует основу доказательства Гёделя.


Студент Курт Гёдель в Вене. Теоремы о неполноте он опубликовал в 1931 году, через год после получения диплома.

Он рассмотрел следующее математическое утверждение: „Формулу с номером Гёделя 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. И сегодня это утверждение остаётся истинным.