{"history":[],"article":{"id":"03f925ce-a70a-44d4-8e40-f631592492e3","title":"Fast-growing hierarchy","slug":"fast-growing-hierarchy","content":":::summary\n:::\n\n# \nIn [computability theory](https://bliptext.com/articles/computability-theory), [computational complexity theory](https://bliptext.com/articles/computational-complexity-theory) and [proof theory](https://bliptext.com/articles/proof-theory), a **fast-growing hierarchy** (also called an **extended [Grzegorczyk hierarchy](https://bliptext.com/articles/grzegorczyk-hierarchy)**, or a **Schwichtenberg-Wainer hierarchy**) is an [ordinal](https://bliptext.com/articles/ordinal-number)-indexed family of rapidly increasing functions fα: ******N****** → ******N****** (where ******N****** is the set of [natural numbers](https://bliptext.com/articles/natural-numbers) {0, 1, ...}, and α ranges up to some large countable [ordinal](https://bliptext.com/articles/ordinal-number)).\nA primary example is the **Wainer hierarchy**, or Löb–**Wainer hierarchy**, which is an extension to all α < [ε0](https://bliptext.com/articles/epsilon-numbers-mathematics).\nSuch hierarchies provide a natural way to classify [computable functions](https://bliptext.com/articles/computable-function) according to rate-of-growth and [computational complexity](https://bliptext.com/articles/computational-complexity-theory).\n\n# Definition\nLet μ be a [large countable ordinal](https://bliptext.com/articles/large-countable-ordinal) such that to every [limit ordinal](https://bliptext.com/articles/limit-ordinal) α < μ there is assigned a [fundamental sequence](https://bliptext.com/articles/fundamental-sequence-ordinals) (a strictly increasing sequence of ordinals whose supremum is α).\nA **fast-growing hierarchy** of functions fα: ****N**** → ****N****, for α < μ, is then defined as follows:\nHere fαn(n) = fα(fα(...(fα(n))...)) denotes the nth [iterate](https://bliptext.com/articles/iterated-function) of fα applied to n, and α[n] denotes the nth element of the fundamental sequence assigned to the limit ordinal α.\n(An alternative definition takes the number of iterations to be n+1, rather than n, in the second line above.)\nThe initial part of this hierarchy, comprising the functions fα with finite index (i.e., α < ω), is often called the **[Grzegorczyk hierarchy](https://bliptext.com/articles/grzegorczyk-hierarchy)** because of its close relationship to the **[Grzegorczyk hierarchy](https://bliptext.com/articles/grzegorczyk-hierarchy)**; note, however, that the former is here an indexed family of functions fn, whereas the latter is an indexed family of sets of functions.\n(See Points of Interest below.)\nGeneralizing the above definition even further, a **fast iteration hierarchy** is obtained by taking f0 to be any non-decreasing function g: ****N**** → ****N****.\nFor limit ordinals not greater than [ε0](https://bliptext.com/articles/epsilon-numbers-mathematics), there is a straightforward natural definition of the fundamental sequences (see the **Wainer hierarchy** below), but beyond [ε0](https://bliptext.com/articles/epsilon-numbers-mathematics) the definition is much more complicated.\nHowever, this is possible well beyond the Feferman–Schütte ordinal, [Γ0](https://bliptext.com/articles/feferman-sch-tte-ordinal), up to at least the [Bachmann–Howard ordinal](https://bliptext.com/articles/bachmann-howard-ordinal).\nUsing [Buchholz psi functions](https://bliptext.com/articles/buchholz-psi-function) one can extend this definition easily to the ordinal of transfinitely iterated \\Pi^1_1-comprehension (see [Analytical hierarchy](https://bliptext.com/articles/analytical-hierarchy)).\nA fully specified extension beyond the [recursive ordinals](https://bliptext.com/articles/recursive-ordinal) is thought to be unlikely; e.g., Prӧmel et al. [1991](p. 348) note that in such an attempt \"there would even arise problems in ordinal notation\".\n\n# The Wainer hierarchy\nThe **Wainer hierarchy** is the particular fast-growing hierarchy of functions fα (α ≤ [ε0](https://bliptext.com/articles/epsilon-numbers-mathematics)) obtained by defining the fundamental sequences as follows [Gallier 1991][Prӧmel, et al., 1991]:\nFor limit ordinals λ < [ε0](https://bliptext.com/articles/epsilon-numbers-mathematics), written in [Cantor normal form](https://bliptext.com/articles/cantor-normal-form),\nand\nSome authors use slightly different definitions (e.g., ωα+1[n] = ωα(n+1), instead of ωαn), and some define this hierarchy only for α < ε0 (thus excluding fε 0 from the hierarchy).\nTo continue beyond ε0, see the [Fundamental sequences for the Veblen hierarchy](https://bliptext.com/articles/veblen-function).\n\n# Points of interest\nFollowing are some relevant points of interest about fast-growing hierarchies:\n\n# Functions in fast-growing hierarchies\nThe functions at finite levels (α < ω) of any fast-growing hierarchy coincide with those of the Grzegorczyk hierarchy: (using [hyperoperation](https://bliptext.com/articles/hyperoperation))\nBeyond the finite levels are the functions of the Wainer hierarchy (ω ≤ α ≤ ε0):\n\n# Sources","current_revision":null,"created_by":"kACnuQmH5k9Nr5VNVEpVeg7XpvUmMctD","created_at":"2025-01-26T12:06:52.735Z","updated_at":"2025-01-26T12:06:52.735Z","search_vector":"'fast':2 'fast-grow':1 'grow':3 'hierarchi':4","search_content":" \n \n\n# \nIn [computability theory](https://bliptext.com/articles/computability-theory), [computational complexity theory](https://bliptext.com/articles/computational-complexity-theory) and [proof theory](https://bliptext.com/articles/proof-theory), a **fast-growing hierarchy** (also called an **extended [Grzegorczyk hierarchy](https://bliptext.com/articles/grzegorczyk-hierarchy)**, or a **Schwichtenberg-Wainer hierarchy**) is an [ordinal](https://bliptext.com/articles/ordinal-number)-indexed family of rapidly increasing functions fα: ******N****** → ******N****** (where ******N****** is the set of [natural numbers](https://bliptext.com/articles/natural-numbers) {0, 1, ...}, and α ranges up to some large countable [ordinal](https://bliptext.com/articles/ordinal-number)).\nA primary example is the **Wainer hierarchy**, or Löb–**Wainer hierarchy**, which is an extension to all α < [ε0](https://bliptext.com/articles/epsilon-numbers-mathematics).\nSuch hierarchies provide a natural way to classify [computable functions](https://bliptext.com/articles/computable-function) according to rate-of-growth and [computational complexity](https://bliptext.com/articles/computational-complexity-theory).\n\n# Definition\nLet μ be a [large countable ordinal](https://bliptext.com/articles/large-countable-ordinal) such that to every [limit ordinal](https://bliptext.com/articles/limit-ordinal) α < μ there is assigned a [fundamental sequence](https://bliptext.com/articles/fundamental-sequence-ordinals) (a strictly increasing sequence of ordinals whose supremum is α).\nA **fast-growing hierarchy** of functions fα: ****N**** → ****N****, for α < μ, is then defined as follows:\nHere fαn(n) = fα(fα(...(fα(n))...)) denotes the nth [iterate](https://bliptext.com/articles/iterated-function) of fα applied to n, and α[n] denotes the nth element of the fundamental sequence assigned to the limit ordinal α.\n(An alternative definition takes the number of iterations to be n+1, rather than n, in the second line above.)\nThe initial part of this hierarchy, comprising the functions fα with finite index (i.e., α < ω), is often called the **[Grzegorczyk hierarchy](https://bliptext.com/articles/grzegorczyk-hierarchy)** because of its close relationship to the **[Grzegorczyk hierarchy](https://bliptext.com/articles/grzegorczyk-hierarchy)**; note, however, that the former is here an indexed family of functions fn, whereas the latter is an indexed family of sets of functions.\n(See Points of Interest below.)\nGeneralizing the above definition even further, a **fast iteration hierarchy** is obtained by taking f0 to be any non-decreasing function g: ****N**** → ****N****.\nFor limit ordinals not greater than [[ε0](https://bliptext.com/articles/epsilon-numbers-mathematics)](https://bliptext.com/articles/epsilon-numbers-mathematics), there is a straightforward natural definition of the fundamental sequences (see the **Wainer hierarchy** below), but beyond [[ε0](https://bliptext.com/articles/epsilon-numbers-mathematics)](https://bliptext.com/articles/epsilon-numbers-mathematics) the definition is much more complicated.\nHowever, this is possible well beyond the Feferman–Schütte ordinal, [Γ0](https://bliptext.com/articles/feferman-sch-tte-ordinal), up to at least the [Bachmann–Howard ordinal](https://bliptext.com/articles/bachmann-howard-ordinal).\nUsing [Buchholz psi functions](https://bliptext.com/articles/buchholz-psi-function) one can extend this definition easily to the ordinal of transfinitely iterated \\Pi^1_1-comprehension (see [Analytical hierarchy](https://bliptext.com/articles/analytical-hierarchy)).\nA fully specified extension beyond the [recursive ordinals](https://bliptext.com/articles/recursive-ordinal) is thought to be unlikely; e.g., Prӧmel et al. [1991](p. 348) note that in such an attempt \"there would even arise problems in ordinal notation\".\n\n# The Wainer hierarchy\nThe **Wainer hierarchy** is the particular fast-growing hierarchy of functions fα (α ≤ [ε0](https://bliptext.com/articles/epsilon-numbers-mathematics)) obtained by defining the fundamental sequences as follows [Gallier 1991][Prӧmel, et al., 1991]:\nFor limit ordinals λ < [ε0](https://bliptext.com/articles/epsilon-numbers-mathematics), written in [Cantor normal form](https://bliptext.com/articles/cantor-normal-form),\nand\nSome authors use slightly different definitions (e.g., ωα+1[n] = ωα(n+1), instead of ωαn), and some define this hierarchy only for α < ε0 (thus excluding fε 0 from the hierarchy).\nTo continue beyond ε0, see the [Fundamental sequences for the Veblen hierarchy](https://bliptext.com/articles/veblen-function).\n\n# Points of interest\nFollowing are some relevant points of interest about fast-growing hierarchies:\n\n# Functions in fast-growing hierarchies\nThe functions at finite levels (α < ω) of any fast-growing hierarchy coincide with those of the Grzegorczyk hierarchy: (using [hyperoperation](https://bliptext.com/articles/hyperoperation))\nBeyond the finite levels are the functions of the Wainer hierarchy (ω ≤ α ≤ ε0):\n\n# Sources","revisionCount":0},"hasMore":false,"nextCursor":null}

History