Today we have a guest post from Phill Schultz, who is a adjunct associate professor in our school.
Take any positive integer and express it in complete 2–adic form, i.e. as a sum of powers of 2 in which the powers themselves are also in complete 2–adic form. For example, . Now replace each 2 by 3, subtract 1 and write the result in 3–adic form, in this case , an integer with 39 digits. Repeat the procedure, replacing 3 by 4 and so on. Although the numbers you get seem to increase rapidly, Goodstein’s Theorem states that after finitely many steps, you reach zero.
This remarkable result, proved by Reuben Goodstein in 1944, has an even more remarkable proof. Suppose is the –adic number constructed from at the th step. Replace each in by , to get , a countable ordinal in Cantor Normal Form. The sequence of ordinals satisfies and , because of the subtraction of 1 in moving from to . But there is no infinite properly descending chain of ordinals, so after finitely many steps, you get .
My interest in Goodstein’s Theorem was sparked by John Stillwell’s new book Roads to Infinity, published in 2010 by A. K. Peters, Ltd. In it, Stillwell points out the connection between the purely arithmetical Goodstein’s Theorem and questions of truth and provability in Logic.
The proof above of Goodstein’s Theorem has some remarkable features. First, note that for each positive integer , the function grows rapidly before diminishing to zero exceedingly slowly. For example, Stillwell points out that the least for which is .
Second, note that although the hypotheses and conclusion can be expressed in the first order language of Peano Arithmetic (PA), this proof cannot. This is because PA only allows finite induction, i.e., “induction up to ”, whereas the proof uses transfinite induction, but only up to a countable ordinal . More precisely, (Cantor’s notation of 1883) is the ordinal that can be described either from above, as the least ordinal such that , or from below as where and . The significance of relates to Gödel’s Incompleteness Theorem (1936), which states that in any consistent formal theory in which PA can be formulated, there are unprovable true statements. A corollary, which I call Gödel’s Corollary, is that no such theory contains a proof of its own consistency. Also in 1936, Gerhard Gentzen proved that PA is consistent by using induction up to . Therefore, by Gödel’s Corollary, –induction cannot be a valid proof method in PA.
We have seen that Goodstein’s Theorem can be expressed as a statement in PA which is true because it has a proof in a subset of ZF Set Theory which is consistent and sound, i.e., every provable statement is true. Hence in order to show that Goodstein’s Theorem is a minimal example of Gödel’s Incompleteness Theorem, it remains to show that it is unprovable in PA.
This is the crux of Stillwell’s presentation. His method is to show that the Goodstein process can be extended to a more general procedure in which is replaced by where is an arbitrary strictly increasing transformation of the natural numbers, the original being . He shows that iterating this procedure also terminates in finitely many steps at zero, and consequently the generalised Goodstein Theorem is logically equivalent to –induction. Hence its provability within PA would contradict Gödel’s Corollary.
There are several known exemplars of Gödel’s Theorem within Combinatorics, such as the Paris–Harrington Theorem and the Graph Minor Theorem, but none as transparent as Goodstein’s Theorem.