The slow-growing hierarchy (SGH) is a certain hierarchy mapping ordinals \(\alpha\) to functions \(g_\alpha: \mathbb{N} \rightarrow \mathbb{N}\). Like its name suggests, it grows much slower than its cousins the fast-growing hierarchy and the Hardy hierarchy.

The functions are defined as follows:

  • \(g_0(n) = 0\)
  • \(g_{\alpha+1}(n) = g_\alpha(n)+1\)
  • \(g_\alpha(n) = g_{\alpha[n]}(n)\) when \(\alpha\) is a limit ordinal

Here, \(\alpha[n]\) denotes the \(n\)th term of the fundamental sequence assigned to ordinal \(\alpha\). A system of fundamental sequences for limit ordinals below a given supremum is not unique, and slow-growing hierarchy heavily depends on the choice of such a system. In particular, slow-growing hierarchy is ill-defined unless a specific choice of a system of fundamental sequences is explicitly fixed in the context. One such hierarchy is the Wainer hierarchy, which is explained in the article for fast-growing hierarchy.

For small ordinals and non-pathologic system of fundamental sequences, SGH is nowhere close to FGH. \(g_{\varepsilon_0}(n)\) only reaches the level of \(f_3(n)\), and SGH does not reach \(f_{\varepsilon_0}(n)\) until the Bachmann-Howard ordinal. Unlike its relatives, SGH is extremely sensitive to the definitions of fundamental sequences: SGH "catches up" FGH at \(\psi_0(\Omega_\omega)\) with repect to unspecified "natural" choice of fundamental sequences and unspecified "reasonable" formulation of the "comparability". Other systems of fundamental sequences and formulations of the comparability, however, have this 'catching ordinal' at \(\omega\), \(\varepsilon_0\), \(\vartheta(\Omega^\Omega)\), or even beyond \(\psi(\psi_I(0))\) in some cases. Therefore beginners should be very careful when a googologist talks about the "catching property" for an ordinal without fixing a specific system of fundamental sequences due to the lack of the knowledge of such an issue.

To googologists, SGH is not quite as useful as FGH. It grows the slowest of all the ordinal hierarchies, so it may be the best suited to stratify the growth rates of functions, if the fundamental sequences are properly specified. However, it has been theorized that it may be useful in creating fast growing functions in a similar manner to Goodstein sequences.

Functions

Below is the list of comparisons between SGH and other googological notations.

Note: A specific system of fundamental sequences was used to obtain these approximations. A different system will likely produce wildly different values, so take care.

Up to \(\Gamma_0\)

\(g_0(n) = 0\)

\(g_1(n) = 1\)

\(g_2(n) = 2\)

\(g_m(n) = m\)

\(g_\omega(n) = n\)

\(g_{\omega+1}(n) = n+1\)

\(g_{\omega+2}(n) = n+2\)

\(g_{\omega+m}(n) = n+m\)

\(g_{\omega2}(n) = 2n\)

\(g_{\omega3}(n) = 3n\)

\(g_{\omega m}(n) = mn\)

\(g_{\omega^2}(n) = n^2\)

\(g_{\omega^3}(n) = n^3\)

\(g_{\omega^m}(n) = n^m\)

\(g_{\omega^{\omega}}(n) = n^n\)

\(g_{\omega^{\omega^{\omega}}}(n) = n^{n^{n}}\)

\(g_{\varepsilon_0}(n) = n \uparrow\uparrow n\) (See epsilon zero)

\(g_{\varepsilon_1}(n) = n \uparrow\uparrow (2n)\)

\(g_{\varepsilon_2}(n) =n \uparrow\uparrow (3n)\)

\(g_{\varepsilon_{\omega}}(n) \approx n \uparrow\uparrow (n^2)\)

\(g_{\varepsilon_{\omega^2}}(n) \approx n \uparrow\uparrow (n^3)\)

\(g_{\varepsilon_{\omega^3}}(n) \approx n \uparrow\uparrow (n^4)\)

\(g_{\varepsilon_{\omega^{\omega}}}(n) \approx n \uparrow\uparrow (n^n)\)

\(g_{\varepsilon_{\varepsilon_0}}(n) \approx n \uparrow\uparrow (n \uparrow\uparrow n)\)

\(g_{\zeta_0}(n) \approx n \uparrow\uparrow\uparrow n\)

\(g_{\varepsilon_{\zeta_0+1}}(n) \approx (n \uparrow\uparrow\uparrow n) \uparrow\uparrow n\)

\(g_{\varepsilon_{\zeta_0+2}}(n) \approx (n \uparrow\uparrow\uparrow n) \uparrow\uparrow (2n)\)

\(g_{\varepsilon_{\zeta_0 2}}(n) \approx (n \uparrow\uparrow\uparrow n) \uparrow\uparrow (n \uparrow\uparrow\uparrow n) \approx n \uparrow\uparrow\uparrow (n+1)\)

\(g_{\varepsilon_{\zeta_0 3}}(n) \approx (n \uparrow\uparrow\uparrow n) \uparrow\uparrow (2(n \uparrow\uparrow\uparrow n))\)

\(g_{\varepsilon_{\zeta_0 4}}(n) \approx (n \uparrow\uparrow\uparrow n) \uparrow\uparrow (3(n \uparrow\uparrow\uparrow n))\)

\(g_{\varepsilon_{\zeta_0 \omega}}(n) \approx (n \uparrow\uparrow\uparrow n) \uparrow\uparrow (n(n \uparrow\uparrow\uparrow n))\)

\(g_{\varepsilon_{\zeta_0^2}}(n) \approx (n \uparrow\uparrow\uparrow n) \uparrow\uparrow ({(n \uparrow\uparrow\uparrow n)}^2)\)

\(g_{\varepsilon_{\zeta_0^{\zeta_0}}}(n) \approx (n \uparrow\uparrow\uparrow n) \uparrow\uparrow ({(n \uparrow\uparrow\uparrow n)}^{n \uparrow\uparrow\uparrow n})\)

\(g_{\varepsilon_{\varepsilon_{\zeta_0+1}}}(n) \approx (n \uparrow\uparrow\uparrow n) \uparrow\uparrow ((n \uparrow\uparrow\uparrow n) \uparrow\uparrow n)\)

\(g_{\varepsilon_{\varepsilon_{\zeta_0 2}}}(n) \approx (n \uparrow\uparrow\uparrow n) \uparrow\uparrow ((n \uparrow\uparrow\uparrow n) \uparrow\uparrow (n \uparrow\uparrow\uparrow n)) \approx n \uparrow\uparrow\uparrow (n+2)\)

\(g_{\varepsilon_{\varepsilon_{\varepsilon_{\zeta_0+1}}}}(n) \approx (n \uparrow\uparrow\uparrow n) \uparrow\uparrow ((n \uparrow\uparrow\uparrow n) \uparrow\uparrow ((n \uparrow\uparrow\uparrow n) \uparrow\uparrow n))\)

\(g_{\zeta_1}(n) \approx n \uparrow\uparrow\uparrow 2n\)

\(g_{\zeta_2}(n) \approx n \uparrow\uparrow\uparrow 3n\)

\(g_{\zeta_\omega}(n) \approx n \uparrow\uparrow\uparrow n^2\)

\(g_{\zeta_{\omega^\omega}}(n) \approx n \uparrow\uparrow\uparrow n^n\)

\(g_{\zeta_{\varepsilon_0}}(n) \approx n \uparrow\uparrow\uparrow (n \uparrow\uparrow n)\)

\(g_{\zeta_{\varepsilon_{\varepsilon_0}}}(n) \approx n \uparrow\uparrow\uparrow (n \uparrow\uparrow (n \uparrow\uparrow n))\)

\(g_{\zeta_{\zeta_0}}(n) \approx n \uparrow\uparrow\uparrow (n \uparrow\uparrow\uparrow n)\)

\(g_{\zeta_{\zeta_{\zeta_0}}}(n) \approx n \uparrow\uparrow\uparrow (n \uparrow\uparrow\uparrow (n \uparrow\uparrow\uparrow n\)))

