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

Медленнорастущая иерархия представляет собой семейство функций $(g_{\alpha }:\mathbb {N} \rightarrow \mathbb {N} )_{\alpha <\mu }$ , где $\mu$ — это некий большой счётный ординал, такой, что фундаментальные последовательности присвоены всем предельным ординалам, меньшим чем $\mu$.

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

• $g_{0}(n)=0$
• $g_{\alpha +1}(n)=g_{\alpha }(n)+1$
• $g_{\alpha }(n)=g_{\alpha [n]}(n)$, если и только если $\alpha$ — предельный ординал,

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

Каждый ненулевой ординал $\alpha <\varepsilon _{0}=\min\{\beta |\beta =\omega ^{\beta }\}$ может быть представлен в уникальной нормальной форме Кантора $\alpha =\omega ^{\beta _{1}}+\omega ^{\beta _{2}}+\cdots +\omega ^{\beta _{k-1}}+\omega ^{\beta _{k}},$ где $\omega$ – первый трансфинитный ординал, $\alpha >\beta _{1}\geq \beta _{2}\geq \cdots \geq \beta _{k-1}\geq \beta _{k}$.

Если $\beta _{k}>0$, тогда $\alpha$ — предельный ординал и ему может быть присвоена фундаментальная последовательность следующим образом:

$\alpha [n]=\omega ^{\beta _{1}}+\omega ^{\beta _{2}}+\cdots +\omega ^{\beta _{k-1}}+\left\{{\begin{array}{lcr}\omega ^{\gamma }n{\text{, если }}\beta _{k}=\gamma +1\\\omega ^{\beta _{k}[n]}{\text{, если }}\beta _{k}{\text{ - предельный ординал.}}\\\end{array}}\right.$

Если $\alpha =\varepsilon _{0}$, тогда $\alpha [0]=0$ и $\alpha [n+1]=\omega ^{\alpha [n]}$.

Используя эту систему фундаментальных последовательностей можно определить медленнорастущую иерархию до первого числа эпсилон $\varepsilon _{0}$. Для $\alpha =\varepsilon _{0}$ верно равенство $g_{\varepsilon _{0}}(n)=n\uparrow \uparrow n$ согласно стрелочной нотации.

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

• Функция Веблена
• Пси-функции Бухгольца

Медленнорастущая иерархия «догоняет» быстрорастущую иерархию при $\alpha =\psi _{0}(\Omega _{\omega })$, используя пси-функции Бухгольца, то есть

$g_{\psi _{0}(\Omega _{\omega })}(n)<f_{\psi _{0}(\Omega _{\omega })}(n)<g_{\psi _{0}(\Omega _{\omega })}(n+1)$ для всех $n>0$.

См. также

• Быстрорастущая иерархия
• Иерархия Харди