Googology Wiki
Register
Advertisement
Googology Wiki

View full site to see MathJax equation

The fast-growing hierarchy (FGH for short) is a certain hierarchy mapping ordinals \(\alpha\) (below the supremum \(\mu\) of a fixed system of fundamental sequences) to a set of functions, which generated from fast-growing functions denoted by \(f_\alpha: \mathbb{N} \rightarrow \mathbb{N}\). For large ordinals \(\alpha\), \(f_\alpha\) may grow very rapidly. Due to its simple and clear definition, as well as its origins in professional mathematics, FGH is a popular benchmark for large number functions.

Warning[]

A reader should be very careful that there are many wrong "introductions" in personal websites, videos, and user blogs, although they are unfortunately preferred by beginners. Since mathematical notions such as ordinals and fundamental sequences are quite abstract and difficult to handle in a precise manner, people tend to give intuitive descriptions of them, which look simpler and cooler for beginners than precise explanations. However, such "introductions" frequently include serious errors, because the authors have also studied them from other intuitive descriptions instead of precise definitions. An important point is that precise descriptions of them are actually needed to understand the fast-growing hierarchy. The reason why precise descriptions look complicated is not because it is just poorly written or redundant, but is because the notions are actually quite difficult, although such wrong "introductions" sometimes explain them as simple notions.

If you are unfamiliar with using ordinals in functions, you may want to read the introduction to the fast-growing hierarchy article. Also, be careful that there are many wrong descriptions of the computability of functions in a fast-growing hierarchy. Although googologists sometimes state that a given function is computable because it is given by a fast-growing hierarchy, it is a typical mistake. A function defined by a method using infinite ordinals such as a fast-growing hierarchy is not necessarily computable. In order to ensure the computability of a function defined by a fast-growing hierarchy, we need to construct an explicit algorithm to compute it, and a common example is an algorithm for fundamental sequences over an ordinal notation. Functions as small as \(f_\omega\) on the fast-growing hierarchy can be uncomputable without a definition using an explicit algorithm. Since an algorithm only accepts elements in a countable set with a fixed enumeration, infinite ordinals in a set without fixed enumeration are not allowed. In order to solve the issue on the computability, we often use ordinal notations.

One of the most important facts on fast-growing hierarchy (together with its cousins, e.g. Hardy hierarchy and Slow-growing hierarchy) is that it is ill-defined unless a specific choice of a system of fundamental sequences is explicitly fixed in the context. Beginners should be very careful about this issue, because this sort of ill-definedness frequently appears when googologists talk about "catching ordinals", "ordinal regarded as the growth rate", "the proof-theoretic ordinal in fast-growing hierarchy" and so on without understanding the dependency of the choice of a system of fundamental sequences.

See also Hardy hierarchy#Warning and Slow-growing hierarchy#Warning.

Definition[]

Fast-growing functions[]

The fast-growing function consists of an ordinal \(\mu\) and a fundamental sequence system \(S:\mu\cap\textrm{Lim} \rightarrow (\mathbb N\rightarrow \mu)\), where \(S(\alpha)(n)\) is denoted \(\alpha[n]\), and where \(\textrm{Lim}\) denotes the class of limit ordinals. The semantics are as follows:

  • \(f_0(n) = n + 1\)
  • \(f_{\alpha+1}(n) = f^n_\alpha(n)\), where \(f^n\) denotes function iteration
  • \(f_\alpha(n) = f_{\alpha[n]}(n)\) if \(\alpha\) is a limit ordinal 

Here, \(\alpha[n]\) denotes the \(n\)th term of a fixed fundamental sequence assigned to ordinal \(\alpha\). 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, as we explained in #Warning.

Some authors instead set \(f_{\alpha+1}(n) = f^{n+1}_\alpha(n)\) for the second line. [1]

For the fast-growing hierarchy to be useful to googologists, it is also expected to satisfy the property that for all \(\alpha < \beta < \mu\), \(f_\alpha\) is eventually dominated by \(f_\beta\), although it is not necessarily true for a general system of fundamenal sequences.[2][3] The reader should be careful that many googologists do not know this fact and implicitly assume this property even when there is no proof for the specific system of fundamental sequence in the context. See also Church-Kleene ordinal#Fast-growing hierarchy for common misconceptions replated to fast-growing hierarchy.

Fast-growing hierarchy[]

