Skip to content

Goodstein’s Theorem

February 9, 2011

Today we have a guest post from Phill Schultz, who is a adjunct associate professor in our school.

Take any positive integer {n} 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, {34=2^{2^2+1}+2}. Now replace each 2 by 3, subtract 1 and write the result in 3–adic form, in this case {3^{3^3+1}+2}, 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 {n_j} is the {j}–adic number constructed from {n} at the {j}th step. Replace each {j} in {n_j} by {\omega}, to get {n_j(\omega)}, a countable ordinal in Cantor Normal Form. The sequence {(n_j(\omega):\, j=2,3,\dots)} of ordinals satisfies {n_j\leq n_j(\omega)} and {n_{j+1}(\omega)<n_j(\omega)}, because of the subtraction of 1 in moving from {n_j} to {n_{j+1}}. But there is no infinite properly descending chain of ordinals, so after finitely many steps, you get {0\leq n_j\leq n_j(\omega)=0}.

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 {n}, the function {j\mapsto n_j} grows rapidly before diminishing to zero exceedingly slowly. For example, Stillwell points out that the least {j} for which {4_j=0} is {3\cdot2^{402653211}-1}.

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 {\omega}”, whereas the proof uses transfinite induction, but only up to a countable ordinal {\varepsilon_0>\omega}. More precisely, {\varepsilon_0} (Cantor’s notation of 1883) is the ordinal that can be described either from above, as the least ordinal {\alpha} such that {\beta<\alpha\Rightarrow \beta^\omega<\alpha}, or from below as {\sup\{\omega_n:\,n<\omega\}} where {\omega_0=\omega} and {\omega_{n+1}=(\omega_n)^\omega}. The significance of {\varepsilon_0} 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 {\varepsilon_0}. Therefore, by Gödel’s Corollary, {\varepsilon_0}–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 {n_j} is replaced by {n_{\lambda(j)}} where {\lambda} is an arbitrary strictly increasing transformation of the natural numbers, the original being {\lambda(n)=n+1}. He shows that iterating this procedure also terminates in finitely many steps at zero, and consequently the generalised Goodstein Theorem is logically equivalent to {\varepsilon_0}–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.

Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: