Теорема Гудстина: последовательность, которая взрывается, но всегда возвращается к нулю
Возьмите любое целое число. Любое. Теперь применяйте к нему снова и снова простое двухшаговое правило и наблюдайте за результатом. Почти при любом начальном значении последовательность ревёт вверх за гугол, за числа, затмевающие количество атомов во всей наблюдаемой вселенной, за всё, что вы могли бы записать за целую жизнь. И тем не менее, это доказано, она всегда возвращается к нулю.
Вот что такое теорема Гудстина, и, услышав её впервые, она звучит как фокус. Правило нехитрое, числа обычные, утверждение чёткое. Но на протяжении десятилетий причина её истинности не находила пристанища внутри обычной арифметики. Эта статья не просит вас следить за логическим доказательством. Вместо этого она покажет вам картину, которая лежит в основе, и, увидев её однажды, вы перестанете считать теорему загадочной.
Правило почти детски простое
Вы начинаете с целого числа и основания, стартуя с основания 2. На каждом шаге делаете два действия: сначала переписываете текущее число в так называемой наследственной записи в основании n; затем заменяете каждое вхождение основания n на n+1 и вычитаете 1. Потом переходите к следующему основанию и повторяете.
Сдвиг основания и вычитание кажутся мягкими операциями. Сменить основание с 2 на 3 ощущается как небольшое изменение. Вычесть 1 кажется сдерживающим ходом. Дальше вы увидите, почему ни одна из этих интуиций не выживает при встрече с наследственной записью.
Смотрите, как оно взрывается
Начнём с 4. В наследственной записи по основанию 2 это 2^2. Заменяем каждую 2 на 3 и вычитаем 1: получаем 3^3 минус 1, то есть 26. Теперь запишем 26 в наследственной записи по основанию 3, перейдём к основанию 4, вычтем 1 и получим 41. Продолжаем.
| Step | Base | Written in that base | Value |
|---|---|---|---|
| 1 | 2 | 2² | 4 |
| 2 | 3 | 2·3² + 2·3 + 2 | 26 |
| 3 | 4 | 2·4² + 2·4 + 1 | 41 |
| 4 | 5 | 2·5² + 2·5 | 60 |
| 5 | 6 | 2·6² + 6 + 5 | 83 |
| 6 | 7 | 2·7² + 7 + 4 | 109 |
Последовательность, начатая с 4, выглядит так: 4, 26, 41, 60, 83, 109, и дальше продолжает расти. Даже это скромное начало долго идёт вверх, прежде чем в итоге пойдёт вниз. Начните вместо этого с 19, и числа достигнут высот, которые физически невозможно записать. Число шагов до того, как последовательность хотя бы начнёт разворачиваться, больше, чем количество атомов во всей наблюдаемой вселенной. Если бы вы начали вычисления в момент Большого взрыва на самом быстром компьютере, который только можно себе представить, вы бы не увидели пика даже сегодня.
Любой инстинкт говорит: это расходится. Нет возврата из чисел такой величины. Интуиция здесь просто неверна, и именно в этом весь смысл. Происходит что-то невидимое, что сырые числа не показывают.
Скрытое число, которое только убывает
Заменяем каждый член его ординальной тенью
Вот ключевой ход. Возьмите любой член последовательности Гудстина и посмотрите на его наследственную запись в основании n. Теперь везде, где стоит основание n, напишите символ омега (первый бесконечный ординал). Структура выражения не изменилась ни на йоту. Вы просто поменяли ярлык. Результатом является ординальное число, своего рода счётчик, уходящий за пределы целых чисел в бесконечность.
Например, 4 в наследственной записи по основанию 2 это 2^2. Заменим 2 на омегу и получим омега^омега. Ординальная тень числа 26 в наследственной записи по основанию 3 это два умножить на омега в квадрате, плюс два умножить на омегу, плюс два: многочлен конечной высоты в омеге, много меньший, чем омега в степени омега. Показатели 2, 1 и 0 в наследственной записи по основанию 3 уже меньше 3, так что дальнейшего вложения не требуется. Эти ординалы вполне конкретные математические объекты.
Сдвиг основания не меняет тень
Когда вы сдвигаете основание с n на n+1, наследственное выражение меняет ярлык с n на n+1, но форма выражения остаётся той же. Так что ординальная тень не меняется при сдвиге. Тень члена до сдвига и тень члена после сдвига это один и тот же ординал.
Но затем вы вычитаете 1 из целого числа. Вычитание 1 в наследственной записи требует отодвинуть назад самый младший член выражения. Это изменяет форму наследственного выражения так, что, когда вы заменяете основание на омегу, получается строго меньший ординал. Не на чуть-чуть, не случайно: каждое вычитание 1 из числовой последовательности принудительно опускает ординальную тень строго вниз.
Так что схема такая: сдвигаем основание (тень стоит на месте), вычитаем 1 (тень опускается). Суммарный эффект за один шаг: ординальная тень убывает не менее чем на один шаг, каждый раз без исключения.
Ординалы не могут убывать вечно
Строго убывающая последовательность ординалов не может продолжаться вечно. Это один из фундаментальнейших фактов об ординалах: в отличие от целых чисел, нельзя бесконечно идти вниз. Есть дно. Последовательность ординальных теней в итоге обязана достигнуть нуля, а когда ординальная тень равна нулю, единственное целое число, чья наследственная запись отображается в нулевой ординал, это само число ноль. Значит, и последовательность Гудстина обязана достигнуть нуля.
Целые числа могут раздуваться до немыслимых размеров. Но ординалы за ними тихо, неотвратимо тикают вниз с каждым шагом. Шум в видимых числах. Правда в тени.
Гидра рассказывает то же самое
Ту же историю можно рассказать в виде игры. Представьте чудовище в форме дерева, гидру, с головами на концах ветвей. Вы рубите голову. В зависимости от того, какую голову и когда, из пня может вырасти несколько новых, иногда намного больше. Вы продолжаете рубить. Гидра будто побеждает.
Игра с гидрой Кирби-Пэрис, введённая математиками Джеффом Пэрисом и Лори Кирби в 1982 году, это именно такая ситуация, и она кодирует ту же математику, что и последовательность Гудстина. Правило прорастания голов соответствует взрывному сдвигу основания. Структура дерева соответствует наследственной записи. А скрытый за деревом ординал строго убывает при каждом ударе, точно так же как в аргументе Гудстина.
Какую бы стратегию вы ни выбрали, как бы небрежно вы ни выбирали, какую голову рубить, вы всегда победите. Гидра всегда умирает. Взрыв новых голов реален и может быть впечатляющим, но под фейерверком тикает обратный отсчёт. Игра с гидрой это теорема Гудстина в костюме.
Почему это важно для математиков
Здесь история делает поворот. Теорема Гудстина истинна. Она доказуемо истинна, как показывает ординальный аргумент выше. Но в 1982 году Кирби и Пэрис доказали нечто иное: теорема не может быть доказана внутри арифметики Пеано.
Арифметика Пеано это стандартная формальная система для рассуждений о целых числах. Она фиксирует почти всё, что вы назвали бы обычной арифметикой: сложение, умножение, индукцию по натуральным числам. Это арена, где живут результаты большинства школьных задач. И она просто недостаточно сильна, чтобы доказать завершение последовательностей Гудстина.
Это не означает, что теорема недоказуема ни в каком смысле. Ординальный аргумент работает и является полностью строгим. Но он требует рассуждений о бесконечности в той манере, которая недоступна арифметике Пеано. Система способна точно описывать последовательности Гудстина. Она может вычислять их, шаг за шагом. Она даже может распознать, что каждый член является конкретным целым числом. Чего она не может сделать, так это увидеть тень, ординальную структуру, которая гарантирует спуск.
Теорема Гудстина стала одним из первых примеров естественного, внешне обычного утверждения об обычных числах, оказавшегося за пределами досягаемости стандартной арифметики. Это не какая-то искусственная логическая головоломка, специально сконструированная, чтобы быть недоказуемой. Это утверждение, которое можно объяснить старшекласснику, о последовательности, которую можно записать на салфетке, и стандартная арифметика не в состоянии закрыть это дело.
Дзен этого
Здесь есть кое-что, с чем стоит задержаться. Последовательность, которая, судя по всему, взрывается без границ, на каждом шаге участвует в нисхождении, скрытом от вас сырыми числами. Оба процесса происходят одновременно: колоссальный рост и тихое неизбежное возвращение.
Это не противоречие. Это напоминание о том, что размер числа не равен его судьбе. Важна структура, которая лежит в основе, а здесь она всегда указывает на ноль.
Математика полна таких моментов: величина, которая, кажется, должна расходиться, но не расходится; доказательство, которое, кажется, должно рухнуть, но держится; последовательность, которая кажется бесконечной, но обрывается. Мастерство не в том, чтобы грубой силой вычислять члены последовательности. Оно в том, чтобы найти правильную тень для отслеживания, ту, которая говорит, что на самом деле происходит. Когда вы видите, как ординал тикает вниз за пиротехникой, теорема не просто истинна. Она ощущается неизбежной.
Размер это шум. Структура это сигнал. Последовательность всегда возвращалась домой.
Частые вопросы
- Что именно утверждает теорема Гудстина?
- Она утверждает, что любая последовательность Гудстина, сколько бы большими ни были её числа по пути, в конце концов достигает нуля. Рост может быть астрономическим и длиться невообразимо долго, но завершение гарантировано для любого начального значения.
- Почему последовательность возвращается вниз, если она всё время растёт?
- У каждого члена есть скрытый ординальный «двойник», который строго убывает на каждом шаге. Видимые целые числа могут раздуваться, но стоящий за ними ординал способен только уменьшаться, а убывающая последовательность ординалов не может падать вечно, значит процесс обязан завершиться нулём.
- Что такое наследственная запись в основании n?
- Это означает записать число в системе счисления с основанием n, а затем записать все его показатели степени тоже в основании n, снова и снова, вплоть до того, что в показателях остаётся только цифра 1. Например, 4 в наследственной записи по основанию 2 записывается как два в степени два, причём и сам показатель выражен через основание 2.
- Почему теорема Гудстина знаменита в логике?
- Потому что она истинна, но не может быть доказана средствами одной лишь арифметики Пеано. Это было одним из первых естественных, не искусственно сконструированных утверждений об обычных числах, которое оказалось недоказуемым в этой системе, именно поэтому оно стоит на границе математики и логики.
- Игра с гидрой описывает ту же идею?
- Да, гидра Кирби-Пэрис это та же самая математика, рассказанная другим языком. Срубить голову может породить множество новых, и всё же гидра всегда будет побеждена в финале, ровно по той же причине, по которой последовательность Гудстина всегда достигает нуля.
Понравилось разбираться?
Math Zen превращает такую интуицию в ежедневную практику: адаптивные задачи по 24 темам математики.
