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

В математической логике теорема Гудштейна — это утверждение о натуральных числах , доказанное Рубеном Гудстейном в 1944 году, которое утверждает, что каждая последовательность Гудштейна (как определено ниже) в конечном итоге заканчивается в 0. Лоуренс Кирби и Джефф Пэрис показал, что это недоказуемо в арифметике Пеано (но можно доказать в более сильных системах, таких как арифметика второго порядка или теория множеств Цермело-Френкеля ). Это был третий пример истинного утверждения о натуральных числах, которое недоказуемо в арифметике Пеано, после примеров, предоставленных теоремой Гёделя о неполноте и прямым доказательством Герхарда Генцена в 1943 году недоказуемости ε ₀ -индукции в арифметике Пеано. Теорема Пэрис-Харрингтона дала еще один пример.

Кирби и Пэрис представили игру с теоретико-графовой гидрой , поведение которой похоже на поведение последовательностей Гудштейна: «Гидра» (названная в честь мифологической многоголовой гидры Лерны ) представляет собой дерево с корнями, и ход состоит в отрезании одной из его частей. «головы» (ветвь дерева), на которые гидра реагирует выращиванием конечного числа новых голов по определённым правилам. Кирби и Пэрис доказали, что Гидра в конечном итоге будет убита, независимо от стратегии, которую Геркулес использует, чтобы отрубить ей головы, хотя это может занять очень много времени. Как и в случае с последовательностями Гудштейна, Кирби и Пэрис показали, что это невозможно доказать только с помощью арифметики Пеано.

Наследственная по основанию n система счисления

Последовательности Гудштейна определяются в терминах концепции, называемой «наследственной записью по основанию n ». Это обозначение очень похоже на обычное по основанию n позиционное обозначение , но обычного обозначения недостаточно для целей теоремы Гудштейна.

Чтобы получить обычную запись по основанию n , где n — натуральное число, большее 1, произвольное натуральное число m записывается как сумма кратных степеней n :

$m=a_{k}n^{k}+a_{k-1}n^{k-1}+\cdots +a_{0},$

где каждый коэффициент a _i удовлетворяет условиям 0 ≤ a _i < n и a _k ≠ 0 . Например, чтобы получить запись по основанию 2 , пишут

$35=32+2+1=2^{5}+2^{1}+2^{0}.$

Таким образом, представление числа 35 по основанию 2 равно 100011, что означает 2. ⁵ + 2 + 1 . Аналогично, 100, представленное в базе 3, равно 10201:

$100=81+18+1=3^{4}+2\cdot 3^{2}+3^{0}.$

Обратите внимание, что сами показатели степени не записаны в системе счисления с основанием n . Например, приведенные выше выражения включают 2 ⁵ и 3 ⁴ , и 5 > 2, 4 > 3.

Чтобы преобразовать нотацию по основанию n (что является шагом в достижении представления по основанию n ) в наследственную нотацию по основанию n , сначала перепишите все показатели степени как сумму степеней n (с ограничением на коэффициенты 0 ≤ a _я < п ). Затем перепишите любую степень внутри показателей в системе счисления по основанию n (с тем же ограничением на коэффициенты) и продолжайте таким образом до тех пор, пока каждое число, появляющееся в выражении (кроме самих чисел по основанию), не будет записано в системе счисления по основанию n .

Например, хотя 35 в обычной записи с основанием 2 равно 2 ⁵ + 2 + 1 , это записывается в наследственной записи по основанию 2 как

$35=2^{2^{2^{1}}+1}+2^{1}+1,$

используя тот факт, что 5 = 2 ^{2 1} + 1. Аналогично, 100 в наследственной системе счисления с основанием 3 равно

$100=3^{3^{1}+1}+2\cdot 3^{2}+1.$

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

