Re: Growth Rate of Level-k Goodstein Function
Bill Taylor
> including the following formula that I derived for g_1
>
> g_1(n) = 2^floor(n/a)*(a + n%a + 1) - 3 (n >= 0)
What does that "%" sign mean?
Is it some standard operastion in this context?
wfct
r.e.s.
Yes, it's just the usual "modulo operation".
n%a is the remainder of n divided by a; i.e.,
n%a = n - a*floor(n/a).
G. A. Edgar
> Yes, it's just the usual "modulo operation".
> n%a is the remainder of n divided by a; i.e.,
> n%a = n - a*floor(n/a).
>
"Usual" is an exaggeration.
Well-known to C programmers, not to others.
--
G. A. Edgar http://www.math.ohio-state.edu/~edgar/
tc...@lsa.umich.edu
G. A. Edgar <ed...@math.ohio-state.edu.invalid> wrote:
>> Yes, it's just the usual "modulo operation".
>> n%a is the remainder of n divided by a; i.e.,
>> n%a = n - a*floor(n/a).
>
>"Usual" is an exaggeration.
>Well-known to C programmers, not to others.
To be fair, the adjective "usual" is here applied to "modulo operation" and
not to the notation. The modulo operation in question is certainly the usual
one even if the notation for it isn't.
--
Tim Chow tchow-at-alum-dot-mit-dot-edu
The range of our projectiles---even ... the artillery---however great, will
never exceed four of those miles of which as many thousand separate us from
the center of the earth. ---Galileo, Dialogues Concerning Two New Sciences
r.e.s.
>>
>> Yes, it's just the usual "modulo operation".
>> n%a is the remainder of n divided by a; i.e.,
>> n%a = n - a*floor(n/a).
>>
>
> "Usual" is an exaggeration.
> Well-known to C programmers, not to others.
That misrepresents what was said. You've snipped
the question to which I was replying ...
>> Is it some standard operastion in this context?
"It" (the operation) is the modulo operation,
which is indeed standard and usual in this context.
The sign used for it is another matter.
--r.e.s.
Jan Burse
r.e.s. wrote:
>>>Yes, it's just the usual "modulo operation".
>>>n%a is the remainder of n divided by a; i.e.,
>>>n%a = n - a*floor(n/a).
> "It" (the operation) is the modulo operation,
> which is indeed standard and usual in this context.
> The sign used for it is another matter.
Usually n%a <> n-a*floor(n/a)
rather n%a = sign(a)*sign(n)*(abs(n)-abs(a)*floor(abs(n)/abs(a)))
which makes a slight difference...
Bye
Deedlit
On Oct 13, 8:08 am, "r.e.s." <r...@ZZmindspring.com> wrote:
> "Bill Taylor" <w.tay...@math.canterbury.ac.nz> wrote ...
>
> > r.e.s. wrote:
>
> >> including the following formula that I derived for g_1
>
> >> g_1(n) = 2^floor(n/a)*(a + n%a + 1) - 3 (n >= 0)
>
I noticed an error in your formula: It should be
g_1(n) = 2^floor(n/a)*(a + n%a + 1) - a - 1.
For g_2 (n), you can write n = Sum (c_i a^i), and then
g_2 (Sum (c_i a^i)) = H_(Sum (c_i w^i)) (a + 1) - a - 1
= F_m^c_m (F_(m-1)^c_(m-1) (... (F_0^c_0 (a + 1)...)) - a - 1.
where H is the Hardy hierarchy, and F is the Gregorczyk-Wainer
hierarchy, i.e.
H_0 (x) = x
H_(a+1) (x) = H_a (x+1)
H_a (x) = H_(a(x)) (x) for a limit, and a(x) the fundamental sequence
of a.
F_0 (x) = x+1
F_(a+1) (x) = F_a^x (x)
F_a (x) = f_(a(x)) (x) for a limit, and a(x) the fundamental sequence
of a.
r.e.s.
Please. It makes no difference at all in the stated context,
which is that n and a are integers, with n >= 0, a >= 2.
r.e.s.
> "r.e.s." <r...@ZZmindspring.com> wrote:
>> "Bill Taylor" <w.tay...@math.canterbury.ac.nz> wrote ...
>>
>> > r.e.s. wrote:
>>
>> >> including the following formula that I derived for g_1
>>
>> >> g_1(n) = 2^floor(n/a)*(a + n%a + 1) - 3 (n >= 0)
>>
>
> I noticed an error in your formula: It should be
>
> g_1(n) = 2^floor(n/a)*(a + n%a + 1) - a - 1.
Yes, thanks. I'd caught and corrected the same thing for g_2
in my 2006-09-21 message, but somehow didn't recall making that
mistake for g_1. I got sloppy translating from my results for
B_k(n) (the value of the base when the level-k sequence for n
reaches 0); e.g.,
B_1(n) = 2^floor(n/a)*(a + n%a + 1) - 1
> For g_2 (n), you can write n = Sum (c_i a^i), and then
>
> g_2 (Sum (c_i a^i)) = H_(Sum (c_i w^i)) (a + 1) - a - 1
> = F_m^c_m (F_(m-1)^c_(m-1) (... (F_0^c_0 (a + 1)...)) - a - 1.
>
> where H is the Hardy hierarchy, and F is the Gregorczyk-Wainer
> hierarchy, i.e.
>
> H_0 (x) = x
> H_(a+1) (x) = H_a (x+1)
> H_a (x) = H_(a(x)) (x) for a limit, and a(x) the fundamental sequence
> of a.
>
> F_0 (x) = x+1
> F_(a+1) (x) = F_a^x (x)
> F_a (x) = f_(a(x)) (x) for a limit, and a(x) the fundamental sequence
> of a. ^^
F_
It's interesting to see the Hardy hierarchy being used.
The version using F_a seems to be another way of writing what I
posted 2006-09-21 (my x_i are your c_i, and my p is your m) ...
g_2(n) = f_p^x_p f_(p-1)^x_(p-1) ... f_0^x_0 a - a
that is,
B_2(n) = f_p^x_p f_(p-1)^x_(p-1) ... f_0^x_0 a
where many parentheses are omitted for easier reading, and where
f_0 (t) = t + 1
f_(k+1) (t) = f_k^(t+1) (t).
A question about terminology ...
I see the F_a hierarchy variously called the Wainer hierarchy,
the extended Grzegorczyk hierarchy, and the Grzegorczyk-Wainer
hierarchy; but, as I recall, the f_a (appropriately defined at
limit ordinals) were used by Wainer in his 1989 JSL paper
"Slow Growing versus Fast Growing". Are the f_a sometimes also
called "the Wainer hierarchy"?
Also ... Could someone please say how Wainer pronounces his name?
Is the first vowel sound as in wine, or as in wane? (FWIW, I
found on the internet a pronunciation of Grzegorczyk:
http://www.polishroots.org/surnames/surnames_28.htm
says it's something like "g'zheh-GORE-chick" -- not what one
might expect from the other spelling used above.)
--r.e.s.
CH
If so could anyone show my a program/function returning it evaluated at
any desired integer?
CH
And to repeat my previous questions:
Aatu Koskensilta
> Is the Howard ordinal computable?
It's a constructive ordinal, and thus there is a p.r. well-ordering of
the naturals of the same order type.
> If so could anyone show my a program/function returning it evaluated at
> any desired integer?
What is it that you want, exactly?
--
Aatu Koskensilta (aatu.kos...@xortec.fi)
"Wovon man nicht sprechen kann, daruber muss man schweigen"
- Ludwig Wittgenstein, Tractatus Logico-Philosophicus
CH
> CH wrote:
> > If so could anyone show my a program/function returning it evaluated at
> > any desired integer?
>
> What is it that you want, exactly?
gamma_0 can be evaluated at (i.e.) 10 returning an integer
epsilon_1 can be evaluated at (i.e.) 100 returning an integer
Can a program be made that outputs howard_x(y) for any desired integers
x,y?
If so could you show me it?
Aatu Koskensilta
> gamma_0 can be evaluated at (i.e.) 10 returning an integer
> epsilon_1 can be evaluated at (i.e.) 100 returning an integer
>
> Can a program be made that outputs howard_x(y) for any desired integers
> x,y?
What does "evaluating" an ordinal at an integer or a pair of integers mean?
tc...@lsa.umich.edu
Aatu Koskensilta <aatu.kos...@xortec.fi> wrote:
>CH wrote:
>> gamma_0 can be evaluated at (i.e.) 10 returning an integer
>> epsilon_1 can be evaluated at (i.e.) 100 returning an integer
>>
>> Can a program be made that outputs howard_x(y) for any desired integers
>> x,y?
>
>What does "evaluating" an ordinal at an integer or a pair of integers mean?
Maybe you should give him more hints?
The most obvious kind of program associated with a computable ordinal alpha
is a program P that takes a pair of integers (x,y) as input and outputs
either 0 or 1, and that has the following property:
There exists a bijection phi from the set of integers to the ordinal alpha
such that P(x,y) = 1 if and only if phi(x) < phi(y).
Is that what you're looking for? It's not quite what you stated, but
perhaps it's what you really want.
CH
> CH wrote:
> > gamma_0 can be evaluated at (i.e.) 10 returning an integer
> > epsilon_1 can be evaluated at (i.e.) 100 returning an integer
> >
> > Can a program be made that outputs howard_x(y) for any desired integers
> > x,y?
>
> What does "evaluating" an ordinal at an integer or a pair of integers mean?
By "evaluating" ordinal A at x I meant evaluating:
f_A(x)=f_A-1(x+1) until A gets to zero and returning the final value of
x.
I think this is called the Hardy hierarchy, though for the howard
ordinal I might as well have used the slow-growing hierarchy.
CH
> The most obvious kind of program associated with a computable ordinal alpha
> is a program P that takes a pair of integers (x,y) as input and outputs
> either 0 or 1, and that has the following property:
>
> There exists a bijection phi from the set of integers to the ordinal alpha
> such that P(x,y) = 1 if and only if phi(x) < phi(y).
>
> Is that what you're looking for? It's not quite what you stated, but
> perhaps it's what you really want.
Hmm... That would be useful too.
CH
tc...@lsa.umich.edu
CH <cchh...@Yahoo.co.uk> wrote:
>No reply?
Well, your request is a little puzzling.
>By "evaluating" ordinal A at x I meant evaluating:
>f_A(x)=f_A-1(x+1) until A gets to zero and returning the final value of x.
I take it that that's supposed to be f_A(x) = f_{A-1}(x+1). But what does
"A-1" mean for a limit ordinal? Whatever it means, surely repeatedly
"subtracting one" from a limit ordinal isn't going to reach any kind of
terminal state in a finite number of steps.
CH
> >By "evaluating" ordinal A at x I meant evaluating:
> >f_A(x)=f_A-1(x+1) until A gets to zero and returning the final value of x.
>
> I take it that that's supposed to be f_A(x) = f_{A-1}(x+1). But what does
> "A-1" mean for a limit ordinal? Whatever it means, surely repeatedly
> "subtracting one" from a limit ordinal isn't going to reach any kind of
> terminal state in a finite number of steps.
Pardon my complete incomprehensibility (and probable incompetence). I'm
a student so I'm unfamiliar with the notation systems. I meant that if
you have (for example) A=w^w (in other words
sup[w,w*w,w*w*w,w*w*w*w...]) and are trying to get (A-1)(3) you will
end up with:
(A-1)(3)
((w^w)-1)(3)
(w*w*w)-1)(3)
(2*w*w+(w*w)-1)(3)
(2*w^2+2*w+w-1)(3)
(2*w^2+2*w+2)(3)
In other words your subtracting one from A evaluated at 3. According to
Goodstien if you continuously evaluate f_A(x)=f_(A-1)(x+1) for any
ordinal smaller than epsilon_0 you will eventually get to f_0(n) were n
is an integer. I thought that was true for all countable ordinals.
I hope I've finally made an understandable post.
Deedlit
hierarchies like the Hardy and Grzegorczyk-Wainer hierarchies at large
ordinals.
CH wrote:
> Pardon my complete incomprehensibility (and probable incompetence). I'm
> a student so I'm unfamiliar with the notation systems.
No problem, CH. Allow me comment on an earlier claim that you made:
that w^^^w is the (smallest) ordinal for which epsilon_a = a. (As Dave
and Robert pointed out, this is not Gamma_0). This is not true using
the standard definition of Knuth arrows, extended to ordinals; if you
work out some examples, you should see that w^^^w is epsilon_0, and
that a {b} c <= epsilon_0 for a < epsilon_0. Robert was using the
notation of Goodstein, which he dubbed "majorant" ordinals - see his
description. According to this ordering, we may well have w^^^w
corresponding to phi_2 (0) (the smallest ordinal for which epsilon_a =
a), but this claim is not trivial; I think you were oversimplifying
things a bit.
I meant that if
> you have (for example) A=w^w (in other words
> sup[w,w*w,w*w*w,w*w*w*w...]) and are trying to get (A-1)(3) you will
> end up with:
> (A-1)(3)
> ((w^w)-1)(3)
> (w*w*w)-1)(3)
> (2*w*w+(w*w)-1)(3)
> (2*w^2+2*w+w-1)(3)
> (2*w^2+2*w+2)(3)
> In other words your subtracting one from A evaluated at 3. According to
> Goodstien if you continuously evaluate f_A(x)=f_(A-1)(x+1) for any
> ordinal smaller than epsilon_0 you will eventually get to f_0(n) were n
> is an integer. I thought that was true for all countable ordinals.
> I hope I've finally made an understandable post.
Unfortunately, the expressions you have above aren't ordinals, because
-1 is not well-defined on the ordinals. The way the Hardy hierarchy
works is
H_0 (x) = x
H_(a+1) (x) = H_a (x+1)
H_a (x) = H_(a(x)) (x) for a limit, and a(x) a fundamental sequence of
a.
As for your other questions:
The formulae you gave earlier are rather complicated and muddled - if
you could write them again, but with more explanation and motivation on
what everything means, then I could probably answer you.
The Howard ordinal is computable. As for a program that outputs either
an ordinal hierarchy at the Howard ordinal, or gives an ordering of the
natural numbers of type the Howard ordinall, that's a tall order -
I'll see what I can work out. I'll probably just describe the basic
algorithm and let you deal with the coding.
CH
> Tim, I believe he is talking about the evaluation of ordinal
> hierarchies like the Hardy and Grzegorczyk-Wainer hierarchies at large
> ordinals.
> CH wrote:
>
> > Pardon my complete incomprehensibility (and probable incompetence). I'm
> > a student so I'm unfamiliar with the notation systems.
>
> No problem, CH. Allow me comment on an earlier claim that you made:
> that w^^^w is the (smallest) ordinal for which epsilon_a = a. (As Dave
> and Robert pointed out, this is not Gamma_0). This is not true using
> the standard definition of Knuth arrows, extended to ordinals; if you
> work out some examples, you should see that w^^^w is epsilon_0, and
> that a {b} c <= epsilon_0 for a < epsilon_0.
defined as w^^w, it's only today that I learnt it happens to define the
strength of an axiomic system (I can't recall at this moment which).
> Robert was using the
> notation of Goodstein, which he dubbed "majorant" ordinals - see his
> description. According to this ordering, we may well have w^^^w
> corresponding to phi_2 (0) (the smallest ordinal for which epsilon_a =
> a), but this claim is not trivial; I think you were oversimplifying
> things a bit.
G(k,n,b) - G iterates F until n gets to zero while incrementing b with
each pass. k is the maximun operator allowed (with 1=+, 2=*, 3=^,...
and so on), b is the base of the current n and n is the value that will
be converted into a base b representation and then have that base
incremented
F(x,y,z,b,i,o) - F finds the largest n such that Ack(b,i,n)<x assigns z
to Ack(z,i,n) and y to Ack(y,i,F(n,b+1,b,b,o,o)) (y is essentaily z
apart from the fact it started at b+1 instead of b and that it changes
n for F(n)) it then decreases i (to work with a smaller operator) and
loops. x is the amount F is trying to reach, z is what it's got so far,
y is z modified to be base b+1 instead of b, b is the current base, i
is the current operator F is working with and o is the largest operator
it is allowed to work with
Ack(x,y,z) - Ack is the ackermann function i.e. if y is 1 then return
x+z, if y is 2 then return x*z, if y is 3 then return x^z and so on
H(a,x,y,i) - if i is 0 then H returns the largest n such that
Ack(x,n,y)<a
recap:
G - iterates the function F
F - does the actual work
Ack - computes the Ackermann
H - computes the inverse of the Ackermann
g_k(n) base= G(k,n,base)
G(k,n,b)=G(k,F(n,b+1,b,b,k,k),b+1)
F(x,y,z,b,i,o)=if(x<b)then(x)else(
if(z<>x)then(
F(x,Ack(y,i,F(H(x,z,i,0),b+1,b,b,o,o)),Ack(z,i,H(x,z,i,0)),b,i-1,o)
)else(y)
)
Ack(x,y,z)=if(y=1)then(x+z)else(
if(z=1)then(x)else( Ack(x,y-1,Ack(x,y,z-1)) )
)
H(a,x,y,i)=if(Ack(x,y,i)>a)then(-1)(else(1+H(a,x,y,i+1))
This might be unclear. If so please tell me what bit is confusing so I
can clarify it.
> The Howard ordinal is computable. As for a program that outputs either
> an ordinal hierarchy at the Howard ordinal, or gives an ordering of the
> natural numbers of type the Howard ordinall, that's a tall order -
> I'll see what I can work out. I'll probably just describe the basic
> algorithm and let you deal with the coding.
Thanks a lot! It shouldn't be to hard to code once I know the algorithm.
CH
> F(x,y,z,b,i,o) - F finds the largest n such that Ack(b,i,n)<x assigns z
F(x,y,z,b,i,o) - F finds the largest n such that Ack(b,i,n)<x, then
assigns z
Deedlit
CH wrote:
> I've only just started studying ordinals so I thought epsilon_0 was
> defined as w^^w,
Basically, although usually not with Knuth arrows. It's often defined
as the smallest ordinal such that w^a = a.
> it's only today that I learnt it happens to define the
> strength of an axiomic system (I can't recall at this moment which).
Peano arithmetic. So Goodstein's Theorem (that the level 3 Goodstein
function is well-defined) isn't provable in PA, which was a big deal:
After Godel's theorem, people knew that there were true statements that
were unprovable in any formal system, but the example from Godel's
theorem is an "unnatural", self-referential statement. So, it was
wondered whether there was a "natural" statement that was true but
unprovable in a standard theory like PA. Goodstein's Theorem and the
Paris-Harrington Theorem were early examples of such theorems.
>
> g_k(n) base= G(k,n,base)
> G(k,n,b)=G(k,F(n,b+1,b,b,k,k),b+1)
This is a problem - it just calls itself indefinitely.
CH
Deedlit wrote:
> Peano arithmetic. So Goodstein's Theorem (that the level 3 Goodstein
> function is well-defined) isn't provable in PA, which was a big deal:
> After Godel's theorem, people knew that there were true statements that
> were unprovable in any formal system, but the example from Godel's
> theorem is an "unnatural", self-referential statement. So, it was
> wondered whether there was a "natural" statement that was true but
> unprovable in a standard theory like PA. Goodstein's Theorem and the
> Paris-Harrington Theorem were early examples of such theorems.
> > g_k(n) base= G(k,n,base)
> > G(k,n,b)=G(k,F(n,b+1,b,b,k,k),b+1)
>
> This is a problem - it just calls itself indefinitely.
Add this:
G(k,0,b)=b
CH
Deedlit wrote:
> Peano arithmetic. So Goodstein's Theorem (that the level 3 Goodstein
> function is well-defined) isn't provable in PA, which was a big deal:
> After Godel's theorem, people knew that there were true statements that
> were unprovable in any formal system, but the example from Godel's
> theorem is an "unnatural", self-referential statement. So, it was
> wondered whether there was a "natural" statement that was true but
> unprovable in a standard theory like PA. Goodstein's Theorem and the
> Paris-Harrington Theorem were early examples of such theorems.
> > g_k(n) base= G(k,n,base)
> > G(k,n,b)=G(k,F(n,b+1,b,b,k,k),b+1)
>
> This is a problem - it just calls itself indefinitely.
Deedlit
> > > g_k(n) base= G(k,n,base)
> > > G(k,n,b)=G(k,F(n,b+1,b,b,k,k),b+1)
> >
> > This is a problem - it just calls itself indefinitely.
> Great another miskake.
> Add this:
> G(k,0,b)=b
Still not quite there - the second argument of G keeps increasing.
Deedlit
r.e.s. wrote:
>
> The version using F_a seems to be another way of writing what I
> posted 2006-09-21 (my x_i are your c_i, and my p is your m) ...
>
> g_2(n) = f_p^x_p f_(p-1)^x_(p-1) ... f_0^x_0 a - a
>
> that is,
> B_2(n) = f_p^x_p f_(p-1)^x_(p-1) ... f_0^x_0 a
>
> where many parentheses are omitted for easier reading, and where
>
> f_0 (t) = t + 1
> f_(k+1) (t) = f_k^(t+1) (t).
>
Hmm... I think for this to work, there has to be an increment on the
limit ordinals as well. I've seen the GW hierarchy with t+1 as the
exponent, but not in the fundamental sequence.
>
> A question about terminology ...
>
> I see the F_a hierarchy variously called the Wainer hierarchy,
> the extended Grzegorczyk hierarchy, and the Grzegorczyk-Wainer
> hierarchy; but, as I recall, the f_a (appropriately defined at
> limit ordinals) were used by Wainer in his 1989 JSL paper
> "Slow Growing versus Fast Growing". Are the f_a sometimes also
> called "the Wainer hierarchy"?
I'd say they would also be called by any of the above names, just like
there are numerous variants of the Ackermann function.
r.e.s.
>
> r.e.s. wrote:
>>
>> The version using F_a seems to be another way of writing what I
>> posted 2006-09-21 (my x_i are your c_i, and my p is your m) ...
>>
>> g_2(n) = f_p^x_p f_(p-1)^x_(p-1) ... f_0^x_0 a - a
>>
>> that is,
>> B_2(n) = f_p^x_p f_(p-1)^x_(p-1) ... f_0^x_0 a
>>
>> where many parentheses are omitted for easier reading, and where
>>
>> f_0 (t) = t + 1
>> f_(k+1) (t) = f_k^(t+1) (t).
>>
>
> Hmm... I think for this to work, there has to be an increment on the
> limit ordinals as well. I've seen the GW hierarchy with t+1 as the
> exponent, but not in the fundamental sequence.
No limit ordinals are used in the above recursion for g_2, just
nonnegative integers -- the extended hierarchy isn't needed here.
(Your recursion for g_2 in terms of the F_a also doesn't involve
limit ordinals, although the Hardy hierarchy version does.)
BTW, I think it can be shown by induction that above f_k and F_k,
for nonnegative integer k, are simply related by
F_k (n+1) = f_k (n) + 1
so that both recursions for g_2 (in the F_k and in the f_k) are
equivalent. I also see now that your recursion for g_2 in terms
of the Hardy hierarchy follows from that of the F_k because of
the general relationships
F_a (n) = H_(w^a) (n)
H_(a+b) (n) = H_a(H_b(n))
H_(w^(a+1)) (n) = (H_(w^a))^n (n)
Hence all three recursions for g_2 (in the f_k, F_k, and H_a)
are equivalent.
>> A question about terminology ...
>>
>> I see the F_a hierarchy variously called the Wainer hierarchy,
>> the extended Grzegorczyk hierarchy, and the Grzegorczyk-Wainer
>> hierarchy; but, as I recall, the f_a (appropriately defined at
>> limit ordinals) were used by Wainer in his 1989 JSL paper
>> "Slow Growing versus Fast Growing". Are the f_a sometimes also
>> called "the Wainer hierarchy"?
>
> I'd say they would also be called by any of the above names, just like
> there are numerous variants of the Ackermann function.
That's what I figured, since I think that when the f_a are
appropriately defined at limit ordinals, F_a(n+1) = f_a(n) + 1,
so that for an arbitrary function h, (h ~ F_a) <=> (h ~ f_a).
(By h ~ F_a, I mean a is the least ordinal such that as n ->oo,
h(n)/F_(a+1)(n) -> 0, etc.) That is, both hierarchies effect
the same calibration of growth rates.
CH
Better?
Deedlit
Yes, it looks good now. Only one change:
g_k (n, b) = G(k,n,b) - b
CH
> Yes, it looks good now. Only one change:
>
> g_k (n, b) = G(k,n,b) - b
Deedlit
Yes, I believe so.
Deedlit
r.e.s. wrote:
> >
> > Hmm... I think for this to work, there has to be an increment on the
> > limit ordinals as well. I've seen the GW hierarchy with t+1 as the
> > exponent, but not in the fundamental sequence.
>
> No limit ordinals are used in the above recursion for g_2, just
> nonnegative integers -- the extended hierarchy isn't needed here.
> (Your recursion for g_2 in terms of the F_a also doesn't involve
> limit ordinals, although the Hardy hierarchy version does.)
Yes, of course, silly of me.
Incidentally, I thought about whether we could extend this to all g_k.
I thought
that perhaps we could use the Hardy hierarchy and index them by
Goodstein's
"majorant ordinals", but after some examination I don't think the
higher limit ordinals
will reduce to the same smaller ordinals - for example, take w^^(w+1).
For n = 2, n^^(n+1) = (n^^n)^n
For n = 3, n^^(n+1) = (n^^n)^[(n^^2)^(n*2 + 2)]
We would need to find an ordinal expression that matches up for all n,
and it doesn't
look like we can do that. So we can't match up the Goodstein function
with an
ordinal hierarchy like we did up to level 3.
Deedlit
First, it wasn't clear from the first page of the paper exactly what
notations we are including in the majorant ordering. I assumed
that the only notations that would appear would be those that
would correspond to a possible base-n notation; so, for example,
(w+1)^w, or (w^^w)^(w^^w) would not be included, since we never
write (n+1)^n or (n^^n)^(n^^n).
It's still an interesting question for larger classes of orderings.
For example, those that include all expressions with w as base
(so (w^^w)^(w^^w) would be included, but not (w+1)^w), or all
expressions we can form period. I recall an expository paper
by Smorynski who stated the conjecture that all exponential
polynomials under the majorant ordering, formed a well-ordered
set with order type epsilon_0. He said that it was still open,
although the paper was pretty old - I'd be interested to hear
whether it has been solved since.
Anyway, under my assumption above, expressions involving
Knuth arrows up to level k have order type equal to the ordinal
phi_{k-2} (0) in Veblen's notation.
Here's level 4 in greater detail:
w^^w matches epsilon_0, of course.
Similarly, any polynomial of w^^w, with coefficients and powers in
epsilon_0,
matches the similar polynomial with epsilon_0.
The next majorant ordinal is w^^(w+1), which corresponds to e_0 ^ e_0.
w^^(w+1)^a matches with e_0 ^ (e_0 * a), for matching a up to
w^^(w+1) / e_0 ^ e_0.
So w^^(w+2) matches with (e_0 ^ e_0) ^ (e_0 ^ e_0) = e_0 ^ e_0 ^ e_0.
Continuing, we have w^^(w+n) = e_0 ^^ (n+1).
w^^(w*2) = e_0 ^^ w = e_1.
w^^(w + w*a) = e_a
w^^w^^w = e_e_0.
w^^w^^w^^w = e_e_e_0.
The limit ordinal is phi_2 (0).
I am pretty certain that the growth rate of the Goodstein functions
match up
with the Hardy/GW hierarchies at the above ordinals. As I said in my
last
post, the hierarchies won't match up exactly with the Goodstein
functions
no matter how we define the fundamental sequences, but clearly the
differences
will be negligible compared to the huge growth rates of the functions.
CH
All this is true for "real" ordinals but I don't think it's true for a
level 4 goodstein sequence:
w * e_0 = e_0 + e_0 + ... + e_0 w times
this has a faster growth rate than epsilon_0.
Note: '=' in this context means "has the same growth rate as"
w ^ e_0 = e_0 + 1 = e_0 and e_0+w^(w+1) =e_0 but e_0 ^ w>e_0
My rule of thumb is if A>B then A + B = A
Of course it is quite possible that this is just a matter of
definitions and e_0+1 has a faster growth rate than e_0.
Deedlit
CH wrote:
>All this is true for "real" ordinals but I don't think it's true for a
>level 4 goodstein sequence:
>w * e_0 = e_0 + e_0 + ... + e_0 w times
Actually, w * e_0 = e_0. e_0 * w = e_0 + e_0 + e_0 + ...
That is, ordinal multiplication is not commutative.
(In fact, neither is addition: 1 + w = w != w + 1.)
>this has a faster growth rate than epsilon_0.
>Note: '=' in this context means "has the same growth rate as"
>w ^ e_0 = e_0 + 1 = e_0 and e_0+w^(w+1) =e_0 but e_0 ^ w>e_0
w ^ e_0 is exactly e_0, so it's the exact same function in an
ordinal hierarchy.
>My rule of thumb is if A>B then A + B = A
>Of course it is quite possible that this is just a matter of
>definitions and e_0+1 has a faster growth rate than e_0.
I'm not sure what you mean here by the growth rate of epsilon_0,
in the context of Goodstein sequences. What I was discussing
above was how Goodstein's majorant ordinals compared with
ordinals written in Veblen notation, i.e. the ordinals below w^^w
"line up" with the ordinals below epsilon_0.
We can have varying definitions as to what it means for two
functions to have "about the same growth rate", but I'm doubtful
that this notion is going to help us. For example, the level-3
Goodstein function is smaller growing than H_(epsilon_0) and
faster growing than H_a for any a < epsilon_0, and this is going
to be true no matter what our definition of "about the same
growth rate" is. The above definition will merely identify "clumps"
of functions together.
r.e.s.
> Okay, I have the answer to Robert's original questions.
Your proposed answers do seem quite speculative though (as
noted below).
> First, it wasn't clear from the first page of the paper exactly what
> notations we are including in the majorant ordering. I assumed
> that the only notations that would appear would be those that
> would correspond to a possible base-n notation; so, for example,
> (w+1)^w, or (w^^w)^(w^^w) would not be included, since we never
> write (n+1)^n or (n^^n)^(n^^n).
That assumption is correct. Definition of the Goodstein ordinals
under discussion was given in my 2006-10-05 posting, and also in
the statement of Question 3 in my FOM posting that you copied to
this thread.
> It's still an interesting question for larger classes of orderings.
> For example, those that include all expressions with w as base
> (so (w^^w)^(w^^w) would be included, but not (w+1)^w), or all
> expressions we can form period. I recall an expository paper
> by Smorynski who stated the conjecture that all exponential
> polynomials under the majorant ordering, formed a well-ordered
> set with order type epsilon_0. He said that it was still open,
> although the paper was pretty old - I'd be interested to hear
> whether it has been solved since.
Do you recall any more as to which Smorynski paper it was?
> Anyway, under my assumption above, expressions involving
> Knuth arrows up to level k have order type equal to the ordinal
> phi_{k-2} (0) in Veblen's notation.
If I'm reading that correctly, the correspondence would be
w[k+1]w <--> phi_(k-2)(0) (k >= 3) ([3]='^', [4]='^^', ...).
Then the least ordinal unrepresentable at all levels k < w,
would be sup{w[k]w: k < w} = phi_w(0) < phi_W(0) = Gamma_0,
where W is the least uncountable ordinal.
That would be an interesting solution to Question 4 of the
FOM posting, and it seems "intuitively plausible" -- but I
don't readily see a proof (or disproof) of the proposed
correspondence.
> Here's level 4 in greater detail:
>
> w^^w matches epsilon_0, of course.
>
> Similarly, any polynomial of w^^w, with coefficients and powers in
> epsilon_0, matches the similar polynomial with epsilon_0.
>
> The next majorant ordinal is w^^(w+1), which corresponds to e_0 ^ e_0.
The next Goodstein ordinal after w^^w is of course (w^^w)+1,
not w^^(w+1). I don't see what principle removes the seeming
arbitrariness of your "matching" ...
> w^^(w+1)^a matches with e_0 ^ (e_0 * a), for matching a up to
> w^^(w+1) / e_0 ^ e_0.
> So w^^(w+2) matches with (e_0 ^ e_0) ^ (e_0 ^ e_0) = e_0 ^ e_0 ^ e_0.
> Continuing, we have w^^(w+n) = e_0 ^^ (n+1).
> w^^(w*2) = e_0 ^^ w = e_1.
> w^^(w + w*a) = e_a
> w^^w^^w = e_e_0.
> w^^w^^w^^w = e_e_e_0.
> The limit ordinal is phi_2 (0).
>
> I am pretty certain that the growth rate of the Goodstein functions
> match up with the Hardy/GW hierarchies at the above ordinals.
If I understand, you're conjecturing g_k ~ F_(a_k) (3 <= k < w),
where a_k = phi_(k-2) (0). But, supposing you're right about the
correspondence w[k+1]w <--> phi_(k-2) (0), no rationale is given
for relating that to the Wainer hierarchy. (Of course the
conjecture being true for k = 3 says nothing about k > 3.)
> As I said in my last post, the hierarchies won't match up exactly
> with the Goodstein functions no matter how we define the fundamental
> sequences, but clearly the differences will be negligible compared
> to the huge growth rates of the functions.
It's unclear to me what "matching up" you're trying to do there.
E.g., if your conjecture correctly matches phi_(k-2) (0) to a_k
for 3 <= k < w, what else is needed concerning the g_k growth
rates in those cases?
Deedlit
r.e.s. wrote:
> "Deedlit" <royc...@hotmail.com> wrote ...
> > Okay, I have the answer to Robert's original questions.
>
> Your proposed answers do seem quite speculative though (as
> noted below).
It's more than just speculation - I have worked out the correspondences
in some detail. I admit I don't have a proof that handles all the
ordinals
uniformly... at the moment, this seems rather tricky.
> > It's still an interesting question for larger classes of orderings.
> > For example, those that include all expressions with w as base
> > (so (w^^w)^(w^^w) would be included, but not (w+1)^w), or all
> > expressions we can form period. I recall an expository paper
> > by Smorynski who stated the conjecture that all exponential
> > polynomials under the majorant ordering, formed a well-ordered
> > set with order type epsilon_0. He said that it was still open,
> > although the paper was pretty old - I'd be interested to hear
> > whether it has been solved since.
>
> Do you recall any more as to which Smorynski paper it was?
>
I'm not totally sure, but it might be the paper "Some rapidly growing
functions."
>
> > Here's level 4 in greater detail:
> >
> > w^^w matches epsilon_0, of course.
> >
> > Similarly, any polynomial of w^^w, with coefficients and powers in
> > epsilon_0, matches the similar polynomial with epsilon_0.
> >
> > The next majorant ordinal is w^^(w+1), which corresponds to e_0 ^ e_0.
>
> The next Goodstein ordinal after w^^w is of course (w^^w)+1,
> not w^^(w+1). I don't see what principle removes the seeming
> arbitrariness of your "matching" ...
I meant the next ordinal after those described in the previous
paragraph,
those that are polynomials in w^^w with exponents and coefficients
smaller than w^^w. You do see at least that w^^(w+1) corresponds to
e_0^e_0, right?
>
> If I understand, you're conjecturing g_k ~ F_(a_k) (3 <= k < w),
> where a_k = phi_(k-2) (0). But, supposing you're right about the
> correspondence w[k+1]w <--> phi_(k-2) (0), no rationale is given
> for relating that to the Wainer hierarchy. (Of course the
> conjecture being true for k = 3 says nothing about k > 3.)
I have examined the corresponding growth rates, and the differences
between the two are negligible, i.e. they are dominated by incrementing
the Wainer hierarchy by one. But I haven't figured out a way to make
an inequality that applies universally to all ordinals - again, it
seems
like tricky business.
Do you have access to JSTOR, say at a university? If so, it would
be great if you could send me a copy of Wainer's "slow-growing
versus fast-growing" paper. I would get it myself, but I am home-
bound for a while.
The reason I ask is that that paper contains the kind of proof that
we are looking for here - a correspondence between growth rates
on a large interval of ordinals.
By the way, does either of the Goodstein papers contain a proof
that his system of ordinals were actually well-ordered, or did he
assume this without proof?
>
>
> > As I said in my last post, the hierarchies won't match up exactly
> > with the Goodstein functions no matter how we define the fundamental
> > sequences, but clearly the differences will be negligible compared
> > to the huge growth rates of the functions.
>
> It's unclear to me what "matching up" you're trying to do there.
> E.g., if your conjecture correctly matches phi_(k-2) (0) to a_k
> for 3 <= k < w, what else is needed concerning the g_k growth
> rates in those cases?
I'm talking here about what we are talking about above, the
correspondence
between the Goodstein functions and the Hardy/GW hierarchies.
Deedlit
about the Howard ordinal.
First, I will describe a standard notation for the Howard ordinal.
An ordinal a is additively principal if for all ordinals b,c less than
a,
b + c is less than a. The additively principal ordinals are exactly
those of the form w^a for some a.
Cantor's Theorem says that each ordinal can be written uniquely
as a weakly decreasing sum of additively principal ordinals.
So every ordinal can be written uniquely as
a = Sum (i = 1 to k) w^a_i, (i < j -> a_i >= a_j)
which is known as Cantor normal form.
By recursively applying the above notation, we eventually reduce
all ordinals to either 0 or epsilon numbers.
For our Howard ordinal notation, we use a function theta that
represents all epsilon numbers. Theta will be a two
variable function. The second variable will be also be less than
the Howard ordinal, so it will be recursively represented using
our notation; however, the first variable can in fact be greater
than our original ordinal! The first variable will be represented
as an exponential polynomial in Omega (we will just write O),
where Omega is typically identified with a very large ordinal,
usually the first uncountable ordinal.
So, if we define Ordinal to be the set of ordinals up to the
Howard ordinal, then we define UncountableOrdinal to be
the set of ordinals a of the form
a = O^a_1 * a_1 + ... + O^a_n * b_n
where the a_i are in UncountableOrdinal, and the b_i are in
Ordinal.
Then theta is a function that takes an UncountableOrdinal
and an Ordinal and maps them to an Ordinal.
Now, to implement an ordinal hierarchy, you take the
input ordinal a (and the input natural n) and determine whether
the ordinal is 0, a successor, or limit.
If the ordinal is 0 (which is easy to determine), we apply the
base rule, like H_0(n) = n or F_0(n) = n+1.
If the ordinal is a successor, then we apply recursion on the
predecessor ordinal of a, either H_(a+1) (n) = H_a (n+1)
or F_(a+1) (n) = F_a^n (n).
If the ordinal is a limit ordinal, then we apply recursion again,
replacing a with the nth ordinal in the fundamental sequence
of a.
A caveat here - fundamental sequences are not uniquely defined
for all ordinals. They are pretty standard below epsilon_0, as
there is pretty much a standard notation for such ordinals
(Cantor Normal Form applied recursively) and the fundamental
sequences are then "obvious". But as you go higher and
higher, there are more and more arbitrary choices to be made.
The idea is that, for "natural" choices of fundamental sequences,
the growth rate of these hierarchies will be the same. This
doesn't seem like something we can prove or necessarily even
make sense of for all recursive ordinals, but it seems to be
true at the low levels we are dealing with. Anyway, keep in
mind that the fundamental sequences that I am talking about
are simply somewhat arbitrary choices, and not uniquely defined
entities.
In our notation, an ordinal is written as a sum
of ordinals; to determine whether it is successor or limit,
check the last summand. If it is 1, it is a successor, otherwise
it is limit.
So everything is rather straightforward, except for determining
what the fundemental sequences of limit ordinals are. So that's
what the remainder of this article will be about.
For an ordinal a, let a[n] be the nth member of the fundamental
sequence. Then, for a = a_1 + a_2 + ... + a_k,
a[n] = a_1 + ... + a_k[n].
If a_k = w^(b+1), then a_k [n] = w^b + w^b + ... + w^b (n times).
If a_k = w^b with b limit, then a_k[n] = w^(b[n]).
So we have reduced the problem to finding the fundamental sequences
of theta values.
First, we have theta (a, b) [n] = theta (a, b[n]) when b is a limit
ordinal.
theta (a+1, 0) [0] = 1
theta (a+1, 0) [n+1] = theta (a, theta (a+1, 0) [n])
theta (a+1, b+1) [0] = theta (a+1, b) + 1
theta (a+1, b+1) [n+1] = theta (a, theta (a+1, b+1) [n])
For the remainder, let a = O^a_1 b_1 + ... + O^a_k b_k.
Let a' = O^a_1 b_1 + ... + O^a_(k-1) b_(k-1).
Assume a_k = 0, b_k limit. Then
theta (a, 0) [0] = 1
theta (a, 0) [n+1] = theta (a[n+1], theta (a, 0) [n])
theta (a, c+1) [0] = theta (a, c) + 1
theta (a, c+1) [n+1] = theta (a[n+1], theta (a, c+1) [n])
I'll address what happens with a_k != 0 with my next post.
r.e.s.
> It's more than just speculation - I have worked out the correspondences
> in some detail. I admit I don't have a proof that handles all the
> ordinals uniformly... at the moment, this seems rather tricky.
I appreciate your efforts, but imo there are good reasons to
doubt both of your proposed correspondences, viz. (for k > 3),
w[k+1]w <--> phi_(k-2) (0)
g_k ~ F_(phi_(k-2) (0))
The reasons are explained below.
> You do see at least that w^^(w+1) corresponds to e_0^e_0, right?
No, because the Goodstein ordinals are defined via the majorant
variable w; consequently,
w^^(w+1) < (w^^w)^(w^^w).
This is just stating that for all sufficiently large integers n,
n^^(n+1) < (n^^n)^(n^^n).
It seems questionable to assert w^^(w+1) <--> e_0^e_0 if both
w^^(w+1) < (w^^w)^(w^^w) and w^^w <--> e_0.
>> If I understand, you're conjecturing g_k ~ F_(a_k) (3 <= k < w),
>> where a_k = phi_(k-2) (0). But, supposing you're right about the
>> correspondence w[k+1]w <--> phi_(k-2) (0), no rationale is given
>> for relating that to the Wainer hierarchy. (Of course the
>> conjecture being true for k = 3 says nothing about k > 3.)
>
> I have examined the corresponding growth rates, and the differences
> between the two are negligible, i.e. they are dominated by incrementing
> the Wainer hierarchy by one. But I haven't figured out a way to make
> an inequality that applies universally to all ordinals - again, it
> seems like tricky business.
Sorry, but I remain skeptical, having seen only an examination
of Goodstein ordinals that imo doesn't make a clear connection
to the Wainer hierarchy.
> Do you have access to JSTOR, say at a university? If so, it would
> be great if you could send me a copy of Wainer's "slow-growing
> versus fast-growing" paper.
Unfortunately, I have no such convenient access -- not even
to hard copy of that particular paper (just some old notes
that I jotted down when reading it long ago.)
The papers cited below might actually be more helpful in
relating the g_k to the Wainer hierarchy.
> By the way, does either of the Goodstein papers contain a proof
> that his system of ordinals were actually well-ordered, or did he
> assume this without proof?
I believe the well-ordering is regarded as immediate upon the
definition via majorant variables.
>> > As I said in my last post, the hierarchies won't match up exactly
>> > with the Goodstein functions no matter how we define the fundamental
>> > sequences, but clearly the differences will be negligible compared
>> > to the huge growth rates of the functions.
>>
>> It's unclear to me what "matching up" you're trying to do there.
>> E.g., if your conjecture correctly matches phi_(k-2) (0) to a_k
>> for 3 <= k < w, what else is needed concerning the g_k growth
>> rates in those cases?
>
> I'm talking here about what we are talking about above, the
> correspondence
> between the Goodstein functions and the Hardy/GW hierarchies.
It's far from clear (to me) how you're getting a connection
between an ordinal and the growth rate of a g_k for k > 3.
For k <= 2, we get a connection from a formula for g_k that
makes it apparent (g_1 ~ F_1, g_2 ~ F_w); and for k = 3,
the connection is an often-cited result (g_3 ~ F_epsilon_0).
But for k > 3, I'm aware of no formula that makes it evident,
and no published results.
So, how are you getting such a correspondence when k > 3?
A look at how g_3 ~ F_epsilon_0 was established might give
some clues about how to proceed for k > 3. According to
http://groups.google.com/group/sci.math/msg/7ed034c97ed64f2c
g_3 ~ F_epsilon_0 is proved in the following two papers
(to which I have no convenient access, however):
E. A. Cichon, A short proof of two recently discovered
independence results using recursion theoretic methods,
Proceedings of the AMS 87, 1983, pp. 704-706.
L. Kirby and J. Paris, Accessible independence results for
Peano arithmetic, Bulletin of the London Math. Soc. 14,
1982, pp. 285-293.
r.e.s.
> Incidentally, I thought about whether we could extend this to all g_k.
> I thought that perhaps we could use the Hardy hierarchy and index them
> by Goodstein's "majorant ordinals", but after some examination I don't
> think the higher limit ordinals will reduce to the same smaller ordinals
> - for example, take w^^(w+1).
>
> For n = 2, n^^(n+1) = (n^^n)^n
> For n = 3, n^^(n+1) = (n^^n)^[(n^^2)^(n*2 + 2)]
The two equations are correct but are irrelevant to the ordinal
-- in each case n^^(n+1) is the correct base-n representation,
whereas the notations on the RHS are not in the required form.
(The definition of the unique hereditary representation is at
the link given in the first posting of this thread.)
> We would need to find an ordinal expression that matches up for all n,
> and it doesn't look like we can do that. So we can't match up the
> Goodstein function with an ordinal hierarchy like we did up to level 3.
Matching up ordinal expressions seems to be about finding a
correspondence between Goodstein *ordinals* and a standard
ordinal notation -- which is NOT the same thing as finding a
correspondence between Goodstein *functions* and a standard
ordinal-indexed hierarchy of functions.
CH
r.e.s.
> "Deedlit" wrote ...
>> You do see at least that w^^(w+1) corresponds to e_0^e_0,
>> right?
>
> No, because the Goodstein ordinals are defined via the majorant
> variable w; consequently,
> w^^(w+1) < (w^^w)^(w^^w).
> This is just stating that for all sufficiently large integers n,
> n^^(n+1) < (n^^n)^(n^^n).
> It seems questionable to assert w^^(w+1) <--> e_0^e_0 if both
> w^^(w+1) < (w^^w)^(w^^w) and w^^w <--> e_0.
Just to clarify ... In the above, (w^^w)^(w^^w) is not a
Goodstein ordinal (i.e., (n^^n)^(n^^n) is not a properly
formed base-n hereditary representation) -- which is why
I say "questionable", as opposed to "contradictory".
r.e.s.
I posted these same questions early last year to sci.math at
http://groups.google.com/group/sci.math/msg/edac659d9a47b223
http://groups.google.com/group/sci.math/msg/fa282e18a4b30d48
(Those are the individual postings in case this one get broken:
http://groups.google.com/group/sci.math/browse_frm/thread/af94b3349a4c1959)
There've been no replies, but the questions seem interesting
enough to be worth the present cross-posted attempt to see
if anyone can shed some light.
Background
----------
What's usually called "the" Goodstein function is only the 3rd
in a hierarchy of functions at levels k = 1,2,3,..., defined
in Goodstein's 1947 paper. The level-k Goodstein function, g_k,
is defined in terms of the hereditary respresentation of
integers, using only the first k operations in the hierarchy
commonly written +,*,^,^^,^^^,... -- see the links for details,
including the following formula that I derived for g_1 (which
uses only '+' in the hereditary representations) ...
g_1(n) = 2^floor(n/a)*(a + n%a + 1) - 3 (n >= 0)
where a >= 2 is the initial base. It turns out that every
Goodstein function g_k (k >= 1) is some subsequence of g_1.
"The" Goodstein function g_3 uses only +,*,^ in the hereditary
representations, and is known to have a growth rate described
by the ordinal epsilon_0 in the "fast-growing" Wainer hierarchy
of functions.
Questions
---------
(1) At what ordinal in the Wainer hierarchy is g_2, Goodstein's
level-2 function? (It's strictly less than epsilon_0, and I
think a formula should be derivable for g_2 involving operators
at levels higher than '^' -- but I haven't yet succeeded.)
(2) Is the growth rate of g_4 described by an ordinal w.r.t.
some fast-growing hierarchy of functions? If so, what is it,
exactly? If not, how might that growth rate be characterised?
(Etc. for the higher-level g_k.)
--r.e.s.
CH
g_4=w^^^w=Gamma_0. Ironic isn't it?
These can be written as recursive functions as follows:
g_2(n)=Ack(log2(n),2)
Ack(x,y)=Ack(x-1,Ack(x,y-1))
Ack(0,y)=y+1
Ack(x,0)=2
g_3(n)=F(n,2)
F(x,y)=F(H(x,0,y)-1,y+1)
F(0,y)=y
H(x,y,z)=(x%z)*(z+1)^F(y,0,z)+F(floor(x/z),y+1,b)
H(0,y,z)=0
g_4(n) is a bit harder I'll get back to you on that one.
Heres an interesting ordinal that occurs if instead of using
+,*,^,^^,... you define each combination of w e.g w^(w+5*w^^(w+1))+3*w
as an operator e.g 1,2,3,4,... would be +,*,^,^^,... ,g_w would be
w(operator w iow Ack)w and g_(w^^(w+1)) would be w(w^^(w+1))w.
g_(g_(...(g_(w)...)) (iirc called kappa_0) is (I think) what the fast
growing hierarchy is.
CH
Oops! that should have been:
H(x,y,z)=(x%z)*(z+1)^H(y,0,z)+H(floor(x/z),y+1,b)
r.e.s.
> g_1=w*w, g_2=w^w=ackermann function, g_3=w^^w=Epsilon_0,
> g_4=w^^^w=Gamma_0. Ironic isn't it?
What you've written in terms of w is the least ordinal
having no level-k hereditary representation (k=1,2,3,4)
but that's not generally the ordinal that describes the
growth rate of g_k, say with respect to a fast-growing
hierarchy. E.g., g_1 ~ f_1, not f_(w*w), in the Wainer
hierarchy; also, Ackermann function ~ f_w, not f_(w^w),
and gamma_0 > w^^^w.
>> These can be written as recursive functions as follows:
>> g_2(n)=Ack(log2(n),2)
>> Ack(x,y)=Ack(x-1,Ack(x,y-1))
>> Ack(0,y)=y+1
>> Ack(x,0)=2
>> g_3(n)=F(n,2)
>> F(x,y)=F(H(x,0,y)-1,y+1)
>> F(0,y)=y
>> H(x,y,z)=(x%z)*(z+1)^F(y,0,z)+F(floor(x/z),y+1,b)
>> H(0,y,z)=0
>> g_4(n) is a bit harder I'll get back to you on that one.
>
> Oops! that should have been:
> H(x,y,z)=(x%z)*(z+1)^H(y,0,z)+H(floor(x/z),y+1,b)
The g_k are certainly recursive functions, but what
you've written is incorrect. (Try some test cases.)
<snip>
CH
> > g_1=w*w, g_2=w^w=ackermann function, g_3=w^^w=Epsilon_0,
> > g_4=w^^^w=Gamma_0. Ironic isn't it?
>
> What you've written in terms of w is the least ordinal
> having no level-k hereditary representation (k=1,2,3,4)
> but that's not generally the ordinal that describes the
> growth rate of g_k, say with respect to a fast-growing
> hierarchy. E.g., g_1 ~ f_1, not f_(w*w), in the Wainer
> hierarchy; also, Ackermann function ~ f_w, not f_(w^w),
> and gamma_0 > w^^^w.
>
w*w,w^w, ect. are being represented as a goodstien list,
not by their place in the Wainer hierarchy. In that setting
the least ordinal not to have a level-k representation is
the ordinal that describes g_k's growth rate.
gamma_0 is the solution to epsilon_a=a. This is w^^^w.
> >> These can be written as recursive functions as follows:
> >> g_2(n)=Ack(log2(n),2)
> >> Ack(x,y)=Ack(x-1,Ack(x,y-1))
> >> Ack(0,y)=y+1
> >> Ack(x,0)=2
> >> g_3(n)=F(n,2)
> >> F(x,y)=F(H(x,0,y)-1,y+1)
> >> F(0,y)=y
> >> H(x,y,z)=(x%z)*(z+1)^F(y,0,z)+F(floor(x/z),y+1,b)
> >> H(0,y,z)=0
> >> g_4(n) is a bit harder I'll get back to you on that one.
> >
> > Oops! that should have been:
> > H(x,y,z)=(x%z)*(z+1)^H(y,0,z)+H(floor(x/z),y+1,b)
>
> The g_k are certainly recursive functions, but what
> you've written is incorrect. (Try some test cases.)
>
What I gave for g_2 was an aproximation. g_2 is between
Ack(log2(n)-1,2) and Ack(log2(n)+1,2).
The exact equation is:
g_2(n)=F(1,floor(log2(n)),g_2(n-2^( floor(log2(n)) )))
F(x,y,z)=F(x-1,y,F(z,y-1,z))
F(0,y,z)=z
F(x,0,z)=z+x
Dave L. Renfro
> gamma_0 is the solution to epsilon_a=a. This is w^^^w.
If you're talking about the least fixed point of
the function f:omega_1 --> omega_1 defined by
f(a) = epsilon_a, where epsilon_a is the a'th fixed
point of the function g:omega_1 --> omega_1 defined
by g(b) = w^b, then you're nowhere near gamma_0.
It is true that gamma_0 is among the solutions to
epsilon_a = a, but gamma_0 is also among the ordinals
that are fixed by gamma_0 many iterations of this
"fixed points of fixed points" process, of which the
first two are described in the previous sentence.
Dave L. Renfro
r.e.s.
> w*w,w^w, ect. are being represented as a goodstien list,
> not by their place in the Wainer hierarchy. In that setting
> the least ordinal not to have a level-k representation is
> the ordinal that describes g_k's growth rate.
Those ordinals do indicate why the growth rate of g_(k+1)
is "much larger" than that of g_k.
> gamma_0 is the solution to epsilon_a=a. This is w^^^w.
As David Renfro mentioned, gamma_0 is one of infinitely-
many solutions (but not the least one).
I find it tricky to determine which ordinal (in more-
standard notation) corresponds to Goodstein's w^^^w.
Although it's surely far below gamma_0, it's not clear
to me which ordinal it is.
> What I gave for g_2 was an aproximation.
> g_2 is between Ack(log2(n)-1,2) and Ack(log2(n)+1,2).
That's not quite right (try it for g_2(4)), but you've
encouraged me to work out some details. Here's what I
find ...
Writing [k] for the kth of the operators +,*,^,^^,...
(e.g. 2[3]4 = 2^4), and writing p for floor(log_a(n)),
2[p+1](p+a-1) < g_2(n) < 2[p+2](p+a) (n > a)
where a >= 2 is the initial base used in the Goodstein
sequences (usually a=2). These bounds result from a set
of p linked recursions, with the final value of the ith
recursion equal to the initial value of the (i+1)th,
and the ith recursion using operations only up to [i].
> The exact equation is:
> g_2(n)=F(1,floor(log2(n)),g_2(n-2^( floor(log2(n)) )))
> F(x,y,z)=F(x-1,y,F(z,y-1,z))
> F(0,y,z)=z
> F(x,0,z)=z+x
That's not correct -- try it for g_2(3). Having looked
more closely now at the situation, I would be very very
suprised if it were possible to define g_2 by such a
simple recursion, let alone the kind of simple "formula"
I at first had in mind.
-
Does anyone know of any work at all that discuss the g_k
hierarchy (other than by Goodstein, of course)?
It surprises me to never have seen it even mentioned that
the function usually called "the" Goodstein function is
only the 3rd in a hierarchy ordered by the highest level
of operation (+,*,^,^^,...) used to represent integers.
It's commonly mentioned that g_3 ~ f_epsilon_0; surely
the other g_k ought to be of interest?
Dave L. Renfro
> Does anyone know of any work at all that discuss the g_k
> hierarchy (other than by Goodstein, of course)?
>
> It surprises me to never have seen it even mentioned that
> the function usually called "the" Goodstein function is
> only the 3rd in a hierarchy ordered by the highest level
> of operation (+,*,^,^^,...) used to represent integers.
> It's commonly mentioned that g_3 ~ f_epsilon_0; surely
> the other g_k ought to be of interest?
I wrote up an extensive set of notes on ordinal numbers
in 1985, and then a revised version in 1991, and I've
been meaning to post an outline of them for several years.
Now seems to be a good time for me to do this. It will
take a few days, however. But for the time being, below
are some things I've posted that might be of use. The
first URL is a sci.math thread (at The Math Forum,
because my posts didn't get picked up by google for
some reason) -- look at the posts by Royce Peng and
myself during the period Feb. 5-11, 2002. The next
URL takes you to a sci.math post that discusses
gamma_0 some. The third URL is a sci.math post at
The Math Forum (again, because it wasn't picked up
by google) that includes some of the material that
I intend to be writing about. However, for some
reason, a lot of funny-looking characters crept
in. (They weren't in the post when it first appeared.
They showed up after The Math Forum's last URL change.
http://mathforum.org/kb/thread.jspa?threadID=77834
http://groups.google.com/group/sci.math/msg/efd4b9cb3c5e6fc9
http://mathforum.org/kb/thread.jspa?messageID=3414869
Dave L. Renfro
r.e.s.
> I wrote up an extensive set of notes on ordinal numbers
> in 1985, and then a revised version in 1991, and I've
> been meaning to post an outline of them for several years.
> Now seems to be a good time for me to do this. It will
> take a few days, however. But for the time being, below
> are some things I've posted that might be of use.
Thanks for the links. I believe that through the years I've
read with interest most if not all of your postings on these
topics!
However, those and all other sources I know of (except for
Goodstein himself) refer to no Goodstein function other than
the one based on hereditary representations using only +,*,^.
The hierarchy of functions that Goodstein obtained by using
operations +,*,^,^^,^^^,..., up to ever-higher levels in the
hereditary representations, seems never to be mentioned.
In terms of the Wainer hierarchy f_a, we now have ...
g_1 ~ f_1
g_2 ~ f_w
g_3 ~ f_epsilon_0
g_4 ~ f_?????
...
and I wonder whether -- comparable to g_3 -- g_4 might be
related to known results for some Hydra-like game.
On the side-issue concerning w^^^w, any pointers on how to
relate that to the epsilon ordinals?
r.e.s.
> "CH" <cchh...@Yahoo.co.uk> wrote ...
>> The exact equation is:
>> g_2(n)=F(1,floor(log2(n)),g_2(n-2^( floor(log2(n)) )))
>> F(x,y,z)=F(x-1,y,F(z,y-1,z))
>> F(0,y,z)=z
>> F(x,0,z)=z+x
>
> That's not correct -- try it for g_2(3). Having looked
> more closely now at the situation, I would be very very
> suprised if it were possible to define g_2 by such a
> simple recursion, let alone the kind of simple "formula"
> I at first had in mind.
Here's the most concise recursion I've managed to write
for g_2 with initial base a ...
g_2(n) = b_(floor(log_a(n+1))) - 2 (n >= 0)
b_0 = a
b_(k+1) = (f_k)^(x_k) (b_k)
where the f_k are in the fast-growing hierarchy of
functions defined recursively by
f_0 (t) = t + 1
f_(k+1) (t) = (f_k)^(t+1) t
and the x_k are defined recursively by
x_0 = n % a
x_(k+1) = ( (n - sum(a^i*x_i, i=0..k)) / a^k ) % a.
(The x_k -- and hence also the b_k -- depend implicitly
on n. x_k is the coefficient of a^k in the polynomial
obtained by expanding the base-a level-2 complete
hereditary representation of n.)
r.e.s.
> Here's the most concise recursion I've managed to write
> for g_2 with initial base a ...
>
> g_2(n) = b_(floor(log_a(n+1))) - 2 (n >= 0)
g_2(n) = b_(floor(log_a(n)+1)) - 2 (n > 0)
CH
question?
r.e.s.: I wrote a set of equations for all k,n and base (took me almost
two hours) when I suffered a power outage! If I find time to rewrite it
I'll post it here. Why don't you try to write the general equation?
r.e.s.
> I wrote a set of equations for all k,n and base (took me almost
> two hours) when I suffered a power outage! If I find time to rewrite it
> I'll post it here. Why don't you try to write the general equation?
Of course the general definition, given in my posting last year,
of g_k (the level-k Goodstein function for Goodstein sequences
with initial base a) *is* a set of recursive equations. It would
be nice to see it recast in a form that gives more insight into
growth rates, but I don't see how to do that for general k.
For readers' benefit, it's probably worth reminding that the
level-k Goodstein *function* g_k, for an initial base of a,
is defined as the number of positive terms in the corresponding
Goodstein *sequence* G(a)(=n),G(a+1),G(a+2),...,G(b)=0. Thus
g_k(n) = b - a, where b is the least b such that G(b)=0.
Which reminds *me* to correct an error in the recursion for g_2
that I just posted (I'd subtracted 2 instead of a) ...
-----
g_2(n) = b_(p+1) - a (n > 0)
p = floor(log_a(n))
b_0 = a
b_(k+1) = f_k ^ x_k (b_k)
f_0 (t) = t + 1
f_(k+1) (t) = f_k ^ (t+1) (t)
x_0 = n % a
x_(k+1) = ( (n - sum(a^i*x_i, i=0..k)) / a^k ) % a
(x_k is the coefficient of a^k in the polynomial obtained by
expanding the base-a level-2 representation of n, and a^p is
the highest power of a in that polynomial.)
---
The recursion can also be written as follows ...
g_2(n) = f_p^x_p f_(p-1)^x_(p-1) ... f_0^x_0 a - a
where many parentheses have been omitted for readability.
(Read the iterated f's as operators associating from the
right.) Since 0 <= x_k < a, it follows readily that
f_p a <= g_2 n < f_(p+1) a
and hence that g_2 ~ f_w -- i.e. the same growth rate as the
(diagonalised) Ackermann function, just as CH claimed.
CH
r.e.s. wrote:
> "CH" <cchh...@Yahoo.co.uk> wrote ...
> > I wrote a set of equations for all k,n and base (took me almost
> > two hours) when I suffered a power outage! If I find time to rewrite it
> > I'll post it here. Why don't you try to write the general equation?
>
> Of course the general definition, given in my posting last year,
> of g_k (the level-k Goodstein function for Goodstein sequences
> with initial base a) *is* a set of recursive equations. It would
> be nice to see it recast in a form that gives more insight into
> growth rates, but I don't see how to do that for general k.
By "set of equations" I didn't mean "set" in the literal sense.
g_k(n) base= G(k,n,base)
G(k,n,b)=G(k,F(n,b+1,b,b,k,k),b+1)
F(x,y,z,b,i,o)=if(x<b)then(x)else(
if(z<>x)then(
F(x,Ack(y,i,F(H(x,z,i,0),b+1,b,b,o,o)),Ack(z,i,H(x,z,i,0)),b,i-1,o)
)else(y)
)
Ack(x,y,z)=if(y=1)then(x+z)else(
if(z=1)then(x)else( Ack(x,y-1,Ack(x,y,z-1)) )
)
H(a,x,y,i)=if(Ack(x,y,i)>a)then(-1)(else(1+H(a,x,y,i+1))
H(a,x,y,0) is the inverse of Ack(x,y,z) e.i.
z=floor(H(a,x,y,0)) a=Ack(x,y,z)
for g_3(27) 2 it will start:
y_27=(3^y_4)*y_1+y_11
z_27=(2^4)*1+11
y_11=(3^y_3)*y_1+y_3
z_11=(2^3)*1+3
y_4=(3^y_2)*y_1+0
z_4=(2^2)*1+0
y_3=(3^1)*y_1+y_1
z_3=(2^1)*1+1
y_2=(3^1)*y_1+0
z_2=(2^1)*1+0
y_1=1
z_1=1
Hopefuly I got everything right this time.
Deedlit
reply to
======================================================================
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.")
======================================================================
This looks like a pretty hard question, but I can answer #4 at least:
after epsilon_0, the Knuth arrow notation kind of stalls, at least
using the obvious definition:
a [b + 1] c + 1 = a [b] (a [b + 1] c)
a [b + 1] c = sup_{d < c} {a [b + 1] d} for limit c
a [b] c + 1 = sup_{d < b} a [d] (a [b] c) for limit b
a [b] c = sup_{d < c} {a [b] d} for limit b, c.
For a < epsilon_0, this leads to a^^c = epsilon_0 for all c >= omega,
which immediately implies that a [b] c = epsilon_0 for all omega <= a <
epsilon_0, b > 2, c > 1.
Doner and Tarski defined a different hierarchy of operators by
a [b + 1] c + 1 = (a [b + 1] c) [b] c.
You can find their paper on the web, along with followup papers by
Rubin and Rubin (I think). Since this is slower growing for the
natural numbers, you would imagine that this is slower growing for the
transfinite ordinals as well, and in fact it is, somewhat. But the key
point is that it doesn't stall at epsilon_0. Basically for a, b, c <
gamma_0, we have a [b] c < gamma_0.
For #2, I'm sure that g_a < f_Gamma_0, in fact it seems likely to me
that g_a doesn't grow faster than phi_a. I'm not sure whether it
actually grows that fast, or slower.
Robert, do you have an electronic copy of the Goodstein paper? It
sounds like an interesting read. I take it that he defines an ordinal
notation with the higher Knuth arrows (although I guess this predates
Knuth) and uses it to prove termination of the higher level Goodstein
functions.
r.e.s.
["r.e.s." wrote (in part) ...]
>> 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?
> I can answer #4 at least:
> after epsilon_0, the Knuth arrow notation kind of stalls, at least
> using the obvious definition:
>
> a [b + 1] c + 1 = a [b] (a [b + 1] c)
> a [b + 1] c = sup_{d < c} {a [b + 1] d} for limit c
> a [b] c + 1 = sup_{d < b} a [d] (a [b] c) for limit b
> a [b] c = sup_{d < c} {a [b] d} for limit b, c.
>
> For a < epsilon_0, this leads to a^^c = epsilon_0 for all c >= omega,
> which immediately implies that a [b] c = epsilon_0 for all omega <= a <
> epsilon_0, b > 2, c > 1.
Given that there is such a "stalling" at epsilon_0 (I haven't yet
worked that out for myself), I think it's not possible that the above
definition corresponds to Goodstein's ordinals of form w[k]w.
To explain this -- and I hope my explanations are not too verbose --
more needs to be said about the context relative to the following
two papers:
R. L. Goodstein, "On the Restricted Ordinal Theorem",
J. Symb. Logic, v9, n2, 33-41, 1944.
R. L. Goodstein, "Transfinite Ordinals in Recursive Number Theory",
J. Symb. Logic, v12, n4, 123-129, 1947.
The 1944 paper introduced a "majorant variable" formulation of
ordinals that (a) involved only one variable, w, and so were later
called "Type 1", and (b) involved only the three operations +,*,^
(and so were at level 3 in the hierarchy +,*,^,^^,^^^,...). These
ordinals are all less than epsilon_0.
The 1947 paper extended the first formulation in two ways --
(a) to "Type n" for n=1,2,3,..., i.e. with expressions in n majorant
variables (w and others), and (b) to any finite level k in the
hierarchy +,*,^,^^,^^^,...
(NB: Goodstein was a finitist, whose stated purpose was to define a
"numerical equivalent" to transfinite ordinals, without reference to
infinite sets -- hence the use of majorant variables.)
What I've been calling "level-k" Goodstein sequences appeared in the
1947 paper in connection with Type-1 level-k ordinals. If I'm
correct in my reading of that paper, these are (for k > 3) the
simplest of Goodstein's ordinals that go beyond epsilon_0:
Definition: A Type-1 level-k ordinal is the expression obtained
by substituting the majorant variable w for the base in a level-k
base-b complete hereditary representation of a nonnegative integer.
Now a relation Rel(w), in just the one majorant variable w, holds
iff there's an integer I such that for every integer i > I, Rel(i)
holds. Consequently, for Goodstein ordinals w^^w and w^^^w, we have
w^^w < w^^^w, because i^^i < i^^^i for every integer i > 2.
So the gist of question #4 is evidently which set-theoretic ordinals
agree with Goodstein's non-set-theoretic ordinals. ISTM that the
set-theoretic ordinal corresponding to Goodstein's w[k+1]w will be
the least such ordinal not expressible (in set-theoretic terms) as
w[k]w[k]...w[k]w with finitely-many w's. That's why I "equated"
w^^w and epsilon_0 -- *not* because Goodstein's w^^w is a fixed point
of a |--> w^a (it isn't; the relation a = w^a cannot hold in majorant
variables w,a). It's simply that w^^w is apparently the least
Goodstein ordinal not expressible at level 3, just as epsilon_0 is
the least set-theoretic ordinal not expressible in Cantor normal form
using only +,*,^.
One last point ... My notation a[k]n is just an abbreviation for
Goodstein's G(k,a,n), introduced in the 1947 paper as follows
(pp.128-129):
"We define, for k >= 0, a >= 0, n >= 0
G(0,a,n) = n+1,
G(1,a,0) = a,
G(2,a,0) = 0,
G(k+3,a,0) = 1,
G(k+1,a,n+1) = G(k,a,G(k+1,a,n))."
"Then G(1,a,n) = a+n, G(2,a,n) = na, G(3,a,n) = a^n
(proof by induction), so that for k = 1,2,3, the
function G(k,a,n) defines addition, multiplication,
and exponentiation. For k >= 4, G(k,a,n) defines
successive new processes (which we will call
tetration, pentation, hexation, and so on)."
(Aside: Did Goodstein here coin the term /tetration/, etc.?)
In particular, Goodstein did not extend this recursive definition of
G (i.e. the a[k]n) to arguments other than integers. The reason for
not doing so is simply that his transfinite ordinals are obtained by
substituting majorant variables into hereditary representations
involving G only with integer arguments -- and a relation between
two such ordinals is then determined, via the majorant variables,
entirely by evaluations of G with integer arguments.
> Doner and Tarski defined a different hierarchy of operators by
>
> a [b + 1] c + 1 = (a [b + 1] c) [b] c.
>
> You can find their paper on the web, along with followup papers by
> Rubin and Rubin (I think). Since this is slower growing for the
> natural numbers, you would imagine that this is slower growing for the
> transfinite ordinals as well, and in fact it is, somewhat. But the key
> point is that it doesn't stall at epsilon_0. Basically for a, b, c <
> gamma_0, we have a [b] c < gamma_0.
I'll try to check out those papers -- I see that David Renfro also
discussed some of this with you in the thread
"My number is bigger than yours." (February 11, 2002)
http://mathforum.org/kb/thread.jspa?messageID=358519
> For #2, I'm sure that g_a < f_Gamma_0, in fact it seems likely to me
> that g_a doesn't grow faster than phi_a. I'm not sure whether it
> actually grows that fast, or slower.
That's unclear to me -- each g_a ranges over integers, whereas each
phi_a (when a > 0) ranges over infinite ordinals only. (I'm supposing
your phi_a refers to the normal functions phi_0(b) = w^b, and phi_a
for a > 0 enumerates the common fixed points of phi_c for all c < a.)
> Robert, do you have an electronic copy of the Goodstein paper? It
> sounds like an interesting read. I take it that he defines an ordinal
> notation with the higher Knuth arrows (although I guess this predates
> Knuth) and uses it to prove termination of the higher level Goodstein
> functions.
Sorry, I have only hardcopy. I notice, though, that the first page
of the 1947 paper is freely available at
http://links.jstor.org/sici?sici=0022-4812(194712)12%3A4%3C123%3ATOIRNT%3E2.0.CO%3B2-E
(there you can at least see how majorant variables are used, etc).
BTW, I think most authors use the term "Goodstein sequence" in
reference to the bump-the-base-and-decrement sequences that
eventually must reach 0, and reserve the term "Goodstein function"
for the function whose value at argument n is the number of positive
terms in the Goodstein sequence that starts with n. (Of course
they're all sequences, which are functions.)
The 1947 paper was not concerned with proving that every Goodstein
sequence terminates, but rather it proved
"that the decreasing ordinal theorem, which asserts that
a sequence of decreasing ordinals terminates, is, for
ordinals of any type, equivalent to a number-theoretic
proposition." (p.128)
--r.e.s.
Michael Press
<UiiVg.5544$Y24....@newsread4.news.pas.earthlink.net>,
"r.e.s." <r...@ZZmindspring.com> wrote:
> BTW, I think most authors use the term "Goodstein sequence" in
> reference to the bump-the-base-and-decrement sequences that
> eventually must reach 0, and reserve the term "Goodstein function"
> for the function whose value at argument n is the number of positive
> terms in the Goodstein sequence that starts with n. (Of course
> they're all sequences, which are functions.)
The values of the Goodstein function get large as the
argument is incremented. How is the rate of growth
characterized? How does it compare with other rapidly
growing sequences? Is there a faster growing sequence that
is as easily described as is the Goodstein function?
--
Michael Press
r.e.s.
> "r.e.s." <r...@ZZmindspring.com> wrote:
>
>> BTW, I think most authors use the term "Goodstein sequence" in
>> reference to the bump-the-base-and-decrement sequences that
>> eventually must reach 0, and reserve the term "Goodstein function"
>> for the function whose value at argument n is the number of positive
>> terms in the Goodstein sequence that starts with n. (Of course
>> they're all sequences, which are functions.)
>
> The values of the Goodstein function get large as the
> argument is incremented. How is the rate of growth
> characterized? How does it compare with other rapidly
> growing sequences?
The only Goodstein function that's commonly discussed is g_3,
for which g_3 ~ f_epsilon_0 relative to the Wainer hierarchy.
As far as I know, it has not been proved whether or not any of
the higher-level Goodstein functions g_k grow faster than that.
(BTW, it's the g_k for 0 < k < w that were defined by Goodstein
-- I defined g_w by diagonalising in the obvious way.)
> Is there a faster growing sequence that is as easily described
> as is the Goodstein function?
Friedman's TREE(), or Fr() as Gallier calls it, grows faster than
f_Gamma_0. Its definition involves a particular homeomorphic
embedding relation for finite trees. Some relevant articles:
"Finite Trees and the Necessary Use of Large Cardinals"
among Harvey Friedman's manuscripts at
http://www.math.ohio-state.edu/%7Efriedman/manuscripts.html
and in various articles in the FOM archives, e.g,
http://www.cs.nyu.edu/pipermail/fom/2006-March/010279.html
"What's so Special about Kruskal's Theorem and the Ordinal Gamma_0?"
among the writings by Jean Gallier at
http://www.cis.upenn.edu/~jean/gallier-old-pubs.html
(Gallier's article is the best discussion of Gamma_0 that I've
managed to find online.)
Michael Press
<R%OVg.4238$Lv3....@newsread1.news.pas.earthlink.net>,
"r.e.s." <r...@ZZmindspring.com> wrote:
Thanks, I will look into them. I should have said that I
am speaking of the bump-the-base-and-decrement progression
and f(n) = the number of non-zero elements in the
progression starting at (n)-base 2.
--
Michael Press
r.e.s.
>> g_3 ~ f_epsilon_0 relative to the Wainer hierarchy.
>> As far as I know, it has not been proved whether or not any of
>> the higher-level Goodstein functions g_k grow faster than that.
I should add that I certainly do expect g_(k+1) to eventually
dominate ("grow faster than") g_k, for every integer k > 0.
"Michael Press" <ja...@abc.net> wrote ...
>>> Is there a faster growing sequence that is as easily described
>>> as is the Goodstein function?
[and then added ...]
> I should have said that I am speaking of the bump-the-base-
> and-decrement progression and f(n) = the number of non-zero
> elements in the progression starting at (n)-base 2.
You haven't said what level of representation is used for the
numbers in the bump-the-base-and-decrement progressions. If
you have in mind just the usual level-3 representations (i.e.,
using only the three operations +,*,^) -- for example as at
http://mathworld.wolfram.com/GoodsteinSequence.html
-- then f = g_3 = the level-3 Goodstein function, whose growth
rate should be far exceeded by g_4 (i.e. with representations
using the four operations +,*,^,^^). More generally, f = g_k,
where k is the level of representation, and g_(k+1) should
grow much faster than g_k.
(Your question also hasn't excluded noncomputable sequences,
some of which -- e.g. "Busy Beaver" functions -- grow faster
than *every* computable sequence.)
--r.e.s.