TOPICS
Search

Goodstein's Theorem


For all n, there exists a k such that the kth 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.

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


See also

Natural Independence Phenomenon, Paris-Harrington Theorem, Peano Arithmetic

Explore with Wolfram|Alpha

References

Borwein, J. and Bailey, D. Mathematics by Experiment: Plausible Reasoning in the 21st Century. Wellesley, MA: A K Peters, pp. 34-35, 2003.Goodstein, R. L. "On the Restricted Ordinal Theorem." J. Symb. Logic 9, 33-41, 1944.Henle, J. M. An Outline of Set Theory. New York: Springer-Verlag, 1986.

Referenced on Wolfram|Alpha

Goodstein's Theorem

Cite this as:

Weisstein, Eric W. "Goodstein's Theorem." From MathWorld--A Wolfram Web Resource. https://mathworld.wolfram.com/GoodsteinsTheorem.html

Subject classifications