User:Sligocki/Goodstein sequences

From Wikipedia, the free encyclopedia
Jump to: navigation, search

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[edit]

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[edit]

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)

And add a new one:

  •  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[edit]

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}