Кирби и Парис: неполнота приходит в обычную арифметику

Возражение, которое звучало полвека

С теоремами Гёделя работающие математики мирились легко, и вот почему.

Недоказуемое утверждение, которое ГёдельКурт Гёдельавстрийский и американский логик · 1906–1978Доказал, что в любой достаточно богатой формальной системе есть истинные утверждения, которые она не может доказать, — и тем закрыл программу Гильберта в двадцать пять лет. предъявил, говорит о себе, что оно недоказуемо. Второе — что система непротиворечива. Оба — про саму систему, не про числа. Ни одно из них не возникнет у человека, занятого простыми числами, диофантовыми уравнениями или суммами рядов.

Отсюда удобная позиция: неполнота есть, но она в стороне от математики. Пусть логики развлекаются, а мы будем доказывать теоремы.

Позиция продержалась до 1977 года.

Оговоримся заранее: возражение было отчасти справедливым уже тогда. Проблема тождества слов (НовиковПётр Сергеевич Новиковсоветский математик · 1901–1975Перенёс неразрешимость из оснований математики в обычную алгебру: доказал, что нет алгоритма, распознающего равенство двух слов в группе. Отец С. П. Новикова, с которым его постоянно путают., 1955) и десятая проблема Гильберта (Матиясевич, 1970) показали, что неразрешимость приходит в обычную алгебру и теорию чисел. Но это про алгоритмы; вопрос о недоказуемости в PA конкретного утверждения о натуральных числах оставался открытым.

Кто и где

Джефф Парис и Лео Харрингтон в 1977 году, а затем Лори Кирби и Парис в 1982-м закрыли его.

Парис и Кирби работали в Манчестерском университете (Харрингтон — в Беркли). Оговорка нужна, потому что в популярных пересказах место действия регулярно превращают то в Париж, то в Лондон: первое — из-за фамилии Paris, второе — из-за журнала, «Bulletin of the London Mathematical Society», где вышла статья 1982 года.

Первый пример: усиленная теорема РамсеяФрэнк Пламптон Рамсейанглийский математик, философ и экономист · 1903–1930Доказал, что полный беспорядок невозможен: в любой достаточно большой структуре найдётся большой упорядоченный кусок. Теорема была у него вспомогательной леммой. Умер в двадцать шесть лет, успев основать три…

Конечная теорема Рамсея говорит: при заданных $n$, $k$, $m$ найдётся такое $N$, что как ни раскрась $n$-элементные подмножества набора $\{1,\dots,N\}$ в $k$ цветов, отыщется одноцветное подмножество из $m$ элементов. Утверждение это в арифметике ПеаноДжузеппе Пеаноитальянский математик и логик · 1858–1932Аксиоматизировал натуральный ряд, векторное пространство и математическую запись — и построил кривую, которая проходит через каждую точку квадрата. доказывается.

Парис и Харрингтон изменили одно слово. Потребуем, чтобы одноцветное подмножество $H$ было вдобавок относительно большим:

$$|H| \geqslant \min H$$

— в нём должно быть не меньше элементов, чем величина его наименьшего элемента.

Условие на вид безобидное. Утверждение по-прежнему истинно — это доказывается стандартными средствами теории множеств. Но в арифметике Пеано оно недоказуемо.

Первое утверждение такого рода: комбинаторное, естественное, никак не говорящее о себе.

Второй пример: последовательности Гудстейна

Пример 1982 года ещё нагляднее, и его можно объяснить восьмикласснику.

Возьмём число и запишем его в наследственной записи по основанию 2: разложим по степеням двойки, потом так же разложим показатели, потом показатели показателей — пока в записи не останется ничего, кроме двоек, единиц и знаков.

$$266 = 2^{8} + 2^{3} + 2 = 2^{2^{2+1}} + 2^{2+1} + 2 .$$

Теперь шаг последовательности Гудстейна:

1. заменить все двойки на тройки (везде, включая показатели);
2. вычесть единицу.

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

Первый шаг увеличивает число резко: старший член $2^{2^{2+1}} = 2^{8} = 256$ превращается в $3^{3^{3+1}} = 3^{81}$ — число из тридцати девяти цифр. Вычитание единицы на этом фоне выглядит издевательством.

Теорема Гудстейна (1944): всякая такая последовательность в конце концов приходит к нулю.

Не «некоторые» — всякая, с любого начального числа.

Посмотреть, как это работает, на маленьких числах

Начнём с 3.

Основание	Запись	Заменили	Вычли 1
2	$2+1$	$3+1=4$	$3$
3	$3$	$4$	$3$
4	$3$	$3$	$2$
5	$2$	$2$	$1$
6	$1$	$1$	$0$

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

