Monthly Archives: July 2011

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:

18
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.