How does one prove Goodstein's Theorem ?

[maddog]

I found this theorem I am having trouble swallowing (accepting). I would like to

know how to go about proving it (if only to myself)....

 

Goodstein's Theorem

Given any positive whole number represented by digits, say 581. We can represent

this as a sum of powers of 2:

 

581 = 2^9 + 2^6 + 2^2 + 1

 

or in binary 581 = 1001000101

 

Also 9 = 1001 = 2^3 + 1, 6 = 110 = 2^2 + 2, 2 = 10 = 2^1 and

3 = 11 = 2^1 + 1

 

So this all breaks down to

 

581 = 2^(2^(2^1+1)+1)+2^(2^2+2^1)+2^(2^1)+1

 

Increase the base by 1 (instead of 2 use 3) and subtract by 1.

So wherever there was a 2 use 3, then 4, 5, and so on. With each iteration you

subtract 1 at the end.

 

The theorem states that for every positive integer the sum eventually reaches zero!

 

This was sited in a book by Roger Penrose, "The Emperor's New Mind" (pp xvi-xx).

His footnote on pg xvii sites (3) RL Goodstein, "On the restricted ordinal theorem",

Journal of Symbolic Logic, 9 (1944), 33-41.

 

I am finding this hard to buy at the moment. Call me from Missouri, I guess. :)

 

Maddog

[Bo]

for the proof:

http://mathworld.wolfram.com/GoodsteinsTheorem.html

"The secret underlying Goodstein's theorem is that the hereditary representation of n in base b mimics an ordinal notation for ordinals less than some number. For such ordinals, the base bumping operation leaves the ordinal fixed whereas the subtraction of one decreases the ordinal. But these ordinals are well ordered, and this allows us to conclude that a Goodstein sequence eventually converges to zero."

 

- the goodsteins theorem cannot be proved within the framework of Peano's axioms (there is a zero, for every number, that number+1 is a number... stuff like that)

 

Bo

[Qfwfq]

Sure, it is an amazing result and certainly not trivial to prove. I haven't so far followed Bo's link, here's another one:

 

http://mathworld.wolfram.com/GoodsteinSequence.html

 

with the very interesting remark:

 

"more amazingly, Paris and Kirby showed in 1982 that Goodstein's theorem is not provable in ordinary Peano arithmetic (Borwein and Bailey 2003, p. 35)."

 

and from which you can also reach:

 

"Paris and Harrington (1977) gave the first "natural" example of a statement which is true for the integers but unprovable in Peano arithmetic (Spencer 1983)."

 

and from there a simple version Peano's axioms

 

These remarks show that you shouldn't expect to easily find a proof, indeed offhand I really can't see how to go about it but I might give it a try before looking at answers. Very interesting problem.