Shadows of infinity cast over the finite realm

We shall fight the fearsome Hydra and in defeating it we shall see how the existence of transfinite numbers can have surprising consequences within the finite realm.

Goodstein sequences

Let us undertake a certain fantastical number process. Begin with any positive number, such as the number 41, and write it in hereditary base 2, which means to write it in base 2 as a sum of powers of 2, but also to write the exponents and iterated exponents in this way. We denote this initial number by a₂, in part to indicate this initial choice of base.

\( a_2 \quad = \quad 41 \quad = \quad 32 + 8 + 1 \quad = \quad 2^5 + 2^3 + 1\quad = \quad 2^{2^2 + 1} + 2^{2 + 1} + 1. \)

We form the next number a₃ simply by replacing all the 2s in this representation with 3s and subtracting 1, writing the result in hereditary base 3.

\( a_3 \quad = \quad 3^{3^3 + 1} + 3^{3 + 1} + 1 - 1 \quad = \quad 3^{3^3 + 1} + 3^{3 + 1}. \)

This number a₃ is 22876792455042 in decimal, or about 2 · 10¹³, which is much larger than our original number 41.

The succeeding number a₄ is formed similarly by replacing all 3s with 4s and subtracting 1.

\( a_4 \quad = \quad 4^{4^4 + 1} + 4^{4 + 1} - 1 \quad = \quad 4^{4^4 + 1} + 3· 4^4 + 3· 4^3 + 3· 4^2 + 3· 4 + 3. \)

In decimal notation, a₄ is the number:

\({\tiny 53631231719770388398296099992823384509917463282369573510894245774887056120294187907207497192667613710760127432745944203415015531247786279785734596024337407} \)

which is about 5· 10¹⁵⁵, a big step up from a₃.

We form a₅ similarly by replacing 4s with 5s in the hereditary base 4 representation and subtracting 1, and so on. Starting from any given initial value a₂, we generate in this way a sequence

\( a_2\quad a_3\quad a_4\quad a_5\quad···\)

This is known as a Goodstein sequence in light of the remarkable theorem about them proved by Reuben Goodstein in 1944. The amazing fact is that for any natural number starting value a₂, if we form the corresponding Goodstein sequence according to the process we have described, then at some point n the value will become zero a_n = 0.

What?! It had seemed that the sequence would always grow larger, with each next value a_n+1 much bigger than the previous value a_n. How can we reach a_n = 0? Won't a_n+1 always be larger than a_n? Actually, no. According to Goodstein's theorem, the initial impression that the numbers grow ever larger is simply mistaken. Eventually, the numbers start getting smaller and they will eventually reach 0.

Let me explain.