Do Goodstein sequences grow faster than Ackermann's function?

logic/goodstein New

New entry, edited from material collected for the archive and not yet in a released version.

Problem

Do Goodstein sequences grow faster than Ackermann's function?

[ Editor: problem statement reconstructed from the summary posting; the
  original question, which mentioned two types of Goodstein sequence,
  is not in the collected material. ]

Show solution

The general consensus is that the Goodstein sequences (both types that
I mentioned) DO GROW FASTER than Ackermann's function.  Here are some of
the comments I got.

There was some objection to my statement that "Goodstein sequences are
more NATURAL than Ackermann's function."  Perhaps a fairer statement is
"Goodstein sequences are an INTERESTING example of a function that grows
fast, that perhaps ought to be shown to grad students along with
Ackermann's function."

  An excellent study of the Goodstein function is given in the Buchholz
  and Wainer article in

      Contemporary Mathematics (Logic and Combinatorics)
      Vol 65, 1987, Stephen Simpson, ed.

  Roughly what goes on in the article is the Grzegorczyk hierarchy is
  extended to epsilon nought.  The Grzegorczyk hierarchy is indexed by
  omega and Ackermann's function lives right on the top (at level
  omega).  The first Goodstein function you mentioned lives at level
  omega to the omega and the second lives at epsilon nought.
  Another reference is Takeuti's Proof Theory.

  ----

  Goodstein sequences grow at the rate "epsilon_0", ie, the limit of
  w, w^w, w^w^w, w^w^w^w, ....  This is intuitively obvious, if you
  think about it for a while.

      What does it mean to "grow at a rate of epsilon_0"?  Or for that
      matter any ordinal?

  Proving it is a little harder: but it is a theorem, due to Laurie A C
  Kirby, that "Vn, Goodstein(n) is finite" is not provable in PA.

  ----

  Though not a specialist on this subject, I just attended a talk by
  Cichon about these sequences.  Indeed the first requires induction up
  to omega^omega and the second up to epsilon_0.  You can find some
  literature on this, e.g. E. A. Cichon, "A short proof of two recently
  discovered independence results using recursion theoretic methods",
  Proc. Amer. Math. Soc. 87 (4), 704-706.

-- Bill Gasarch <gasarch@mimsy.umd.edu>

[ Editor: the indented paragraphs are replies Gasarch received by mail
  and quoted without names; the question in the middle is his. ]