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

Медленнорастущая иерархия представляет собой семейство функций $(g_{\alpha }:\mathbb{N}\to \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 <{\epsilon }_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\ge {\beta }_2\ge \cdots \ge {\beta }_{k-1}\ge {\beta }_k$.

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

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

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

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

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

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

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

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

См. также

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