my-server
← Wiki

Hardy hierarchy

In computability theory, computational complexity theory and proof theory, the Hardy hierarchy, named after G. H. Hardy, is a hierarchy of sets of numerical functions generated from an ordinal-indexed family of functions h<sub>α</sub>:&nbsp;N&nbsp;→&nbsp;N (where N is the set of natural numbers, {0,&nbsp;1,&nbsp;...}) called Hardy functions. It is related to the fast-growing hierarchy and slow-growing hierarchy.

The Hardy hierarchy was introduced by Stanley S. Wainer in 1972, but the idea of its definition comes from Hardy's 1904 paper, in which Hardy exhibits a set of reals with cardinality .

Definition

Let μ be a large countable ordinal such that a fundamental sequence is assigned to every limit ordinal less than μ. The Hardy functions h<sub>α</sub>:&nbsp;N&nbsp;→&nbsp;N, for α&nbsp;<&nbsp;μ, is then defined as follows:

  • if α is a limit ordinal.

Here α[n] denotes the n<sup>th</sup> element of the fundamental sequence assigned to the limit ordinal&nbsp;α. A standardized choice of fundamental sequence for all&nbsp;α&nbsp;≤&nbsp;ε<sub>0</sub> is described in the article on the fast-growing hierarchy.

The Hardy hierarchy is a family of numerical functions. For each ordinal , a set is defined as the smallest class of functions containing , zero, successor and projection functions, and closed under limited primitive recursion and limited substitution (similar to Grzegorczyk hierarchy).

defines a modified Hardy hierarchy of functions by using the standard fundamental sequences, but with α[n+1] (instead of α[n]) in the third line of the above definition.

Relation to fast-growing hierarchy

The Wainer hierarchy of functions f<sub>α</sub> and the Hardy hierarchy of functions H<sub>α</sub> are related by f<sub>α</sub> = H<sub>ω<sup>α</sup></sub> for all α < ε<sub>0</sub>. Thus, for any α < ε<sub>0</sub>, H<sub>α</sub> grows much more slowly than does f<sub>α</sub>. However, the Hardy hierarchy "catches up" to the Wainer hierarchy at α = ε<sub>0</sub>, such that f<sub>ε<sub>0</sub></sub> and H<sub>ε<sub>0</sub></sub> have the same growth rate, in the sense that f<sub>ε<sub>0</sub></sub>(n-1) ≤ H<sub>ε<sub>0</sub></sub>(n) ≤ f<sub>ε<sub>0</sub></sub>(n+1) for all n ≥ 1.

Notes

References

  • . (In particular Section 12, pp.&nbsp;59–64, "A Glimpse at Hierarchies of Fast and Slow Growing Functions".)
  • .