Jerarquía Hardy

En teoría de la computabilidad , teoría de la complejidad computacional y teoría de la demostración , la jerarquía de Hardy , llamada así por GH Hardy , es una jerarquía de conjuntos de funciones numéricas generadas a partir de una familia de funciones indexadas ordinalmente h _α :  N  →  N (donde N es el conjunto de números naturales , {0, 1, ...}) llamadas funciones de Hardy . Está relacionada con la jerarquía de crecimiento rápido y la jerarquía de crecimiento lento .

La jerarquía de Hardy fue introducida por Stanley S. Wainer en 1972, ^{[1] [2]} pero la idea de su definición proviene del artículo de Hardy de 1904, ^{[2] [3]} en el que Hardy exhibe un conjunto de números reales con cardinalidad . ${\displaystyle \aleph _{1}}$

Definición

Sea μ un ordinal contable grande tal que se asigne una secuencia fundamental a cada ordinal límite menor que μ. La función de Hardy h _α :  N  →  N , para α  <  μ , se define entonces de la siguiente manera:

• ${\displaystyle H_{0}(n)=n,}$
• ${\displaystyle H_{\alpha +1}(n)=H_{\alpha }(n+1),}$
• ${\displaystyle H_{\alpha }(n)=H_{\alpha [n]}(n)}$si α es un ordinal límite.

Aquí α[ n ] denota el n ^º elemento de la secuencia fundamental asignada al ordinal límite  α . En el artículo sobre la jerarquía de rápido crecimiento se describe una elección estandarizada de la secuencia fundamental para todos  los α  ≤  ε ₀ .

La jerarquía de Hardy es una familia de funciones numéricas. Para cada ordinal α , se define un conjunto como la clase más pequeña de funciones que contiene H _α , funciones cero, sucesoras y de proyección, y está cerrada bajo recursión primitiva limitada y sustitución limitada ^[2] (similar a la jerarquía de Grzegorczyk ). ${\displaystyle \{{\mathcal {H}}_{\alpha }\}_{\alpha <\mu }}$ ${\displaystyle {\mathcal {H}}_{\alpha }}$

Caicedo (2007) define una jerarquía Hardy modificada de funciones utilizando las secuencias fundamentales estándar, pero con α[ n +1] (en lugar de α[ n ]) en la tercera línea de la definición anterior. ${\displaystyle H_{\alpha }}$

Relación con la jerarquía de rápido crecimiento

La jerarquía de funciones de Wainer f _α y la jerarquía de funciones de Hardy H _α están relacionadas por f _α = H _{ω ^α} para todo α < ε ₀ . Por lo tanto, para todo α < ε ₀ , H _α crece mucho más lentamente que f _α . Sin embargo, la jerarquía de Hardy "alcanza" a la jerarquía de Wainer en α = ε ₀ , de modo que f _{ε 0} y H _{ε 0} tienen la misma tasa de crecimiento, en el sentido de que f _{ε 0} ( n -1) ≤ H _{ε 0} ( n ) ≤ f _{ε 0} ( n +1) para todo n ≥ 1. (Gallier 1991)

Notas

1. Fairtlough, Matt; Wainer, Stanley S. (1998). "Capítulo III - Jerarquías de funciones recursivas demostrables". Manual de teoría de la prueba . Vol. 137. Elsevier. págs. 149–207. doi :10.1016/S0049-237X(98)80018-9. ISBN . 9780444898401.
2. Wainer, SS (1972). "Recursión ordinal y un refinamiento de la jerarquía de Grzegorczyk extendida". Revista de lógica simbólica . 37 (2): 281–292. doi :10.2307/2272973. ISSN  0022-4812. JSTOR  2272973. S2CID  34993575.
3. Hardy, GH (1904). "UN TEOREMA SOBRE LOS NÚMEROS CANÓNICOS INFINITOS". Quarterly Journal of Mathematics . 35 : 87–94.

Referencias

• Hardy, GH (1904), "Un teorema sobre los números cardinales infinitos", Quarterly Journal of Mathematics , 35 : 87–94
• Gallier, Jean H. (1991), "¿Qué tiene de especial el teorema de Kruskal y el ordinal Γ0? Un estudio de algunos resultados en teoría de la demostración" (PDF) , Ann. Pure Appl. Logic , 53 (3): 199–260, doi : 10.1016/0168-0072(91)90022-E , MR  1129778. (En particular, la Sección 12, págs. 59-64, "Un vistazo a las jerarquías de funciones de crecimiento rápido y lento".)
• Caicedo, A. (2007), "Función de Goodstein" (PDF) , Revista Colombiana de Matemáticas , 41 (2): 381–391.