Последовательность Гудштейна G ( m ) числа m является последовательностью натуральных чисел. Первый элемент в последовательности G ( m ) — это сам m . Чтобы получить второе значение, G ( m )(2), запишите m в наследственной системе счисления по основанию 2, замените все двойки на тройки, а затем вычтите 1 из результата. В общем, ( n + 1)-й член G ( m )( n + 1) последовательности Гудстейна m выглядит следующим образом:

• Возьмем наследственное по основанию n + 1 представление группы G ( m )( n ).
• Замените каждое вхождение основания - n + 1 на n + 2 .
• Вычтите один. (Обратите внимание, что следующий член зависит как от предыдущего, так и от индекса n .)
• Продолжайте до тех пор, пока результат не станет нулевым, после чего последовательность завершается.

Ранние последовательности Гудштейна быстро заканчиваются. Например, G (3) завершается на 6-м шаге:

База	Наследственные обозначения	Ценить	Примечания
2	$2^{1}+1$	3	Запишите 3 в системе счисления по основанию 2.
3	$3^{1}+1-1=3^{1}$	3	Поменяйте 2 на 3, затем вычтите 1.
4	$4^{1}-1=3$	3	Поменяйте 3 на 4, затем вычтите 1. Теперь четверок больше не осталось.
5	$3-1=2$	2	Осталось 4, чтобы перейти на 5. Просто вычтите 1
6	$2-1=1$	1	Не осталось 5, чтобы перейти на 6. Просто вычтите 1
7	$1-1=0$	0	Осталось 6, чтобы перейти на 7. Просто вычтите 1

Более поздние последовательности Гудштейна увеличиваются на очень большое количество шагов. Например, G (4) OEIS : A056193 начинается следующим образом:

База	Наследственные обозначения	Ценить
2	$2^{2^{1}}$	4
3	$3^{3^{1}}-1=2\cdot 3^{2}+2\cdot 3+2$	26
4	$2\cdot 4^{2}+2\cdot 4+1$	41
5	$2\cdot 5^{2}+2\cdot 5$	60
6	$2\cdot 6^{2}+2\cdot 6-1=2\cdot 6^{2}+6+5$	83
7	$2\cdot 7^{2}+7+4$	109
$\vdots$	$\vdots$	$\vdots$
11	$2\cdot 11^{2}+11$	253
12	$2\cdot 12^{2}+12-1=2\cdot 12^{2}+11$	299
$\vdots$	$\vdots$	$\vdots$
24	$2\cdot 24^{2}-1=24^{2}+23\cdot 24+23$	1151
$\vdots$	$\vdots$	$\vdots$
$B=3\cdot 2^{402\,653\,209}-1$	$2\cdot B^{1}$	$3\cdot 2^{402\,653\,210}-2$
$B=3\cdot 2^{402\,653\,209}$	$2\cdot B^{1}-1=B^{1}+(B-1)$	$3\cdot 2^{402\,653\,210}-1$
$\vdots$	$\vdots$	$\vdots$

Элементы G (4) некоторое время продолжают увеличиваться, но в базе $3\cdot 2^{402\,653\,209}$,они достигают максимума $3\cdot 2^{402\,653\,210}-1$, оставайся там до следующего $3\cdot 2^{402\,653\,209}$ шаги, а затем начинают спуск.

Однако даже G (4) не дает хорошего представления о том, насколько быстро могут увеличиваться элементы последовательности Гудштейна. G (19) возрастает гораздо быстрее и начинается следующим образом:

