A Sequence That Always Dies, But You Can't Prove It

Start with the number 4. Write it in base 2, but recursively: 4 is 2 squared, and the exponent 2 is itself 2 to the 1, so you write 4 as 2^(2^1). Now bump every base from 2 to 3, getting 3^(3^1) = 27, then subtract 1, leaving 26. Bump every 3 to a 4. Subtract 1. Repeat forever, or until you hit zero.

This is a Goodstein sequence, and at first it does what you'd expect: the numbers shoot up. Starting from 4, the sequence climbs past 26, then past a googol, then past a googolplex, and keeps going. It peaks at a value larger than 3 times 2 to the 402,653,210 — a number with roughly 121 million digits. Then, somehow, it starts coming down. After about 3 times 2 to the 402,653,211 steps, it reaches zero.

Reuben Goodstein proved in 1944 that every such sequence, starting from any natural number, eventually terminates. The trick is to replace each base in the expression with the ordinal omega and watch what happens. The natural-number sequence keeps growing, but the parallel ordinal sequence — living up in the transfinite, where you can subtract 1 from omega and get a smaller ordinal — strictly decreases. Any decreasing sequence of ordinals below epsilon-zero must hit zero in finite time, so the natural sequence does too.

The move that makes the proof work is exactly the move Peano arithmetic, the standard formalization of natural-number reasoning, cannot make. In 1982, Laurence Kirby and Jeff Paris showed that Goodstein's theorem is unprovable from the Peano axioms. It is true about the natural numbers, you can verify it for small starting values by computer, and yet inside the system that's supposed to describe arithmetic, no proof exists. To know why your sequence terminates, you have to leave the naturals and reach for the ordinals.