Hierarkia kasvaa hitaasti

Hitaasti kasvava hierarkia on funktioperhe , jossa on suuri laskentajärjestys siten, että perussekvenssit osoitetaan kaikille rajajärjestyksille, jotka ovat pienempiä kuin . ${\displaystyle (g_{\alpha }:\mathbb {N} \rightarrow \mathbb {N} )_{\alpha <\mu ))$ $\mu$ $\mu$

Hitaasti kasvava hierarkia määritellään seuraavasti:

$g_{0}(n)=0$
$g_{\alpha +1}(n)=g_{\alpha }(n)+1$
$g_{\alpha }(n)=g_{\alpha [n]}(n)$ , jos ja vain jos raja on järjestysluku, $\alpha$

jossa tarkoittaa rajajärjestäjälle määritetyn perussekvenssin th elementtiä . $\alpha[n]$ $n$ $\alpha$

Jokainen nollasta poikkeava järjestysluku voidaan esittää ainutlaatuisessa Cantor-normaalimuodossa, jossa on ensimmäinen transfiniittinen järjestysluku, . ${\displaystyle \alpha <\varepsilon _{0}=\min\{\beta |\beta =\omega ^{\beta }\))$ $\alpha =\omega ^{\beta _{1}}+\omega ^{\beta _{2}}+\cdots +\omega ^{\beta _{k-1}}+\omega ^ {\beta _{k)),$ $\omega$ ${\displaystyle \alpha >\beta _{1}\geq \beta _{2}\geq \cdots \geq \beta _{k-1}\geq \beta _{k))$

Jos , then on rajajärjestys, ja sille voidaan määrittää perussekvenssi seuraavasti: $\beta _{k}>0$ $\alpha$

$\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]}{\teksti{ if }}\beta _{k}{\text{ - limit ordinaal.}}\\\end{array}}\right.$

Jos , sitten ja . $\alpha =\varepsilon _{0}$ $\alpha [0]=0$ $\alpha [n+1]=\omega ^{\alpha [n]}$

Käyttämällä tätä perussekvenssijärjestelmää voidaan määrittää hitaasti kasvava hierarkia ensimmäiseen epsiloniin asti . Todelliseen tasa -arvoon nuolimerkinnän mukaan . $\varepsilon_{0}$ $\alpha =\varepsilon _{0}$ $g_{\varepsilon _{0}}(n)=n\uparrow \uparrow n$

Tehokkaampia perussekvenssijärjestelmiä löytyy seuraavilta sivuilta:

Hitaasti kasvava hierarkia "takaa" kiinni nopeasti kasvavan hierarkian kanssa käyttämällä Buchholzin psi-funktioita , eli [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)$ kaikille . $n>0$

Katso myös

Muistiinpanot

↑ Wainer, S. Slow Growing Versus Fast Growing // The Journal of Symbolic Logic: Journal. - 1989. - Voi. 54 , nro. 2 . — s. 608-614 .

Linkit

Isoja lukuja
Numerot	googol Shannonin numero Googolplex Skewesin numero Moserin numero Grahamin numero PUU(3) Rayo numero
Toiminnot	Ackermann-toiminto Veblen-toiminto Buchholzin Psi-funktiot tetration Pentation Hyperoperaattori Nopeasti kasvava hierarkia Hierarkia kasvaa hitaasti Kova hierarkia
Merkinnät	Steinhaus-Moser-merkintä Knuthin nuolen merkintä Conway-nuolen merkintä Massiivinen Bowers-merkintä