The God of Small Things

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:

[1] Eric W. Weisstein.  “Goodstein’s Theorem.” From MathWorld–A
Wolfram Web Resource.  http://mathworld.wolfram.com/GoodsteinsTheorem.html

[2] Goodstein, R. L. “On the Restricted Ordinal Theorem.” J. Symb. Logic 9,
33-41, 1944.

There are 3 comments

  1. Sophia Singer

    R.L. Goodstein was my father. I’m tickled by “Goodstein is not a Turing machine”. I think he would have been tickled too! I remember him talking about his mathematical research, saying that he made intuitive leaps, and then had the hard work of proving he was right. I don’t know how much his philosophy training at Wittgentstein’s feet had to play in this.

    • David Freiberg

      I don’t know whether this message will ever get to you, but I’m an engineering student, I’ve been researching the calculus of hyperoperational functions for some time, and R.L. Goodstein is an inspiration to me.  His mathematical work was unparalleled in many fields, and I think it’s a shame that very little of it has been expanded on since he wrote it.

      Had he still been alive, his hundredth birthday would have been two days ago.  I think it’s a shame that Google didn’t have a custom logo or something to celebrate it, but that’s life for you.  I do wish I could have met him in person, and I wish you and your family the best.

      Cheers,

      David Freiberg


Comments are closed.