Медленнорастущая иерархия
Медленнорастущая иерархия представляет собой семейство функций [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], используя пси-функции Бухгольца, то есть[1]
[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].
См. также
Примечания
- ↑ Wainer, S. Slow Growing Versus Fast Growing (англ.) // The Journal of Symbolic Logic : journal. — 1989. — Vol. 54, no. 2. — P. 608-614.