Fast-growing hierarchy

From Cantor's Attic
Jump to: navigation, search

The fast-growing hierarchy is a sequence of functions that grow faster very fast. It maps countable ordinals to certain functions. It is defined as follows:

\(f_0(n)=n+1 \\ f_{\alpha+1}(n)=f^n_\alpha(n)\)

\(f_\alpha(n)=f_{\alpha[n]}(n)\) if and only if \(\alpha\) is a limit ordinal.

Values

These calculations are based on Diagonalization. There are a few things to note: "\(\uparrow\)" means Knuth's up-arrow notation. "\(\lbrace\rbrace\)" means BAN.

\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 \uparrow n \\ f_3(n) &>& 2\uparrow\uparrow n \\ f_4(n) &>& 2\uparrow\uparrow\uparrow n \\ f_m(n) &>& 2\uparrow^{m-1} n \\ f_\omega(n) &>& 2\uparrow^{n-1} n = 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_{\omega2}(n) &>& \lbrace n,n,n,2 \rbrace \\ f_{\omega3}(n) &>& \lbrace n,n,n,3 \rbrace \\ f_{\omega 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 \rbrace \\ f_{\varepsilon_02}(n) &>& \lbrace n,n [ [1]] 3 \rbrace \\ f_{\varepsilon_0m}(n) &>& \lbrace n,n [ [1]] m+1 \rbrace \\ f_{\varepsilon_0\omega}(n) &>& \lbrace n,n [ [1]] n+1 \rbrace \\ f_{\varepsilon_0{\omega^{\omega}}}(n) &>& \lbrace n,n [ [1]] 1 [2] 2 \rbrace \\ f_{\varepsilon_0{\omega^{\omega^{\omega}}}}(n) &>& \lbrace n,n [ [1]] 1 [1,2] 2 \rbrace \\ f_{\varepsilon_0{\omega^{\omega^{\omega^{\omega}}}}}(n) &>& \lbrace n,n [ [1]] 1 [1 [2] 2] 2 \rbrace \\ f_{\varepsilon_0^2}(n) &>& \lbrace n,n [ [1]] 1 [ [1]] 2 \rbrace \\ f_{\varepsilon_0^3}(n) &>& \lbrace n,n [ [1]] 1 [ [1]] 1 [ [1]] 2 \rbrace \\ f_{\varepsilon_0^{\omega}}(n) &>& \lbrace n,n [ [2]] 2 \rbrace \\ f_{\varepsilon_0^{\omega^{\omega}}}(n) &>& \lbrace n,n [ [1,2]] 2 \rbrace \\ f_{\varepsilon_0^{\omega^{\omega^{\omega}}}}(n) &>& \lbrace n,n [[1 [2] 2]] 2 \rbrace \\ f_{\varepsilon_0^{\varepsilon_0}}(n) &>& \lbrace n,n [[1 [ [1]] 2]] 2 \rbrace \\ f_{\varepsilon_0^{\varepsilon_0^{\varepsilon_0}}}(n) &>& \lbrace n,n [[1 [ [1]] 1 [ [1]] 2]] 2 \rbrace \\ f_{\varepsilon_0^{\varepsilon_0^{\varepsilon_0^{\varepsilon_0}}}}(n) &>& \lbrace n,n [[1 [[1 [ [1]] 2]] 2]] 2 \rbrace \\ f_{\varepsilon_1}(n) &>& \lbrace n,n [[[1]]] 2 \rbrace \\ f_{\varepsilon_2}(n) &>& \lbrace n,n [[[ [1]]]] 2 \rbrace \\ f_{\varepsilon_{\omega}}(n) &>& \lbrace n,n [1\backslash1,2] 2 \rbrace \\ f_{\varepsilon_{\omega^2}}(n) &>& \lbrace n,n [1\backslash1,1,2] 2 \rbrace \\ f_{\varepsilon_{\omega^{\omega}}}(n) &>& \lbrace n,n [1\backslash1 [2] 2] 2 \rbrace \\ f_{\varepsilon_{\omega^{\omega^{\omega}}}}(n) &>& \lbrace n,n [1\backslash1 [1,2] 2] 2 \rbrace \\ f_{\varepsilon_{\varepsilon_0}}(n) &>& \lbrace n,n [1\backslash1 [ [1]] 2] 2 \rbrace \\ f_{\varepsilon_{\varepsilon_{\varepsilon_0}}}(n) &>& \lbrace n,n [1\backslash1 [1\backslash1 [ [1]] 2] 2] 2 \rbrace \\ f_{\zeta_0}(n) &>& \lbrace n,n [1\backslash1\backslash2] 2 \rbrace \\ f_{\zeta_0^{\zeta_0}}(n) &>& \lbrace n,n [1 [1\backslash1\backslash2] 2\backslash1\backslash2] 2 \rbrace \\ f_{\varepsilon_{\zeta_0+1}}(n) &>& \lbrace n,n [1\backslash2\backslash2] 2 \rbrace \\ f_{\varepsilon_{\zeta_0+2}}(n) &>& \lbrace n,n [1\backslash3\backslash2] 2 \rbrace \\ f_{\varepsilon_{\varepsilon_{\zeta_0+1}}} &>& \lbrace n,n [1\backslash1 [1\backslash2\backslash2] 2\backslash2] 2 \rbrace \\ f_{\zeta_1}(n) &>& \lbrace n,n [1\backslash1\backslash3] 2 \rbrace \\ f_{\zeta_2}(n) &>& \lbrace n,n [1\backslash1\backslash4] 2 \rbrace \\ f_{\zeta_{\zeta_0}}(n) &>& \lbrace n,n [1\backslash1\backslash1 [1\backslash1\backslash2] 2] 2 \rbrace \\ f_{\eta_0}(n) &>& \lbrace n,n [1\backslash1\backslash1\backslash2] 2 \rbrace \\ f_{\varphi(4,0)}(n) &>& \lbrace n,n [1\backslash1\backslash1\backslash1\backslash2] 2 \rbrace \\ f_{\varphi(\omega,0)}(n) &>& \lbrace n,n [1 [2]\backslash2] 2 \rbrace \\ f_{\varphi(\varphi(\omega,0),0)}(n) &>& \lbrace n,n [1 [1 [1 [2]\backslash2]\backslash2] 2] 2 \rbrace \\ f_{\Gamma_0}(n) &>& \lbrace n,n [1/2] 2 \rbrace \\ f_{\varphi(1,0,0,0)}(n) &>& \lbrace n,n [1 [1\neg4] 2] 2 \rbrace \\ f_{\vartheta(\Omega^{\omega})}(n) &>& \lbrace n,n [1 [1\neg1,2] 2] 2 \rbrace \\ f_{\vartheta(\Omega^{\Omega})}(n) &>& \lbrace n,n [1 [1\neg1\neg2] 2] 2 \rbrace \\ f_{\vartheta(\Omega^{\Omega^{\Omega}})}(n) &>& \lbrace n,n [1 [1 [1\backslash_33] 2] 2] 2 \rbrace \\ f_{\vartheta(\vartheta_1(1))}(n) &>& \lbrace n,n [1 [1\sim3] 2] 2 \rbrace \\ f_{\vartheta(\vartheta_1(2))}(n) &>& \lbrace n,n [1 [1\sim1\sim2] 2] 2 \rbrace \\ f_{\vartheta(\vartheta_1(\omega))}(n) &>& \lbrace n,n [1 [1 [2/_32] 2] 2] 2 \rbrace \\ f_{\vartheta(\vartheta_1(\Omega))}(n) &>& \lbrace n,n [1 [1 [1/2/_32] 2] 2] 2 \rbrace \\ f_{\vartheta(\Omega_2)}(n) &>& \lbrace n,n [1 [1 [1\sim2/_32] 2] 2] 2 \rbrace \\ f_{\vartheta(\Omega_3)}(n) &>& \lbrace n,n [1 [1 [1 [1/_32/_42] 2] 2] 2] 2 \rbrace \\ f_{\vartheta(\Omega_{\omega})}(n) &>& \lbrace n,n [1\bullet2] 2 \rbrace \\ f_{\vartheta(\Omega_{\varepsilon_0})}(n) &>& \lbrace n,n [1 [2/_{1 [1\backslash2] 2}2] 2] 2 \rbrace \\ f_{\vartheta(\Omega_{\Gamma_0})}(n) &>& \lbrace n,n [1 [2/_{1 [1/2] 2}2] 2] 2 \rbrace \\ f_{\vartheta(\Omega_{\vartheta(\Omega_2)})}(n) &>& \lbrace n,n [1 [2/_{1 [1 [1 [1\sim2/_32] 2] 2] 2}2] 2] 2 \rbrace \\ f_{\vartheta(\Omega_{\vartheta(\Omega_3)})}(n) &>& \lbrace n,n [1 [2/_{1 [1 [1 [1 [1/_32/_42] 2] 2] 2] 2}2] 2] 2 \rbrace \\ f_{\vartheta(\Omega_{\vartheta(\Omega_{\omega})})}(n) &>& \lbrace n,n [1 [2/_{1 [1\bullet2] 2}2] 2] 2 \rbrace \\ f_{\vartheta(\Omega_{\vartheta(\Omega_{\vartheta(\Omega_{\omega})})})}(n) &>& \lbrace n,n [1 [2/_{1 [2/_{1 [1\bullet2] 2}2] 2}2] 2] 2 \rbrace \end{eqnarray*}

An Example

\(f_{\varepsilon_0}(2)=f_\omega(2)=f_2(2)=2^2 2=8\)

It might seem very strange that the gigantic input \(\varepsilon_0\) causes the output to be small, but at \(n=3\), the value is huge. Plug the smaller 2 into it and it will give you a surprise. These calculations are based on Diagonalization.

Other Hierarchies

It turns out that there is a hierarchy called the Slow-growing hierarchy. It is defined as follows:

\(g_0(n)=0 \\ g_{\alpha+1}(n)=g_\alpha(n)+1\)

\(g_\alpha(n)=g_{\alpha[n]}(n)\) if and only if \(\alpha\) is a limit ordinal.

The slow-growing hierarchy at \(\varepsilon_0\) only reaches the level of \(f_3(n)\), and doesn't reach \(f_{\varepsilon_0}(n)\) until the Bachmann-Howard ordinal. It might seem surprising that the slow-growing hierarchy can catch the fast-growing hierarchy, but it does this at \(\psi(\Omega_\omega)\), using Madore's ψ function.