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

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.

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$.

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