Наследственные обозначения	Ценить
$2^{2^{2}}+2+1$	19
$3^{3^{3}}+3$	7 625 597 484 990
$4^{4^{4}}+3$	$\approx 1.3\times 10^{154}$
$5^{5^{5}}+2$	$\approx 1.8\times 10^{2\,184}$
$6^{6^{6}}+1$	$\approx 2.6\times 10^{36\,305}$
$7^{7^{7}}$	$\approx 3.8\times 10^{695\,974}$
$8^{8^{8}}-1=7\cdot 8^{7\cdot 8^{7}+7\cdot 8^{6}+7\cdot 8^{5}+7\cdot 8^{4}+7\cdot 8^{3}+7\cdot 8^{2}+7\cdot 8+7}$${}+7\cdot 8^{7\cdot 8^{7}+7\cdot 8^{6}+7\cdot 8^{5}+7\cdot 8^{4}+7\cdot 8^{3}+7\cdot 8^{2}+7\cdot 8+6}+\cdots$${}+7\cdot 8^{8+2}+7\cdot 8^{8+1}+7\cdot 8^{8}$${}+7\cdot 8^{7}+7\cdot 8^{6}+7\cdot 8^{5}+7\cdot 8^{4}$${}+7\cdot 8^{3}+7\cdot 8^{2}+7\cdot 8+7$	$\approx 6.0\times 10^{15\,151\,335}$
$7\cdot 9^{7\cdot 9^{7}+7\cdot 9^{6}+7\cdot 9^{5}+7\cdot 9^{4}+7\cdot 9^{3}+7\cdot 9^{2}+7\cdot 9+7}$${}+7\cdot 9^{7\cdot 9^{7}+7\cdot 9^{6}+7\cdot 9^{5}+7\cdot 9^{4}+7\cdot 9^{3}+7\cdot 9^{2}+7\cdot 9+6}+\cdots$${}+7\cdot 9^{9+2}+7\cdot 9^{9+1}+7\cdot 9^{9}$${}+7\cdot 9^{7}+7\cdot 9^{6}+7\cdot 9^{5}+7\cdot 9^{4}$${}+7\cdot 9^{3}+7\cdot 9^{2}+7\cdot 9+6$	$\approx 5.6\times 10^{35\,942\,384}$
$\vdots$	$\vdots$

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

Доказательство теоремы Гудштейна

Теорему Гудстейна можно доказать (используя методы, не относящиеся к арифметике Пеано, см. ниже) следующим образом: по последовательности Гудштейна G ( m ) мы строим параллельную последовательность P ( m ) порядковых чисел в нормальной форме Кантора , которая строго убывает и заканчивается. Распространенным заблуждением этого доказательства является мнение, что G ( m ) стремится к 0, потому что над ним доминирует P ( m ). На самом деле тот факт, что P ( m ) доминирует над G ( m ), вообще не играет никакой роли. Важным моментом является то, что G ( m )( k ) существует тогда и только тогда, когда существует P ( m )( k ) (параллелизм), и сравнение между двумя членами G ( m ) сохраняется при сравнении соответствующих записей P ( m ). . Тогда, если P ( m ) прекращается, то же самое происходит и с G ( m ). Путем бесконечного регресса G ( m ) должен достичь 0, что гарантирует завершение.

Мы определяем функцию $f=f(u,k)$ который вычисляет наследственное по базе k представление u , а затем заменяет каждое вхождение базы k первым бесконечным порядковым числом ω. Например, $f(100,3)=f(3^{3^{1}+1}+2\cdot 3^{2}+1,3)=\omega ^{\omega ^{1}+1}+\omega ^{2}\cdot 2+1=\omega ^{\omega +1}+\omega ^{2}\cdot 2+1$.

Каждый член P ( m )( n ) последовательности P ( m ) затем определяется как f ( G ( m )( n ), n+1 ). Например, G (3)(1) = 3 = 2 ¹ + 2 ⁰ и P (3)(1) = f (2 ¹ + 2 ⁰ ,2) = ω ¹ + ох ⁰ = ω + 1 . Сложение, умножение и возведение в степень порядковых чисел четко определены.

Мы утверждаем, что $f(G(m)(n),n+1)>f(G(m)(n+1),n+2)$:

Позволять $G'(m)(n)$ быть G ( m )( n ) после применения первого, операция изменения основания при создании следующего элемента последовательности Гудштейна, но до второй операции минус 1 в этом поколении. Обратите внимание, что $G(m)(n+1)=G'(m)(n)-1$.

