Русская Википедия:Медленнорастущая иерархия

Содержание

Текст

Текст

Текст

Текст

Текст

Текст

Текст

Текст

Текст

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

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

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

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

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

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

<math>\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>\alpha=\varepsilon_0</math>, тогда <math>\alpha[0]=0</math> и <math>\alpha[n+1]=\omega^{\alpha[n]}</math>.

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

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

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

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

<math> g_{\psi_0(\Omega_\omega)}(n) <f_{\psi_0(\Omega_\omega)}(n) <g_{\psi_0(\Omega_\omega)}(n+1)</math> для всех <math>n >0</math>.

См. также

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