User:Sligocki/Goodstein sequences

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

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.

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:

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)}$

And add a new one:

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

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)<f_{\omega ^{\omega }}^{64}(4)=f_{\omega ^{\omega }\cdot 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 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}}}$