# How fast can the base-bumping function in Goodstein's theorem grow?

In the usual presentation of Goodstein's theorem, the base is bumped up by the "add 1" function. Does the theorem still hold when we replace this function by a fast-growing one (e.g. Ackermann or busy beaver)? How far can we push this? For example, let's define $g_0(n)$ to be the number of Goodstein iterations needed to reach 0 when we start with base 2 and seed $n$ (so that $g_0(0)$ = 0). Then we can build a hierarchy of functions by defining $g_{k+1}(n)$ as the number of Goodstein iterations needed to reach 0 with seed $n$ and base-bumping function $g_k$ ($k$ = 0, 1, ...), continuing through the ordinals by diagonalization at each limit ordinal. Surely it's got to break down when we go past $\epsilon\_0$, if not long before that!

-

As long as your fast-growing "base-bumping" function still takes every natural number to a natural number (instead of, say, an infinite ordinal)--and the busy beavers do--the Goodstein iterations are still upper-bounded by the strictly-decreasing sequence of ordinals in "base" $\omega$, which must be of finite length as a decreasing sequence in a well-ordered set.

-
@Tracy: Thank you for your compendious answer, from which I conclude that defining $g_\kappa$ as in the question is unproblematic as long as $\kappa$-induction is permissible, at least for countable ordinals $\kappa$. –  John Bentin Aug 14 '10 at 15:55

First, let me say that this is a really great question.

It seems to me that any increasing base-bumping function would give the same Goodstein result that you eventually hit $0$. That is, I claim that for any increasing sequence of bases $b_1$, $b_2$ and so on, if we define the Goodstein sequence by starting with any number $a_1$, and then if $a_n$ is defined, we write it in complete base $b_n$, replace all instances of $b_n$ with $b_{n+1}$, subtract $1$, and call the answer $a_{n+1}$. The theorem would be that at some point $n$ in the construction, we have $a_n=0$.

The proof of the original theorem proceeded by associating any number $a$ in complete base $b$ with the countable ordinal obtained by replacing all instances of $b$ with the ordinal $\omega$ and interpreting the resulting expression in ordinal arithmetic. They key fact is that the ordinal associated with $a$ in base $b$ is strictly larger than the ordinal associated in base $b+1$ with the number obtained by replacing all $b$'s with $b+1$'s and subtracting $1$. If we replace $b$ with some larger $b'$ and do the same thing, then it appears that this key fact still goes through, since it was proved by observing what happens when the subtract-$1$ part causes a complex term to be broken up with coefficients below the new base. Thus, the newly associated ordinals would still be descending, so they must hit $0$, but this happens only if the numbers themselves hit $0$.

-
If I remember correctly, Goodstein proved the theorem for an arbitrary base-bumping function. The reason people often present just the case of "add 1 to the base" is that already this relatively weak case is unprovable by finite combinatorial methods. (By "finite combinatorial methods" I mean ZFC with the axiom of infinity replaced by its negation; this theory is known to be equivalent, via coding, to Peano arithmetic.) –  Andreas Blass Aug 13 '10 at 20:37
@Joel: Thank you for the encouragement. That Goodstein's theorem (GT) holds for any base-bumping function gives it awesome power. (I don't think that the function has to be increasing---not that it makes much difference.) Thus it seems that we have $2^\aleph_0$ base-bumpers to choose from, each corresponding to a particular version of GT. –  John Bentin Aug 15 '10 at 6:02
You can't allow an arbitrary base-bumping sequence. For example, if your bases are 2, 4, 2, 4, ... and you start with $a=2$, then the Goodstein sequence will be periodic 2, 3, 2, 3,..., and never hit 0. The Goodstein proof uses that the bases are non-decreasing when it shows that the associated ordinals descend, because you need to know that none of the old coefficients (below the base) are absorbed into the new (smaller) base. –  Joel David Hamkins Aug 15 '10 at 9:59
@Joel: Thanks for the correction. I think I'll refrain from off-the-cuff remarks (and attempts at LaTeX) in comments in future. –  John Bentin Aug 15 '10 at 15:39

Dear all,

let me give the following remark:

"Goodstein actually employed arbitrary increasing base-bumping functions. He showed that the convergence of all such is equivalent to transfinite induction below ϵ0."

This statement has to be taken with care when it comes to weakly increasing base bumping functions. When we reach functions in the neighboorhood of log* then the Goodsteinprocess becomes provable in PRA.

But when we take a fixed iterate of log then of course termination of Goodstein sequences is equivalent to the 1 consistency of PA.

If the base bumping function growth faster than H_epsilon_0 then Goodstein can of course yield more than the 1 consistency of PA.

Best, Andreas

-
Welcome to MO, Andreas! –  Emil Jeřábek May 30 '11 at 14:32

Goodstein actually employed arbitrary increasing base-bumping functions. He showed that the convergence of all such is equivalent to transfinite induction below $\epsilon_0$. This is illustrated somewhat more graphically by the Hercules vs. Hydra game. See the references from my old post [1] of 1995 which helped serve to popularize these topics on (use)net. Curiously that post received far more feedback than any of my other posts - from popular science writers to researchers, teachers and students.

[1] Bill Dubuque, sci.math, Dec 11, 1995. Goedel's theorem: about anything in real world?