# User:Sligocki/Goodstein sequences

Goodstein sequences are very long sequences which eventually reach 0, but run for so long that Peano arithmetic cannot be used to prove that they reach 0.

## Introduction

Let $G(n)$ be the Goodstein sequence starting with n and ending at 0.

$G(3) = (2 + 1, 3, 3, 2, 1, 0)$
$G(4) = (2^2, 2 \cdot 3^2 + 2 \cdot 3 + 2, \dots, 2\cdot 23^2, \dots, (24 \cdot 2^{24} - 1)^2, \dots, 3, 2, 1, 0)$

Let $g_n$ be the base of the hereditary notation of the last term of $G(n)$ (Alternatively, it is the length of the Goodstein sequence + 1). We shall call these the Goodstein numbers

$n$ $g_n$
0 2
1 3
2 5
3 7
4 $3 \cdot 2^{402653211} - 1 = (24 \cdot 2^{24}) 2^{24 \cdot 2^{24}} - 1$
$\vdots$

Now, in fact, if $f(n) = (n+1) 2^{n+1} - 1$, then $g_4 = f^3(2)$. I show that this function has a meaning.

## Growth of Goodstein Numbers

Let us define a family of functions:

• $f_0(B) = B + 1$
• $f_k(B) = f_{k-1}^{B+1}(B)$

Ah ha,

• $f_1(B) = 2B + 1$
• $f_2(B) = (B+1) \cdot 2^{B+1} - 1$ and
• $f_3(2) = f_2^3(2) = g_4$

In fact:

$n$ $g_n$ $G(n)$
0 2
1 $f_0(2)$ $(2^0, \dots)$
2 $f_1(2)$ $(2^1, \dots)$
3 $f_1(3)$ $(2^1 + 1, 3^1, \dots)$
4 $f_3(2)$ $(2^2, 3^3 - 1, \dots)$
5 $f_4(3)$ $(2^2 + 1, 3^3, 4^4 - 1, \dots)$
6 $f_6(5)$ $(2^2 + 2, 3^3 + 2, 4^4 + 1, 5^5, 6^6 - 1, \dots)$
7 $f_8(7)$ $(2^2 + 2 + 1, 3^3 + 3, 4^4 + 3, \dots, 7^7, 8^8 - 1, \dots)$
$\vdots$

Notice the pattern? If $B^k$ appears in $G(n)$ then $g_n = f_k(B)$ (where B is the base and k<B). Likewise, if $B^B$ appears, then $g_n = f_{B+1}(B)$.

In fact, let's rename our functions (here $\omega$ is a label, not a variable — in fact, it is actually an ordinal number, or generalized index, who's properties I hope to take advantage of):

• $f_{\omega^0}(B) = B + 1$
• $f_{\omega^k}(B) = f_{\omega^{k-1}}^{B+1}(B)$

• $f_{\omega^\omega}(B) = f_{\omega^{B+1}}(B)$

Thus, if we have a value of the form $\alpha$ at base B in $G(n)$, then $g_n = f_\alpha(B)$.

## Derivation of Growth Function

Note: It turns out that the function I define here is a variant of the fast-growing hierarchy much like the Hardy hierarchy.

Goodstein talks about the hereditary form of a number and the unique ordinal number associated with each hereditary form. For example:

$266 = 2^5 + 2^3 + 2 = 2^{2^2 + 1} + 2^{2 + 1} + 2$ is in form $\omega^{\omega^\omega + 1} + \omega^{\omega + 1} + \omega$

Let us identify the hereditary form with that ordinal number.

If N has hereditary form $\alpha$ with base B, then let $f_\alpha(B)$ be the base at which the the Goodstein sequence starting at N in base B will end.

For some values of $\alpha$:

• $f_0(B) = B$
• $f_1(B) = B + 1$
• $f_k(B) = f_1^k(B) = B + k$

• $f_\omega(B) = f_B(B+1) = f_1^{B+1}(B) = 2B + 1$
• $f_{\omega \cdot k}(B) = f_\omega^k(B)) = (B + 1) 2^k - 1$

• $f_{\omega^2}(B) = f_{\omega \cdot B + B}(B+1) = f_{\omega \cdot B}(f_B(B+1)) = f_{\omega \cdot B}(f_\omega(B)) = f_{\omega \cdot (B+1)}(B) = f_\omega^{B+1}(B) = (B + 1) 2^{B + 1} - 1$
• $f_{\omega^2 \cdot k}(B) = f_{\omega^2}^k(B)) > 2 \uparrow \uparrow k$

• $f_{\omega^3}(B) = f_{\omega^2 \cdot B + \omega \cdot B + B}(B+1) = f_{\omega^2 \cdot B}(f_{\omega^2 \cdot B + B}(B+1)) = f_{\omega^2 \cdot B}(f_{\omega^2}(B)) = f_{\omega^2 \cdot (B+1)}(B) = f_{\omega^2}^{B+1}(B) > 2 \uparrow \uparrow (B+1)$