The fast-growing hierarchy \(\{\mathcal{F}_\alpha\}_{\alpha<\mu}\) is defined like the Grzegorczyk hierarchy. For each ordinal \(\alpha<\mu\), a set \(\mathcal{H}_\alpha\) of numerical functions is defined as the smallest class satisfying the following conditions:

  1. It contains
    • zero constant \(0\), denoted to \(z:\mathbb{N}^0\to\mathbb{N}\),
    • successor function \(s(n)=n+1\),
    • projection function \(p_i^m(x_1,\dots,x_m)=x_i\) and
    • fast-growing function \(f_\alpha\).
  2. It is closed under
    • substitution, \(g(f_1,\dots,f_n)\) for \(g,f_1,\dots,f_n\in\mathcal{F}_\alpha\) and
    • limited recursion, \(h(n+1,x_1,\dots,x_n)=f(n,x_1,\dots,x_n,h(n,x_1,\dots,x_n)),\) \(h(0,x_1,\dots,x_n)=g(x_1,\dots,x_n)\) for \(f,g\in\mathcal{F}_\alpha\) and \(h(n,x_1,\dots,x_n)\leq M(n,x_1,\dots,x_n)\) for some \(M\in\mathcal{F}_\alpha\)

The general case where \(f_0\) is any increasing function forms a fast iteration hierarchy.

Systems of fundamental sequences[]

See also: List of systems of fundamental sequences

Wainer hierarchy[]

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.

Veblen hierarchy[]

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 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.

Other hierarchies[]

We can easily replace the Wainer hierarchy with a different one, such as a hierarchy that works for much larger ordinals such as the small Veblen ordinal or the Takeuti-Feferman-Buchholz ordinal. As long as fundamental sequences are defined, it is possible to extend FGH up to an arbitrary countable ordinal. However, it is impossible to create an effective system that works for all countable ordinals, since a system of fundamental sequences up to \(\omega_1\) would be nonconstructive.

Selecting fundamental sequences is not an easy problem, since some selections can lead to pathological hierarchies where \(\alpha < \beta\) does not necessarily imply \(f_\alpha <^* f_\beta\) (where \(<^*\) means eventual domination). In a 1976 paper, Diana Schmidt proved a theorem that is useful for identifying and guarding against pathological hierarchies.[4] Given a fundamental sequence system, define \(P(\beta + 1) = \beta\) and \(\forall \beta \in \text{Lim} : P(\beta) = \beta[0]\). A fundamental sequence system is built-up if, for all \(\alpha\) and \(n\), \(\alpha[n] = P^k(\alpha[n+1])\) for some \(1 \leq k < \omega\). Schmidt essentially showed that a built-up fundamental sequence system guarantees that all \(f_\alpha\) are monotonically increasing and that \(\alpha < \beta \Rightarrow f_\alpha <^* f_\beta\). (Although the proof assume that a given hierarchy satisfies \(f_{\alpha}(1) < f_{\alpha+1}(1)\), which is false in the fast-growing hierarchy, it is easy to modify the proof so that it becomes applicable to the fast-growing hierarchy.)

It is possible to define the fast-growing hierarchy for all recursive ordinals, and even for nonrecursive countable ordinals. However, the definitions will necessarily be nonrecursive, making analysis far more complicated. To our knowledge, there has been no research into the creation of nonrecursive fast-growing hierarchies.

For many cases, the computability of a fast-growing hierachy for a given system of fundamental sequences is non-trivial, although googologists often regard it trivial without understanding the issue.

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.
  • \(\uparrow\) indicates arrow notation.
  • \(\textrm{Ack}\) indicates Harvey Friedman's single-argument Ackermann function \(\textrm{Ack}(n)\).
  • \(\lbrace \rbrace\) indicates BAN (Hierarchical Hyper-Nested Array Notation).
  • We use several systems of fundamental sequences throughout this section, such as those for Cantor normal form and those for the Veblen function. Since they are not explicitly specified, we do not know what systems are suitable for these results. Therefore please be careful that the computation might not hold when one tries to apply it to a specific system.

