В 1931 году 25-летний австрийский логик Курт Гёдель совершил невероятное: он разрушил мечту математиков о полном и непротиворечивом фундаменте своей науки. Он доказал, что любой набор аксиом, который можно предложить как основу математики, неизбежно неполон. Всегда найдутся истинные утверждения о числах, которые из этих аксиом не доказать. И никакой набор аксиом не способен доказать собственную непротиворечивость.
С тех пор математики действительно находили неразрешимые вопросы, предсказанные Гёделем. Континуум-гипотеза о размерах бесконечности неразрешима. Проблема остановки — тоже. Неразрешимые вопросы возникают даже в физике.
Как Гёдель это доказал? Он придумал нумерацию: высказывания о системе аксиом превращаются в высказывания о числах внутри самой системы. Сначала он назначил 12 базовым символам номера от 1 до 12: ~ — 1, ∨ — 2, ⊃ — 3, ∃ — 4, = — 5, 0 — 6, s — 7, скобки — 8, 9, запятая — 10, + — 11, × — 12. Переменные x, y, z получили простые числа больше 12.
Любая формула получает свой номер Гёделя. Например, 0=0 превращается в 2^6 × 3^5 × 5^6 = 243 000 000. Декодирование однозначно, ведь разложение на простые множители единственно. Так же кодируются и последовательности формул, то есть доказательства. Даже метаматематические утверждения о формулах становятся арифметическими формулами со своими номерами.
Главный трюк — подстановка. Формула (∃x)(x=sy) имеет номер m. Подставим m вместо y — получим формулу с номером sub(m, m, 17), где 17 — номер y. Теперь Гёдель строит утверждение: «Формула с номером sub(y, y, 17) недоказуема». Пусть его номер n. Подставим n вместо y — получаем G: «Формула с номером sub(n, n, 17) недоказуема». Но sub(n, n, 17) — это номер самой G. Значит, G утверждает: я недоказуема.
Если G доказуема, система противоречива. Если нет — G истинна, но недоказуема, значит система неполна. Добавить аксиому не поможет: возникнет новая G'. Вторая теорема следует из первой: если бы аксиомы доказывали свою непротиворечивость, они бы доказали и G, но это невозможно. Поиски полной и непротиворечивой системы математики умерли. Смысл неполноты, как писали Нагель и Ньюмен в книге «Gödel's Proof» (1958), не разгадан до сих пор. Статья перепечатана на Wired.com.