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

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

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

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

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

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

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

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

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

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

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

для всех .


Смотри также[ | ]

Примечания[ | ]

  1. Wainer, S. Slow Growing Versus Fast Growing (англ.) // The Journal of Symbolic Logic : journal. — 1989. — Vol. 54, no. 2. — P. 608-614.

Ссылки[ | ]