Proving Goodstein's Theorem and Transfinite Methods

This is the third part of a post series on Goodstein's theorem. For the first part, see here.

The previous post introduced the reader to Peano arithmetic (PA), the archetypical example of an axiomatic system introduced to standardize the foundations of mathematics. Despite having tremendous expressive power in formulating and proving theorems about natural numbers, the system is not without limitations. Gödel's Incompleteness Theorem guarantees the existence of statements out of the reach of formal proofs in PA. Goodstein's Theorem, which states that every Goodstein sequence terminates at 0, is an example. Further, it is a "natural" example in the sense that it was not contrived to demonstrate incompleteness. In fact, Goodstein proved the theorem in 1944, decades before Laurence Kirby and Jeff Paris discovered that it is independent of the axioms of PA in 1982.

To see why this independence holds, we consider the proof of Goodstein's Theorem. As mentioned, it is not provable in PA, so the proof makes use of tools outside of arithmetic: in particular, infinite ordinal numbers. A more thorough discussion of ordinal numbers may be found elsewhere on this blog. For our purposes, the key property of ordinal numbers is that they represent order types of well-ordered sets.

A well-ordered set is simply a set of elements and an ordering relation (often called "less than" and denoted by "<") such that any two elements are comparable (each is less than, equal to, or greater than) the others, and every subset has a minimal element. The set may be finite or infinite. Here are some examples:

• The set of natural numbers itself, {0,1,2,3,...}, with the relation "less than" is well-ordered because every two elements are comparable and every subset has a smallest number
• The set of natural numbers with the "greater than" relation is not well-ordered: with this relation, "minimal" elements are really largest elements, and the subset {3,4,5,...}, for example, has no greatest element
• The set {A,H,M,R,Z} with the relation "comes before in the alphabet" is well-ordered because we can compare any two letters to see which comes first in the alphabet, and any subset has a first letter
• The set of all integers {...-2,-1,0,1,2,...} is not well-ordered by either less than or greater than relations

The gist of the definition is that all set elements are listed in a particular order so that we can always tell which of a pair comes first, and that infinite ascending sequences are acceptable while decreasing ones are not. To understand order type, we need a notion of when two well-ordered sets are "the same". For example, the set {1,2,3,4,5} with the less than relation and {A,H,M,R,Z} with the alphabet relation are quite similar. Using the one-to-one relabeling 1 → A, 2 → H, 3 → M, 4 → R, 5 → Z, we can move from one set to the another and preserve the ordering relation. That is, 1 < 2 in the first set and their images satisfy A < H in the second set, and so on. If there is a relabeling like the one above between two sets, they are said to be of the same order type.

The purpose of ordinal numbers is to enumerate all possible order types for well-ordered sets; there is one ordinal for each order type. To make thinking about ordinals simpler, we often say that an ordinal is a specific set of the given order type, a particularly nice set. Specifically, we choose the set of all smaller ordinals. Since the sets in the example of the previous paragraph have five elements, their order type is the ordinal 5 = {0,1,2,3,4} (the reader may wish to show that any well-ordered five element set in fact has this order type). In fact, for finite sets, there is simply one ordinal for each size set. For infinite sets, matters become more interesting.

The ordinal corresponding to the order type of the natural numbers is called ω. Using the canonical choice of representative set, ω = {0,1,2,3,...} (where we now view the elements as ordinals). The next ordinal is ω + 1, the order type of {0,1,2,3,...,ω} or in general the order type of a well-ordered set with an infinite ascending collection plus one element defined to be greater than all others. One can go on to define ω + n for any finite n and ω*2, the order type of {0,1,2,3,...,ω,ω + 1,ω + 2,...} (two infinite ascending chains stuck together). The precise details do not concern us here, but ω², ω^ω, ω^ωω, and so on may be defined as well. What matters is that these ordinals exist and that the set of all ordinals expressible with ordinary operations on ω (for example, (ω^ω)*4 + (ω³)*2 + ω*5 + 7) is a well-ordered set. In fact, the set of such ordinals is itself a larger ordinal called ε₀.

Once these preliminaries are established, the proof of Goodstein's Theorem is rather simple, and even clearer when considered intuitively. For any Goodstein sequence, the members are represented in hereditary base-n notation at every step: the first member is put into base 2, the next base 3, and so on. The idea is to take each member of the sequence and replace the base with ω to obtain a sequence of ordinals. For example, the sequence G₄ generates a sequence of ordinals H₄ in the following way:

G₄(1) = 4 = 1*2^1*21 → H₄(1) = ω^ω (the 2's are replaced with ω's),
G₄(2) = 26 = 2*3² + 2*3¹ + 2 → H₄(2) = (ω²)*2 + ω*2 + 2 (3's are replaced with ω's),
G₄(3) = 41 = 2*4² = 2*4¹ + 1 → H₄(3) = (ω²)*2 + ω*2 + 1 (4's are replaced by ω's),
and so on.

Note that the multiplication by coefficients has been moved to the other side of the ω's for technical reasons and that some of the 1's have been removed for clarity. One may precede in this matter to get a sequence of ordinals, the key property of which is that the sequence is strictly decreasing. In the above example, ω^ω > (ω²)*2 + ω*2 + 2 > (ω²)*2 + ω*2 + 1 and this downward trend would continue if we were to list more terms. This is because the H sequences "forget" about the base: it is always replaced by ω. The only change is caused by the subtraction of 1 at each step, which slowly reduces the coefficients. Intuitively, this is the point of the proof: by forgetting about the base, we replace the extreme growth of Goodstein sequences with a gradual decline. The units digit of the H sequence decreases by 1 every step. When it reaches 0, on the next step the ω coefficient is reduced by 1 and the units digit is replaced by the current base minus 1 (the highest allowed coefficient). These may become quite large, but they always reach zero eventually. Reasoning this way, it is clear that Goodstein's Theorem should be true.

In formal terms, the set of ordinals is well-ordered, so the set consisting of all members of an H sequence must have a minimal element, i.e., it cannot decrease forever. The only way that it can stop decreasing is if the G sequence stops, and Goodstein sequences only terminate at 0. Therefore, every Goodstein sequence terminates at 0 after a finite number of steps. We've proved Goodstein's Theorem!

Bringing in infinite ordinals to prove a statement about natural numbers is strange. So strange in fact that the argument is not formalizable in PA; there is simply no way to even define infinite ordinals in this language! This indicates why the given proof does not go through in PA, but does not settle the matter as to whether there is no possible proof of Goodstein's Theorem within PA. It leaves the possibility that there is a different clever approach that can succeed without infinite ordinals. A discussion of why this in fact does not occur may be found in the final post of this series.

Sources: http://www.cs.tau.ac.il/~nachumd/term/Kirbyparis.pdf, http://blog.kleinproject.org/?p=674, http://www.ams.org/journals/proc/1983-087-04/S0002-9939-1983-0687646-0/S0002-9939-1983-0687646-0.pdf