Затем $f(G(m)(n),n+1)=f(G'(m)(n),n+2)$. Теперь применим операцию минус 1 , и $f(G'(m)(n),n+2)>f(G(m)(n+1),n+2)$, как $G'(m)(n)=G(m)(n+1)+1$.Например, $G(4)(1)=2^{2}$ и $G(4)(2)=2\cdot 3^{2}+2\cdot 3+2$, так $f(2^{2},2)=\omega ^{\omega }$ и $f(2\cdot 3^{2}+2\cdot 3+2,3)=\omega ^{2}\cdot 2+\omega \cdot 2+2$, что строго меньше. Обратите внимание: чтобы вычислить f(G(m)(n),n+1) , нам сначала нужно записать G ( m )( n ) в наследственной записи по основанию n +1 , как, например, выражение $\omega ^{\omega }-1$ не является порядковым номером.

Таким образом, последовательность P ( m ) строго убывает. Поскольку стандартный порядок < ординалов хорошо обоснован , бесконечная строго убывающая последовательность не может существовать или, что то же самое, каждая строго убывающая последовательность ординалов заканчивается (и не может быть бесконечной). Но P ( m )( n ) вычисляется непосредственно из G ( m )( n ). Следовательно, последовательность G ( m ) также должна завершиться, то есть она должна достичь 0.

Хотя это доказательство теоремы Гудштейна довольно простое, теорема Кирби – Пэрис , который показывает, что теорема Гудштейна не является теоремой арифметики Пеано, является технической и значительно более сложной. Он использует счетные нестандартные модели арифметики Пеано.

Расширенная теорема Гудштейна

Приведенное выше доказательство по-прежнему работает, если определение последовательности Гудштейна изменить так, что операция изменения основания заменяет каждое вхождение основания b на b + 2 вместо b + 1 .В более общем смысле, пусть b ₁ , b ₂ , b ₃ , ... будет любой неубывающей последовательностью целых чисел с b ₁ ≥ 2 .Тогда пусть ( n + 1)-й член G ( m )( n + 1) расширенной последовательности Гудштейна m будет иметь видследует:

• Возьмем наследственное базовое представление _G ( n m ) ( ) .
• основания bn ₊₁ на bn _{Замените каждое вхождение} .
• Вычтите один.

Простая модификация приведенного выше доказательства показывает, что эта последовательность все равно завершается. Например, если bn _и = 4 если +1 _{bn =} 9 ,затем $f(3\cdot 4^{4^{4}}+4,4)=3\omega ^{\omega ^{\omega }}+\omega =f(3\cdot 9^{9^{9}}+9,9)$, следовательно, порядковый номер $f(3\cdot 4^{4^{4}}+4,4)$ строго больше порядкового номера $f{\big (}(3\cdot 9^{9^{9}}+9)-1,9{\big )}.$

Расширенная версия на самом деле является той, которая рассматривается в оригинальной статье Гудштейна: где Гудштейн доказал, что это эквивалентно ограниченной порядковой теореме (т.е. утверждение, что трансфинитная индукция ниже ε ₀ справедлива), и дал финитистское доказательство для случая, когда $m\leq b_{1}^{b_{1}^{b_{1}}}$ (эквивалентно трансфинитной индукции до $\omega ^{\omega ^{\omega }}$).

Расширенная теорема Гудстейна без каких-либо ограничений на последовательность не _bn формализуема в арифметике Пеано (PA), поскольку такая произвольная бесконечная последовательность не может быть представлена ​​в PA. Похоже, именно это удержало Гудстейна от заявления еще в 1944 году о том, что расширенная теорема Гудстейна недоказуема в PA из-за второй теоремы Гёделя о неполноте и доказательства Генцена непротиворечивости PA с использованием ε ₀ -индукции. Однако проверка доказательства Генцена показывает, что для него нужен только тот факт, что не существует -рекурсивной строго убывающей бесконечной последовательности ординалов, поэтому ограничение bn _{примитивно} примитивно-рекурсивными последовательностями позволило бы Гудштейну доказать результат о недоказуемости. Более того, с помощью относительно элементарной техники иерархии Гжегорчика можно показать, что каждая примитивно-рекурсивная строго убывающая бесконечная последовательность ординаловможет быть «замедлен» так, чтобы его можно было преобразовать в последовательность Гудштейна, где b _n = n + 1 , тем самым давая альтернативное доказательство того же результата, который доказали Кирби и Пэрис.

Длина последовательности как функция начального значения

Функция Гудштейна , ${\mathcal {G}}:\mathbb {N} \to \mathbb {N}$, определяется так, что ${\mathcal {G}}(n)$ — длина последовательности Гудштейна, начинающейся с n . (Это полная функция , поскольку каждая последовательность Гудштейна завершается.) Чрезвычайно высокая скорость роста ${\mathcal {G}}$ можно калибровать, связывая его с различными стандартными иерархиями функций с порядковым индексом, такими как функции $H_{\alpha }$ в иерархии Харди и функции $f_{\alpha }$ в быстрорастущей иерархии Лёба и Вайнера:

• Кирби и Пэрис (1982) доказали, что

${\mathcal {G}}$ имеет примерно такой же темп роста, как и $H_{\epsilon _{0}}$ (что то же самое, что и у $f_{\epsilon _{0}}$); точнее, ${\mathcal {G}}$ доминирует $H_{\alpha }$ для каждого $\alpha <\epsilon _{0}$, и $H_{\epsilon _{0}}$ доминирует ${\mathcal {G}}\,\!.$

(Для любых двух функций $f,g:\mathbb {N} \to \mathbb {N}$, $f$ говорят, что доминирует $g$ если $f(n)>g(n)$ для всех достаточно больших $n$.)

• Сишон (1983) показал, что

${\mathcal {G}}(n)=H_{R_{2}^{\omega }(n+1)}(1)-1,$

где $R_{2}^{\omega }(n)$ является результатом помещения n в наследственную систему счисления по основанию 2 и последующей замены всех двоек на ω (как это было сделано при доказательстве теоремы Гудштейна).

• Кайседо (2007) показал, что если $n=2^{m_{1}}+2^{m_{2}}+\cdots +2^{m_{k}}$ с $m_{1}>m_{2}>\cdots >m_{k},$ затем

${\mathcal {G}}(n)=f_{R_{2}^{\omega }(m_{1})}(f_{R_{2}^{\omega }(m_{2})}(\cdots (f_{R_{2}^{\omega }(m_{k})}(3))\cdots ))-2$.

Некоторые примеры:

н			${\mathcal {G}}(n)$
1	$2^{0}$	$2-1$	$H_{\omega }(1)-1$	$f_{0}(3)-2$	2
2	$2^{1}$	$2^{1}+1-1$	$H_{\omega +1}(1)-1$	$f_{1}(3)-2$	4
3	$2^{1}+2^{0}$	$2^{2}-1$	$H_{\omega ^{\omega }}(1)-1$	$f_{1}(f_{0}(3))-2$	6
4	$2^{2}$	$2^{2}+1-1$	$H_{\omega ^{\omega }+1}(1)-1$	$f_{\omega }(3)-2$	3·2 402653211 − 2 ≈ 6.895080803×10 121210694
5	$2^{2}+2^{0}$	$2^{2}+2-1$	$H_{\omega ^{\omega }+\omega }(1)-1$	$f_{\omega }(f_{0}(3))-2$	> А (4,4) > 10 10 10 19727
6	$2^{2}+2^{1}$	$2^{2}+2+1-1$	$H_{\omega ^{\omega }+\omega +1}(1)-1$	$f_{\omega }(f_{1}(3))-2$	> А (6,6)
7	$2^{2}+2^{1}+2^{0}$	$2^{2+1}-1$	$H_{\omega ^{\omega +1}}(1)-1$	$f_{\omega }(f_{1}(f_{0}(3)))-2$	> А (8,8)
8	$2^{2+1}$	$2^{2+1}+1-1$	$H_{\omega ^{\omega +1}+1}(1)-1$	$f_{\omega +1}(3)-2$	> А 3 (3,3) = А ( А (61, 61), А (61, 61))
$\vdots$
12	$2^{2+1}+2^{2}$	$2^{2+1}+2^{2}+1-1$	$H_{\omega ^{\omega +1}+\omega ^{\omega }+1}(1)-1$	$f_{\omega +1}(f_{\omega }(3))-2$	> f ω+1 (64) > число Грэма
$\vdots$
19	$2^{2^{2}}+2^{1}+2^{0}$	$2^{2^{2}}+2^{2}-1$	$H_{\omega ^{\omega ^{\omega }}+\omega ^{\omega }}(1)-1$	$f_{\omega ^{\omega }}(f_{1}(f_{0}(3)))-2$

