Goodsteins Theorem

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.

This is best illustrated with an example, lets start with the number 25. It can be written using only powers of 2 as follows

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⁰ and 2 for 2¹ as it simplifies the expressions and makes no difference to the procedure. So 25 is represented as

The next term is

134078079299425970995740249982058461274793658205923933777 235614437217640300735469768018742981669034276900318581864 86050853753882811946569946433649006085119.....

The next term is

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!

Goodstein's theorem states that this series tends to zero! In 1944 R. L. Goodstein proved that this is the case for any natural number. Goodstein's theorem cannot be proved in Peano Arithmetic (ie: formal Number Theory).

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. :-)