Goodstein's Amazing Sequence

The following excerpt is reproduced from Bull.London Math. Soc. 20 (1988) 160-161 with the permission of the LMS.

The Restricted Ordinal Theorem

Given a positive integer n, another integer Px(n) can be constructed as follows.
Write n in radix form with base x (x > 1), that is
n=akxk+ak-1xk-1+⋯+a0 ,
where 0 ai < x for i=0,...,k. Further, write each exponent of x in this expresion in radix form with base x, and continue this process until all exponents, exponents of exponents, etc., are in radix form. Now define a new integer Px(n) by subtracting 1 and replacing each occurrence of x in this radix form by x+1.
So, for example, if n=529 and x=2 then
529=29+24+1=223+1+222+1=222+1+1+222+1,
and P2(529)=333+1+1+333 ≈ 1.33x1039.

The sequence n, Px(n), Px+1(Px(n)), Px+2(Px+1(Px(n))),… is now called a Goodstein sequence. The restricted ordinal theorem states that for all positive integers n and bases x, the Goodstein sequence

n, Px(n), Px+1(Px(n)), Px+2(Px+1(Px(n))),…

terminates with zero in a finite number of steps. This result is a number theoretic analogue of the fact that all strictly decreasing sequences of transfinite ordinal are finite. Goodstein gave a proof of the restricted ordinal theorem (see [26]) using transfinite induction.

The importance of this result only became apparent in 1982 when Kirby and Paris (see <3>) showed that it provided a straightforward number theoretic property which is not provable in first order arithmetic.

REFERENCES

[26]. R.L. Goodstein, On the restricted ordinal theorem, J. Symbolic Logic 9 (1944) 33-41.
<3>. L. Kirby and J. Paris, Accessible independence results in Peano arithmetic, Bull. London Math. Soc. 14 (1982) 285-93.

Also see the bc program of John Tromp.

Last modified 10th January 2005