## Goodsteins TheoremWritten by Paul BourkeJanuary 1997
Goodstein's theorem is an example of a Gödel theorem for the mathematical process of induction, that is, given the correctness of mathematical induction, then we must believe Goodstein's theorem even though it cannot be proved by mathematical induction. Consider a series generated as follows: starting with any number N, represent that number using only powers of a single base, say 2 (see example). Write all exponents also in their base 2 expansion. To form the next term in the series increase each digit of the current base by 1 and subtract 1 from the resulting number. Goodstein's theorem states that such a series tends to zero. Example 1
This is best illustrated with an example, lets start with the number
25. It can be written using only powers of 2 as follows ^{221} +
2^{21 + 20} +
2^{0}
This is often referred to as hereditary representation of a base, 2 in
this case.
In the following discussion I will simply use 1 for 2 ^{22} + 2^{2 + 1} + 1
^{33} + 3^{3 + 1} = 7625597485068
The next term is ^{44} + 4^{4 + 1} - 1
which is reduced to powers of the current base "4" to ^{44} + 3 * 4^{4} + 3 * 4^{3} +
3 * 4^{2} + 3 * 4 + 3
134078079299425970995740249982058461274793658205923933777 235614437217640300735469768018742981669034276900318581864 86050853753882811946569946433649006085119..... The next term is
^{55} + 3 * 5^{5} + 3 * 5^{3} +
3 * 5^{2} + 3 * 5 + 2
It is important to understand what happened in the second to last term above, this is the how the number is expressed in power of the current base of 4. The subsequent terms of the series only have the current base digit increased!
Example 2
The first example above obviously leads to unmanageable numbers, how about more modest starting points. 0 obviously isn't very interesting. 1 tends to 0 on the first iteration. 2 and 3 are also trivial. 4 is at last interesting, the sequence starts off simple enough: 4, 26, 41, 60, 83, 109, .... but then one needs to wait for an enormous number of iterations before it starts to decrease, finally arriving at 0. Stage Value Expansion 2 4 2^2 3 26 2*3^2 + 2*3 + 2 4 41 2*4^2 + 2*4 + 1 5 60 2*5^2 + 2*5 6 83 2*6^2 + 6 + 5 7 109 2*7^2 + 7 + 4 8 139 2*8^2 + 8 + 3 9 173 2*9^2 + 9 + 2 10 211 2*10^2 + 10 + 1 11 253 2*11^2 + 11 12 299 2*12^2 + 11 13 348 2*13^2 + 10 : : : 23 1058 2*23^2 24 1151 24^2 + 23*24 + 23 25 1222 25^2 + 23*25 + 22 : : : 47 3290 47^2 + 23*47 48 3407 48^2 + 22*48 + 47 : : : 95 11115 95^2 + 22*95 96 11327 96^2 + 21*96 + 95 : : : The square term will not be "alone" for about 3*2^27 further iterations, that is, about 402 million iterations. The series does not reach zero for another 10 followed by over 121 zeros later! The outcome of the Goodstein series for 5 and above will be left as an exercise for the reader. :-) |