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.