\begin{eqnarray*} 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^n \\ f_3(n) &\ge& 2^nn((2^{2^nn})\uparrow\uparrow (n-1)) \ge 2\uparrow\uparrow n = n\times(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) \\ f_{\omega+1}(n) &>& \lbrace n,n,1,2 \rbrace \\ f_{\omega+2}(n) &>& \lbrace n,n,2,2 \rbrace \\ f_{\omega+m}(n) &>& \lbrace n,n,m,2 \rbrace \\ f_{\omega\times 2}(n) &>& \lbrace n,n,n,2 \rbrace \\ f_{\omega\times 3}(n) &>& \lbrace n,n,n,3 \rbrace \\ f_{\omega\times m}(n) &>& \lbrace n,n,n,m \rbrace \\ f_{\omega^2}(n) &>& \lbrace n,n,n,n \rbrace \\ f_{\omega^3}(n) &>& \lbrace n,n,n,n,n \rbrace \\ f_{\omega^m}(n) &>& \lbrace n,m+2 [2] 2 \rbrace \\ f_{\omega^{\omega}}(n) &>& \lbrace n,n+2 [2] 2 \rbrace > \lbrace n,n [2] 2 \rbrace \\ f_{\omega^{\omega}+1}(n) &>& \lbrace n,n,2 [2] 2 \rbrace \\ f_{\omega^{\omega}+2}(n) &>& \lbrace n,n,3 [2] 2 \rbrace \\ f_{\omega^{\omega}+m}(n) &>& \lbrace n,n,m+1 [2] 2 \rbrace \\ f_{\omega^{\omega}+\omega}(n) &>& \lbrace n,n,n+1 [2] 2 \rbrace > \lbrace n,n,n [2] 2 \rbrace \\ f_{\omega^{\omega}+\omega+1}(n) &>& \lbrace n,n,1,2 [2] 2 \rbrace \\ f_{\omega^{\omega}+\omega2}(n) &>& \lbrace n,n,n,2 [2] 2 \rbrace \\ f_{\omega^{\omega}+\omega^2}(n) &>& \lbrace n,n,n,n [2] 2 \rbrace \\ f_{{\omega^{\omega}}2}(n) &>& \lbrace n,n [2] 3 \rbrace \\ f_{{\omega^{\omega}}3}(n) &>& \lbrace n,n [2] 4 \rbrace \\ f_{{\omega^{\omega}}m}(n) &>& \lbrace n,n [2] m+1 \rbrace \\ f_{\omega^{\omega+1}}(n) &>& \lbrace n,n [2] n+1 \rbrace > \lbrace n,n [2] n \rbrace \\ f_{\omega^{\omega+2}}(n) &>& \lbrace n,n [2] n,n \rbrace \\ f_{\omega^{\omega+3}}(n) &>& \lbrace n,n,n [2] n,n,n \rbrace \\ f_{\omega^{\omega+m}}(n) &>& \lbrace n,m [2] 1 [2] 2 \rbrace \\ f_{\omega^{\omega2}}(n) &>& \lbrace n,n [2] 1 [2] 2 \rbrace = \lbrace n,2 [3] 2 \rbrace \\ f_{\omega^{\omega3}}(n) &>& \lbrace n,n [2] 1 [2] 1 [2] 2 \rbrace = \lbrace n,3 [3] 2 \rbrace \\ f_{\omega^{\omega m}}(n) &>& \lbrace n,m [3] 2 \rbrace \\ f_{\omega^{\omega^2}}(n) &>& \lbrace n,n [3] 2 \rbrace \\ f_{\omega^{\omega^3}}(n) &>& \lbrace n,n [4] 2 \rbrace \\ f_{\omega^{\omega^m}}(n) &>& \lbrace n,n [m+1] 2 \rbrace \\ f_{\omega^{\omega^\omega}}(n) &>& \lbrace n,n [n+1] 2 \rbrace > \lbrace n,n [1,2] 2 \rbrace \\ f_{^4{\omega}}(n) &>& \lbrace n,n [1 [2] 2] 2 \rbrace \\ f_{^5{\omega}}(n) &>& \lbrace n,n [1 [1,2] 2] 2 \rbrace \\ f_{^6{\omega}}(n) &>& \lbrace n,n [1 [1 [2] 2] 2] 2 \rbrace \\ f_{\varepsilon_0}(n) &>& \lbrace n,n [1 / 2] 2 \rbrace \\ f_{\varepsilon_02}(n) &>& \lbrace n,n [1 / 2] 3 \rbrace \\ f_{\varepsilon_03}(n) &>& \lbrace n,n [1 / 2] 4 \rbrace \\ f_{\varepsilon_0m}(n) &>& \lbrace n,n [1 / 2] m+1 \rbrace \\ f_{\varepsilon_0\omega}(n) &>& \lbrace n,n [1 / 2] n+1 \rbrace \\ f_{\varepsilon_0{\omega^{\omega}}}(n) &>& \lbrace n,n [1 / 2] 1 [2] 2 \rbrace \\ f_{\varepsilon_0{\omega^{\omega^{\omega}}}}(n) &>& \lbrace n,n [1 / 2] 1 [1,2] 2 \rbrace \\ f_{\varepsilon_0{\omega^{\omega^{\omega^{\omega}}}}}(n) &>& \lbrace n,n [1 / 2] 1 [1 [2] 2] 2 \rbrace \\ f_{\varepsilon_0^2}(n) &>& \lbrace n,n [1 / 2] 1 [1 / 2] 2 \rbrace \\ f_{\varepsilon_0^3}(n) &>& \lbrace n,n [1 / 2] 1 [1 / 2] 1 [1 / 2] 2 \rbrace \\ f_{\varepsilon_0^{\omega}}(n) &>& \lbrace n,n [2 / 2] 2 \rbrace \\ f_{\varepsilon_0^{\omega^{\omega}}}(n) &>& \lbrace n,n [1,2 / 2] 2 \rbrace \\ f_{\varepsilon_0^{\omega^{\omega^{\omega}}}}(n) &>& \lbrace n,n [1 [2] 2 / 2] 2 \rbrace \\ f_{\varepsilon_0^{\varepsilon_0}}(n) &>& \lbrace n,n [1 [1 / 2] 2 / 2] 2 \rbrace \\ f_{\varepsilon_0^{\varepsilon_0^{\varepsilon_0}}}(n) &>& \lbrace n,n [1 [1 / 2] 1 [1 / 2] 2 / 2] 2 \rbrace \\ f_{\varepsilon_0^{\varepsilon_0^{\varepsilon_0^{\varepsilon_0}}}}(n) &>& \lbrace n,n [1 [1 [1 / 2] 2 / 2] 2 / 2] 2 \rbrace \\ f_{\varepsilon_1}(n) &>& \lbrace n,n [1 / 3] 2 \rbrace \\ f_{\varepsilon_2}(n) &>& \lbrace n,n [1 / 4] 2 \rbrace \\ f_{\varepsilon_{\omega}}(n) &>& \lbrace n,n [1 / 1,2] 2 \rbrace \\ f_{\varepsilon_{\omega^2}}(n) &>& \lbrace n,n [1 / 1,1,2] 2 \rbrace \\ f_{\varepsilon_{\omega^{\omega}}}(n) &>& \lbrace n,n [1 / 1 [2] 2] 2 \rbrace \\ f_{\varepsilon_{\omega^{\omega^{\omega}}}}(n) &>& \lbrace n,n [1 / 1 [1,2] 2] 2 \rbrace \\ f_{\varepsilon_{\varepsilon_0}}(n) &>& \lbrace n,n [1 / 1 [1 / 2] 2] 2 \rbrace \\ f_{\varepsilon_{\varepsilon_{\varepsilon_0}}}(n) &>& \lbrace n,n [1 / 1 [1 / 1 [1 / 2] 2] 2] 2 \rbrace \\ f_{\zeta_0}(n) &>& \lbrace n,n [1 / 1 / 2] 2 \rbrace \\ f_{\zeta_0^{\zeta_0}}(n) &>& \lbrace n,n [1 [1 / 1 / 2] 2 / 1 / 2] 2 \rbrace \\ f_{\varepsilon_{\zeta_0+1}}(n) &>& \lbrace n,n [1 / 2 / 2] 2 \rbrace \\ f_{\varepsilon_{\zeta_0+2}}(n) &>& \lbrace n,n [1 / 3 / 2] 2 \rbrace \\ f_{\varepsilon_{\varepsilon_{\zeta_0+1}}}(n) &>& \lbrace n,n [1 / 1 [1 / 2 / 2] 2 / 2]2 \rbrace \\ f_{\zeta_1}(n) &>& \lbrace n,n [1 / 1 / 3] 2 \rbrace \\ f_{\zeta_2}(n) &>& \lbrace n,n [1 / 1 / 4] 2 \rbrace \\ f_{\zeta_{\zeta_0}}(n) &>& \lbrace n,n [1 / 1 / 1 [1 / 1 / 2] 2] 2 \rbrace \\ f_{\eta_0}(n) &>& \lbrace n,n [1 / 1 / 1 / 2] 2 \rbrace \\ f_{\varphi(4,0)}(n) &>& \lbrace n,n [1 / 1 / 1 / 1 / 2] 2 \rbrace \\ f_{\varphi(\omega,0)}(n) &>& \lbrace n,n [1 [2 \sim 2] 2] 2 \rbrace \\ f_{\varphi(\varphi(\omega,0),0)}(n) &>& \lbrace n,n [1 [1 [1 [2 \sim 2] 2] 2 \sim 2] 2] 2 \rbrace \\ f_{\Gamma_0}(n) &>& \lbrace n,n [1 [1 / 2 \sim 2] 2] 2 \rbrace \\ f_{\varphi(1,0,0,0)}(n) &>& \lbrace n,n [1 [1 / 3 \sim 2] 2] 2 \rbrace \\ f_{\vartheta(\Omega^{\omega})}(n) &>& \lbrace n,n [1 [1 / 1, 2 \sim 2] 2] 2 \rbrace \\ f_{\vartheta(\Omega^{\Omega})}(n) &>& \lbrace n,n [1 [1 / 1 / 2 \sim 2] 2] 2 \rbrace \\ f_{\vartheta(\Omega^{\Omega^{\Omega}})}(n) &>& \lbrace n,n [1 [1 [1 / 2 \sim 2] 2 \sim 2] 2] 2 \rbrace \\ f_{\vartheta(\vartheta_1(1))}(n) &>& \lbrace n,n [1 [1 \sim 3] 2] 2 \rbrace \\ f_{\vartheta(\vartheta_1(2))}(n) &>& \lbrace n,n [1 [1 \sim 1 \sim 2] 2] 2 \rbrace \\ f_{\vartheta(\vartheta_1(\omega))}(n) &>& \lbrace n,n [1 [1 [2 /_3 2] 2] 2] 2 \rbrace \\ f_{\vartheta(\vartheta_1(\Omega))}(n) &>& \lbrace n,n [1 [1 [1 / 2 /_3 2] 2] 2] 2 \rbrace \\ f_{\vartheta(\Omega_2)}(n) &>& \lbrace n,n [1 [1 [1 \sim 2 /_3 2] 2] 2] 2 \rbrace \\ f_{\vartheta(\Omega_3)}(n) &>& \lbrace n,n [1 [1 [1 [1 /_3 2 /_4 2] 2] 2] 2] 2 \rbrace \\ f_{\vartheta(\Omega_{\omega})}(n) &>& \lbrace n,n [1 [2 /_{1,2} 2] 2] 2 \rbrace \\ f_{\vartheta(\Omega_{\varepsilon_0})}(n) &>& \lbrace n,n [1 [2 /_{1 [1 / 2] 2} 2] 2] 2 \rbrace \\ f_{\vartheta(\Omega_{\Gamma_0})}(n) &>& \lbrace n,n [1 [2 /_{1 [1 / 2 \sim 2] 2} 2] 2] 2 \rbrace \\ f_{\vartheta(\Omega_{\vartheta(\Omega_2)})}(n) &>& \lbrace n,n [1 [2 /_{1 [1 [1 [1 \sim2 /_3 2] 2] 2] 2} 2] 2] 2 \rbrace \\ f_{\vartheta(\Omega_{\vartheta(\Omega_3)})}(n) &>& \lbrace n,n [1 [2/_{1 [1 [1 [1 [1 /_3 2/_4 2] 2] 2] 2] 2} 2] 2] 2 \rbrace \\ f_{\vartheta(\Omega_{\vartheta(\Omega_{\omega})})}(n) &>& \lbrace n,n [1 [2 /_{1 [1 [2 /_{1,2} 2] 2] 2} 2] 2] 2 \rbrace \\ f_{\vartheta(\Omega_{\vartheta(\Omega_{\vartheta(\Omega_{\omega})})})}(n) &>& \lbrace n,n [1 [2 /_{1 [2 /_{1 [1 [2 /_{1,2} 2] 2] 2} 2] 2} 2] 2] 2 \rbrace \end{eqnarray*}