Начнём с 4, то есть с $2^{2}$.

Основание	Запись	Заменили	Вычли 1
2	$2^{2}$	$3^{3}=27$	$26$
3	$2\cdot3^{2}+2\cdot3+2$	$2\cdot4^{2}+2\cdot4+2=42$	$41$
4	$2\cdot4^{2}+2\cdot4+1$	$2\cdot5^{2}+2\cdot5+1=61$	$60$
5	$2\cdot5^{2}+2\cdot5$	$2\cdot6^{2}+2\cdot6=84$	$83$
6	$2\cdot6^{2}+6+5$	$2\cdot7^{2}+7+5=110$	$109$

Растёт. И будет расти долго: наибольшее значение этой последовательности равно $3\cdot 2^{402653211}-1$, а нуля она достигает через $3\cdot 2^{402653211}-2$ шагов. Тем не менее достигает.

Почему она всё-таки приходит к нулю

Доказательство Гудстейна занимает полстраницы, и оно замечательно.

Сопоставим каждому члену последовательности ординал: в наследственной записи заменим основание на $\omega$. Для $266$ при основании 2 получится

$$\omega^{\omega^{\omega+1}} + \omega^{\omega+1} + \omega .$$

Теперь посмотрим, что делает шаг.

• Замена основания ординал не меняет вовсе: $\omega$ стоит на месте основания, а какое оно — 2, 3 или 1000 — ординалу безразлично.
• Вычитание единицы ординал строго уменьшает.

Значит, ординалы образуют строго убывающую последовательность. А ординалы вполне упорядочены: бесконечно убывать нельзя. Следовательно, последовательность обрывается — то есть доходит до нуля. $\blacksquare$

Гигантский рост самих чисел — оптический обман. Убывает не число, а его ординал, и убывает он неукоснительно.

И вот здесь появляется ГенценГерхард Генценнемецкий логик · 1909–1945Доказал непротиворечивость арифметики — после того, как Гёдель показал, что этого сделать нельзя. Оба утверждения верны: Генцен вышел за пределы самой арифметики, и его доказательство измеряет, насколько…

Все встречающиеся ординалы меньше $\varepsilon_0$. А доказательство состоит ровно в том, что бесконечного убывания ординалов ниже $\varepsilon_0$ не бывает, — то есть в трансфинитной индукции до $\varepsilon_0$.

Генцен в 1943 году доказал, что именно этот принцип арифметике Пеано недоступен.

Кирби и Парис замкнули круг: они показали, что теорема Гудстейна не просто доказывается трансфинитной индукцией до $\varepsilon_0$, а равносильна ей над арифметикой Пеано. Значит, в PA она недоказуема — а если бы была доказуема, PA доказала бы собственную непротиворечивость вопреки второй теореме Гёделя.

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

Гидра

В той же статье 1982 года — вторая, ещё более наглядная конструкция.

Гидра — дерево. Геракл рубит одну из голов (концевую вершину). После этого гидра отращивает новые: то поддерево, откуда была срублена голова, копируется $n$ раз, где $n$ — номер хода. Растёт она быстрее любой мыслимой скорости рубки.

Теорема: Геракл побеждает при любой стратегии. Как ни руби — гидра погибнет за конечное число ходов.

Доказательство то же самое: дереву сопоставляется ординал ниже $\varepsilon_0$, рубка его уменьшает. И то же следствие: в арифметике Пеано это недоказуемо.

Что из этого вышло

Возражение снято. Утверждения, недоступные арифметике, бывают вполне обыкновенные. Гёделевская щель — не аномалия на границе языка, а свойство самой арифметики.

Появилась мера трудности. Раз теорема Гудстейна равносильна индукции до $\varepsilon_0$, то её «сила» измерена. Так работает обратная математика: для каждой теоремы выясняют, какая именно аксиоматика ей нужна, — и оказывается, что почти вся классическая математика укладывается в пять уровней силы, известных как «большая пятёрка».

Найдены и более сильные примеры. Харви Фридман построил комбинаторные утверждения (теорема Краскала о деревьях, теорема Робертсона — Сеймура о минорах графов), недоказуемые уже в системах гораздо более мощных, чем PA. Функция $\mathrm{TREE}(3)$, выросшая из этого круга задач, — одно из самых больших конкретных чисел, встречающихся в математике.

Между Кёнигсбергом 1930 года и Манчестером 1982-го — пятьдесят два года. Ровно столько понадобилось, чтобы перевести теорему о границах познания с языка логики на язык, где её увидит школьник.

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