Медленнорастущая иерархия

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

Медленнорастущая иерархия представляет собой семейство функций , где  — это некий большой счётный ординал, такой, что фундаментальные последовательности присвоены всем предельным ординалам, меньшим чем .

Медленнорастущая иерархия определяется следующим образом:

  • , если и только если  — предельный ординал,

где обозначает -й элемент фундаментальной последовательности присвоенной предельному ординалу .

Каждый ненулевой ординал может быть представлен в уникальной нормальной форме Кантора где – первый трансфинитный ординал, .

Если , тогда — предельный ординал и ему может быть присвоена фундаментальная последовательность следующим образом:

Если , тогда и .

Используя эту систему фундаментальных последовательностей можно определить медленнорастущую иерархию до первого числа эпсилон . Для верно равенство согласно стрелочной нотации.

С более мощными системами фундаментальных последовательностей можно ознакомиться на следующих страницах:

Медленнорастущая иерархия «догоняет» быстрорастущую иерархию при , используя пси-функции Бухгольца, то есть[1]

для всех .

Примечания

[править | править код]
  1. Wainer, S. Slow Growing Versus Fast Growing (англ.) // The Journal of Symbolic Logic : journal. — 1989. — Vol. 54, no. 2. — P. 608-614.