Härlig hierarki

I beräkningsteori , beräkningskomplexitetsteori och bevisteori är Hardy -hierarkin , uppkallad efter GH Hardy , en hierarki av uppsättningar numeriska funktioner genererade från en ordinalindexerad familj av funktioner h _α : N → N (där N är mängden av naturliga tal , {0, 1, ...}) kallade Hardy-funktioner . Det är relaterat till den snabbt växande hierarkin och den långsamt växande hierarkin .

Hardy hierarki introducerades av Stanley S. Wainer 1972, men idén om dess definition kommer från Hardys 1904 papper, där Hardy uppvisar en uppsättning reals med kardinalitet ℵ $\displaystyle \aleph _{1}}$ .

Definition

Låt μ vara en stor räknbar ordinal så att en fundamental sekvens tilldelas varje gränsordinal mindre än μ. De härdiga funktionerna h _α : N → N , för α < μ , definieras sedan enligt följande:

$h_{0}(n)=n,$
$h_{\alpha +1}(n)=h_{\alpha }(n+1),$
$h_{\alpha }(n)=h_{\alpha [n]}(n)$ om α är en limitordinal.

₀ betecknar α[ n ] det n: ^te elementet i den fundamentala sekvensen som är tilldelad gränsordinalen α . Ett standardiserat val av fundamental sekvens för alla α ≤ ε beskrivs i artikeln om den snabbt växande hierarkin .

Hardy -hierarkin ${\displaystyle \{{\mathcal {H}}_{\alpha }\}_{\alpha <\mu }} är$ en familj av numeriska funktioner. För varje ordinal $α$ definieras en mängd ${\displaystyle {\mathcal {H}}_{\alpha }} som den minsta klassen av funktioner som innehåller$ $h α$ , noll, efterföljande och projektionsfunktioner, och stängd under begränsad primitiv rekursion och begränsad substitution (liknande Grzegorczyk-hierarkin) .

Caicedo (2007) definierar en modifierad Hardy-hierarki av funktioner $H_{\alpha }$ genom att använda standardgrundsekvenserna, men med α[ n +1] (istället för α[ n ]) på den tredje raden av definitionen ovan.

Förhållande till snabbt växande hierarki

₀₀₀ Wainer- hierarkin av funktioner f _α och Hardy-hierarkin av funktioner h _α är relaterade till f _α = h _{ω ^α} för alla α < ε . Sålunda, för vilken α < ε som helst, växer h _α mycket långsammare än f _α . Hardy-hierarkin "kommer ikapp" Wainer-hierarkin vid α = ε , så att f _{ε ₀} och h _{ε ₀} har samma tillväxthastighet, i den meningen att f _{ε ₀} ( n -1) ≤ h _{ε ₀} ( n ) ≤ f _{ε ₀} ( n +1) för alla n ≥ 1. ( Gallier 1991 )

Anteckningar

Hardy, GH (1904), "A theorem concerning the infinite cardinal numbers", Quarterly Journal of Mathematics , 35 : 87–94
Gallier, Jean H. (1991), ₀ "Vad är så speciellt med Kruskals sats och ordinalen Γ ? En översikt över några resultat i bevisteori" (PDF) , Ann. Ren appl. Logic , 53 (3): 199-260, doi : 10.1016/0168-0072(91)90022-E , MR 1129778 . (Särskilt avsnitt 12, s. 59–64, "A Glimt at Hierarchies of Fast and Slow Growing Functions".)
Caicedo, A. (2007), "Goodsteins funktion" (PDF) , Revista Colombiana de Matemáticas , 41 (2): 381–391 .