(Информацию о функции Аккермана и границах чисел Грэма см. в разделе быстрорастущая иерархия#Функции в быстрорастущих иерархиях .)

Приложение к вычислимым функциям

Теорему Гудштейна можно использовать для построения полной вычислимой функции , полная которой не может быть доказана арифметикой Пеано. Последовательность чисел Гудштейна можно эффективно перечислить с помощью машины Тьюринга ; таким образом, функция, которая отображает n в число шагов, необходимых для завершения последовательности Гудштейна n , вычислима с помощью конкретной машины Тьюринга. Эта машина просто перечисляет последовательность Гудштейна n и, когда последовательность достигает 0 , возвращает длину последовательности. Поскольку каждая последовательность Гудштейна в конечном итоге завершается, эта функция является полной. Но поскольку арифметика Пеано не доказывает, что каждая последовательность Гудштейна завершается, арифметика Пеано не доказывает, что эта машина Тьюринга вычисляет полную функцию.

См. также

• Нестандартная модель арифметики
• Быстрорастущая иерархия
• Теорема Пэрис – Харрингтона
• Теорема Канамори – Макалуна
• Теорема Краскала о дереве

Библиография

• Кирби, Л.; Пэрис, Дж. (1982). «Доступные результаты независимости для арифметики Пеано» (PDF) . Бюллетень Лондонского математического общества . 14 (4): 285. CiteSeerX   10.1.1.107.3303 . дои : 10.1112/blms/14.4.285 .
• Ратьен, Майкл (2014). «Возвращение Гудштейна». arXiv : 1405.4484 [ math.LO ].
• Гудштейн, Р. (1944), «Об ограниченной порядковой теореме», Journal of Символическая логика , 9 (2): 33–41, doi : 10.2307/2268019 , JSTOR   2268019 , S2CID   235597 .
• Сишон, Э. (1983), «Краткое доказательство двух недавно обнаруженных результатов независимости с использованием рекурсивных теоретических методов», Proceedings of the American Mathematical Society , 87 (4): 704–706, doi : 10.2307/2043364 , JSTOR   2043364 .
• Кайседо, А. (2007), «Функция Гудштейна» (PDF) , Revista Colombiana de Matemáticas , 41 (2): 381–391 .

Внешние ссылки

• Вайсштейн, Эрик В. «Последовательность Гудштейна» . Математический мир .
• Некоторые элементы доказательства того, что теорема Гудштейна не является теоремой PA, из студенческой диссертации Джастина Т. Миллера.
• Классификация нестандартных моделей арифметики Пеано по теореме Гудштейна - диссертация Дэна Каплана, Библиотека колледжа Франклана и Маршалла
• Определение последовательностей Гудштейна в Haskell и лямбда-исчисление
• Игра Hydra реализована в виде Java-апплета.
• Javascript-реализация варианта игры Hydra
• Последовательности Гудштейна: Сила обхода через бесконечность - хорошая экспозиция с иллюстрациями последовательностей Гудштейна и игры с гидрой.
• Калькулятор Goodstein. Архивировано 4 февраля 2017 г. на Wayback Machine.