\(g_{\eta_0}(n) \approx n \uparrow\uparrow\uparrow\uparrow n\)

\(g_{\varepsilon_{\eta_0+1}}(n) \approx (n \uparrow\uparrow\uparrow\uparrow n) \uparrow\uparrow n\)

\(g_{\varepsilon_{\eta_0+2}}(n) \approx (n \uparrow\uparrow\uparrow\uparrow n) \uparrow\uparrow 2n\)

\(g_{\varepsilon_{\eta_0+\omega}}(n) \approx (n \uparrow\uparrow\uparrow\uparrow n) \uparrow\uparrow n^2\)

\(g_{\varepsilon_{\eta_0+\omega^\omega}}(n) \approx (n \uparrow\uparrow\uparrow\uparrow n) \uparrow\uparrow n^n\)

\(g_{\varepsilon_{\eta_0+\varepsilon_0}}(n) \approx (n \uparrow\uparrow\uparrow\uparrow n) \uparrow\uparrow (n \uparrow\uparrow n)\)

\(g_{\varepsilon_{\eta_0+\varepsilon_{\varepsilon_0}}}(n) \approx (n \uparrow\uparrow\uparrow\uparrow n) \uparrow\uparrow (n \uparrow\uparrow n \uparrow\uparrow n)\)

\(g_{\varepsilon_{\eta_0+\zeta_0}}(n) \approx (n \uparrow\uparrow\uparrow\uparrow n) \uparrow\uparrow (n \uparrow\uparrow\uparrow n)\)

\(g_{\varepsilon_{\eta_0+\zeta_1}}(n) \approx (n \uparrow\uparrow\uparrow\uparrow n) \uparrow\uparrow (n \uparrow\uparrow\uparrow 2n)\)

\(g_{\varepsilon_{\eta_0+\zeta_\omega}}(n) \approx (n \uparrow\uparrow\uparrow\uparrow n) \uparrow\uparrow (n \uparrow\uparrow\uparrow n^2)\)

\(g_{\varepsilon_{\eta_0+\zeta_{\omega^\omega}}}(n) \approx (n \uparrow\uparrow\uparrow\uparrow n) \uparrow\uparrow (n \uparrow\uparrow\uparrow n^n)\)

\(g_{\varepsilon_{\eta_0+\zeta_{\zeta_0}}}(n) \approx (n \uparrow\uparrow\uparrow\uparrow n) \uparrow\uparrow (n \uparrow\uparrow\uparrow n \uparrow\uparrow\uparrow n)\)

\(g_{\varepsilon_{\eta_0 2}}(n) \approx (n \uparrow\uparrow\uparrow\uparrow n) \uparrow\uparrow (n \uparrow\uparrow\uparrow\uparrow n)\)

\(g_{\varepsilon_{\eta_0 3}}(n) \approx (n \uparrow\uparrow\uparrow\uparrow n) \uparrow\uparrow 2(n \uparrow\uparrow\uparrow\uparrow n)\)

\(g_{\varepsilon_{\eta_0 \omega}}(n) \approx (n \uparrow\uparrow\uparrow\uparrow n) \uparrow\uparrow n-1(n \uparrow\uparrow\uparrow\uparrow n)\)

\(g_{\zeta_{\eta_0+1}}(n) \approx (n \uparrow\uparrow\uparrow\uparrow n) \uparrow\uparrow\uparrow n\)

\(g_{\varphi(4,0)}(n) \approx n \uparrow\uparrow\uparrow\uparrow\uparrow n\)

\(g_{\varphi(5,0)}(n) \approx n \uparrow\uparrow\uparrow\uparrow\uparrow\uparrow n\)

\(g_{\varphi(\omega,0)}(n) \approx \{n,n,n+1\}\)

\(g_{\varphi(\omega^\omega,0)}(n) \approx \{n,n,n^n+1\}\)

\(g_{\varphi(\varepsilon_0,0)}(n) \approx \{n,n,n \uparrow\uparrow n+1\}\)

\(g_{\varphi(\zeta_0,0)}(n) \approx \{n,n,n \uparrow\uparrow\uparrow n+1\}\)

