Hardy Hierarchie - Hardy hierarchy

In der Berechenbarkeitstheorie , der Computational Complexity Theory und der Beweistheorie ist die Hardy-Hierarchie , benannt nach GH Hardy , eine ordinalindexierte Familie von Funktionen h _α :  N  →  N (wobei N die Menge der natürlichen Zahlen {0, 1, . ..}). Es hängt mit der schnell wachsenden Hierarchie und der langsam wachsenden Hierarchie zusammen . Die Hierarchie wurde erstmals 1904 in Hardys Papier "Ein Satz über die unendlichen Kardinalzahlen" beschrieben.

Definition

Sei μ eine große abzählbare Ordinalzahl, so dass jeder Grenzordinalzahl kleiner als μ eine Fundamentalfolge zugeordnet ist . Die Hardy-Hierarchie der Funktionen h _α :  N  →  N , für α  <  μ , ist dann wie folgt definiert:

• ${\displaystyle h_{0}(n)=n,}$
• ${\displaystyle h_{\alpha+1}(n)=h_{\alpha}(n+1),}$
• ${\displaystyle h_{\alpha}(n)=h_{\alpha[n]}(n)}$ wenn α eine Grenzordinal ist.

Dabei bezeichnet α[ n ] das n- ^te Element der der Grenzordinalzahl α zugeordneten Fundamentalfolge  . Eine standardisierte Wahl der Fundamentalfolge für alle  α  ≤  ε ₀ wird im Artikel über die schnell wachsende Hierarchie beschrieben .

Caicedo (2007) definiert eine modifizierte Hardy-Hierarchie von Funktionen unter Verwendung der Standard-Fundamentalfolgen, jedoch mit α[ n +1] (anstelle von α[ n ]) in der dritten Zeile der obigen Definition. ${\displaystyle H_{\alpha}}$

Bezug zu schnell wachsender Hierarchie

Die Wainer- Funktionshierarchie f _α und die Hardy-Hierarchie der Funktionen h _α stehen in Beziehung zu f _α = h _{ω ^α} für alle α < related ₀ . So kann jede α <ε ₀ , h _α wächst viel langsamer , als dies f _α . Jedoch "holt" die Hardy-Hierarchie die Wainer-Hierarchie bei α = ε _{0 ein} , so dass f _{ε 0} und h _{ε 0} die gleiche Wachstumsrate haben, in dem Sinne, dass f _{ε 0} ( n -1) ≤ h _{ε 0} ( n ) ≤ f _{ε 0} ( n +1) für alle n ≥ 1. ( Gallier 1991 )

Verweise

• Hardy, GH (1904), „Ein Theorem über die unendlichen Kardinalzahlen“, Quarterly Journal of Mathematics , 35 : 87–94
• Gallier, Jean H. (1991), "Was ist das Besondere am Satz von Kruskal und der Ordinalzahl Γ ₀ ? Ein Überblick über einige Ergebnisse in der Beweistheorie" (PDF) , Ann. Reine Appl. Logik , 53 (3): 199–260, doi : 10.1016/0168-0072(91)90022-E , MR  1129778. (Insbesondere Abschnitt 12, S. 59–64, „Ein Blick auf Hierarchien schnell und langsam wachsender Funktionen“.)
• Caicedo, A. (2007), "Goodsteins Funktion" (PDF) , Revista Colombiana de Matemáticas , 41 (2): 381–391.