Fish used continuous arrow notation to approximate \(f_m(n)\) more precisely, with a program published at the site.[5]

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.

Historical variations[]

Löb & Wainer's 1970 version (original)[]

The original fast-growing functions, defined by Martin Löb and Stanley S. Wainer in 1970,[6] was different from the known form.

The following is the definition in 1970 paper:

  1. \(F^n_0(x)=(n+1)\cdot(x+1)\),
  2. \(F^0_{\alpha+1}(x)=F^x_\alpha(x)\),
  3. \(F^0_\beta(x)=F^0_{\beta[x]}(\varrho_\beta(x))\) for a limit ordinal \(\beta\),
  4. \(F^{n+1}_\gamma(x)=F^0_\gamma(F^n_\gamma(x)), \gamma\neq 0\)

Here for a limit ordinal \(\beta\), \(\varrho_\beta:\mathbb{N}\to\mathbb{N}\) is defined as

  • \(\varrho_\beta(0)=0\),
  • \(\varrho_\beta(m+1)=\mu_z(z>\varrho_\beta(m)\land\forall i\leq m.(F^0_{\beta[m+1]}(z)>F^0_{\beta[i]}(z)))\)

where \(\mu_z(\varphi(z))\) is μ operator, which returnes the least n satisfying \(\varphi(z)\), if exists. That is, \(\varrho_\beta(m+1)\) is the least number \(z\) such that \(F^0_{\beta[i]}(z)<F^0_{\beta[m+1]}(z)\) for all \(i\leq m\) and larger than \(\varrho_\beta(m)\). Note that \(F^0_{\beta[i]}(m+1)<F^0_{\beta[m+1]}(m+1)\) is not trivial and this is because \(\varrho\) is required in the 1970 paper.

