On why Goodstein sequences should terminate

In this post, I will give an intuition behind the ridiculous theorem that all Goodstein sequences eventually reach zero. I call it ridiculous because the construction of a Goodstein sequence is so strange that it’s surprising anything can be said about it at all, and that it accelerates upwards so quickly it is hard to imagine it ever coming back down. But after a little exploration, we will see what is happening with the structure of the numbers, and be able to picture an algorithm for computing how long it should take to come back down. Of course, the really interesting thing about Goodstein’s theorem is that it is equivalent to the consistency of Peano Arithmetic (and thus PA cannot prove it). I won’t give an intuition for this part, because I don’t fully understand it yet.

To define a Goodstein sequence, we need to define hereditary base-n notation, which I will denote H-n. To write a number is H-n, first write it in base n, and then (recursively) write all the exponents in H-n. So for example, to write 18 in hereditary base 2, we do:

24 + 21
222 + 21
2221 + 21

To generalize to larger bases, we rewrite any exponent that is greater than or equal to the base.

Now we can define a Goodstein sequence starting at n. First, write n in H-2. Now, change all the 2′s to 3′s in that representation, compute the number, subtract 1, and rewrite in H-3. Change all the 3′s to 4′s, compute the number, subtract 1, and rewrite in H-4. Continue forever or until you reach zero.

Let’s do an example. Let G be the Goodstein sequence starting at 4. I will start the sequence at index 2, so that the index in the sequence is the same as the base.

G(2) = 4 = 22
G(3) = 33 - 1 = 27 - 1 = 26 = 2 * 32 + 2 * 31 + 2
G(4) = 2 * 42 + 2 * 41 + 2 - 1 = 32 + 8 + 2 - 1 = 41 = 2 * 42 + 2 * 41 + 1
G(5) = 2 * 52 + 2 * 51 + 1 - 1 = 50 + 10 + 1 - 1 = 60 = 2 * 52 + 2 * 51
G(6) = 2 * 62 + 2 * 61 - 1 = 72 + 12 - 1 = 83 = 2 * 62 + 61 + 5
G(7) = 2 * 72 + 71 + 5 - 1 = 98 + 7 + 5 - 1 = 109 = 2 * 72 + 71 + 4
G(11) = 2 * 112 + 111 - 1 = 242 + 11 - 1 = 252 = 2 * 112 + 10
G(21) = 2 * 212 - 1 = 882 - 1 = 881 = 212 + 20 * 211 + 20
G(41) = 412 + 20 * 411 - 1 = 1681 + 820 - 1 = 2500 = 412 + 19 * 411 + 40

And so on. So the sequence goes 4, 26, 41, 60, 83, 109, … (A056193). Those who have followed this example closely may already be seeing why this sequence will eventually terminate.

Let’s introduce a device to understand what is happening to the structure of these numbers. At each step, most of the H-n structure stays the same, the base is just increasing. So let’s write each step with a symbol, say ω, instead of the increasing variable. We will see what to do with the fringes in a bit. I will be essentially copying the last representation from above. This example would begin:

G(2) = ωω
G(3) = 2 * ω2 + 2 * ω1 + 2
G(4) = 2 * ω2 + 2 * ω1 + 1
G(5) = 2 * ω2 + 2 * ω1
G(6) = 2 * ω2 + ω + 5
G(7) = 2 * ω2 + ω + 4
G(10) = 2 * ω2 + ω
G(11) = 2 * ω2 + 10

Ah! Now the sequence looks much more regular! At each step we are simply subtracting 1, and if there is an ω at the right, we are replacing it with a finite number. The number we replace it with keeps growing with the index of the sequence, but each time it is finite, which “deconstructs” the structure a little bit. So even though the numbers are growing, the structure of the H-n representation will never be more “complex” than it was in the first step. I haven’t defined complex; for the sophisticates, it is the ordering on Cantor normal forms of ordinal notations.

We haven’t yet seen what happens with limits that are more complex than ω. For example, at some point, the G sequence will reach:

G(n) = n2
G(n+1) = (n+1)2 - 1 = n * (n+1) + n

In our ω-notation:

G(n) = ω2
G(n+1) = n * ω + n

And indeed the structure has become a little simpler. I’m struggling to describe it in words, but I hope these examples have demonstrated how this sequence is always “decreasing in structure”, which is really all there is to Goodstein’s theorem.

A few technical notes: The H-2 representation of all possible starting numbers correspond to the Cantor normal forms, which are ordinal notations involving finite exponentiations of ordinals involving ω. So for Goodstein’s theorem to work, we need to know that the Cantor normal forms are indeed well-ordered, which is equivalent to ε0 (the supremum of all the Cantor normal forms; the limit of ω, ωω, ωωω, …) being well-ordered. There is a hint of the deep connection to ε0, I wish I could say more about it.

About these ads

3 thoughts on “On why Goodstein sequences should terminate

  1. The relation between the “number of steps before termination starting from ” function and functions provably total in PA is similar to the relation between the Ackermann function and primitive recursive functions.

    There is an easy, but cheating, way to prove that termination of Goodstein sequences implies consistency of PA: assuming termination of sequences gives you well-ordering of ε₀, and from there you can use a standard proof of PA consistency (Gentzen-Buchholz-Takeuti) that assumes well-ordering of ε₀.

    The more serious proofs are indeed hard to understand, and I only have a limited understanding of them. The argument is, like for Ackermann, that it “grows too fast”, but the proofs I know make use of delicate model theoretic techniques. The big picture goes as follows. First you relate the goodstein function to well-known ordinal sequences such as Hardy’s hierarchy H_α, which are more regular and nicer to manipulate, but grow approximatively as fast. Then you show, and this is the most difficult part of the proof that I’m just hand-waving, that they grow fast enough that you can in some sense “embed” partial models of PA in intervals of the form [0..H_α(x)]. This gives you the usual self-contradicting techniques to show that they are not provably total in PA – otherwise PA could represent models of itself, and that any PA-provably total function grows less fast.

    For more references, see the historic proof of Kirby and Paris, the work on ordinal recursive functions by Wainer, and later reformulation work by Cichon.

  2. If you are given that every provably recursive function of PA is dominated by some H_a with a < epsilon_0 (here H is the Hardy hierarchy), then to prove that Goodstein's theorem is unprovable in PA, it suffices to prove that the function G(n), where G(n) is the number of steps it takes to reach zero starting from n, is not dominated by any H_a with a < epsilon_0.

    It's not hard to prove that

    G(n) = H_O(n,2) (3) – 3

    where O(n,b) is the ordinal you get when you write n in hereditary base-b notation, then replace b with omega. Thus G(n) dominates H_a for every a < epsilon_0, and Goodstein's theorem is unprovable in PA.

  3. Recommending the book:

    Roads to Infinity: The Mathematics of Truth and Proof
    John C. Stillwell

    Winner of a CHOICE Outstanding Academic Title Award for 2011.

    This book offers an introduction to modern ideas about infinity and their implications for mathematics. It unifies ideas from set theory and mathematical logic, and traces their effects on mainstream mathematical topics of today, such as number theory and combinatorics. The treatment is historical and partly informal, but with due attention to the subtleties of the subject.

    Ideas are shown to evolve from natural mathematical questions about the nature of infinity and the nature of proof, set against a background of broader questions and developments in mathematics. A particular aim of the book is to acknowledge some important but neglected figures in the history of infinity, such as Post and Gentzen, alongside the recognized giants Cantor and Gödel.

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