Recently I learned about a family of sequences of nonnegative integers (called Goodstein sequences) and two remarkable theorems about these sequences.
Begin with any positive integer . This is the first term in the sequence. For example, suppose we begin with .
The first step in computing the second term of the sequence, , is to write in hereditary base 2 notation. That is, write using only powers of 2 (the base 2 expansion of ): . Then write all of the exponents in their base 2 expansions. Then write all of the exponents of the exponents in that way, etc. Our number written in hereditary base 2 notation is .
To obtain we change all of the 2′s to 3′s, then subtract 1. For our example, . Notice that is very large number; it is approximately
We continue in the same way. We obtain from by writing in hereditary base notation, changing all of the ‘s to ‘s, and subtracting 1.
To obtain we must express in hereditary base 6 notation. First notice that
(An easy way to see this is that written in base 6, is , 1 followed by zeros. So is , fives.) But this expansion of is not in hereditary base 6 notation yet. We must express the towers of exponents in base 6, etc. When that is done, we replace the 6′s with 7′s and subtract 1. In the end, is a gigantic number.
Now here are two amazing theorems about this sequence of integers. In 1944 Reuben Goodstein proved:
Theorem. There is a such that .
That is, this sequence, which looks like it is rocketing to infinity, will eventually become zero and terminate. Wow! The proof of this theorem is very sophisticated and uses the theory of ordinal numbers.
I’ll have to file this sequence away as an example that shows why we can’t use the behavior of the first few (or first few million) terms of a sequence to determine the limiting behavior of a sequence.
Then, in 1982 Laurie Kirby and Jeff Paris proved the following theorem.
Theorem. Goodstein’s Theorem is not provable using the Peano axioms of arithmetic.
In other words, this is exactly the type of theorem described in 1931 by Gödel’s first incompleteness theorem!
Recall what Gödel’s theorem says. If there is an axiomatic that is rich enough to express all elementary arithmetic (such as that formed from the Peano axioms), then it must be incomplete. In other words, there must be a true statement about arithmetic that cannot be proven from the axioms. In his proof Gödel produces an explicit example of a true, but unprovable statement. But it is complicated to grasp and more reminiscent of a logical paradox than a mathematical statement.
The first nice mathematical example of such a statement was presented in 1977 by Paris and Harrington (in a field called Ramsey theory). Then in 1982 Kirby and Paris proved that Goodstein’s theorem was unprovable and they gave another elementary example, called “Hercules versus the hydra,” which relates to the growth of the hydra (a tree) and its destruction by Hercules.