In the 1970 sequel paper,[7] Löb and Wainer showed \(\varrho(x)=x\) if the fundamental sequence is set to the specific way (this is more complicated way and not used now).

Wainer's 1972 version[]

In 1972, Wainer used more refined version of fast-growing function:

  • \(F_0(x)=x+1\),
  • \(F_1(x)=(x+1)^2\),
  • \(F_{\beta+1}(x)=F_\beta^{x+1}(x)\), for \(\beta>0\),
  • \(F_\sigma(x)=F_{\sigma[x]}(x)\), for a limit ordinal \(\sigma\),

where \(F_\beta^{x+1}(x)\) is the \(x+1\) times iteration of \(F_\beta\), that is \(F_\beta(\cdots F_\beta(x)\cdots)\), applying \(F_\beta\) \(x+1\) times.

In this time, the fundamental sequence is set as the same to Wainer hierarchy, except \(\varepsilon_0[0]=1\).

Ketonen & Solovay's 1981 version[]

The known form is introduced in 1981, by Jussi Ketonen and Robert Solovay.[8] We finally obtain a simple and powerful sequences of functions.

Specific numbers[]

  • \(\tan^{-1}(\frac{1}{2})\) is a real number equal to \(\sum_{n=0}^{\infty} \frac{(-1)^n}{f_2(2n+1)}\).[9]
  • 160 is an integer equal to f2(5), and also the number of possible knight moves in 6×6 minichess.
  • 212 is the first number n, such that f2(n) is larger than the first noncanonical -illion.
    • The isotope radium-212 is the only radium nuclide with negative mass excess. No heavier elements have any isotopes with negative mass excess.
  • 384 is an integer equal to f2(6), 8!! and 12!!!!, and also the number of days in some years in the Hebrew calendar.
  • 896 is an integer equal to f2(7), and also the number of possible Rook moves in chess.
  • 1,651 is the smallest number n, for which f2(n) is larger than a googolding. Its prime factorization is 13 × 127.
  • 4,608 is an integer equal to f2(9), and also an Achilles number and the number of possible Rook moves in quatrochess.
  • 10,240 is an integer equal to f2(10), which Denis Maksudov calls that number 'balum'.
  • 491,520 is an integer equal to f2(15). Additionally, it has an unrelated property: As it is equal to 6C4 × 224−1, it also appears in UEFA European Championship-related combinatorics.

