Goodstein's sequences and theorem.

Question

I was wondering if anyone would be able to provide me with any textbooks that discuss the Goodstein sequence and the Goodstein theorem and which provide a proof also?
Thanks.

Answer 1

A very nice introduction to this area is

MR0891258(88g:03084). Simpson, Stephen G. Unprovable theorems and fast-growing functions. In Logic and combinatorics (Arcata, Calif., 1985), 359–394, Contemp. Math., 65, Amer. Math. Soc., Providence, RI, 1987.

Simpson describes the paper as inspired by the question of whether there could be "a comprehensive, self-contained discipline of finite combinatorial mathematics". He argues that the incompleteness results he describes (the unprovability of Goodstein's theorem in Peano arithmetic being one example) indicate that the answer is no. The paper is expository and assumes almost no background from logic. For instance, it introduces ordinals and provides many intuitions for several of the results it describes. I think it is a joy to read. I actually really like the collection it appears in. Many of the papers in it (although in general much more technical) deal with similar results (unprovability of Hydra-Hercules games, variants of Kruskal's tree theorem, etc).

One of the results Simpson's presents is Goodstein's, and the paper contains a decent sketch (together with references to papers proving its unprovability in $\mathsf{PA}$).

Specifically on Goodstein's theorem, you may also enjoy reading the paper The termite and the tower by Will Sladek. Will wrote it while an undergraduate student at Caltech, as part of their Mathematical writing course; I served as a mentor through the write-up process. I think the metaphor in the title is a great way of describing Goodstein's theorem.

While Will was working on the paper, I thought it would be nice to include some numbers illustrating how long some Goodstein sequences take to terminate. This ballooned into a short paper of my own,

MR2585906(2011c:03139). Caicedo, Andrés Eduardo. Goodstein's function. Rev. Colombiana Mat. 41 (2007), no. 2, 381–391.

In the paper I present a formula for computing Goodstein's function, the map that to each $n$ assigns the number of steps that it takes the Goodstein sequence starting at $n$ to terminate.

Recall that the sequence is defined as follows: Let $n\ge2$. The base-$n$ expansion of $m\in\mathbb N$ is the unique way of writing $m$ as a sum $\sum_{j=0}^k a_j n^k$ where each $a_j$ is a base-$n$ "digit" (a number in $\{0,1,\dots,n-1\}$. The complete base-$n$ expansion is the result of iterating this representation, by also writing in base $n$ all the exponents $k$ of powers of $n$ in the expansion of $m$, and all the exponents in the expansion of these exponents, and so on.

An example I give in the paper is $m=266$. Its base-$2$ expansion is $266=2^8 + 2^3 + 2^1$. To obtain the complete base-$2$ expansion, we write $8$ as $2^3=2^{2^1+1}$, and $3$ as $2^1+1$, thus $$ 266= 2^{2^{2+1}} + 2^{2+1} + 2 $$ where, for clarity, I am just writing $2$ instead of $2^1$ throughout.

The change of base function $R_n$ assigns to each $m\in\mathbb N$ the result of replacing with $n+1$ each $n$ in the complete base-$n$ expansion of $m$.

For instance, $$ R_2(266)=3^{3^{3+1}}+3^{3+1}+3=443426488243037769948249630619149892887. $$

The Goodstein sequence starting at $m$ is the sequence $(m)_k$ where $(m)_1=m$ and $$(m)_{k+1}=\begin{cases} R_{k+1}((m)_k)-1&\text{if }(m)_k>0,\\0&\text{if }(m)_k=0.\end{cases}$$

That the sequence terminates means that $(m)_k=0$ for some $k$. Goodstein's theorem is the statement that the sequence terminates for any $m$, and Goodstein's function $\mathcal G$ assigns to $m$ the least $k$ such that $(m)_k=0$.

The "tower" in Will's paper refers to the stack of exponentials in the complete base-$n$ representation of a number. The "termite" is the $-1$, the small bit we chip away at each step. The usual proof of Goodstein's theorem replaces at each step $k$ each $k$ in the complete base-$k$ representation of the number with an $\omega$, thus associating to each step in the sequence an ordinal number written in Cantor normal form. What one checks is that these ordinals are decreasing. For example, the sequence for $m=4$ is $(4)_1=4=2^2$, $(4)_2=26=3^3-1=2\cdot 3^2+2\cdot 3+2$, $(4)_3=41=2\cdot 4^2+2\cdot 4+1$, $(4)_4=60=2\cdot 5^2+2\cdot 5$, $(4)_5=83=2\cdot 6^2+6+5$, etc. The associated sequence of ordinals is $$\omega^\omega>2\cdot \omega^2+2\cdot \omega+2>2\cdot\omega^2+2\cdot \omega+1>2\cdot\omega^2+2\cdot \omega>2\cdot\omega^2+\omega+5>\dots$$ The sequence keeps going for a long time indeed, but it eventually reaches zero, with $$ \mathcal G(4)=3\cdot 2^{402653211}-2.$$

The formula I obtain verifies that Goodstein's function $\mathcal G$ is fast growing, in this case meaning that it grows so quickly that given any function $f\!:\mathbb N\to\mathbb N$ provably total in Peano arithmetic, there is a $k$ such that for all $n\ge k$, $\mathcal G(n)>f(n)$.