[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.
Tim
======================================================================
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
http://groups.google.com/group/sci.math/browse_frm/thread/af94b3349a4c1959
http://groups.google.com/group/comp.theory/browse_frm/thread/fe0ee6a4a175d767
Questions:
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),
etc.)
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