Programs[]

Turing machine[]

Sources[]

  1. A. Freund and F. Pakhomov, “Short Proofs for Slow Consistency” (p.4). Notre Dame Journal of Formal Logic, 61 (1): 31–49. doi:10.1215/00294527-2019-0031 arXiv:1712.03251
  2. User blog:P進大好きbot/A larger orderinal does not necessarily correspond to a greater function through FGH
  3. T. Kihara, omega-1-ck.pdf.
  4. Diana Schmidt, Built-up systems of fundamental sequences and hierarchies of number-theoretic functions, Archiv für mathematische Logik und Grundlagenforschung 18 (1976), pp. 47--53.
  5. Fish. Approximation of FGH with arrow notation 2023-12-05.
  6. Löb, M. H. and Wainer, S. S.: Hierarchies of Number-Theoretic Functions Ⅰ. Archiv für mathematische Logik und Grundlagenforschung, Vol 13, Issue 1–2 (1970). pp. 39–51. doi:10.1007/BF01967649
  7. Löb, M. H. and Wainer, S. S.: Hierarchies of Number-Theoretic Functions Ⅱ. Archiv für mathematische Logik und Grundlagenforschung, Vol 13, Issue 3–4, pp. 97–113 (1970). doi:10.1007/BF01973616
  8. Ketonen, Jussi and Solovay, Robert: Rapidly growing Ramsey functions. Annals of Mathematics, Vol. 113, No. 2, pp. 267–314 (1981). doi:10.2307/2006985. JSTOR:[1]
  9. User blog:Plain'N'Simple/A cool geometric connection regarding the fast-growing-hierarchy
  10. DeepLineMadom's googology - Numbers I've coined (Retrieved 4 May 2022)
  11. Unrelated Numbers | PlantStar's Large Numbers
  12. Khang2009 Turing machine for computing FGH of growth rate less than omega, 2021-12-20.

