Slow-growing hierarchy

The slow-growing hierarchy (SGH) is a certain hierarchy mapping ordinals \(\alpha\) (below the supremum \(\mu\) of a fixed system of fundamental sequences) 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.
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.
== Warning ==
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)\), which is tetrational level, 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 respect 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_0(\Omega_{\Omega_{\cdot_{\cdot_{\cdot}}}})\) 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.
== Definition ==
The slow-growing hierarchy 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:
* \(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 fixed fundamental sequence assigned to an ordinal \(\alpha\).
== Functions ==
Below is the list of comparisons between SGH with respect to uncertain choice of fundamental sequences and other googological notations ( Wainer hierarchy before \(\varepsilon_0))). Do note the following analysis is heavily dependent on the choice of very specific fundamental sequences and will give wildly different values for different fundamental sequences. Therefore the results might be incorrect when one tries to consider a specific system of fundamental sequences.
=== 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) =n \uparrow\uparrow ((n + 1)n)\)
\(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 + 1)\)
\(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 + 1)\)
\(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 + 1)\)
\(g_{\varphi(5,0)}(n) \approx n \uparrow\uparrow\uparrow\uparrow\uparrow\uparrow (n + 1)\)
\(g_{\varphi(m,0)}(n) \approx n \uparrow^{m + 1} (n + 1)\)
\(g_{\varphi(\omega,0)}(n) \approx \{n,n+1,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\)
ja:緩増加関数
zh:緩慢增長的層次結構
== See also ==
Category:Hierarchies
Category:Functions
Category:Transfinite ordinals
Category:Notations