How fast can the base-bumping function in Goodstein's theorem grow? - MathOverflow most recent 30 from http://mathoverflow.net 2013-05-20T07:32:37Z http://mathoverflow.net/feeds/question/35524 http://www.creativecommons.org/licenses/by-nc/2.5/rdf http://mathoverflow.net/questions/35524/how-fast-can-the-base-bumping-function-in-goodsteins-theorem-grow How fast can the base-bumping function in Goodstein's theorem grow? John Bentin 2010-08-13T19:22:06Z 2011-05-30T14:16:01Z <p>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! </p> http://mathoverflow.net/questions/35524/how-fast-can-the-base-bumping-function-in-goodsteins-theorem-grow/35535#35535 Answer by Tracy Hall for How fast can the base-bumping function in Goodstein's theorem grow? Tracy Hall 2010-08-13T20:00:02Z 2010-08-13T20:00:02Z <p>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.</p> http://mathoverflow.net/questions/35524/how-fast-can-the-base-bumping-function-in-goodsteins-theorem-grow/35536#35536 Answer by Joel David Hamkins for How fast can the base-bumping function in Goodstein's theorem grow? Joel David Hamkins 2010-08-13T20:02:17Z 2010-08-13T21:10:05Z <p>First, let me say that this is a really great question. </p> <p>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$.</p> <p>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$.</p> http://mathoverflow.net/questions/35524/how-fast-can-the-base-bumping-function-in-goodsteins-theorem-grow/35546#35546 Answer by Bill Dubuque for How fast can the base-bumping function in Goodstein's theorem grow? Bill Dubuque 2010-08-13T22:05:31Z 2010-12-01T02:52:43Z <p>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 <a href="http://groups.google.com/groups?selm=WGD.95Dec11023450@martigny.ai.mit.edu" rel="nofollow">post [1]</a> 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. </p> <p>[1] Bill Dubuque, sci.math, Dec 11, 1995. Goedel's theorem: about anything in real world?<br> <a href="http://groups.google.com/groups?selm=WGD.95Dec11023450@martigny.ai.mit.edu" rel="nofollow">http://groups.google.com/groups?selm=WGD.95Dec11023450@martigny.ai.mit.edu</a></p> http://mathoverflow.net/questions/35524/how-fast-can-the-base-bumping-function-in-goodsteins-theorem-grow/66454#66454 Answer by Andreas Weiermann for How fast can the base-bumping function in Goodstein's theorem grow? Andreas Weiermann 2011-05-30T14:16:01Z 2011-05-30T14:16:01Z <p>Dear all,</p> <p>let me give the following remark:</p> <p>"Goodstein actually employed arbitrary increasing base-bumping functions. He showed that the convergence of all such is equivalent to transfinite induction below ϵ0."</p> <p>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. </p> <p>But when we take a fixed iterate of log then of course termination of Goodstein sequences is equivalent to the 1 consistency of PA.</p> <p>If the base bumping function growth faster than H_epsilon_0 then Goodstein can of course yield more than the 1 consistency of PA.</p> <p>Best, Andreas</p>