10,825 Pages

## Problem of Goodstein function

What's the growth rate of Goodstein function? $$\varepsilon_0$$?

No. Unlike Hydra function and Worm function, which are comparable to $$f_{\varepsilon_0}(n)$$, Goodstein function has some "cost" - $$G(2\uparrow\uparrow n)\approx f_{\varepsilon_0}(n)$$. By the definition of "functional approximation":

$$f\ge^*g$$ if there exists k such that for all n > 0, $$f(n+k)\ge g(n)$$

and

$$f\approx g$$ if $$f\ge^*g$$ and $$g\ge^*f$$

Goodstein function is not comparable to $$f_{\varepsilon_0}(n)$$. Currently we don't have a compact notation to express the growth rate of it. However, in this blog post I won't consider this thing. Instead, I'll consider what it "costs" and extend it. Goodstein has a 3-level cost under $$\varepsilon_0$$, since $$G(f_3(n))\approx f_{\varepsilon_0}(n)$$; then what about a function with a $$\varepsilon_0$$-level cost under $$\varepsilon_0$$?

## An $$\varepsilon_0$$-level cost function

The answer depends on the fundamental sequences.

Here I'll introduce a function with $$\varepsilon_0$$-level cost under $$\varepsilon_0$$: $$FH(n)=f_{\sup\{\alpha<\varepsilon_0|H_\alpha(2)\le n+2\}}(2)$$, where f and H are fast-growing hierarchy and Hardy hierarchy respectively, and the fundamental sequences are shown here.

Its behavior is quite similar to Goodstein function. We can write it in a similar form: $$G(n)=H_{\sup\{\alpha<\varepsilon_0|g_\alpha(2)\le n\}}(3)-3$$, then the $$g_\alpha(2)\le n$$ means the "cost". The $$\alpha$$ is limited below $$\varepsilon_0$$, so the cost is $$g_{\varepsilon_0}(n)\approx f_3(n)$$. In FH function, the cost is $$H_{\varepsilon_0}(n)$$, which is comparable to $$f_{\varepsilon_0}(n)$$. And, $$FH(H_{\varepsilon_0}(n))\approx f_{\varepsilon_0}(n)$$.

FH function is actually a fast-growing function. Consider the difference between the "$$\varepsilon_0$$" in $$f_{\varepsilon_0}(n)$$ and in $$H_{\varepsilon_0}(n)$$. From $$f_\alpha(n)=H_{\omega^\alpha}(n)$$, we have $$H_{\varepsilon_0[k+1]}(n)=f_{\varepsilon_0[k]}(n)$$. As a result, $$FH(H_{\varepsilon_0[k]}(n))\approx H_{\varepsilon_0[k+1]}(n)$$, so $$FH^n(0)\approx H_{\varepsilon_0}(n)\approx f_{\varepsilon_0}(n)$$.

This result suggests the FH function to have growth rate $$\varepsilon_0-1$$, because $$f_{\varepsilon_0}(n)=f_{\varepsilon_0-1+1}(n)=f_{\varepsilon_0-1}^n(n)$$ (though the $$f_{\varepsilon_0-1}$$ doesn't really exist) and $$FH^n(n)\approx f_{\varepsilon_0}(n)$$ show similar way.

## Injection

This section is off-topic.

The first several values of FH function make me uncomfortable. Here are some small values:

\begin{eqnarray*} FH(0) &=& 3 \\ FH(1) &=& 4 \\ FH(2) &=& 8 \\ FH(3) &=& 8 \\ FH(4) &=& f_8(8) \\ FH(5) &=& f_8(8) \\ FH(6) &=& f_{\omega+1}(f_8(8)) \\ FH(7) &=& f_{\omega+1}(f_8(8)) \\ FH(8) &=& f_{\omega+1}(f_8(8)) \\ \vdots & & \vdots \\ FH(3\times2^{402653211}-3) &=& f_{\omega+1}(f_8(8)) \\ FH(3\times2^{402653211}-2) &=& f_{\omega^\omega}(f_{\omega+1}(f_8(8))) \end{eqnarray*}

It's due to the fast growing of HH while the ordinal increases.

This definition, shown below, may make me more comfortable. $$\sigma$$ is a function from natural numbers to ordinals below $$\varepsilon_0$$: $$\sigma(n,k)=\sup\{\alpha<\varepsilon_0|H_\alpha(k)\le n+2\}$$. Then the a-sequence is defined as follows: Set $$a(n)_1=2$$; if $$H_{\sigma(n,a(n)_k)}(a(n)_k)<n+2$$, let $$a(n)_{k+1}=H_{\sigma(n,a(n)_k)}(a(n)_k)$$; if $$H_{\sigma(n,a(n)_k)}(a(n)_k)=n+2$$, then the a-sequence have only k terms, and define $$fh(n)=f_{\sigma(n,a(n)_k)}(f_{\sigma(n,a(n)_{k-1})}(\cdots f_{\sigma(n,a(n)_2)}(f_{\sigma(n,a(n)_1)}(2))))$$.

fh function still has similar growth rate to FH function. Here are some small values of fh function:

\begin{eqnarray*} fh(0) &=& 3 \\ fh(1) &=& 4 \\ fh(2) &=& 8 \\ fh(3) &=& 16 \\ fh(4) &=& f_8(8) \\ fh(5) &=& 2f_8(8) \\ fh(6) &=& f_{\omega+1}(f_8(8)) \\ fh(7) &=& 2f_{\omega+1}(f_8(8)) \\ fh(8) &=& f_2(f_{\omega+1}(f_8(8))) \\ fh(9) &=& f_3(f_{\omega+1}(f_8(8))) \\ \vdots & & \vdots \\ fh(13) &=& f_7(f_{\omega+1}(f_8(8))) \\ fh(14) &=& f_\omega(f_{\omega+1}(f_8(8))) \\ fh(15) &=& 2f_\omega(f_{\omega+1}(f_8(8))) \\ fh(16) &=& f_{\omega+1}^2(f_8(8)) \\ fh(17) &=& 2f_{\omega+1}^2(f_8(8)) \\ fh(18) &=& f_{\omega+2}(f_{\omega+1}(f_8(8))) \\ fh(19) &=& 2f_{\omega+2}(f_{\omega+1}(f_8(8))) \\ fh(20) &=& f_{\omega+3}(f_{\omega+1}(f_8(8))) \\ \vdots & & \vdots \\ fh(29) &=& 2f_{\omega+7}(f_{\omega+1}(f_8(8))) \\ fh(30) &=& f_{\omega2}(f_{\omega+1}(f_8(8))) \\ fh(62) &=& f_{\omega3}(f_{\omega+1}(f_8(8))) \\ fh(1022) &=& f_{\omega7}(f_{\omega+1}(f_8(8))) \\ fh(2046) &=& f_{\omega^2}(f_{\omega+1}(f_8(8))) \\ fh(3\times2^{402653211}-2) &=& f_{\omega^\omega}(f_{\omega+1}(f_8(8))) \end{eqnarray*}