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

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

2010-08-13T19:22:06Z

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!

Answer by Tracy Hall for How fast can the base-bumping function in Goodstein's theorem grow?

2010-08-13T20:00:02Z

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.

Answer by Joel David Hamkins for How fast can the base-bumping function in Goodstein's theorem grow?

2010-08-13T20:02:17Z

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

Answer by Bill Dubuque for How fast can the base-bumping function in Goodstein's theorem grow?

2010-08-13T22:05:31Z

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?
http://groups.google.com/groups?selm=WGD.95Dec11023450@martigny.ai.mit.edu

Answer by Andreas Weiermann for How fast can the base-bumping function in Goodstein's theorem grow?

2011-05-30T14:16:01Z

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