External links[]

See also[]

Basics: cardinal numbers · ordinal numbers · limit ordinals · fundamental sequence · normal form · transfinite induction · ordinal notation · Absolute infinity
Theories: Robinson arithmetic · Presburger arithmetic · Peano arithmetic · KP · second-order arithmetic · ZFC
Model Theoretic Concepts: structure · elementary embedding
Countable ordinals: \(\omega\) · \(\varepsilon_0\) · \(\zeta_0\) · \(\eta_0\) · \(\Gamma_0\) (Feferman–Schütte ordinal) · \(\varphi(1,0,0,0)\) (Ackermann ordinal) · \(\psi_0(\Omega^{\Omega^\omega})\) (small Veblen ordinal) · \(\psi_0(\Omega^{\Omega^\Omega})\) (large Veblen ordinal) · \(\psi_0(\varepsilon_{\Omega + 1}) = \psi_0(\Omega_2)\) (Bachmann-Howard ordinal) · \(\psi_0(\Omega_\omega)\) with respect to Buchholz's ψ · \(\psi_0(\varepsilon_{\Omega_\omega + 1})\) (Takeuti-Feferman-Buchholz ordinal) · \(\psi_0(\Omega_{\Omega_{\cdot_{\cdot_{\cdot}}}})\) (countable limit of Extended Buchholz's function)‎ · \(\omega_1^\mathfrak{Ch}\) (Omega one of chess) · \(\omega_1^{\text{CK}}\) (Church-Kleene ordinal) · \(\omega_\alpha^\text{CK}\) (admissible ordinal) · recursively inaccessible ordinal · recursively Mahlo ordinal · reflecting ordinal · stable ordinal · \(\lambda,\gamma,\zeta,\Sigma\) (Infinite time Turing machine ordinals) · gap ordinal · List of countable ordinals
Ordinal hierarchies: Fast-growing hierarchy · Hardy hierarchy · Slow-growing hierarchy · Middle-growing hierarchy · N-growing hierarchy
Ordinal functions: enumeration · normal function · derivative · Veblen function · ordinal collapsing function · Weak Buchholz's function · Bachmann's function · Madore's function · Feferman's theta function · Buchholz's function · Extended Weak Buchholz's function · Extended Buchholz's function · Jäger-Buchholz function · Jäger's function · Rathjen's psi function · Rathjen's Psi function · Stegert's Psi function · Arai's psi function
Uncountable cardinals: \(\omega_1\) · omega fixed point · inaccessible cardinal \(I\) · Mahlo cardinal \(M\) · weakly compact cardinal \(K\) · indescribable cardinal · rank-into-rank cardinal
Classes: \(\textrm{Card}\) · \(\textrm{On}\) · \(V\) · \(L\) · \(\textrm{Lim}\) · \(\textrm{AP}\) · Class (set theory)

Advertisement