\(g_{\varphi(\eta_0,0)}(n) \approx \{n,n,n \uparrow\uparrow\uparrow\uparrow n+1\}\)

\(g_{\varphi(\varphi(\omega,0),0)}(n) \approx \{n,n,\{n,n,n+1\}+1\}\)

\(g_{\varphi(\varphi(\varphi(\omega,0),0),0)}(n) \approx \{n,n,\{n,n,\{n,n,n+1\}+1\}+1\}\)

From \(\Gamma_0\) to \(\vartheta(\Omega^\omega)\)

\(g_{\Gamma_0}(n) \approx \{n,n,1,2\}\)

\(g_{\varphi(\Gamma_0,1)}(n) \approx \{n,n+1,1,2\}\)

\(g_{\varphi(\varphi(\Gamma_0,1),0)}(n) \approx \{n,n+2,1,2\}\)

\(g_{\Gamma_1}(n) \approx \{n,2n,1,2\}\)

\(g_{\Gamma_2}(n) \approx \{n,3n,1,2\}\)

\(g_{\Gamma_\omega}(n) \approx \{n,(n+1)n,1,2\}\)

\(g_{\Gamma_{\omega^2}}(n) \approx \{n,(n^2+1)n,1,2\}\)

\(g_{\Gamma_{\omega^\omega}}(n) \approx \{n,(n^{n-1}+1)n,1,2\}\)

\(g_{\Gamma_{\omega^{\omega^\omega}}}(n) \approx \{n,(n^{n^n-1}+1)n,1,2\}\)

\(g_{\Gamma_{\varepsilon_0}}(n) \approx \{n,n \uparrow\uparrow n,1,2\}\)

\(g_{\Gamma_{\zeta_0}}(n) \approx \{n,n \uparrow\uparrow\uparrow n,1,2\}\)

\(g_{\Gamma_{\eta_0}}(n) \approx \{n,n \uparrow\uparrow\uparrow\uparrow n,1,2\}\)

\(g_{\Gamma_{\varphi(\omega,0)}}(n) \approx \{n,\{n,n,n+1\},1,2\}\)

\(g_{\Gamma_{\Gamma_0}}(n) \approx \{n,\{n,n,1,2\},1,2\}\)

\(g_{\Gamma_{\Gamma_{\Gamma_0}}}(n) \approx \{n,\{n,\{n,n,1,2\},1,2\},1,2\}\)

\(g_{\varphi(1,1,0)}(n) \approx \{n,n,2,2\}\)

\(g_{\varphi(1,2,0)}(n) \approx \{n,n,3,2\}\)

\(g_{\varphi(1,\omega,0)}(n) \approx \{n,n,n,2\}\)

\(g_{\varphi(1,\Gamma_0,0)}(n) \approx \{n,n,\{n,n,1,2\},2\}\)

\(g_{\varphi(1,\varphi(1,\Gamma_0,0),0)}(n) \approx \{n,n,\{n,n,\{n,n,1,2\},2\},2\}\)

\(g_{\varphi(2,0,0)}(n) \approx \{n,n,1,3\}\)

\(g_{\varphi(3,0,0)}(n) \approx \{n,n,1,4\}\)

\(g_{\varphi(\omega,0,0)}(n) \approx \{n,n,1,n+1\}\)

\(g_{\varphi(\Gamma_0,0,0)}(n) \approx \{n,n,1,\{n,n,1,2\}+1\}\)

\(g_{\varphi(1,0,0,0)}(n) \approx \{n,n,1,1,2\}\)

\(g_{\varphi(1,0,0,0,0)}(n) \approx \{n,n,1,1,1,2\}\)

\(g_{\varphi(1,0,0,0,0,0)}(n) \approx \{n,n,1,1,1,1,2\}\)

From \(\vartheta(\Omega^\omega)\) to \(\vartheta(\Omega^\Omega)\)

\(g_{\vartheta(\Omega^\omega)}(n) \approx \{n,n+2 (1) 2\}\)

\(g_{\vartheta(\Omega^{\omega+1})}(n) \approx \{n,n+3 (1) 2\}\)

\(g_{\vartheta(\Omega^{\omega+m})}(n) \approx \{n,n+m+2 (1) 2\}\)

\(g_{\vartheta(\Omega^{\omega 2})}(n) \approx \{n,2n(1) 2\}\)

\(g_{\vartheta(\Omega^{\omega 3})}(n) \approx \{n,3n(1) 2\}\)

\(g_{\vartheta(\Omega^{\omega m})}(n) \approx \{n,m \times n(1) 2\}\)

\(g_{\vartheta(\Omega^{\omega^2})}(n) \approx \{n,n^2(1) 2\}\)

\(g_{\vartheta(\Omega^{\omega^\omega})}(n) \approx \{n,n^n(1) 2\}\)

\(g_{\vartheta(\Omega^{\varepsilon_0})}(n) \approx \{n,n\uparrow\uparrow n(1) 2\}\)

\(g_{\vartheta(\Omega^{\Gamma_0})}(n) \approx \{n,\{n,n,1,2\}(1)2\}\)

From \(\vartheta(\Omega^\Omega)\) to \(\vartheta(\Omega^{\Omega^\Omega})\)

\(g_{\vartheta(\Omega^{\Omega})}(n) \approx \{n,n,2(1)2\}\)

\(g_{\vartheta(\Omega^{\Omega}+1)}(n) \approx \{n,n,3(1)2\}\)

\(g_{\vartheta(\Omega^{\Omega}+m)}(n) \approx \{n,n,m+2(1)2\}\)

\(g_{\vartheta(\Omega^{\Omega}+\omega)}(n) \approx \{n,n,n+2(1)2\}\)

\(g_{\vartheta(\Omega^{\Omega}+\Omega)}(n) \approx \{n,n,1,2(1)2\}\)

\(g_{\vartheta(\Omega^{\Omega}+\Omega \omega)}(n) \approx \{n,n,n,n(1)2\}\)

\(g_{\vartheta(\Omega^{\Omega}+\Omega^m \omega)}(n) \approx \{n,m+3(1)3\}\)

\(g_{\vartheta(\Omega^{\Omega}+\Omega^\omega)}(n) \approx \{n,n+3(1)3\}\)

\(g_{\vartheta(\Omega^{\Omega} 2)}(n) \approx \{n,n,2(1)3\}\)

\(g_{\vartheta(\Omega^{\Omega} 2+\Omega^\omega)}(n) \approx \{n,n+3(1)4\}\)

\(g_{\vartheta(\Omega^{\Omega} m+\Omega^\omega)}(n) \approx \{n,n+3(1)m+1\}\)

\(g_{\vartheta(\Omega^{\Omega} \omega)}(n) \approx \{n,n+3(1)n\}\)

\(g_{\vartheta(\Omega^{\Omega + 1})}(n) \approx \{n,n+1(1)1,2\}\)

\(g_{\vartheta(\Omega^{\Omega + m})}(n) \approx \{n,n+1(1)\underbrace{1,1...1,1}_{m},2\}\)

\(g_{\vartheta(\Omega^{\Omega 2})}(n) \approx \{n,n+1(1)(1)2\}\)

\(g_{\vartheta(\Omega^{\Omega 2 + m})}(n) \approx \{n,n+1(1)(1)\underbrace{1,1...1,1}_{m},2\}\)

\(g_{\vartheta(\Omega^{\Omega 3})}(n) \approx \{n,n+1(1)(1)(1)2\}\)

\(g_{\vartheta(\Omega^{\Omega m})}(n) \approx \{n,n+1\underbrace{(1)...(1)}_{m}2\}\)

\(g_{\vartheta(\Omega^{\Omega \omega})}(n) \approx \{n,n+1(2)2\}\)

\(g_{\vartheta(\Omega^{\Omega^2})}(n) \approx \{n,n,2(2)2\}\)

\(g_{\vartheta(\Omega^{\Omega^2}+\Omega^{\Omega \omega})}(n) \approx \{n,n+1(2)3\}\)

\(g_{\vartheta(\Omega^{\Omega^2}\omega)}(n) \approx \{n,n+1(2)n\}\)

