Ierarhie în creștere lent

Ierarhia care crește încet este o familie de funcții , unde este un ordinal mare de numărare , astfel încât secvențele fundamentale sunt atribuite tuturor ordinalelor limită mai mici de . $(g_{\alpha }:\mathbb {N} \rightarrow \mathbb {N} )_{\alpha <\mu )$ $\mu$ $\mu$

O ierarhie cu creștere lentă este definită după cum urmează:

$g_{0}(n)=0$
$g_{\alpha +1}(n)=g_{\alpha }(n)+1$
$g_{\alpha }(n)=g_{\alpha [n]}(n)$ , dacă și numai dacă este un ordinal limită, $\alfa$

unde denotă al-lea element al șirului fundamental alocat ordinalului limită . $\alpha[n]$ $n$ $\alfa$

Fiecare ordinal diferit de zero poate fi reprezentat într-o formă normală Cantor unică, unde este primul ordinal transfinit, . $\alpha <\varepsilon _{0}=\min\{\beta |\beta =\omega ^{\beta }\)$ $\alpha =\omega ^{\beta _{1}}+\omega ^{\beta _{2}}+\cdots +\omega ^{\beta _{k-1}}+\omega ^ {\beta _{k)),$ $\omega$ $\alpha >\beta _{1}\geq \beta _{2}\geq \cdots \geq \beta _{k-1}\geq \beta _{k)$

Dacă , atunci este un ordinal limită și i se poate atribui o secvență fundamentală după cum urmează: $\beta _{k}>0$ $\alfa$

$\alpha [n]=\omega ^{\beta _{1}}+\omega ^{\beta _{2}}+\cdots +\omega ^{\beta _{k-1}}+ \left\{{\begin{array}{lcr}\omega ^{\gamma }n{\text{ if }}\beta _{k}=\gamma +1\\\omega ^{\beta _{ k }[n]}{\text{ if }}\beta _{k}{\text{ - limita ordinal.}}\\\end{array}}\right.$

Dacă , atunci și . $\alpha =\varepsilon _{0}$ $\alpha [0]=0$ $\alpha [n+1]=\omega ^{\alpha [n]}$

Folosind acest sistem de secvențe fundamentale, se poate defini o ierarhie care crește încet până la primul epsilon . Pentru egalitate adevărată conform notației cu săgeți . $\varepsilon_{0}$ $\alpha =\varepsilon _{0}$ $g_{\varepsilon _{0}}(n)=n\uparrow \uparrow n$

Sisteme mai puternice de secvențe fundamentale pot fi găsite pe următoarele pagini:

Ierarhia cu creștere lentă „prinde din urmă” cu ierarhia cu creștere rapidă de la , folosind funcțiile psi Buchholz , adică [1] $\alpha =\psi _{0}(\Omega _{\omega })$

$g_{\psi _{0}(\Omega _{\omega })}(n)<f_{\psi _{0}(\Omega _{\omega })}(n)<g_{\ psi _{0}(\Omega _{\omega })}(n+1)$ pentru toată lumea . $n>0$

Vezi și

Note

↑ Wainer, S. Slow Growing Versus Fast Growing // Jurnalul de logică simbolică: jurnal. - 1989. - Vol. 54 , nr. 2 . — P. 608-614 .

Link -uri

Cifre mari
Numerele	googol Numărul Shannon Googlelplex Număr înclinat numărul Moser Numărul Graham TREE(3) Numărul Rayo
Funcții	Funcția Ackermann Funcția Veblen Funcțiile Psi ale lui Buchholz tetrare Pentație Hiperoperator Ierarhie în creștere rapidă Ierarhie în creștere lent Ierarhie Hardy
Notații	Notația Steinhaus-Moser Notație cu săgeată Knuth Notație săgeată Conway Notație masivă Bowers