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

Теорема о натуральных числах

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

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

Наследственная основа-нобозначение

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

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

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

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

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

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

${\displaystyle 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 _i < n ). Затем перепишите любую экспоненту внутри показателей в записи с основанием n (с тем же ограничением на коэффициенты) и продолжайте таким образом, пока каждое число, появляющееся в выражении (за исключением самих оснований), не будет записано в записи с основанием n .

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Мы определяем функцию , которая вычисляет наследственное представление основания k числа u , а затем заменяет каждое вхождение основания k первым бесконечным порядковым числом ω. Например, . ${\displaystyle f=f(u,k)}$ ${\displaystyle 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 1 ⁺ 2 ⁰ и P (3)(1) = f (2 ¹ + 2 ⁰ ,2) = ω ¹ + ω ⁰ = ω + 1 . Сложение, умножение и возведение в степень порядковых чисел хорошо определены.

Мы заявляем, что : ${\displaystyle f(G(m)(n),n+1)>f(G(m)(n+1),n+2)}$

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

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

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

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

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

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

• Возьмем наследственное представление основания b _n для G ( m )( n ).
• Замените каждое вхождение основания b _n на b _{n +1} .
• Вычтите один.

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

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

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

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

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

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

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

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

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

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

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

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

${\displaystyle {\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}$.

Вот несколько примеров:

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

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

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

Смотрите также

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

Ссылки

1. Кирби и Пэрис 1982.
2. Ратьен 2014, лемма 2.2.
3. Гудстейн 1944.
4. Ратьен 2014.

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

• Кирби, Л.; Пэрис, Дж. (1982). "Доступные результаты независимости для арифметики Пеано" (PDF) . Бюллетень Лондонского математического общества . 14 (4): 285. CiteSeerX  10.1.1.107.3303 . doi :10.1112/blms/14.4.285.
• Ратьен, Майкл (2014). «Возвращение Гудштейна». arXiv : 1405,4484 [math.LO].
• Гудстейн, Р. (1944), «Об ограниченной порядковой теореме», Журнал символической логики , 9 (2): 33–41, doi : 10.2307/2268019, JSTOR  2268019, S2CID  235597.
• Cichon, E. (1983), «Краткое доказательство двух недавно обнаруженных результатов независимости с использованием рекурсивных теоретических методов», Труды Американского математического общества , 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 варианта игры Гидра
• Последовательности Гудштейна: сила обходного пути через бесконечность — хорошее изложение с иллюстрациями последовательностей Гудштейна и игры «Гидра».
• Калькулятор Гудстейна Архивировано 2017-02-04 на Wayback Machine