# 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 ${\displaystyle G(n)}$ be the Goodstein sequence starting with n and ending at 0.

${\displaystyle G(3)=(2+1,3,3,2,1,0)}$
${\displaystyle 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 ${\displaystyle g_{n}}$ be the base of the hereditary notation of the last term of ${\displaystyle G(n)}$ (Alternatively, it is the length of the Goodstein sequence + 1). We shall call these the Goodstein numbers

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

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

## Growth of Goodstein Numbers

Let us define a family of functions:

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

Ah ha,

• ${\displaystyle f_{1}(B)=2B+1}$
• ${\displaystyle f_{2}(B)=(B+1)\cdot 2^{B+1}-1}$ and
• ${\displaystyle f_{3}(2)=f_{2}^{3}(2)=g_{4}}$

In fact:

${\displaystyle n}$ ${\displaystyle g_{n}}$ ${\displaystyle G(n)}$
0 2
1 ${\displaystyle f_{0}(2)}$ ${\displaystyle (2^{0},\dots )}$
2 ${\displaystyle f_{1}(2)}$ ${\displaystyle (2^{1},\dots )}$
3 ${\displaystyle f_{1}(3)}$ ${\displaystyle (2^{1}+1,3^{1},\dots )}$
4 ${\displaystyle f_{3}(2)}$ ${\displaystyle (2^{2},3^{3}-1,\dots )}$
5 ${\displaystyle f_{4}(3)}$ ${\displaystyle (2^{2}+1,3^{3},4^{4}-1,\dots )}$
6 ${\displaystyle f_{6}(5)}$ ${\displaystyle (2^{2}+2,3^{3}+2,4^{4}+1,5^{5},6^{6}-1,\dots )}$
7 ${\displaystyle f_{8}(7)}$ ${\displaystyle (2^{2}+2+1,3^{3}+3,4^{4}+3,\dots ,7^{7},8^{8}-1,\dots )}$
${\displaystyle \vdots }$

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

In fact, let's rename our functions (here ${\displaystyle \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):

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

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

Thus, if we have a value of the form ${\displaystyle \alpha }$ at base B in ${\displaystyle G(n)}$, then ${\displaystyle 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:

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

Let us identify the hereditary form with that ordinal number.

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

For some values of ${\displaystyle \alpha }$:

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

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

• ${\displaystyle 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}$
• ${\displaystyle f_{\omega ^{2}\cdot k}(B)=f_{\omega ^{2}}^{k}(B))>2\uparrow \uparrow k}$

• ${\displaystyle 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)}$

• ${\displaystyle 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)}$

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

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

Now ${\displaystyle 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 ${\displaystyle g_{4}=f_{\omega ^{\omega }}(2)=3\cdot 2^{402653211}-1>64}$. So, ${\displaystyle g_{12}=f_{\omega ^{\omega }\cdot g_{4}}(g_{4}+1)>f_{\omega ^{\omega }\cdot 64}(4)>{\mathcal {G}}}$

• ${\displaystyle 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}$
• ${\displaystyle f_{\omega ^{\omega +1}\cdot k}(B)=f_{\omega ^{\omega +1}}^{k}(B)>2\to B+1\to k\to 3}$

• ${\displaystyle 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}$

• ${\displaystyle 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}$

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

...

• ${\displaystyle 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:

${\displaystyle n}$ ${\displaystyle g_{n}}$ ${\displaystyle G(n)}$
0 ${\displaystyle f_{0}(2)=2}$ ${\displaystyle (0,\dots )}$
1 ${\displaystyle f_{1}(2)=f_{1}(g_{0})=3}$ ${\displaystyle (1,\dots )}$
2 ${\displaystyle f_{\omega }(2)=f_{\omega }(g_{0})=5}$ ${\displaystyle (2^{1},\dots )}$
3 ${\displaystyle f_{\omega +1}(2)=f_{\omega }(f_{1}(2))=f_{\omega }(g_{1})=7}$ ${\displaystyle (2^{1}+1,3^{1},\dots )}$
4 ${\displaystyle f_{\omega ^{\omega }}(2)=f_{\omega ^{\omega }}(g_{0})}$ ${\displaystyle (2^{2},\dots )}$
5 ${\displaystyle f_{\omega ^{\omega }+1}(2)=f_{\omega ^{\omega }}(f_{1}(2))=f_{\omega ^{\omega }}(g_{1})}$ ${\displaystyle (2^{2}+1,3^{3},\dots )}$
6 ${\displaystyle f_{\omega ^{\omega }+\omega }(2)=f_{\omega ^{\omega }}(f_{\omega }(2))=f_{\omega ^{\omega }}(g_{2})}$ ${\displaystyle (2^{2}+2,5^{5},\dots )}$
7 ${\displaystyle f_{\omega ^{\omega }+\omega +1}(2)=f_{\omega ^{\omega }}(f_{\omega }(f_{1}(2)))=f_{\omega ^{\omega }}(g_{3})}$ ${\displaystyle (2^{2}+2+1,3^{3}+3,\dots ,7^{7},\dots )}$
8 ${\displaystyle 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})}$ ${\displaystyle (2^{2+1},\dots ,2\cdot g_{4}^{g_{4}},\dots )}$
9 ${\displaystyle 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})}$ ${\displaystyle (2^{2+1}+1,3^{3+1},\dots ,3\cdot g_{5}^{g_{5}},\dots )}$
10 ${\displaystyle 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})}$ ${\displaystyle (2^{2+1}+2,\dots ,5^{5+1},\dots ,5\cdot g_{6}^{g_{6}},\dots )}$
11 ${\displaystyle f_{\omega ^{\omega +1}+\omega +1}(2)=f_{\omega ^{\omega +1}}(f_{\omega }(f_{1}(2)))=f_{\omega ^{\omega +1}}(g_{3})}$ ${\displaystyle (2^{2+1}+2+1,3^{3+1}+3,\dots ,7^{7+1},\dots ,7\cdot g_{7}^{g_{7}},\dots )}$
12 ${\displaystyle f_{\omega ^{\omega +1}+\omega ^{\omega }}(2)=f_{\omega ^{\omega +1}}(f_{\omega ^{\omega }}(2)))=f_{\omega ^{\omega +1}}(g_{4})}$ ${\displaystyle (2^{2+1}+2^{2},\dots ,g_{4}^{g_{4}+1},\dots ,g_{4}\cdot g_{8}^{g_{8}},\dots )}$
13 ${\displaystyle f_{\omega ^{\omega +1}+\omega ^{\omega }+1}(2)=f_{\omega ^{\omega +1}}(f_{\omega ^{\omega }}(f_{1}(2))))=f_{\omega ^{\omega +1}}(g_{5})}$ ${\displaystyle (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 ${\displaystyle f_{\omega ^{\omega +1}+\omega ^{\omega }+\omega }(2)=f_{\omega ^{\omega +1}}(f_{\omega ^{\omega }}(f_{\omega }(2))))=f_{\omega ^{\omega +1}}(g_{6})}$ ${\displaystyle (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 ${\displaystyle 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})}$ ${\displaystyle (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 ${\displaystyle f_{\omega ^{\omega ^{\omega }}}(2)=f_{\omega ^{\omega ^{\omega }}}(g_{0})=?}$ ${\displaystyle (2^{2^{2}},\dots ,2\cdot n^{2\cdot n^{2}+2\cdot n+2},\dots )}$
${\displaystyle \vdots }$

• ${\displaystyle 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}))=?}$

${\displaystyle {\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}}}$