Goodstein Sequence

Given a hereditary representation of a number  in base , let  be the nonnegative integer which results if we syntactically replace each  by  (i.e.,  is a base change operator that 'bumps the base' from  up to ). The hereditary representation of 266 in base 2 is

			(1)
			(2)

so bumping the base from 2 to 3 yields

(3)

Now repeatedly bump the base and subtract 1,

			(4)
			(5)
			(6)
			(7)
			(8)
			(9)
			(10)
			(11)
			(12)

etc.

Starting this procedure at an integer  gives the Goodstein sequence . Amazingly, despite the apparent rapid increase in the terms of the sequence, Goodstein's theorem states that  is 0 for any  and any sufficiently large . Even 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).

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.

Simpson, S. G. "Unprovable Theorems and Fast-Growing Functions." Contemp. Math. 65, 359-394, 1987.