info prev up next book cdrom email home

Goodstein's Theorem

For all $n$, there exists a $k$ such that the $k$th term of the Goodstein Sequence $G_k(n)=0$. In other words, every Goodstein Sequence converges to 0.

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.

Goodstein's theorem cannot be proved in Peano Arithmetic (i.e., formal Number Theory).

See also Natural Independence Phenomenon, Peano Arithmetic

© 1996-9 Eric W. Weisstein