В математической логике , теорема гудстейн является утверждением о натуральных числах , доказанное Рувим Гудстейн в 1944 году, в котором говорится , что каждая последовательность Гудстейн в конечном счете заканчивается на 0. Кирби и Париж [1] показал , что это недоказуемо в арифметике Пеано (но это может быть доказанным в более сильных системах, таких как арифметика второго порядка ). Это был третий пример истинного утверждения, недоказуемого в арифметике Пеано, после теоремы Гёделя о неполноте и прямого доказательства недоказуемости ε 0 Герхарда Гентцена в 1943 г.-индукция по арифметике Пеано. Теорема Пэрис – Харрингтона была более поздним примером.
Лоуренс Кирби и Джефф Пэрис представили теоретико- графовую игру про гидру с поведением, аналогичным поведению последовательностей Гудштейна: «Гидра» (названная в честь мифологической многоглавой Гидры Лерны ) - это дерево с корнями, и ход состоит из отсечения одного своих «голов» (ветвь дерева), на которые гидра отвечает, выращивая конечное число новых голов по определенным правилам. Кирби и Пэрис доказали, что Гидра в конечном итоге будет убита, независимо от стратегии, которую Геракл использует, чтобы отрубить ей головы, хотя это может занять очень много времени. Как и в случае с последовательностями Гудштейна, Кирби и Пэрис показали, что это не может быть доказано только с помощью арифметики Пеано. [1]
Наследственные base- п обозначения
Гудстейн последовательности определены в терминах концепции называемых «наследственная base- п обозначением». Эта запись очень похожа на обычный base- п позиционной системы счисления, но обычные обозначения не хватает для целей теоремы Гудстейна.
В обычных обозначениях с основанием n , где n - натуральное число, большее 1, произвольное натуральное число m записывается как сумма кратных степеней n :
где каждый коэффициент a i удовлетворяет условию 0 ≤ a i < n и a k ≠ 0 . Например, в базе 2
Таким образом, представление 35 по основанию 2 равно 100011, что означает 2 5 + 2 + 1 . Точно так же 100, представленное в базе-3, равно 10201:
Следует отметить , что сами по себе показатели не записаны в базе - н нотации. Например, приведенные выше выражения включают 2 5 и 3 4 и 5> 2, 4> 3.
Чтобы преобразовать base- п представление к наследственным base- п нотации, первым переписать все экспонент в базе - н нотации. Затем перепишите все экспоненты внутри показателей и продолжайте таким образом, пока все числа, появляющиеся в выражении (кроме самих оснований), не будут преобразованы в систему счисления с основанием n .
Например, в то время как 35 в обычной системе счисления с основанием 2 равно 2 5 + 2 + 1 , в наследственной системе счисления с основанием 2 оно записывается как
используя тот факт, что 5 = 2 2 + 1. Аналогично, 100 в наследственной системе счисления с основанием 3 равно
Последовательности Гудштейна
Последовательность Гудштейна G ( m ) числа m - это последовательность натуральных чисел. Первым элементом в последовательности G ( m ) является сам m . Чтобы получить второе, G ( m ) (2), напишите m в наследственной системе счисления с основанием 2, замените все двойки на 3, а затем вычтите 1 из результата. В общем, ( n + 1) -й член G ( m ) ( n + 1) последовательности Гудштейна m имеет следующий вид:
- Возьмем наследственное базовое n + 1 представление группы G ( m ) ( n ).
- Замените каждое вхождение основания- n + 1 на n + 2 .
- Вычтите один. (Обратите внимание, что следующий член зависит как от предыдущего члена, так и от индекса n .)
- Продолжайте до тех пор, пока результат не станет нулевым, после чего последовательность завершится.
Ранние последовательности Гудштейна быстро обрываются. Например, G (3) завершается на 6-м шаге:
База | Наследственные обозначения | Значение | Заметки |
---|---|---|---|
2 | 3 | Запишите 3 в системе счисления с основанием 2. | |
3 | 3 | Измените 2 на 3, затем вычтите 1 | |
4 | 3 | Измените 3 на 4, затем вычтите 1. Теперь четверок больше не осталось. | |
5 | 2 | Нет 4s, чтобы переключиться на 5s. Просто вычтите 1 | |
6 | 1 | Не осталось 5 секунд, чтобы переключиться на 6 секунд. Просто вычтите 1 | |
7 | 0 | Не осталось 6 секунд, чтобы переключиться на 7. Просто вычтите 1 |
Позже последовательности Гудштейна увеличиваются на очень большое количество шагов. Например, G (4) OEIS : A056193 начинается следующим образом:
База | Наследственные обозначения | Значение |
---|---|---|
2 | 4 | |
3 | 26 год | |
4 | 41 год | |
5 | 60 | |
6 | 83 | |
7 | 109 | |
11 | 253 | |
12 | 299 | |
24 | 1151 | |
Элементы G (4) продолжают увеличиваться некоторое время, но в основе, они достигают максимума , оставайся там до следующего шагов, а затем начните свой первый спуск.
Значение 0 достигается на базе . (Любопытно, что это число Вудалла :. То же самое и со всеми другими окончательными базами для начальных значений больше 4. [ необходима ссылка ] )
Однако даже G (4) не дает хорошего представления о том, насколько быстро могут увеличиваться элементы последовательности Гудштейна. G (19) растет гораздо быстрее и начинается следующим образом:
Наследственные обозначения | Значение |
---|---|
19 | |
7 625 597 484 990 | |
| |
| |
Несмотря на такой быстрый рост, теорема Гудстейна утверждает, что каждая последовательность Гудстейна в конечном итоге заканчивается на 0 , независимо от начального значения.
Доказательство теоремы Гудштейна
Теорема Гудстейна может быть доказана (используя методы, отличные от арифметики Пеано, см. Ниже) следующим образом: для данной последовательности Гудстейна G ( m ) мы строим параллельную последовательность P ( m ) порядковых чисел, которая строго убывает и заканчивается. Тогда G ( m ) тоже должна завершиться, и она может завершиться только тогда, когда перейдет в 0. Распространенное заблуждение этого доказательства состоит в том, что полагают, что G ( m ) стремится к 0, потому что над ней доминирует P ( m ). На самом деле тот факт, что P ( m ) доминирует над G ( m ), не играет никакой роли. Важный момент: G ( m ) ( k ) существует тогда и только тогда, когда существует P ( m ) ( k ) (параллелизм). Тогда, если P ( m ) завершается, то же самое происходит и с G ( m ). И G ( m ) может завершиться только тогда, когда доходит до 0.
Определим функцию который вычисляет наследственное представление базы k для u, а затем заменяет каждое вхождение базы k первым бесконечным порядковым числом ω. Например,.
Каждый член P ( m ) ( n ) последовательности P ( m ) затем определяется как f ( G ( m ) ( n ), n + 1 ). Например, G (3) (1) = 3 = 2 1 + 2 0 и P (3) (1) = f (2 1 + 2 0 , 2) = ω 1 + ω 0 = ω + 1 . Сложение, умножение и возведение порядковых чисел в степень хорошо определены.
Мы утверждаем, что :
Позволять быть G ( m ) ( n ) после применения первой операции изменения базы при генерации следующего элемента последовательности Гудштейна, но перед второй операцией минус 1 в этом поколении. Заметьте, что.
Тогда ясно, . Теперь применим операцию минус 1 и, в виде . Например, а также , так а также , что строго меньше. Обратите внимание, что для вычисления f (G (m) (n), n + 1) нам сначала нужно записать G ( m ) ( n ) в наследственной системе счисления n +1 , как, например, выражение либо не имеет смысла, либо равно .
Таким образом, последовательность P ( m ) строго убывает. Поскольку стандартный порядок <на порядковых числах хорошо обоснован , бесконечная строго убывающая последовательность не может существовать, или, что эквивалентно, каждая строго убывающая последовательность ординалов завершается (и не может быть бесконечной). Но P ( m ) ( n ) вычисляется непосредственно из G ( m ) ( n ). Следовательно, последовательность G ( m ) также должна завершиться, что означает, что она должна достичь 0.
Хотя это доказательство теоремы Гудстейна довольно легко, теорема Кирби-Париж , [1] , который показывает , что теорема гудстейна не является теорема арифметики Пеано, является техническим и значительно сложнее. Он использует счетные нестандартные модели арифметики Пеано.
Расширенная теорема Гудштейна
Предположим, что определение последовательности Гудштейна изменено так, что вместо замены каждого вхождения основания b на b +1 оно заменяет его на b +2 . Будет ли последовательность все еще прервана? В более общем смысле, пусть b 1 , b 2 , b 3 ,… - любые последовательности целых чисел. Тогда пусть n + 1-й член G ( m ) ( n +1) расширенной последовательности Гудштейна m будет следующим: возьмем наследственное базовое представление b n группы G ( m ) ( n ) и заменим каждое вхождение базы b n с b n +1, а затем вычесть единицу. Утверждается, что эта последовательность все еще завершается. Расширенное доказательство определяет P ( m ) ( n ) = f ( G ( m ) ( n ), n ) следующим образом: возьмите наследственное базовое представление b n группы G ( m ) ( n ) и замените каждое вхождение базы b n с первым бесконечным порядковым номером ω. Операция изменения базы последовательности Гудштейна при переходе от G ( m ) ( n ) к G ( m ) ( n +1) по- прежнему не изменяет значение f . Например, если b n = 4 и если b n +1 = 9 , то, следовательно, порядковый строго больше порядкового
Длина последовательности как функция от начального значения
Функция Гудштейна ,, определяется так, что - длина последовательности Гудштейна, которая начинается с n . (Это полная функция, поскольку каждая последовательность Гудштейна завершается.) Чрезвычайная скорость роста можно откалибровать, связав его с различными стандартными иерархиями функций с порядковым индексом, такими как функции в иерархии Харди , а функциив быстрорастущей иерархии Лёба и Вайнера:
- Кирби и Пэрис (1982) доказали, что
- имеет примерно такую же скорость роста, как (что такое же, как у ); точнее, доминирует для каждого , а также доминирует
- (Для любых двух функций , Говорят, что доминирует если для всех достаточно больших .)
- Cichon (1983) показал, что
- где является результатом помещения n в наследственную систему обозначений с основанием 2 и последующей замены всех 2 на ω (как это было сделано при доказательстве теоремы Гудстейна).
- Caicedo (2007) показал, что если с участием тогда
- .
Несколько примеров:
п | |||||
---|---|---|---|---|---|
1 | 2 | ||||
2 | 4 | ||||
3 | 6 | ||||
4 | 3 · 2 402653211 - 2 ≈ 6,895080803 × 10 121210694 | ||||
5 | > А (4,4)> | ||||
6 | > А (6,6) | ||||
7 | > А (8,8) | ||||
8 | > A 3 (3,3) = A ( A (61, 61), A (61, 61)) | ||||
12 | > f ω + 1 (64)> число Грэма | ||||
19 |
(Для функции Аккермана и границ числа Грэма см. Быстрорастущую иерархию # Функции в быстрорастущих иерархиях .)
Приложение к вычислимым функциям
Теорема Гудстейна может быть использована для построения полной вычислимой функции, которую арифметика Пеано не может доказать, чтобы быть тотальной. Последовательность чисел Гудштейна может быть эффективно пронумерована машиной Тьюринга ; таким образом, функция, которая отображает n на количество шагов, необходимых для завершения последовательности Гудштейна n , вычисляется конкретной машиной Тьюринга. Эта машина просто перечисляет последовательность Гудштейна из n и, когда последовательность достигает 0 , возвращает длину последовательности. Поскольку каждая последовательность Гудштейна в конечном итоге завершается, эта функция является полной. Но поскольку арифметика Пеано не доказывает, что каждая последовательность Гудстейна завершается, арифметика Пеано не доказывает, что эта машина Тьюринга вычисляет полную функцию.
Смотрите также
Рекомендации
- ^ a b c Кирби, L .; Пэрис, Дж. (1982). «Доступные результаты независимости для арифметики Пеано» (PDF) . Бюллетень Лондонского математического общества . 14 (4): 285. CiteSeerX 10.1.1.107.3303 . DOI : 10.1112 / БЛМ / 14.4.285 .
Библиография
- Гудстейна, R. (1944), "О запретной порядковой теореме", журнал символической логики , 9 (2): 33-41, DOI : 10,2307 / 2268019 , JSTOR 2268019 , S2CID 235597.
- Cichon, E. (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.
Внешние ссылки
- Вайсштейн, Эрик В. «Последовательность Гудштейна» . MathWorld .
- Некоторые элементы доказательства того, что теорема Гудстейна не является теоремой PA, из дипломной работы Джастина Т. Миллера
- Классификация нестандартных моделей арифметики Пеано по теореме Гудстейна - диссертация Дэна Каплана, Библиотека Франклана и Маршалла
- Определение последовательностей Гудштейна в Haskell и лямбда-исчисление
- Игра Hydra реализована в виде Java-апплета.
- Реализация Javascript варианта игры Hydra
- Последовательности Гудштейна: сила объезда бесконечности - хорошая экспозиция с иллюстрациями к «Последовательностям Гудштейна» и игре «Гидра».
- Калькулятор Гудштейна