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

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

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

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

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

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

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

${\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.}$

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

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

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

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

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

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

См. также

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

Примечания

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

Ссылки