Big Numbers

Tavian Barnes Comments

Take a number, say, 264, and write it in binary:

264=28+23.264 = 2^8 + 2^3.

Because we like binary so much, write the exponents in binary too:

264=223+22+1=222+1+22+1\begin{aligned} 264 &= 2^{2^3} + 2^{2 + 1} \\ &= 2^{2^{2 + 1}} + 2^{2 + 1} \end{aligned}

and so on, until every number is 2 or less. This is the hereditary base-2 representation of 264. Now, transform that number by increasing the base from 2 to 3, and subtracting one:

G2(264)=333+1+33+11=333+1+233+232+23+24.41038.\begin{aligned} G_2(264) &= 3^{3^{3 + 1}} + 3^{3 + 1} - 1 \\ &= 3^{3^{3 + 1}} + 2 \cdot 3^3 + 2 \cdot 3^2 + 2 \cdot 3 + 2 \\ &\approx 4.4 \cdot 10^{38}. \end{aligned}

And again:

G3(G2(264))=444+1+244+242+24+23.210616.\begin{aligned} G_3(G_2(264)) &= 4^{4^{4 + 1}} + 2 \cdot 4^4 + 2 \cdot 4^2 + 2 \cdot 4 + 2 \\ &\approx 3.2 \cdot 10^{616}. \end{aligned}

Goodstein sequences are defined by these repeated applications of GnG_n. The Goodstein sequence starting at mm is m1=mm_1 = m, m2=G2(m1)m_2 = G_2(m_1), m3=G3(m2)m_3 = G_3(m_2), etc.

Goodstein's theorem

Goodstein's theorem states that every Goodstein sequence eventually reaches zero. Despite the deceivingly explosive initial increase (the next value for m=264m = 264 above is m42.51010921m_4 \approx 2.5 \cdot 10^{10921}), the surprising truth is that for all initial values of mm, mk=0m_k = 0 for some finite kk.

This counterintuitive theorem is actually fairly easy to prove. We simply find an upper bound on the base bb used in the hereditary base-bb representations in the sequence. Finding the upper bound is actually the easiest part:

b<b < \infty

"But wait," you say, "that's obvious and unhelpful!" Well, by using a particular kind of infinity, this upper bound becomes useful. Precisely, we use ω\omega, the first transfinite ordinal number. For m=264m = 264 as before, the bounds look like this:

m1=222+1+22+1ωωω+1+ωω+1m2=333+1+233+232+23+2ωωω+1+ωω2+ω22+ω2+2m3=444+1+244+242+24+1ωωω+1+ωω2+ω22+ω2+1m4=555+1+255+252+25ωωω+1+ωω2+ω22+ω2m5=666+1+266+262+6+5ωωω+1+ωω2+ω22+ω+5m6=777+1+277+272+7+4ωωω+1+ωω2+ω22+ω+4\begin{array}{cclcl} m_1 & = & 2^{2^{2 + 1}} + 2^{2 + 1} & \le & \omega^{\omega^{\omega + 1}} + \omega^{\omega + 1} \\ m_2 & = & 3^{3^{3 + 1}} + 2 \cdot 3^3 + 2 \cdot 3^2 + 2 \cdot 3 + 2 & \le & \omega^{\omega^{\omega + 1}} + \omega^\omega \cdot 2 + \omega^2 \cdot 2 + \omega \cdot 2 + 2 \\ m_3 & = & 4^{4^{4 + 1}} + 2 \cdot 4^4 + 2 \cdot 4^2 + 2 \cdot 4 + 1 & \le & \omega^{\omega^{\omega + 1}} + \omega^\omega \cdot 2 + \omega^2 \cdot 2 + \omega \cdot 2 + 1 \\ m_4 & = & 5^{5^{5 + 1}} + 2 \cdot 5^5 + 2 \cdot 5^2 + 2 \cdot 5 & \le & \omega^{\omega^{\omega + 1}} + \omega^\omega \cdot 2 + \omega^2 \cdot 2 + \omega \cdot 2 \\ m_5 & = & 6^{6^{6 + 1}} + 2 \cdot 6^6 + 2 \cdot 6^2 + 6 + 5 & \le & \omega^{\omega^{\omega + 1}} + \omega^\omega \cdot 2 + \omega^2 \cdot 2 + \omega + 5 \\ m_6 & = & 7^{7^{7 + 1}} + 2 \cdot 7^7 + 2 \cdot 7^2 + 7 + 4 & \le & \omega^{\omega^{\omega + 1}} + \omega^\omega \cdot 2 + \omega^2 \cdot 2 + \omega + 4 \\ \vdots \end{array}

These upper bounds are well-defined using ordinal arithmetic. They are also strictly decreasing, and since the ordinals are well-ordered, every such strictly-decreasing sequence must reach zero in a finite number of steps. Note that we write ω2\omega \cdot 2 rather than 2ω2 \cdot \omega above because ordinal arithmetic is not commutative; in fact, 2ω=ω<ω22 \cdot \omega = \omega < \omega \cdot 2.

Independence

Despite being a theorem about natural numbers, Goodstein's theorem is independent of the Peano axioms. It's a natural, concrete example of Gödel's incompleteness theorem for those axioms.

Kirby and Paris proved its independence by essentially showing that any proof of Goodstein's theorem requires induction over sets too large for Peano's axioms to handle. They showed that Goodstein's theorem implies Gentzen's theorem.

The Goodstein function

How long are Goodstein sequences? It turns out they are extremely long. Let the Goodstein function G(m)\mathcal{G}(m) be the length of the Goodstein sequence starting at m1=mm_1 = m.

G(12)\mathcal{G}(12) is larger than Graham's number. G(m)\mathcal{G}(m) grows faster than the Ackermann function A(m,m)A(m, m). G(m)\mathcal{G}(m) grows faster than the iterated Ackermann function AA(m,m)(m,m)=A(A(),A())A^{A(m, m)}(m, m) = A(A(\cdots), A(\cdots)). In fact, G(m)\mathcal{G}(m) grows faster than any function that can be proven to be total in Peano arithmetic. That means G(m)\mathcal{G}(m) grows faster than any function that can be shown to even exist by induction over the natural numbers.

References


Comments

Luqman

This is good explanation of ordinals: http://www.sjsu.edu/faculty/watkins/ordinals.htm