Теорема Гудстейна

Теорема Гудстейна — это утверждение теории чисел, доказанное британским логиком и математиком Рубеном Гудстейном в 1944 году. Теорема гласит, что любая последовательность Гудстейна, начинающаяся с произвольного натурального числа, в конечном счёте достигает нуля. Несмотря на свою простую формулировку, теорема примечательна тем, что она недоказуема в рамках формальной арифметики Пеано (PA) и требует использования более мощных теоретико-множественных методов, в частности, ординалов до эпсилон-нуля (ε₀). Это делает её классическим примером утверждения, которое является истинным, но недоказуемым в PA, что демонстрирует ограничения формальных систем, предсказанные теоремами Гёделя о неполноте.

Определение и основные понятия

Последовательность Гудстейна

Для любого натурального числа \( m \) можно построить последовательность Гудстейна \( G(m) \). Процесс построения основан на представлении числа в наследственной системе счисления с основанием \( k \).

1. Наследственная запись с основанием \( k \): Число записывается в системе счисления с основанием \( k \), а затем все показатели степени в этой записи также записываются в той же системе счисления, и так далее, пока все числа в записи не станут меньше \( k \).

• Пример для \( k = 2 \): Число 266 = 2⁸ + 2³ + 2¹. Записываем показатели: 8 = 2³, 3 = 2¹ + 2⁰, 1 = 2⁰. Тогда наследственная запись 266 с основанием 2 будет: \( 2^{2^{2+1}} + 2^{2+1} + 2 \).

1. Шаг последовательности: Для получения следующего члена последовательности \( G(m) \) выполняются две операции:

• Заменить текущее основание \( k \) на \( k+1 \) в наследственной записи числа.
• Вычесть единицу из полученного числа.

Последовательность начинается с \( G_1(m) = m \) (с основанием 2). Затем \( G_2(m) \) получается заменой основания 2 на 3 и вычитанием 1, и так далее.

Формулировка теоремы

Теорема Гудстейна: Для любого натурального числа \( m \) последовательность Гудстейна \( G(m) \) в конечном счёте достигает нуля. Иными словами, существует такое натуральное число \( n \), что \( G_n(m) = 0 \).

Примеры

Пример 1: \( m = 3 \)

1. \( G_1(3) = 3 \). Запись с основанием 2: \( 2^1 + 2^0 \).
2. Заменяем основание 2 на 3: \( 3^1 + 3^0 = 3 + 1 = 4 \). Вычитаем 1: \( G_2(3) = 3 \).
3. Запись с основанием 3: \( 3^1 \). Заменяем основание 3 на 4: \( 4^1 = 4 \). Вычитаем 1: \( G_3(3) = 3 \).
4. Запись с основанием 4: \( 4^0 + 4^0 + 4^0 = 1+1+1 = 3 \). Заменяем основание 4 на 5: \( 1+1+1 = 3 \). Вычитаем 1: \( G_4(3) = 2 \).
5. Аналогично, \( G_5(3) = 1 \), \( G_6(3) = 0 \).

Последовательность для \( m = 3 \) обрывается на 6-м шаге.

Пример 2: \( m = 4 \)

Последовательность для \( m = 4 \) значительно длиннее. Первые шаги:

1. \( G_1(4) = 4 = 2^2 \).
2. \( G_2(4) = 3^3 - 1 = 27 - 1 = 26 \).
3. \( G_3(4) \): 26 = 3³ + 3² + 3¹ + 3⁰ + 3⁰. Заменяем 3 на 4: \( 4^3 + 4^2 + 4^1 + 4^0 + 4^0 = 64 + 16 + 4 + 1 + 1 = 86 \). Вычитаем 1: \( G_3(4) = 85 \).
4. И так далее. Последовательность растёт очень быстро, но в конечном счёте достигает нуля. Количество шагов для \( m = 4 \) оценивается как \( 3 \cdot 2^{402653211} - 2 \), что является астрономически большим числом (более 10¹²¹ миллионов).

Доказательство

Нестандартная модель и ординалы

Доказательство теоремы Гудстейна, данное самим Гудстейном, использует теорию ординалов. Каждому члену последовательности \( G_k(m) \) ставится в соответствие некоторый ординал \( \alpha_k \), меньший \( \varepsilon_0 \) (эпсилон-нуль — первый неподвижный элемент экспоненциальной функции \( \omega^\alpha = \alpha \)).

Процесс замены основания \( k \) на \( k+1 \) в наследственной записи числа соответствует замене всех \( k \) на \( \omega \) (первый бесконечный ординал). Полученное выражение является ординалом. Например, для \( m = 4 \) на первом шаге \( 2^2 \) превращается в \( \omega^\omega \). Вычитание единицы на следующем шаге (в обычной арифметике) соответствует уменьшению этого ординала.

Ключевой момент: при переходе от \( G_k(m) \) к \( G_{k+1}(m) \) соответствующий ординал \( \alpha_k \) строго уменьшается. Поскольку ординалы образуют вполне упорядоченный класс (не существует бесконечно убывающей последовательности ординалов), процесс уменьшения не может продолжаться бесконечно. Следовательно, последовательность ординалов, а вместе с ней и последовательность Гудстейна, должна достичь нуля.

Недоказуемость в арифметике Пеано

В 1982 году австралийский математик Лоуренс Кирби и американский логик Джефф Парис доказали, что теорема Гудстейна недоказуема в рамках формальной арифметики Пеано (PA). Они показали, что доказательство теоремы требует принципа, эквивалентного утверждению о непротиворечивости PA, или, что то же самое, использования ординалов до \( \varepsilon_0 \). Арифметика Пеано не может оперировать с такими ординалами, поэтому для неё теорема остаётся недоказуемой, хотя и истинной (в стандартной модели натуральных чисел).

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

Значение и следствия

Связь с теоремой Гёделя

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

Значение в теории доказательств

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

Парадокс роста

Теорема иллюстрирует контраст между простотой формулировки и сложностью доказательства, а также между кажущейся неограниченностью роста последовательности (для \( m = 4 \) она сначала возрастает до гигантских чисел) и её неизбежным затуханием до нуля.

Интересные факты

• Теорема была впервые опубликована Рубеном Гудстейном в 1944 году в статье «On the restricted ordinal theorem».
• Долгое время она оставалась малоизвестной, пока Кирби и Парис не открыли её заново и не установили её связь с неполнотой.
• Последовательность Гудстейна для \( m = 1, 2, 3 \) обрывается очень быстро (на 2, 3 и 6 шагах соответственно). Для \( m = 4 \) число шагов настолько велико, что его невозможно вычислить в рамках обычной арифметики.
• Существует обобщение теоремы, известное как «теорема Гудстейна для конечных последовательностей», которое также недоказуемо в PA.

Источники

• Goodstein, R. L. (1944). On the restricted ordinal theorem. The Journal of Symbolic Logic, 9(2), 33-41.
• Kirby, L., & Paris, J. (1982). Accessible independence results for Peano arithmetic. Bulletin of the London Mathematical Society, 14(4), 285-293.
• Гёдель, К. (1931). О формально неразрешимых предложениях Principia Mathematica и родственных систем I. Monatshefte für Mathematik und Physik, 38, 173-198.
• Успенский, В. А. (2007). Теорема Гёделя о неполноте. М.: МЦНМО.