Быстрорастущая иерархия

Материал из Википедии — свободной энциклопедии
Перейти к: навигация, поиск

Быстрорастущая иерархия (также называемая расширенной иерархией Гржегорчика) — это семейство быстрорастущих функций, индексированных ординалами. Наиболее известным частным случаем быстрорастущей иерархии является иерархия Лёба-Вайнера.

Определение[править | править вики-текст]

Быстрорастущая иерархия определяется следующими правилами

  1. (в общем случае может быть любой растущей функцией),
  2. ,
  3. если предельный ординал,
    • где является n-ым элементом фундаментальной последовательности, установленной для некого предельного ординала .
    • Существуют различные версии быстрорастущей иерархии, однако наиболее известной является иерархия Лёба-Вайнера, в которой фундаментальные последовательности для предельных ординалов, записанных в нормальной форме Кантора, определяются следующими правилами
  4. ,
    • для ,
  5. ,
  6. если предельный ординал,
  7. и .

Примеры[править | править вики-текст]

,

.

Для функций, индексированных конечными ординалами верно

.

В частности при n=10[1]

,

,

.

Таким образом, уже первый трансфинитный ординал соответствует пределу стрелочной нотации Кнута.

Знаменитое число Грэма меньше, чем .

Благодаря простоте и ясности определения быстрорастущая иерархия применяется для анализа различных нотаций для записи больших чисел.

нотация Кнута нотация Конвея нотация Бауэрса
предел нотации
примеры

Данная выше дефиниция определяет быстрорастущую иерархию до . Для дальнейшего роста можно использовать функцию Веблена и другие, еще более мощные нотации для ординалов[2].

Примечания[править | править вики-текст]

  1. Tralum. googology.wikia . Проверено 4 октября 2016.
  2. Ordinal notation. googology.wikia . Проверено 4 октября 2016.

Ссылки[править | править вики-текст]