[FOM] Growth Rate of Level-k Goodstein Function

Timothy Y. Chow tchow at alum.mit.edu
Tue Oct 3 09:47:25 EDT 2006

I am posting the queries below on behalf of Robert Sawyer 
(r.s at mindspring.com).  Replies may be posted to FOM or emailed directly.


The "usual" Goodstein function is only the third function, g_3, in a
particularly simple hierarchy of functions that were introduced by
R. L. Goodstein.  These are based on his extension of the hereditary
representation of integers so as to use the first k >= 1 operations in
the hierarchy commonly written with Knuth arrows as +,*,^,^^,^^^,...
For each integer k >= 1, the level-k Goodstein function g_k is defined
using level-k representations in precisely the same manner as level-3
representations are used to define the usual Goodstein function g_3.
The level-w Goodstein function g_w is then defined by g_w(n) = g_n(n).

Details, examples, and a few developments are given in the threads


1. In terms of the Wainer hierarchy of functions f_a,

g_1 ~ f_1
g_2 ~ f_w
g_3 ~ f_epsilon_0
g_4 ~ f_?????
g_w ~ f_?????

How can one characterise the growth rates of the g_a for a > 3?

2. Is every g_a (0 < a <= w) dominated by f_Gamma_0?

3. In Goodstein's ordinal notation, obtained by substituting w for
the base in a level-k representation (0 < k < w), the least ordinal
not representable at level k (0 < k < w) is evidently w[k+1]w, where
[k] denotes the kth of the operations +,*,^,^^,^^^,...

Can w[k+1]w, for 3 < k < w, be usefully related to the ordinal index
of the Wainer function that characterises g_k?  (They're equal for
k = 3, but not for k < 3; specifically,
g_1 < f_(w*w),  g_2 < f_(w^w),  g_3 = f_(w^^w),  g_4 ??? f_(w^^^w),

4. How does one express Goodstein's w[k]w in more-standard notation?
E.g., w^^w = epsilon_0, w^^^w = ?????
Is w[k]w < Gamma_0 if 0 < k < w?

Robert Sawyer ("r.e.s.")

More information about the FOM mailing list