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

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

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

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

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

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

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

α [ n ] = ω β 1 + ω β 2 + ⋯ + ω β k − 1 + { ω γ n , если  β k = γ + 1 ω β k [ n ] , если  β k  - предельный ординал. {displaystyle alpha [n]=omega ^{eta _{1}}+omega ^{eta _{2}}+cdots +omega ^{eta _{k-1}}+left{{egin{array}{lcr}omega ^{gamma }n{ ext{, если }}eta _{k}=gamma +1omega ^{eta _{k}[n]}{ ext{, если }}eta _{k}{ ext{ - предельный ординал.}}end{array}} ight.}

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

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

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

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

Медленнорастущая иерархия "догоняет" быстрорастущую иерархию при α = ψ 0 ( Ω ω ) {displaystyle alpha =psi _{0}(Omega _{omega })} , используя пси-функции Бухгольца, то есть

g ψ 0 ( Ω ω ) ( n ) < f ψ 0 ( Ω ω ) ( n ) < g ψ 0 ( Ω ω ) ( n + 1 ) {displaystyle g_{psi _{0}(Omega _{omega })}(n)<f_{psi _{0}(Omega _{omega })}(n)<g_{psi _{0}(Omega _{omega })}(n+1)} для всех n > 0 {displaystyle n>0} .