\(g_{\vartheta(\Omega^{\Omega^2 + 1})}(n) \approx \{n,n(2)1,2\}\)

\(g_{\vartheta(\Omega^{\Omega^2 + \omega})}(n) \approx \{n,n(2)(1)2\}\)

\(g_{\vartheta(\Omega^{\Omega^2 + \Omega\omega})}(n) \approx \{n,n(2)(2)2\}\)

\(g_{\vartheta(\Omega^{\Omega^2\omega})}(n) \approx \{n,n+1(3)2\}\)

\(g_{\vartheta(\Omega^{\Omega^3})}(n) \approx \{n,n,2(3)2\}\)

\(g_{\vartheta(\Omega^{\Omega^{n-1}\omega})}(n) \approx \{n,n+1(n)2\}\)

\(g_{\vartheta(\Omega^{\Omega^\omega})}(n) \approx \{n,n+1(0,1)2\}\)

\(g_{\vartheta(\Omega^{\Omega^{\vartheta(\Omega^{\Omega^\omega})}})}(n) \approx \{n,\{n,n+1(0,1)2\}(0,1)2\}\)

From \(\vartheta(\Omega^{\Omega^\Omega})\) to \(\vartheta(\varepsilon_{\Omega + 1})\)

\(g_{\vartheta(\Omega^{\Omega^\Omega})}(n) \approx \{n,n,2(0,1)2\}\)

\(g_{\vartheta(\Omega^{\Omega^\Omega + \Omega^\omega})}(n) \approx \{n,n(0,1)1(0,1)2\}\)

\(g_{\vartheta(\Omega^{\Omega^\Omega\omega})}(n) \approx \{n,n(1,1)2\}\)

\(g_{\vartheta(\Omega^{\Omega^{\Omega + \omega}})}(n) \approx \{n,n(0,2)2\}\)

\(g_{\vartheta(\Omega^{\Omega^{\Omega \omega}})}(n) \approx \{n,n(0,0,1)2\}\)

\(g_{\vartheta(\Omega^{\Omega^{\Omega^\omega}})}(n) \approx \{n,n((1)1)2\}\)

\(g_{\vartheta(\Omega^{\Omega^{\Omega^\Omega}})}(n) \approx \{n,n,2((1)1)2\}\)

\(g_{\vartheta(\Omega^{\Omega^{\Omega^{\Omega^\omega}}})}(n) \approx \{n,n((0,1)1)2\}\)

\(g_{\vartheta(\Omega^{\Omega^{\Omega^{\Omega^\Omega}}})}(n) \approx \{n,n,2((0,1)1)2\}\)

\(g_{\vartheta(\varepsilon_{\Omega+1})}(n) \approx X \uparrow\uparrow X\ \&\ n\)

See also

Ordinals, ordinal analysis, and set theory

Basics: cardinal numbers · normal function · ordinal numbers · limit ordinals · fundamental sequence · ordinal notation · transfinite induction
Theories: Robinson arithmetic · Presburger arithmetic · Peano arithmetic · KP · second-order arithmetic · ZFC
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}}}})\) (the countable limit of Extended Buchholz's function)‎ · \(\omega_1^\mathfrak{Ch}\) · \(\omega_1^{\text{CK}}\) (Church-Kleene ordinal) · \(\omega_\alpha^\text{CK}\) (admissible ordinal) · recursively Mahlo ordinal · reflecting ordinal · stable ordinal · \(\lambda,\zeta,\Sigma,\gamma\) (ordinals on infinite time Turing machine) · List of countable ordinals
Ordinal hierarchies: Fast-growing hierarchy · Slow-growing hierarchy · Hardy hierarchy · Middle-growing hierarchy · N-growing hierarchy
Ordinal functions Veblen function · ordinal collapsing function · Madore's function · Buchholz's function · Jäger's 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: \(V\) · \(L\) · \(\textrm{On}\) · \(\textrm{Lim}\) · \(\textrm{AP}\) · Class (set theory)

Community content is available under CC-BY-SA unless otherwise noted.