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.
Let G ( n ) {\displaystyle G(n)} be the Goodstein sequence starting with n and ending at 0.
Let g n {\displaystyle g_{n}} be the base of the hereditary notation of the last term of G ( n ) {\displaystyle G(n)} (Alternatively, it is the length of the Goodstein sequence + 1). We shall call these the Goodstein numbers
Now, in fact, if f ( n ) = ( n + 1 ) 2 n + 1 − 1 {\displaystyle f(n)=(n+1)2^{n+1}-1} , then g 4 = f 3 ( 2 ) {\displaystyle g_{4}=f^{3}(2)} . I show that this function has a meaning.
Let us define a family of functions:
Ah ha,
In fact:
Notice the pattern? If B k {\displaystyle B^{k}} appears in G ( n ) {\displaystyle G(n)} then g n = f k ( B ) {\displaystyle g_{n}=f_{k}(B)} (where B is the base and k<B). Likewise, if B B {\displaystyle B^{B}} appears, then g n = f B + 1 ( B ) {\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):
And add a new one:
Thus, if we have a value of the form α {\displaystyle \alpha } at base B in G ( n ) {\displaystyle G(n)} , then g n = f α ( B ) {\displaystyle g_{n}=f_{\alpha }(B)} .
Goodstein talks about the hereditary form of a number and the unique ordinal number associated with each hereditary form. For example:
Let us identify the hereditary form with that ordinal number.
If N has hereditary form α {\displaystyle \alpha } with base B, then let f α ( B ) {\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 } :
Note: h ( n ) = 3 ↑ n 3 < 2 ↑ n ( n − 1 ) = f ω ω ( n − 1 ) {\displaystyle h(n)=3\uparrow ^{n}3<2\uparrow ^{n}(n-1)=f_{\omega ^{\omega }}(n-1)} . So Graham's number G = h 64 ( 4 ) < f ω ω 64 ( 4 ) = f ω ω ⋅ 64 ( 4 ) {\displaystyle {\mathcal {G}}=h^{64}(4)<f_{\omega ^{\omega }}^{64}(4)=f_{\omega ^{\omega }\cdot 64}(4)} .
Now G ( 12 ) = ( 2 2 + 1 + 2 2 , … , g 4 g 4 + 1 , g 4 ( g 4 + 1 ) g 4 + 1 , … ) {\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 g 4 = f ω ω ( 2 ) = 3 ⋅ 2 402653211 − 1 > 64 {\displaystyle g_{4}=f_{\omega ^{\omega }}(2)=3\cdot 2^{402653211}-1>64} . So, g 12 = f ω ω ⋅ g 4 ( g 4 + 1 ) > f ω ω ⋅ 64 ( 4 ) > G {\displaystyle g_{12}=f_{\omega ^{\omega }\cdot g_{4}}(g_{4}+1)>f_{\omega ^{\omega }\cdot 64}(4)>{\mathcal {G}}}
...
Now let's look back at the table: