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

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

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

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

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

Каждый ненулевой ординал [math]\displaystyle{ \alpha\lt \varepsilon_0=\min\{\beta|\beta=\omega^\beta\} }[/math] может быть представлен в уникальной нормальной форме Кантора [math]\displaystyle{ \alpha=\omega^{\beta_{1}}+ \omega^{\beta_{2}}+\cdots+\omega^{\beta_{k-1}}+\omega^{\beta_{k}}, }[/math] где [math]\displaystyle{ \omega }[/math] – первый трансфинитный ординал, [math]\displaystyle{ \alpha\gt \beta_1\geq\beta_2\geq\cdots\geq\beta_{k-1}\geq\beta_k }[/math].

Если [math]\displaystyle{ \beta_k\gt 0 }[/math], тогда [math]\displaystyle{ \alpha }[/math] — предельный ординал и ему может быть присвоена фундаментальная последовательность следующим образом:

[math]\displaystyle{ \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. }[/math]

Если [math]\displaystyle{ \alpha=\varepsilon_0 }[/math], тогда [math]\displaystyle{ \alpha[0]=0 }[/math] и [math]\displaystyle{ \alpha[n+1]=\omega^{\alpha[n]} }[/math].

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

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

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

Медленнорастущая иерархия «догоняет» быстрорастущую иерархию при [math]\displaystyle{ \alpha=\psi_0(\Omega_\omega) }[/math], используя пси-функции Бухгольца, то есть

[math]\displaystyle{ g_{\psi_0(\Omega_\omega)}(n) \lt f_{\psi_0(\Omega_\omega)}(n) \lt g_{\psi_0(\Omega_\omega)}(n+1) }[/math] для всех [math]\displaystyle{ n \gt 0 }[/math].

См. также

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