Goodstein’s remarkable theorem is almost completely unknown outside of formal logic. Roger Penrose sees deep consequences in the fact that Goodstein’s mind was able to discover it. Penrose’s claim, as I understand it, is that human minds can derive theorems that a Turing machine cannot, and therefore  we’re not — or rather, Goodstein is not — a Turing machine. So what’s this theorem about?

Note: 2^x means 2 multiplied with itself x times. Thus 2^3 = 2 * 2 * 2 = 8.

1. Take any positive number. [We’ll use the number 33 as a running example.] 2. Write the number in base-2 representation. [33 =  2^5 + 1] 3. Express everything — even the the powers — in base 2. [33 = 2^5 + 1 = 2^(2^2 + 1) + 1] (This is called the hereditary representation of a number. )

4. Increase the base by 1.  [33 = 2^(2^2 + 1) + 1 –> 3^(3^3 + 1) + 1 = 22876792454962.] 5. Decrease the whole number by 1. [3^(3^3 + 1) + 1 –>  3^(3^3 + 1) = 22876792454961.] 6. Repeat steps 4 and 5 alternatively.

What do you think will happen? One would think that the number would get larger and larger and larger, since base increases have much more impact than the tiny reductions by 1. In the running example, the number went from 33 to 22876792454962 after step 4.

But R. L. Goodstein showed that the small constant decreases by 1 will eventually make the sequence converge to … ZERO!

Initially, the increases in base sends the numbers exploding, but the decrements in step 5 take their fatal toll and eventually converges the sequence to zero. It is death by a googol of pinpricks.

Amazing, right? Here’s an even more amazing fact. J. Paris and L. Kirby showed that Goodstein’s theorem cannot be proved using Peano’s axioms (roughly, basic arithmetic). In short, it’s an example of a Godel statement.

So how did Goodstein prove it? He used a stronger form of induction known as transfinite induction.

Goodstein’s theorem: a mathematical version of the God of Small Things, so to speak. Why did Arundhati Roy take so many pages?

References: