display | more...

We claim (or rather, Goodstein does) that every Goodstein's sequence eventually reaches 0. This cannot be proved in arithmetic (see Goodstein's theorem), so we'll be using something a good bit stronger: Set Theory. Specifically, we'll be using (countable) ordinal numbers.

Recall how we construct a Goodstein's sequence. For example, we'll start from 19 with base 2. 19 = 222+0 + 220 + 20 + 0, so g2(19) = 333+0 + 330 + 30 - 1 = 333+0 + 330 + 0 (which is a paltry 7625597484990, but it doesn't matter).

Let's grab just the shape of the base-b representation of each number; instead of writing b, we'll write ω. Then the first shape (allowing ourselves now to use 1 = ω0, and omitting 0's) is ωωω + ω1 + 1. Bumping the base (from 2 to 3) does nothing to the shape; on the other hand, subtracting 1 changes it to ωωω + ω1. It's "obvious" (in the sense of being straightforward to show) that the sequence of shapes is decreasing (it's trivial that a shape of the form ... + k with k>0 a natural number just changes to ... + k-1; a small trick is needed to show the same thing happens when k=0).

But the ordinal numbers are well ordered. This means that we cannot have an infinite decreasing sequence of ordinals! So at some point we must get the shape "0". No matter what the base b is at that point, the number being represented must be 0, which proves Goodstein's theorem.

We haven't really used the fact that at each step of the way we bumped our base b by 1; in fact, the proof works well if we increase the base at every step by any amount!

The ordinals appearing in this proof are bounded by ε0 (the limit of ω, ωω, ωωω, ...); no smaller bound for the ordinals in the proof exists. Unprovability of the result in arithmetic comes from the fact that it is in fact equivalent to the nonexistence of an infinite decreasing sequence of ordinals below ε0, a statement that is known to be sufficient to prove consistency of arithmetic.

Log in or register to write something here or to contact authors.