• $f_{\omega^k}(B) = f_{\omega^{k-1} \cdot (B+1)}(B) = f_{\omega^{k-1}}^{B+1}(B) > 2 \uparrow^{k-1} (B+1)$

• $f_{\omega^\omega}(B) = f_{\omega^{B+1}}(B) > 2 \uparrow^B (B+1) = 2 \to B + 1 \to B$
• $f_{\omega^\omega \cdot k}(B) = f_{\omega^\omega}^k(B) > 2 \to B + 1 \to k \to 2$

Note: $h(n) = 3 \uparrow^n 3 < 2 \uparrow^n (n-1) = f_{\omega^\omega}(n-1)$. So Graham's number $\mathcal{G} = h^{64}(4) < f_{\omega^\omega}^{64}(4) = f_{\omega^\omega \cdot 64}(4)$.

Now $G(12) = (2^{2+1} + 2^2, \dots, g_4^{g_4 + 1}, g_4 (g_4 + 1)^{g_4 + 1}, \dots)$ where we remember that $g_4 = f_{\omega^\omega}(2) = 3 \cdot 2^{402653211} - 1 > 64$. So, $g_{12} = f_{\omega^\omega \cdot g_4}(g_4 + 1) > f_{\omega^\omega \cdot 64}(4) > \mathcal{G}$

• $f_{\omega^{\omega + 1}}(B) = f_{\omega^\omega \cdot B + \omega^B \cdot B + \cdots + B}(B+1) = f_{\omega^\omega \cdot B}(f_{\omega^{B+1}}(B)) = f_{\omega^\omega \cdot B}(f_{\omega^\omega}(B)) = f_{\omega^\omega \cdot (B + 1)}(B) = f_{\omega^\omega}^{B+1}(B) > 2 \to B + 1 \to B + 1 \to 2$
• $f_{\omega^{\omega + 1} \cdot k}(B) = f_{\omega^{\omega + 1}}^k(B) > 2 \to B + 1 \to k \to 3$

• $f_{\omega^{\omega + 2}}(B) = f_{\omega^{\omega + 1} \cdot B + \omega^\omega \cdot B + \omega^B \cdot B + \cdots + B}(B+1) = f_{\omega^{\omega + 1} \cdot B}(f_{\omega^{\omega+1}}(B)) = f_{\omega^{\omega + 1} \cdot (B + 1)}(B) = f_{\omega^{\omega + 1}}^{B+1}(B) > 2 \to B + 1 \to B + 1 \to 3$

• $f_{\omega^{\omega + k}}(B) = f_{\omega^{\omega + (k-1)} \cdot (B + 1)}(B) = f_{\omega^{\omega + (k-1)}}^{B+1}(B) > 2 \to B + 1 \to B + 1 \to k + 1$

• $f_{\omega^{\omega \cdot 2}}(B) = f_{\omega^{\omega + (B+1)}}(B) > 2 \to B + 1 \to B + 1 \to B + 2$

...

• $f_{\omega^{\omega^\omega}}(B) = f_{\omega^{\omega^{B+1}}}(B) >> 2 \to \overbrace{B + 1 \to \cdots \to B + 1}^{B^2 + 2}$

Now let's look back at the table:

$n$ $g_n$ $G(n)$
0 $f_0(2) = 2$ $(0, \dots)$
1 $f_1(2) = f_1(g_0) = 3$ $(1, \dots)$
2 $f_\omega(2) = f_\omega(g_0) = 5$ $(2^1, \dots)$
3 $f_{\omega+1}(2) = f_\omega(f_1(2)) = f_\omega(g_1) = 7$ $(2^1 + 1, 3^1, \dots)$
4 $f_{\omega^\omega}(2) = f_{\omega^\omega}(g_0)$ $(2^2, \dots)$
5 $f_{\omega^\omega + 1}(2) = f_{\omega^\omega}(f_1(2)) = f_{\omega^\omega}(g_1)$ $(2^2 + 1, 3^3, \dots)$
6 $f_{\omega^\omega + \omega}(2) = f_{\omega^\omega}(f_\omega(2)) = f_{\omega^\omega}(g_2)$ $(2^2 + 2, 5^5, \dots)$
7 $f_{\omega^\omega + \omega + 1}(2) = f_{\omega^\omega}(f_\omega(f_1(2))) = f_{\omega^\omega}(g_3)$ $(2^2 + 2 + 1, 3^3 + 3, \dots, 7^7, \dots)$
8 $f_{\omega^{\omega + 1}}(2) = f_{\omega^{\omega + 1}}(g_0) = f_{\omega^\omega}^{g_0 + 1}(2) = f_{\omega^\omega}^{g_0}(g_4)$ $(2^{2 + 1}, \dots, 2 \cdot g_4^{g_4}, \dots)$
9 $f_{\omega^{\omega + 1} + 1}(2) = f_{\omega^{\omega + 1}}(f_1(2)) = f_{\omega^{\omega + 1}}(g_1) = f_{\omega^\omega}^{g_1 + 1}(f_1(2)) = f_{\omega^\omega}^{g_1}(g_5)$ $(2^{2 + 1} + 1, 3^{3 + 1}, \dots, 3 \cdot g_5^{g_5}, \dots)$
10 $f_{\omega^{\omega + 1} + \omega}(2) = f_{\omega^{\omega + 1}}(f_\omega(2)) = f_{\omega^{\omega + 1}}(g_2) = f_{\omega^\omega}^{g_2 + 1}(g_2) = f_{\omega^\omega}^{g_2}(g_6)$ $(2^{2 + 1} + 2, \dots, 5^{5 + 1}, \dots, 5 \cdot g_6^{g_6}, \dots)$
11 $f_{\omega^{\omega + 1} + \omega + 1}(2) = f_{\omega^{\omega + 1}}(f_\omega(f_1(2))) = f_{\omega^{\omega + 1}}(g_3)$ $(2^{2 + 1} + 2 + 1, 3^{3 + 1} + 3, \dots, 7^{7 + 1}, \dots, 7 \cdot g_7^{g_7}, \dots)$
12 $f_{\omega^{\omega + 1} + \omega^\omega}(2) = f_{\omega^{\omega + 1}}(f_{\omega^\omega}(2))) = f_{\omega^{\omega + 1}}(g_4)$ $(2^{2 + 1} + 2^2, \dots, g_4^{g_4 + 1}, \dots, g_4 \cdot g_8^{g_8}, \dots)$
13 $f_{\omega^{\omega + 1} + \omega^\omega + 1}(2) = f_{\omega^{\omega + 1}}(f_{\omega^\omega}(f_1(2)))) = f_{\omega^{\omega + 1}}(g_5)$ $(2^{2 + 1} + 2^2 + 1, 3^{3+1} + 3^3, \dots, g_5^{g_5 + 1}, \dots, g_5 \cdot g_9^{g_9}, \dots)$
14 $f_{\omega^{\omega + 1} + \omega^\omega + \omega}(2) = f_{\omega^{\omega + 1}}(f_{\omega^\omega}(f_\omega(2)))) = f_{\omega^{\omega + 1}}(g_6)$ $(2^{2 + 1} + 2^2 + 2, \dots, 5^{5+1} + 5^5, \dots, g_6^{g_6 + 1}, \dots, g_6 \cdot g_{10}^{g_{10}}, \dots)$
15 $f_{\omega^{\omega + 1} + \omega^\omega + \omega + 1}(2) = f_{\omega^{\omega + 1}}(f_{\omega^\omega}(f_\omega(f_1(2))))) = f_{\omega^{\omega + 1}}(g_7)$ $(2^{2 + 1} + 2^2 + 2 + 1, \dots, 7^{7+1} + 7^7, \dots, g_7^{g_7 + 1}, \dots, g_7 \cdot g_{11}^{g_{11}}, \dots)$
16 $f_{\omega^{\omega^\omega}}(2) = f_{\omega^{\omega^\omega}}(g_0) = ?$ $(2^{2^2}, \dots, 2 \cdot n^{2 \cdot n^2 + 2 \cdot n + 2}, \dots)$
$\vdots$

• $g_{16} = f_{\omega^{\omega^\omega}}(g_0) = f_{\omega^{\omega^{g_0+1}}}(g_0) = f_{\omega^{\omega^{g_0} \cdot (g_0 + 1)}}(g_0) = f_{\omega^{\omega^{g_0} \cdot g_0 + g_0 + 1}}(g_0) = f_{\omega^{\omega^{g_0} \cdot g_0 + g_0}}^{g_0 + 1}(g_0) = f_{\omega^{\omega^{g_0} \cdot g_0 + g_0}}^{g_0}(f_{\omega^{\omega^2 \cdot 2 + 2}}(g_0)) = ?$

$\begin{array}{rcl} g_6 &=& f_{\omega^\omega + \omega}(2) = f_{\omega^\omega}(f_\omega(2)) \\ &=& f_{\omega^\omega}(5) = f_{\omega^6}(5) = f_{\omega^5}^6(5) \\ &=& f_{\omega^5}^5(f_{\omega^4}^5(f_{\omega^3}^5(f_{\omega^2}^5(f_{\omega^2}(5))))) \\ &=& f_{\omega^5}^5(f_{\omega^4}^5(f_{\omega^3}^5(f_{\omega^2}^5(2^{B+1} - 1)))) \\ &=& f_{\omega^5}^5(f_{\omega^4}^5(f_{\omega^3}^5(f_{\omega^2}^4(2^{2^{B+1} - 1} - 1)))) \\ &=& f_{\omega^5}^5(f_{\omega^4}^5(f_{\omega^3}^5(f_{\omega^2}^3(2^{2^{2^{B+1} - 1} - 1} - 1)))) \\ \end{array}$