Hiérarchie de croissance rapide

La hiérarchie de croissance rapide (HCR en abrégé) est une certaine hiérarchie faisant correspondre des ordinaux α (sous le supremum μ d'un système fixe de séquences fondamentales) à des fonctions $f_\alpha: \mathbb{N} \rightarrow \mathbb{N}$. Pour les grands ordinaux α, $f_\alpha$ peut croître très rapidement. En raison de sa définition simple et claire, ainsi que de ses origines dans les mathématiques professionnelles, la HCR est une référence populaire pour les fonctions de grands nombres.

Définition

La hiérarchie de croissance rapide est constituée d'un ordinal μ et d'un système de séquence fondamentale $S:\mu\cap\textrm{Lim} \rightarrow (\mathbb N\rightarrow\mu)$, où S(α)(n) est noté α[n], et où Lim désigne la classe des ordinaux limites. La sémantique est la suivante :

• $f_{0}(n) = n+1$
• $f_{\alpha+1}(n) = f^n_\alpha(n)$, où fⁿ désigne l'itération de la fonction
• $f_{\alpha}(n) = f_{\alpha[n]}(n)$ si α est un ordinal limite

Certains auteurs fixent plutôt $f_{\alpha+1}(n) = f^{n+1}_\alpha(n)$ pour la deuxième ligne.

Here, α[n] denotes the n-th term of a fixed fundamental sequence assigned to ordinal α. A system of fundamental sequences for limit ordinals below a given supremum is not unique, and fast-growing hierarchy heavily depends on the choice of such a system. In particular, fast-growing hierarchy is ill-defined unless a specific choice of a system of fundamental sequences is explicitly fixed in the context. In googology, it is customary to assume Wainer hierarchy, as explained below, for the fundamental sequences of ordinals not exceeding $\varepsilon_0$, unless otherwise noted.

Le cas général où f₀ est une fonction croissante quelconque forme une hiérarchie d'itération.

For the fast-growing hierarchy to be useful to googologists, it is also expected to satisfy the property that for all α < β < μ, $f_\alpha$ is eventually dominated by $f_\beta$.

Systems of fundamental sequences

Hiérarchie de Wainer

Definitions of the fast-growing hierarchy and choices of fundamental sequence systems vary between authors, so it is generally problematic to speak of "the" fast-growing hierarchy. The most well-known FGH, however, is the Wainer hierarchy, which has \(\mu = \varepsilon_0 + 1\) and an FS system defined as follows:

• \(\omega[n] = n\)
• \(\omega^{\alpha + 1}[n] = \omega^\alpha n\) (where \(\omega^\alpha n = \omega^\alpha + \omega^\alpha + \cdots + \omega^\alpha + \omega^\alpha\) with n \(\omega^\alpha\)'s)
• \(\omega^{\alpha}[n] = \omega^{\alpha[n]}\) if and only if \(\alpha\) is a limit ordinal
• \((\omega^{\alpha_1} + \omega^{\alpha_2} + \cdots + \omega^{\alpha_{k - 1}} + \omega^{\alpha_k})[n] = \omega^{\alpha_1} + \omega^{\alpha_2} + \cdots + \omega^{\alpha_{k - 1}} + \omega^{\alpha_k}[n]\) where \(\alpha_1 \geq \alpha_2 \geq \cdots \geq \alpha_{k - 1} \geq \alpha_k\)
• \(\varepsilon_0[0] = 0\) (alternatively \(1\))
• \(\varepsilon_0[n + 1] = \omega^{\varepsilon_0[n]}\) = \(\omega\uparrow\uparrow (n-1)\) (alternatively \(\omega\uparrow\uparrow n\))

For example, the fundamental sequence for \(\omega^\omega\) is \(1, \omega, \omega^2, \omega^3, \ldots\). When authors refer to "the fast-growing hierarchy" without clarification, the Wainer hierarchy is usually meant.

Functions in Wainer hierarchy are known to be computable, because the whole system can be encoded into the ordinal notation associated to Iterated Cantor normal form with additional structures.

Hiérarchie de Veblen

Every non-zero ordinal \(\alpha\) can be uniquely written in Veblen's variation of Cantor's normal form:

\(\alpha=\varphi_{\beta_1}(\gamma_1) + \varphi_{\beta_2}(\gamma_2) + \cdots + \varphi_{\beta_k}(\gamma_k)\), where \(\varphi_{\beta}(\gamma)\) is a function of Veblen's hierarchy, \(\varphi_{\beta_1}(\gamma_1) \ge \varphi_{\beta_2}(\gamma_2) \ge \cdots \ge \varphi_{\beta_k}(\gamma_k)\) and each \(\gamma_m < \varphi_{\beta_m}(\gamma_m)\),

For limit ordinals \(\alpha<\Gamma_0\), written in Veblen's variation of Cantor's normal form, the fundamental sequences for the Veblen's hierarchy are defined as follows:

• \((\varphi_{\beta_1}(\gamma_1) + \varphi_{\beta_2}(\gamma_2) + \cdots + \varphi_{\beta_k}(\gamma_k))[n]=\varphi_{\beta_1}(\gamma_1) + \cdots + \varphi_{\beta_{k-1}}(\gamma_{k-1}) + (\varphi_{\beta_k}(\gamma_k) [n])\)
• \(\varphi_0(\gamma)=\omega^{\gamma}\) and \(\varphi_0(\gamma+1) [n] = \omega^{\gamma} \cdot n\)
• \(\varphi_{\beta+1}(0)[n]=\varphi_{\beta}^n(0)\), where \(\varphi^n\) denotes function iteration
• \(\varphi_{\beta+1}(\gamma+1)[n]=\varphi_{\beta}^n(\varphi_{\beta+1}(\gamma)+1)\)
• \(\varphi_{\beta}(\gamma) [n] = \varphi_{\beta}(\gamma [n])\) for a limit ordinal \(\gamma<\varphi_\beta(\gamma)\)
• \(\varphi_{\beta}(0) [n] = \varphi_{\beta [n]}(0)\) for a limit ordinal \(\beta<\varphi_\beta(0)\)
• \(\varphi_{\beta}(\gamma+1) [n] = \varphi_{\beta [n]}(\varphi_{\beta}(\gamma)+1)\) for a limit ordinal \(\beta\)

Veblen's function can be presented as a two-argument function \(\varphi_\beta(\gamma)=\varphi(\beta,\gamma)\).

Note: \(\varphi(0,\gamma)=\omega^\gamma\), \(\varphi(1,\gamma)=\varepsilon_\gamma\), \(\varphi(2,\gamma)=\zeta_\gamma\) and \(\varphi(3,\gamma)=\eta_\gamma\)

Functions in Veblen hierarchy are known to be computable, because the whole system can be encoded into the ordinal notation associated to Veblen's \(\varphi\) with additional structures.

Buchholz hierarchy

In An Independence Result for (\(\Pi_1^1\)-CA) + BI, Wilfried Buchholz discusses an ordinal hierarchy where \(\mu = \psi_0(\varepsilon_{\Omega_\omega + 1})\), where \(\psi\) is Buchholz's ordinal collapsing function and \(\psi_0(\varepsilon_{\Omega_\omega + 1})\) is the en:TFB ordinal.

Functions in Buchholz hierarchy are known to be computable, because the whole system can be encoded into Buchholz's ordinal notation with additional structures.

Approximations

Below are some functions in the Wainer hierarchy and Veblen's hierarchy compared to other googological notations.

There are a few things to note:

• Relationships denoted $f_\alpha(n) > g(n)$ hold for sufficiently large n, not necessarily all n (i.e. $f_\alpha$ eventually dominates g.
• m indicates any positive integer.
• ↑ indicates notation des puissances itérées.
• Ack indicates fonction d'Ackermann.
• Wainer hierarchy is used

$\begin{array}{rl} f_0(n) &=& n + 1 \\ f_1(n) &=& f_0^n(n) = ( \cdots ((n + 1) + 1) + \cdots + 1) = n + n = 2n \\ f_2(n) &=& f_1^n(n) = 2(2(\ldots 2(2n))) = 2^n n > 2 \uparrow n \\ f_3(n) &\ge& 2^nn((2^{2^nn})\uparrow\uparrow (n-1)) \ge 2\uparrow\uparrow n\\ f_4(n) &\ge& f_3(n)\uparrow\uparrow\uparrow n \ge 2\uparrow\uparrow\uparrow n \\ f_m(n) &\ge& f_{m-1}(n)\uparrow^{m-1}n \ge 2\uparrow^{m-1} n \\ f_\omega(n) &\ge& f_\omega(n-1)\uparrow^{n-1}n \ge 2\uparrow^{n-1} n = \text{Ack}(n, n) \\ \end{array}$

Extended Grzegorczyk hierarchy

The Grzegorczyk hierarchy is a hierarchy of functions (specifically - it contains all and only the primitive recursive functions) classified by growth rate. Although the 'extended Grzegorczyk hierarchy' can sometimes be an alternate name for the fast-growing hierarchy, it may also be used as a way of strictly classifying functions based on their growth rates, and a system of fundamental sequences.