computability theory Computability theory, also known as recursion theory, is a branch of mathematical logic, computer science, and the theory of computation that originated in the 1930s with the study of computable functions and Turing degrees. The field has since ex ...

computational complexity theory In theoretical computer science and mathematics, computational complexity theory focuses on classifying computational problems according to their resource usage, and explores the relationships between these classifications. A computational problem ...

and

proof theory Proof theory is a major branchAccording to , proof theory is one of four domains mathematical logic, together with model theory, axiomatic set theory, and recursion theory. consists of four corresponding parts, with part D being about "Proof The ...

, the Hardy hierarchy, named after

G. H. Hardy Godfrey Harold Hardy (7 February 1877 – 1 December 1947) was an English mathematician, known for his achievements in number theory and mathematical analysis. In biology, he is known for the Hardy–Weinberg principle, a basic principle of pop ...

, 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 In mathematics, the natural numbers are the numbers 0, 1, 2, 3, and so on, possibly excluding 0. Some start counting with 0, defining the natural numbers as the non-negative integers , while others start with 1, defining them as the positiv ...

, ) called Hardy functions. It is related to the

fast-growing hierarchy In computability theory, computational complexity theory and proof theory, a fast-growing hierarchy (also called an extended Grzegorczyk hierarchy, or a Schwichtenberg-Wainer hierarchy) is an ordinal-indexed family of rapidly increasing functions ' ...

and

slow-growing hierarchy In computability theory, computational complexity theory and proof theory, the slow-growing hierarchy is an ordinal-indexed family of slowly increasing functions ''g''α: N → N (where N is the set of natural numbers, ). It contrasts with the fast- ...

. 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

\aleph_1

Definition

Let ''μ'' be a

large countable ordinal In the mathematical discipline of set theory, there are many ways of describing specific countable ordinals. The smallest ones can be usefully and non-circularly expressed in terms of their Cantor normal forms. Beyond that, many ordinals of relev ...

such that a fundamental sequence is assigned to every

limit ordinal In set theory, a limit ordinal is an ordinal number that is neither zero nor a successor ordinal. Alternatively, an ordinal λ is a limit ordinal if there is an ordinal less than λ, and whenever β is an ordinal less than λ, then there exists a ...

less than ''μ''. The Hardy functions ''h''_''α'': N → N, for ''α'' < ''μ'', is then defined as follows: *

H_0(n) = n,

H_(n) = H_\alpha(n + 1),

H_(n) = H_(n)

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

. The Hardy hierarchy

\_

is a family of numerical functions. For each ordinal , a set

\mathcal_\alpha

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 The Grzegorczyk hierarchy (, ), named after the Polish logician Andrzej Grzegorczyk, is a hierarchy of functions used in computability theory. Every function in the Grzegorczyk hierarchy is a primitive recursive function, and every primitive recu ...

). defines a modified Hardy hierarchy of functions

H_\alpha

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''_ε₀ and ''H''_ε₀ have the same growth rate, in the sense that ''f''_ε₀(''n''-1) ≤ ''H''_ε₀(''n'') ≤ ''f''_ε₀(''n''+1) for all ''n'' ≥ 1.

Notes

References

* *. (In particular Section 12, pp. 59–64, "A Glimpse at Hierarchies of Fast and Slow Growing Functions".) * {{Citation , last=Caicedo , first=A. , title=Goodstein's function , url=http://andrescaicedo.files.wordpress.com/2008/04/goodstein.pdf , journal=Revista Colombiana de Matemáticas , volume=41 , issue=2 , year=2007 , pages=381–391 . Computability theory Proof theory Hierarchy of functions