Английская Википедия: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_α: N → N (where N is the set of natural numbers, {0, 1, ...}) called Hardy functions. It is related to the fast-growing hierarchy and slow-growing hierarchy.

Hardy hierarchy is 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 <math>\aleph_1</math>.

Definition

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

• <math> H_0(n) = n,</math>
• <math> H_{\alpha+1}(n) = H_\alpha(n + 1),</math>
• <math> H_{\alpha}(n) = H_{\alpha[n]}(n) </math> if α is a limit ordinal.

Here α[n] denotes the n^th element of the fundamental sequence assigned to the limit ordinal α. A standardized choice of fundamental sequence for all α ≤ ε₀ is described in the article on the fast-growing hierarchy.

The Hardy hierarchy <math>\{\mathcal{H}_\alpha\}_{\alpha<\mu}</math> is a family of numerical functions. For each ordinal Шаблон:Math, a set <math>\mathcal{H}_\alpha</math> is defined as the smallest class of functions containing Шаблон:Math, zero, successor and projection functions, and closed under limited primitive recursion and limited substitution (similar to Grzegorczyk hierarchy).

Шаблон:Harvp defines a modified Hardy hierarchy of functions <math>H_\alpha</math> 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_α and the Hardy hierarchy of functions H_α are related by f_α = H_ω^α for all α < ε₀. Thus, for any α < ε₀, H_α grows much more slowly than does f_α. However, the Hardy hierarchy "catches up" to the Wainer hierarchy at α = ε₀, such that f_ε0 and H_ε0 have the same growth rate, in the sense that f_ε0(n-1) ≤ H_ε0(n) ≤ f_ε0(n+1) for all n ≥ 1. Шаблон:Harv

References

• Шаблон:Citation
• Шаблон:Citation. (In particular Section 12, pp. 59–64, "A Glimpse at Hierarchies of Fast and Slow Growing Functions".)
• Шаблон:Citation.