Goodstein's theorem can be proved (using techniques outside Peano arithmetic, see below) as follows: Given a Goodstein sequence G_m, we construct a parallel sequence P_m of
ordinal numbers in
Cantor normal form that is strictly decreasing and terminates. A common misunderstanding of this proof is to believe that G_m goes to 0
because it is dominated by P_m. Actually, the fact that P_m dominates G_m plays no role at all. The important point is: G_m(k) exists if and only if P_m(k) exists (parallelism), and comparison between two members of G_m is preserved when comparing corresponding entries of P_m. Then if P_m terminates, so does G_m. By
infinite regress, G_m must reach 0, which guarantees termination. We define a function f=f(u,k) that computes the hereditary base k representation of u and then replaces each occurrence of the base k with the first infinite
ordinal number \omega. For example, f(100,3)=f(3^{3^1+1}+2\cdot3^2+1,3)=\omega^{\omega^1+1} + \omega^2\cdot2 + 1 = \omega^{\omega+1} + \omega^2\cdot2 + 1. Each term P_m(n) of the sequence P_m is then defined as f(G_m(n),n+1). For example, G_3(1) = 3 = 2^1 + 2^0 and P_3(1) = f(2^1 + 2^0,2) = \omega^1 + \omega^0 = \omega + 1. Addition, multiplication and exponentiation of ordinal numbers are well defined. We claim that f(G_m(n),n+1) > f(G_m(n+1),n+2): Let G'_m(n) be G_m(n) after applying the first,
base-changing operation in generating the next element of the Goodstein sequence, but before the second
minus 1 operation in this generation. Observe that G_m(n+1)= G'_m(n)-1. Then f(G_m(n),n+1) = f(G'_m(n),n+2). Now we apply the
minus 1 operation, and f(G'_m(n),n+2) > f(G_m(n+1),n+2), as G'_m(n) = G_m(n+1)+1. For example, G_4(1)=2^2 and G_4(2)=2\cdot 3^2 + 2\cdot 3+2, so f(2^2,2)=\omega^\omega and f(2\cdot 3^2 + 2\cdot 3+2,3)= \omega^2\cdot2+\omega\cdot2+2, which is strictly smaller. Note that in order to calculate f(G_m(n),n+1), we first need to write G_m(n) in hereditary base n+1 notation, as for instance the expression \omega^\omega-1 is not an ordinal. Thus the sequence P_m is strictly decreasing. As the standard order P_m(n) is calculated directly from G_m(n). Hence the sequence G_m must terminate as well, meaning that it must reach 0. While this proof of Goodstein's theorem is fairly easy, the
Kirby–Paris theorem, which shows that Goodstein's theorem is not a theorem of Peano arithmetic, is technical and considerably more difficult. It makes use of
countable nonstandard models of Peano arithmetic.
Extended Goodstein's theorem The above proof still works if the definition of the Goodstein sequence is changed so that the base-changing operation replaces each occurrence of the base b with b+2 instead of b+1. More generally, let b_1, b_2, b_3, \ldots be any non-decreasing sequence of integers with b_1 \geq 2. Then let the (n+1)st term G_m(n+1) of the extended Goodstein sequence of m be as follows: • Take the hereditary base b_n representation of G_m(n). • Replace each occurrence of the base b_n with b_{n+1}. • Subtract one. A simple modification of the above proof shows that this sequence still terminates. For example, if b_n = 4 and if b_{n+1} = 9, then f(3 \cdot 4^{4^4} + 4, 4) = 3 \omega^{\omega^\omega} + \omega= f(3 \cdot 9^{9^9} + 9, 9), hence the ordinal f(3 \cdot 4^{4^4} + 4, 4) is strictly greater than the ordinal f\big((3 \cdot 9^{9^9} + 9) - 1, 9\big). The extended version is in fact the one considered in Goodstein's original paper, where Goodstein proved that it is equivalent to the restricted ordinal theorem (i.e. the claim that
transfinite induction below
ε0 is valid), and gave a
finitist proof for the case where m \le b_1^{b_1^{b_1}} (equivalent to transfinite induction up to \omega^{\omega^\omega}). The extended Goodstein's theorem without any restriction on the sequence
bn is not formalizable in Peano arithmetic (PA), since such an arbitrary infinite sequence cannot be represented in PA. This seems to be what kept Goodstein from claiming back in 1944 that the extended Goodstein's theorem is unprovable in PA due to
Gödel's second incompleteness theorem and Gentzen's proof of the consistency of PA using ε0-induction. However, inspection of Gentzen's proof shows that it only needs the fact that there is no
primitive recursive strictly decreasing infinite sequence of ordinals, so limiting
bn to primitive recursive sequences would have allowed Goodstein to prove an unprovability result. Furthermore, with the relatively elementary technique of the
Grzegorczyk hierarchy, it can be shown that every primitive recursive strictly decreasing infinite sequence of ordinals can be "slowed down" so that it can be transformed to a Goodstein sequence where b_n = n+1, thus giving an alternative proof to the same result Kirby and Paris proved. == Sequence length as a function of the starting value ==