Back to . . . .

Curve Bank Home
 

The Students of CS 390
CSU Logo

NCB Deposit  # 34

NCB logo
Goodstein's Theorem

. . . . with notes on its "proof."

An interactive Java sequence that always converges to zero.

Goodstein
R. L. Goodstein
Instructions:

Pick a number - a positive integer - expressed in simple base notation.
Then repeatedly - recursively - perform the following two operations:

  • Subtract one from the number.
  • Increment the base. 
  • What will happen?  The answer is the number eventually converges to 0.  Most people incorrectly guess the sequence goes to infinity. Let's begin by studying this recursion in simple base notation.

    For  number = 4  and  base = 2,

    Start. 

    [1, 0, 0] (base 2) = 4 

    [1, 1] (base 3) = 4 
    Completed 1 iteration. 

    [1, 0] (base 4) = 4 
    Completed 2 iterations. 

    [3] (base 5) = 3 
    Completed 3 iterations.

    [2] (base 6) = 2 
    Completed 4 iterations. 

    [1] (base 7) = 1 
    Completed 5 iterations. 

    [0] (base 8) = 0 
    Completed 6 iterations.

    For  number = 3  and  base = 2,

    Start. 

    [1, 1] (base 2) = 3 

    [1, 0] (base 3) = 3 
    Completed 1 iteration. 

    [2] (base 4) = 2 
    Completed 2 iterations. 

    [1] (base 5) = 1 
    Completed 3 iterations. 

    [0] (base 6) = 0 
    Completed 4 iterations.

    For  number = 5  and  base = 3,

    Start. 

    [1, 2] (base 3) = 5 

    [1, 1] (base 4) = 5 
    Completed 1 iteration. 

    [1, 0] (base 5) = 5 
    Completed 2 iterations. 

    [4] (base 6) = 4 
    Completed 3 iterations. 

    [3] (base 7) = 3 
    Completed 4 iterations. 

    [2] (base 8) = 2 
    Completed 5 iterations. 

    [1] (base 9) = 1 
    Completed 6 iterations. 

    [0] (base 10) = 0 
    Completed 7 iterations. 
     

    For  number = 10  and  base = 8,

    Start. 

    [1, 2] (base 8) = 10 
    [1, 1] (base 9) = 10 
    Completed 1 iteration. 
    [1, 0] (base 10) = 10 
    Completed 2 iterations. 
    [9] (base 11) = 9 
    Completed 3 iterations. 
    [8] (base 12) = 8 
    Completed 4 iterations. 
    [7] (base 13) = 7 
    Completed 5 iterations. 
    [6] (base 14) = 6 
    Completed 6 iterations. 
    [5] (base 15) = 5 
    Completed 7 iterations. 
    [4] (base 16) = 4 
    Completed 8 iterations. 
    [3] (base 17) = 3
    Completed 9 iterations. 
    [2] (base 18) = 2 
    Completed 10 iterations. 
    [1] (base 19) = 1 
    Completed 11 iterations. 
    [0] (base 20) = 0 
    Completed 12 iterations.


    Now that you have examined simple base notation, you are ready to tackle Goodstein's Sequence, which uses hereditary base notation.  Amazingly, Goodstein's Sequence also converges to 0!

    Equation

    If base two is recursively incremented to base three, the right side of the expression becomes

    Equation

    The Goodstein Sequence is therefore

    Equation

    The following applet is written in the Goodstein hereditary base notation. Enter a number, its base, and then select "Start." If you select a number greater than 3 base two, the recursion can take a long time to converge and requires your computer to have sizable memory. [Note: We suggest you begin with 3 base two; and then try 4 base three. After these two examples that converge quickly, try other larger numbers. Please observe that if the base is larger than the number, the sequence converges quickly. Even numbers as small as 4 base two can increase for approximately 2.6 × 1060605351 steps.]


      If you enjoy writing applets, please be sure to look at the source code.

    For the more advanced student. . . .
    On Proof and Goodstein's Theorem
    Goodstein's Theorem

    Goodstein's statement about natural numbers cannot be proved using only Peano's arithmetic and axioms. Goodstein's Theorem is proved in the stronger axiomatic system of set theory by applying Gödel's Incompleteness Theorem.

    The Incompleteness Theorem asserts that powerful formal systems will always be incomplete.  That is to say, there will exist true statements that the system cannot prove nor disprove. Gödel's Incompleteness Theorem assures us that we must believe Goodstein's theorem even if it cannot be proved by mathematical induction. 

    The crucial insight for Goodstein's sequence is that the iterations are  well-ordered.  In our examples, note that the order of the iteration counted backwards, always goes to zero.

    Interestingly, the Goodstein sequence is unique in that it may calculate large numbers before the size of the base forces the sequence to converge to zero.  The calculation for larger numbers reaches a point where the computer may be unable to continue.  Many personal  computers will simply cease the calculation.
     


    References

    Goodstein, R. L. "On the Restricted Ordinal Theorem." J. Symb. Logic 9, 33-41, 1944.

    Henle, J. M. An Outline of Set Theory, Springer-Verlag, 45 - 48, 1986.

    For On-line seminar notes:
    < http://www2.maths.bris.ac.uk/~maadb/research/seminars/online/fgfut/ >

    "Although no naturally occurring dynamical systems are known to exhibit the behavior of a Goodstein Sequence, the Goodstein dynamical system is of interest because its properties greatly differ from the common strange-attractor systems."                           Justin T. Miller, University of Arizona 
    http://www.u.arizona.edu/~miller/thesis/node3.html

    For examples of a Goodstein Sequence in hereditary notation
    equations
    http://en2.wikipedia.org/wiki/Goodstein's_theorem

    For students interested in mathematical proof: 
    http://astronomy.swin.edu.au/~pbourke/analysis/goodstein/


    For an encyclopedia of integer sequences:
    http://www.research.att.com/~njas/sequences
    Comment on set theory

    Related
    Topics

    • Hereditary Sequences
    • Peano's axioms and arithmetic
    • Gödel's Incompleteness Theorem 
    • "Well-ordered" in proof

    R
    euben Goodstein (1912 - 1985)

    was a student of Littlewood's at Cambridge.
    See "Hardy and Littlewood."
       

    Java logo
    Warning:

    This animation requires a download.  Your computer must have the Java 2 plug-in of at least version 1.4.

    Java Software
    • If you do not have the free Java software, go to http://www.java.com/ and click on "Get It Now."  Follow the on-screen instructions to download and install all components. The Java installation will take several minutes.
    February 26, 2004 

    Home button
    Dr. Russell Abbott
    Matthew Nelson, FITSC Lab, CSULA