TOPICS
Search

Goodstein Sequence

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

266=2^8+2^3+2
(1)
=2^(2^(2+1))+2^(2+1)+2,
(2)

so bumping the base from 2 to 3 yields

B[2](266)=3^(3^(3+1))+3^(3+1)+3.
(3)

Now repeatedly bump the base and subtract 1,

G_0(266)=266
(4)
=2^(2^(2+1))+2^(2+1)+2
(5)
G_1(266)=B[2](266)-1=3^(3^(3+1))+3^(3+1)+2
(6)
G_2(266)=B[3](G_1)-1=4^(4^(4+1))+4^(4+1)+1
(7)
G_3(266)=B[4](G_2)-1=5^(5^(5+1))+5^(5+1)
(8)
G_4(266)=B[5](G_3)-1=6^(6^(6+1))+6^(6+1)-1
(9)
=6^(6^(6+1))+5·6^6+5·6^5+...+5·6+5
(10)
G_5(266)=B[6](G_4)-1
(11)
=7^(7^(7+1))+5·7^7+5·7^5+...+5·7+4,
(12)

etc.

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

See also

Goodstein's Theorem, Hereditary Representation, Paris-Harrington Theorem

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.Simpson, S. G. "Unprovable Theorems and Fast-Growing Functions." Contemp. Math. 65, 359-394, 1987.

Referenced on Wolfram|Alpha

Goodstein Sequence

Cite this as:

Weisstein, Eric W. "Goodstein Sequence." From MathWorld--A Wolfram Web Resource. https://mathworld.wolfram.com/GoodsteinSequence.html

Subject classifications