Jerarquía de crecimiento lento

La jerarquía de crecimiento lento es una familia de funciones , donde hay un ordinal de conteo grande , de modo que las secuencias fundamentales se asignan a todos los ordinales límite menores que . ${\displaystyle (g_{\alpha }:\mathbb {N} \rightarrow \mathbb {N} )_{\alpha <\mu ))$ $\mu$ $\mu$

Una jerarquía de crecimiento lento se define de la siguiente manera:

$g_{0}(n)=0$
$g_{\alfa +1}(n)=g_{\alfa}(n)+1$
$g_{\alpha }(n)=g_{\alpha [n]}(n)$ , si y solo si es un ordinal límite, $\alfa$

donde denota el elemento th de la secuencia fundamental asignado al ordinal límite . ${\ estilo de visualización \ alfa [n]}$ $norte$ $\alfa$

Cada ordinal distinto de cero se puede representar en la forma normal única de Cantor, donde es el primer ordinal transfinito, . ${\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$ ${\ estilo de visualización \ alfa > \ beta _ {1} \ geq \ beta _ {2} \ geq \ cdots \ geq \ beta _ {k-1} \ geq \ beta _ {k}}$

Si , entonces es un ordinal límite y se le puede asignar una secuencia fundamental de la siguiente manera: ${\ estilo de visualización \ beta _ {k}> 0}$ $\alfa$

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

Si , entonces y . ${\ estilo de visualización \ alfa = \ varepsilon _ {0}}$ ${\ estilo de visualización \ alfa [0] = 0}$ ${\ estilo de visualización \ alfa [n+1] = \ omega ^ {\ alfa [n]}}$

Usando este sistema de secuencias fundamentales, se puede definir una jerarquía de crecimiento lento hasta el primer épsilon . Para la verdadera igualdad según la notación de flechas . $\varepsilon_{0}$ ${\ estilo de visualización \ alfa = \ varepsilon _ {0}}$ $g_{\varepsilon _{0}}(n)=n\flecha arriba \flecha arriba n$

Se pueden encontrar sistemas más poderosos de secuencias fundamentales en las siguientes páginas:

La jerarquía de crecimiento lento "alcanza" a la jerarquía de rápido crecimiento en , utilizando las funciones psi de Buchholz , es decir, [1] ${\ estilo de visualización \ alfa = \ psi _ {0} (\ omega _ {\ omega})}$

$g_{\psi_{0}(\Omega_{\omega })}(n)<f_{\psi_{0}(\Omega_{\omega })}(n)<g_{\ psi _{0}(\Omega _{\omega })}(n+1)$ para todos ${\ estilo de visualización n> 0}$

Véase también

Notas

↑ Wainer, S. Crecimiento lento versus crecimiento rápido // The Journal of Symbolic Logic: diario. - 1989. - vol. 54 , núm. 2 . — pág. 608-614 .

Enlaces

Grandes números
Números	gogol Número de Shannon googolplex número de sesgos número de Moser número de graham ÁRBOL(3) Número de Rayo
Funciones	Función de Ackermann Función Veblen Funciones psi de Buchholz tetración pentación hiperoperador Jerarquía de rápido crecimiento Jerarquía de crecimiento lento Jerarquía resistente
Notaciones	Notación de Steinhaus-Moser Notación de flecha Knuth Notación de flecha de Conway Notación masiva de Bowers