Monday Notes 9–10–18

Goodstein Sequences — An Unprovable Truth of Arithmetic

There is a game you can play with numbers. Unless you are rather bizarrely excited about esoteric sequences of numerals, it probably won’t be a very fun game. However it does exhibit a rather phenomenal property and that’s what I hope to demonstrate in this passage.

Consider the way we write numbers such as 10, or 453, or 928445. We don’t often need to think about why we write numbers this way. But there are are plenty of other ways to express them. Why not use tally marks like ||| for three or ||||||| for seven? Or should we use scientific notation like 2.58e2 for two hundred and fifty eight? Even if there are many ways to express a number, that doesn’t change what the number means. 82 is bigger than 81 no matter how you write it. Because of this, the way we choose to express a number is able to carry its own meaning independent from the number itself. For tally marks, the meaning might just be that we wanted a very fast way to count things without having to think. With scientific notation we usually want to express the degree of accuracy of a measurement or computation. With the numbers in a Goodstein sequence, the way we choose to express each number carries with it a very tricky meaning. Let’s look a little further.

In a Goodstein sequence, we write numbers in recursive base-n notation. Let’s break that down into two parts: recursive and base-n. We’ll discuss the latter first.

The numbers we use every day are typically expressed in base-10 notation. We write 123 because 1*10² + 2*10¹ + 3*10⁰ = 123. Notice that we can generalize this pattern. We write a number A as the string of numerals

if we can express A as

We might also notice that there’s nothing particularly special about the number 10. We could choose 2, or 16, or whichever number we like. This would give a new set of strings for representing numbers in a different base. We call this base-n notation to indicate that the base can be any number you’d like.

Usually we refer to a number just by its string. For instance eighteen could be expressed in base-2 as 10010. For our purposes, we’re going to keep the base explicit by writing 1*2⁴+0*2³+0*2²+1*2¹+0. We will also save some tedium by suppressing the 0 terms; we’d write the above as 1*2⁴+1*2¹.

Now to handle the recursive part. Consider the base-3 representation for two hundred and fifty three, which is 2*3⁵+3²+1. What we’ll notice is that the first exponent is 5, which is not a valid base-3 number. To fix this, we have to rewrite it as 1*3^1+2. So the recursive base-3 notation would be

To make the concept a little more clear, here are some examples of recursive base-n notation:

The key point is that a number in recursive base-n notation cannot have any numerals for numbers larger than n. You can’t have a 6 in recursive base-4, and you can’t have an 11 in recursive base-10.

Now that we understand how to write the numbers, we’re going to learn how to play the game. The game has two steps.

To begin, you are given a number in recursive base-n notation. First, you must replace every instance of n in the representation with (n+1). For example, if the number is in base 5, we need to replace all 5s with 6s. So the following number

would become

Then you subtract 1 and rewrite the whole number in recursive base-(n+1). In our example we get

Now repeat with the number you just computed, and that’s all there is to the game! The winning condition is that you reach 0.

Here are a few facts about this game:

  • You will always win the game.
  • For most starting numbers, the universe will have ended many times over before you even you get close to 0. We’re talking waaaaay bigger than Graham’s number.
  • There is no way to prove the above statements using only the laws of arithmetic.

The first two statements are surprising. The third is astounding. So let’s talk about how one goes about proving a statement that I just told you was unprovable.

The trick to this proof is to realize that recursive base-n notation carries with it a hidden meaning. In fact, this representation was picked specifically because it carries such a meaning.

No Infinite Sequence of Decreasing Ordinal Numbers

In my last Monday Notes, I discussed the concept of ordinal numbers. Ordinal numbers extend the natural numbers up to and beyond infinity while retaining the semantic concept of succession. An important fact about ordinals is the there can be no infinite, decreasing sequence of ordinals. Let’s demonstrate why this is true:

Assume we pick a finite ordinal to start from. Then there are only a finite number of ordinals which are less than our starting point; hence any decreasing sequence is finite.

If we pick ω, then we need to pick a smaller ordinal and the only smaller ordinals are finite. Therefore we reduce the problem the case of picking a finite ordinal. If we pick something like ω² we still can’t pick a smaller number without reducing the exponent. Even if we pick ωᵅ where α is a possibly infinite ordinal, to pick a smaller number we have to replace that exponent with an ordinal which is less than α.

Now that we have some intuition about why there can be no infinite decreasing sequence of ordinals, we can sketch out a proof. The proof necessarily uses transfinite induction (or something logically equivalent).

If the starting ordinal is a successor ordinal, then there are only finitely many smaller ordinals you can choose before reaching a limit ordinal.

If the starting ordinal is a limit ordinal, you must pick a smaller limit ordinal or the n-th successor of a smaller limit ordinal. You may have an infinite number of ordinals which are smaller than your starting ordinal, but in practice you will always pick a strictly smaller limit ordinal or a finite successor of one. Hence there is no infinite decreasing sequence of ordinals. By picking a really big successor, you can make the sequence as long as you like, but you can never make it infinite.

Recursive Base-ω

Now we’ll start to see why we chose recursive base-n for the Goodstein sequences. Consider a new concept, which we will call recursive base-ω ordinal (note that the ordinal is different number, not a representation!). Given a number in recursive base-n notation, there is a corresponding ordinal which is created by replacing every instance of n with ω. Look at the examples below:

So if we have a Goodstein sequence, we can immediately see that there is corresponding sequence of ordinals.

Also note that the ordinals on the right are a strictly decreasing sequence. By No Infinite Sequence of Decreasing Ordinal Numbers, we conclude that such an ordinal sequence must terminate. Since the Goodstein sequence and the ordinal sequence are parallel, we further conclude that the Goodstein sequence must terminate.

And there you have it; a proof that every Goodstein sequence will eventually terminate. But how do we know that there isn’t some proof that doesn’t use ordinal numbers? Why isn’t there some purely-arithmetic proof? The answer lies in the way we proved that there is no infinite decreasing sequence of ordinals. Any proof of that fact requires the use of transfinite induction. And, as Gentzen proved in 1936, transfinite induction can be used to prove the consistency of arithmetic. Godel’s incompleteness proof states that no formal system can prove its own consistency. We therefore conclude that any proof that all Goodstein sequences terminate cannot be proven in the formal language of arithmetic.