LARGE NUMBERS--The Gloves Come Off!
Dave L. Renfro
[sci.math 22 Dec 1999 20:54:41 GMT]
<http://forum.swarthmore.edu/epigone/sci.math/vorkhahthax>
WROTE
############################################################
>Are you telling me that Ackermann(100)
>is greater than say
>100^(100^(100^(100...^100)))
>for say 100 iterations of exponentiation?
>
>I am very interested in this Ackermann
>function. Could you walk me thru step by
>step in a calculation of say Ackermann(3)
>using letters X,Y, Z etc. to denote large
>numbers if the actual calculated numbers
>get " to large to write " ?
############################################################
AND
Dave Seaman <a...@seaman.cc.purdue.edu>
[sci.math 22 Dec 1999 17:11:56 -0500]
<http://forum.swarthmore.edu/epigone/sci.math/vorkhahthax>
WROTE IN RESPONSE TO THIS (in part)
############################################################
>The ackermann function takes two arguments.
>Here is a lisp implementation, complete with comments.
>
>Notice that your number is g(3,100,100) in the
>notation used here.
>
>#|
>*****************************************************
>
>Definition of Ackermann's function:
>
> f(0,y) = y + 1
> f(x+1,0) = f(x,1)
> f(x+1,y+1) = f(x,f(x+1,y))
>
>Definition of Ackermann's generalized exponential:
>
> (informally:)
>
> g(0,x,y) = y + x
> g(1,x,y) = y * x
> g(2,x,y) = y^x
> g(3,x,y) = y^^x = y^y^...^y (x times)
> (etc.)
>
> (formally:)
>
> g(0,0,y) = y
> g(0,x+1,y) = g(0,x,y) + 1
> g(1,0,y) = 0
> g(z+2,0,y) = 1
> g(z+1,x+1,y) = g(z,g(z+1,x,y),y)
>
>Relation of Ackermann's function to Ackermann's
>generalized exponential:
>
> f(1,y) = 2 + (y+3) - 3 = y + 2
> f(2,y) = 2 * (y+3) - 3 = 2*y + 3
> f(3,y) = 2 ^ (y+3) - 3
> f(4,y) = 2 ^^ (y+3) - 3
> (etc.)
>
>And in general:
>
> f(x+1,y) = g(x,y+3,2) - 3
############################################################
I've posted in sci.math a huge amount of information
related to iterated exponentiation and higher order
operations, along with dozens of references on the
internet and published papers.
See the following ----->>>>>
Progression of operators? [Sept. 3, 1999]
<http://forum.swarthmore.edu/epigone/sci.math/frunyixblou>
Re: Progression of operators? (expanded answer)
[3 POSTS: Sept. 5, 1999, Sept. 5, 1999, Sept. 6, 1999]
<http://forum.swarthmore.edu/epigone/sci.math/rurerdshul>
Problems in (0,1/e) [Sept. 9, 1999]
<http://forum.swarthmore.edu/epigone/sci.math/ranbrelbrel>
In the first post mentioned above, for instance, I discussed
numbers that make anything I've seen posted so far under the
thread "Re: WORLD'S LARGEST NUMBER" pale into insignificance
(except for the Busy Beaver function). I didn't get much
response at all from that post, at least regarding what I
thought were the more interesting aspects of it. Perhaps I
was a bit brief and hurried in some of my comments there
and the significance escaped those for whom the material
isn't well-known. With this in mind, what follows is a
rather lengthy discussion of "concise" ways to obtain
*really large* numbers. My intent is to provide some
background for two of my posts above, the one dated Sept. 3
and the one dated Sept. 5 (the one that has a "received date"
of 4 Sep 99 20:43:48 -0400), and for the web pages and
published papers that I provide in those posts.
OX2X's 100 iterations of exponentiated 100's,
100^(100^(100^(100...^100))), is "essentially" the same
as 100 iterations of exponentiated 10's. In any event,
it's MUCH less than 101 iterations of exponentiated 10's.
In fact, each (the tower of 100 100's and the tower of
100 10's) is "essentially" the same as f(4,97), which
is 3 less than 100 iterations of exponentiated 2's, and
MUCH less than f(4,98). [See Seaman's notation for Ackermann's
function, given above.]
Since 10 has a more popular appeal, and since my present
discussion is aimed in that direction, I'll stick with
"base 10" in the following. Also, by x^x^x^x I mean
x^(x^(x^x)), and similarly for other towers of powers.
A large number is
10^10^ ... ^10 [100 times].
Larger still is
10^10^ ... ^10 [1000 times].
REALLY huge is
10^10^ ... ^10 [10^10 times].
Oh, heck, now that we've broken down and begun to use
exponential notation to describe the tower height, we
can consider this ----->>>>>
10^10^ ... ^10 [ 10^10^ ... ^10 [100 times] ].
Or, for that matter, this ----->>>>>
10^10^ ... ^10 [ 10^10^ ... ^10 [1000 times] ].
Or maybe this (!?!) ----->>>>
10^10^ ... ^10 [ 10^10^ ... ^10 [10^10 times] ].
Ah, now I've gone and done it! I've used exponential
notation to describe the height of the tower that describes
the height of the tower. So I may as well jump to
10^10^ ... ^10 [ 10^10^ ... ^10 [10^10^ ... ^10 [10 times]]].
Well, you can see where this is going--after a while, you're
going to be dealing with expressions in which you'll have to
count the number of brackets in order to make comparisons:
10^10^ ... ^10 [ 10^10^ ... ^10 [10 times] ]
<--------------- 2 brackets ----------------->
10^10^ ... ^10 [ 10^10^ ... ^10 [10^10^ ... ^10 [10 times]]]
<---------------------- 3 brackets ------------------------>
With this method of description we can now consider these
monsters:
10^10^ ... ^10 [ ... [10 times] ... ]
<----------- 10 brackets ----------->
10^10^ ... ^10 [ ... [10 times] ... ]
<----------- 100 brackets ---------->
10^10^ ... ^10 [ ... [10 times] ... ]
<---------- 10^10 brackets --------->
Graham's number, mentioned in some of the other posts in the
thread "Re: WORLD'S LARGEST NUMBER", and mentioned in some
of the links you can find in the posts of mine I mentioned
above, is (I think)
3^3^ ... ^3 [ ... [3^3^3^3^3 times] ... ]
<------------ 65 brackets -------------->
Taking a deep breath, we continue . . .
10^10^ ... ^10 [ ... [10 times] ... ]
<---- 10^10^ ... ^10 [10 times] brackets ---->
10^10^ ... ^10 [ ... [10 times] ... ]
<----- 10^10^ ... ^10 [10^10 times] brackets ---->
10^10^ ... ^10 [ ... [10 times] ... ]
<--- 10^10^ ... ^10 [10^10^ ... ^10 [10 times]] brackets --->
Hummm... It's looking as if I might run into notational
problems again, but this time in describing the number of
brackets. Well, I guess I'll have to use "bracket descriptions"
to describe the number of brackets!
10^10^ ... ^10 [ ... [10 times] ... ]
<--- 10^10^ ... ^10 [ ... [10 times] ... ] brackets --->
<----- 10 brackets ----->
10^10^ ... ^10 [ ... [10 times] ... ]
<--- 10^10^ ... ^10 [ ... [10 times] ... ] brackets --->
<----- 10^10 brackets ----->
10^10^ ... ^10 [ ... [10 times] ... ]
<--- 10^10^ ... ^10 [ ... [10 times] ... ] brackets --->
<----- 10^10^ ... ^10 [10 times] brackets ----->
To speed things up, let's skip the obvious. Clearly, I'll
soon find myself having to count the number of ROWS of
bracket descriptions. For instance,
--- 10^10^ ... ^10 [ ... [10 times] ... ]
|
| <-- 10^10^ ... ^10 [ ... [10 times] ... ] brackets -->
|
| *
| * [[ 10 rows ]]
| *
|
| <----- 10 brackets ----->
---
Next, we could consider 100 rows, then 10^10 rows, then
10^10^ ... ^10 [10 times] rows, etc. Then we'll resort
to bracket notation to describe the number of rows, then
to a counting of the number of brackets needed to count the
number of rows. Eventually, we're going to be using
rows to count the number of rows! And if the number of
rows of rows gets too big, we'll need to begin a 3'rd
column that counts the rows of the rows. Then we'll
begin using brackets to count the rows of rows, after
which comes rows to describe the number of rows of rows.
O-K, so then what? Well, I've just mentioned numbers that
use rows to describe them, then rows of rows to describe
them, and the last alludes to numbers requiring rows of
rows of rows to describe them. Speeding things up, we see
that we'll have to begin counting the number of row iterations!
Call each row iteration a "column". Then we'll have numbers
requiring 10 columns, 10^10 columns, 10^10^ ... ^10 [10 times]
columns, etc. We'll have to use brackets to count the columns,
then use rows to count the columns, ...
Eventually, we'll have to start *another column* to
count the number of columns! And if you keep going, you'll
have to introduce "super-rows" to keep a count of the
number of columns you start up.
Notice the progression: ^ times, brackets, rows, columns, ...
If you *REALLY* want to get some large numbers, then
you might want to begin counting the number of "notational
changes" needed in order to describe the number. By
notational change, I mean (for instance) going from
using bracket notation only to using rows. Thus, to get
from 10^10 to the last number I described explicitly
(it's more like a picture of the number) requires 3
notational changes. [Note that 10^10 doesn't even use
the "^ times" notation.]
Here's the connection with Ackermann's function.
f(4,y) is "essentially" 10^10^ ... ^10 [y+3 times]
f(5,y) is "essentially" y+3 brackets utilized
f(6,y) is "essentially" y+3 rows utilized
f(7,y) is "essentially" y+3 columns utilized
f(8,y) is "essentially" y+3 super-rows utilized
With this notation we can consider numbers such as:
f(10,10)
f(10^10, 10)
f( 10^10^ ... ^10 [10 times], 10 )
f( f(10,10), 10 )
f( f(10^10, 10), 10 )
f( f(10^10^ ... ^10 [10 times], 10), 10 )
f( f(f(10,10), 10), 10 )
Eventually we're going to have to begin keeping careful
track of the number of times we've nested the Ackermann
function! There's a more efficient way to proceed that
proof theorists use. They employ a certain ordinal indexed
sequence of functions from the positive integers into
the positive integers. Roughly, their f_n is f(n,*) and
their f_w is f(n,n). [w represents the smallest infinite
ordinal.] Their f_{w+1} is roughly the level at which one
counts the number of iterations of Ackermann's function
you employ. For instance, the image of 3 under f_{w+1} is
f( f(f(10,10), 10), 10 ) and the image of 4 under f_{w+1} is
f( f( f(f(10,10), 10), 10 ), 10 ).
[Note: For simplicity, I'm taking these to be one-variable
functions. I don't recall if they're one-variable or
two-variable in the literature. But for the purposes in
which they're used (to measure the logical strength of
weak axiomatic theories) and, for that matter, for
the purpose that I'm using them (to efficiently describe
extremely large numbers), it doesn't make any difference.]
Of course, we could consider f_{w+1} evaluated at 10, or
evaluated at 10^10, or evaluated at any of the numbers
thus far described. You can even evaluate f_{w+1} at
the image of f_{w+1} of 4, or at the image of f_{w+1} of 10,
etc. The next step is to evaluate f_{w+1} at the image
of f_{w+1} of f_{w+1} of 10, and similarly, where you're
considering various numbers of nestings of f_{w+1}.
The function f_{w+2} *very roughly* involves counting
the number of nestings of f_{w+1}, in the same way that
f_{w+1} *very roughly* involves counting the number of
nestings of the Ackermann function. [This is exactly
analogous to exponentiation being a way of keeping track
of the number of multiplications, multiplication being
a way of keeping track of the number of additions, and
addition being a way of keeping track of the number of
applications of the successor function.]
At this point it becomes (I hope!) roughly clear what
f_{w+3}, f_{w+10}, f_{w+10^10}, and
f_{w + 10^10^ ... ^10 [10 times] } mean.
In the same way that f_w (roughly, Ackermann's function)
represents a diagonalization over all the f_n functions
for n < w [i.e. (f_w)(n) = (f_n)(n) ], we can define
a function f_{2w} by diagonalizing over all the f_{w+n}
functions:
(f_{2w}) (n) = (f_{w+n}) (n).
Trying to describe, say, the number (f_{2w}) (10) by making
use of the Ackermann function is somewhat like trying to
describe the number f(10,10) [using Seamen's notation] by
using only the successor function.
Now we can consider f_{2w+1}--obtained by iterating the function
f_{2w}, f_{2w+2}--obtained by iterating the function f_{2w+1},
and so on. The function f_{3w} is defined by diagonalizing
over all the f_{2w+n} functions:
(f_{3w}) (n) = (f_{2w+n}) (n).
In a similar way one can obtain the functions f_{4w},
f_{5w}, etc. The function f_{w^2} is defined by diagonalizing
over all the f_{nw} functions:
(f_{w^2}) (n) = (f_{nw}) (n).
Those familiar with ordinal numbers can see where
I'm going with this. You use an iteration of the function
at the previous level to take care of the successor ordinal
step and you use diagonalization to take care of the
limit ordinal steps. Note that you can't just say "use
transfinite induction", since you'll get *different*
functions at the limit stages, according to which
fundamental sequence you use to represent that limit
ordinal. For example, (f_{nw+n}) (n) IS NOT THE SAME
NUMBER AS (f_{nw}) (n). Therefore, by choosing to represent
w^2 as sup{w, 2w, 3w, ...}, we get a different function than
if we were to represent w^2 as sup{w+1, 2w+2, 3w+3, ...}.
For that matter, you will not get f_w if you diagonalize
over the functions f_2, f_4, f_6, ... . However, it can
be shown that (at least, for any of the *recursive* ordinals
I'll be dealing with) all the various functions you get by
diagonalizing over various fundamental sequences
representing a particular limit ordinal will have
"essentially the same growth rate". In particular, all
of them will grow much faster than any of the functions
corresponding to smaller ordinals (this half is trivial)
and all of them will grow much slower than any of the
functions obtained by an iteration of any of the limit
ordinal variations.
So now we can get functions corresponding to ordinals such
as w^3, w^4, w^w, w^(3w^2 - 2w + 7), w^(w^w), ...
After a while we'll arrive at the function f_{epsilon_0},
where epsilon_0 represents an w-tower of w's:
epsilon_0 = sup{w, w^w, w^(w^w), w^(w^(w^w)), ...}.
Are these functions ever used in math? Well, f_w represents
the slowest growing function in this scale that is not
a primitive recursive function. The function f_{w^w} is
the slowest growing function in this scale that doesn't
belong to the class of multiply recursive functions.
[Ackermann's function is a doubly recursive function.
In 1936, R. Peter formulated and studied the more general
classes of k-recursive functions for k = 1, 2, 3, ...]
The function f_{epsilon_0} is the first of these functions
(all of which are recursive) that isn't provably
recursive in Peano Arithmetic (PA). [More precisely,
G. Kreisel proved in 1952 that every PA-provably recursive
function of one variable is eventually dominated by f_a for
some a < epsilon_0. Conversely, Godel (1958), Kreisel (1959),
and Tait (1959) proved that f_a is PA-provably recursive
for each a < epsilon_0.] The numerical function associated
with Goodstein sequences grows at essentially the same
rate that f_{epsilon_0} does. [This was proved in L. Kirby
and J. Paris in 1982. For introductory discussions on
Goodstein sequences (introduced by R. L. Goodstein in
1944), see pp. 124-126 in the 3'rd edition of Karel
Hrbacek and Thomas Jech, INTRODUCTION TO SET THEORY, 1999
AND around p. 135 in James Henle, AN OUTLINE OF SET THEORY,
1986.]
There is a way to quickly reach way past f_{epsilon_0}. What
you do is extend the functions f_a, from the positive integers
to the positive integers, so that they are functions from
the countable ordinals to the countable ordinals. This
is not difficult using transfinite induction. In this
case, it is more convenient to switch to a "base w"
formulation. In what follows, whenever an f_a function
is used to obtain infinite ordinals I will be using a
base w formulation. However, you'll have to switch back
to a base 10 formulation (or some finite base; Ackermann's
function as given by Seaman is actually a diagonalization
over f_n's using a base 2 formulation) when you want to
use the f_a's to generate LARGE finite numbers.
With this said, we have epsilon_0 = (f_4)(w). I believe that
epsilon_0 is also equal to (f_5)(w). That is,
sup{w, w^w, w^w^w, ...} = w^w^ ... [w times]
= sup { w^w^ ... [w times], w^w^ ... [epsilon_0 times],
w^w^ ... [w^w^ ... [epsilon_0 times]], ... }.
However, when you use f_6 you can get larger ordinals.
I think [This is coming from a 1969 Fund. Math. paper by
John Doner and Alfred Tarski that I worked through the details
of about 8 years ago.] that the b'th epsilon number (i.e. the
b'th fixed point of the map a |---> w^a) is given by
(f_6)( (1+b)w ). I believe that the smallest epsilon number
b that has the property that b is the b'th epsilon number
is given by (f_7)(w). [Note: The map a |---> epsilon_a is
a normal function, so there *will* be fixed points.]
You can generate some really huge countable ordinals by
considering things like (f_10)(w), (f_{10^10}) (w), etc.
In fact, you can even consider
(f_w)(w) = sup{ (f_1)(w), (f_2)(w), (f_3)(w), ... }.
Of course, there's nothing to stop us from looking at
(f_{w^w}) (w),
(f_{epsilon_0}) (w),
(f_{(f_{w^w}) (w)}) (w),
and so on. Are we finished with applications to mathematics?
No, not by a long shot. The function a |---> (f_a)(w) is
a normal function from the countable ordinals to the
countable ordinals. Hence, it will have a fixed point.
[In fact, it will have a cofinal-in-w_1 set of fixed points.]
The smallest solution to (f_a)(a) = a is usually denoted
by Gamma_0 ("capital" gamma with subscript of 0).
Gamma_0 is so far beyond anything I've described thus
far that it would be an injustice to compare it to the
things like (f_{(f_{w^w}) (w)}) (w).
In a certain sense Gamma_0 represents the upper bound
on what you can obtain by iterating everything done thus
far to countable ordinals. The only way to reach Gamma_0
is to use at least the (Gamma_0)'th operation or to input
an ordinal at least as large as Gamma_0! That is, if you pick
ordinals a and b, both less than Gamma_0, then (f_a)(b)
will be less than Gamma_0. You just can't reach Gamma_0
without using Gamma_0, at least with the tools used up
to this point.
Tarski/Donner don't mention Gamma_0 in their 1969 paper,
but those interested will want to look at the following.
(In particular, Gallier's paper requires very little
background compared to the typical papers in this field.)
Hilbert Levitz, "On the Finsler and Donner-Tarski arithmetical
hierarchies", Comment. Math. Helvetici 44 (1969), 89-92.
J. H. Gallier, "What's so special about Kruskal's theorem
and the ordinal $\Gamma_0$? A survey of results in
proof theory", Annals of Pure and Applied Logic 53 (1991),
199-260. [See also "Erratum to ...", 89 (1997), 275.]
Besides other relatively well-known work along these
lines [E. Jacobstahl (1909), P. Finsler (1951),
H. Bachmann (1952), H. Levitz, etc.], I recently came
across an unknown to me book in the Iowa State Univ.
library that seems very much related to the ideas
in the Donner/Tarski paper. [DT, I believe, was written
without the knowledge of Finsler, Bachmann, and Levitz's
similar work.]
Uuno Saarnio, "DAS SYSTEM UND DIE DARSTELLUNG DER
TRANSFINITEN ORDNUNGSZAHLEN MIT HILFE DER HOHEREN
RECHENOPERATIONEN, Gesellschaft fur Logik und ihre
Anwendungen, Helsinki, 1958.
[Iowa State Univ. QA 248 Sal 2s]
Since I don't read German, I can't comment about its
contents with any assurance. Does anyone happen to
know anything about this book? It wasn't reviewed
by Zbl <http://www.emis.de/ZMATH/en/zmath.html>
that I can determine, and I don't know if it was
reviewed by MR.
In 1980 (published in 1982) H. Friedman, K. McAloon, and
S. Simpson published a finite combinatorial analog of
a well-known Ramsey-type result by F. Galvin (yep, sci.math's
Fred) and K. Prikry that gives rise to a function which
grows at least as fast as f_{Gamma_0}. [I imagine that it's
growth rate has been precisely pinned down by now, but off-hand
I don't know anything more.]
Functions from the natural numbers to the natural numbers
which grow much faster than f_{Gamma_0} also appear
in the literature. See some of the web pages I cite in
my earlier posts, whose links I gave near the beginning
of the present post.
Of course, to get further along the f_a scale of functions
requires ordinals larger than Gamma_0. We could add 1,
multiply by w (in the manner that represents Gamma_0
added to itself w-times; by a historical accident, in the
literature one often finds a+a+... [w-times] written as
w*a rather than the a*w notation I've employed), etc.
However, this doesn't get you very far in a certain sense.
Better would be to look at other fixed points of the
map a |---> (f_a)(a). The next one, Gamma_1, is MUCH MUCH
larger than Gamma_0. Then there is Gamma_2, Gamma_3, etc.
The ordinal Gamma_w = sup{Gamma_0, Gamma_1, Gamma_2, ...}
is also a fixed point (even if it wasn't, taking sup's
would give us a way to leap-frog past all the Gamma_n's),
and so on. Because the fixed points of a normal function,
when ordered in their natural ordering, give rise to a
another normal function, we can look at *its* fixed points.
Thus, we have Gamma_0, Gamma_1, ..., Gamma_w, ...,
Gamma_{w^w}, ..., Gamma_{epsilon_0}, ..., Gamma_{epsilon_w},
..., Gamma_{ (f_{(f_{w^w}) (w)}) (w) }, ...,
Gamma_{Gamma_0}, ..., Gamma_{Gamma_w}, ..., (hold your breath)
Gamma_{Gamma_{Gamma_0}}, ...
Eventually, you'll get to an ordinal g such that
Gamma_g = g. In fact, it will be this ordinal:
sup{ Gamma_0, Gamma_{Gamma_0}, Gamma_{Gamma_{Gamma_0}}, ...}.
Let's call the b'th fixed point of a |---> Gamma_a
Gamma_{(1,b)}. [I'm thinking that we might want
Gamma_{(0,b)} to be another name for Gamma_b.]
The map a |---> Gamma_{(1,a)} will itself have
fixed points. Call the b'th fixed point of *this* map
Gamma_{(2,b)}. Continue in this way, obtaining fixed points of
fixed points of fixed points ...
Can we leap-frog past all of this? Yes, just take the
supremum of {Gamma_{(1,0)}, Gamma_{(2,0)}, Gamma_{(3,0)}, ...}.
Let's call this Gamma_{(w,0)}. Then the b'th fixed point
of the map a |---> Gamma{(w,a)} can be denoted by
Gamma_{(w+1,b)}. Continuing in this manner, you'll get
Gamma_{(w+2,0)},
Gamma_{(w+10^10,0)},
Gamma_{(6w,0)},
Gamma_{(w^3,0)},
Gamma_{(epsilon_0,0)},
Gamma_{(Gamma_{(2,0)},0)}, etc.
At some point we'll find an ordinal b such that
Gamma_{(b,b)} = b, and this new notation jams up.
Use the same procedure that I applied to go from Gamma_#
to Gamma_{(*,#)} to develop a notation for "3-variable"
Gamma-type ordinals. This new notation will fail at
some point in the sense that you will reach a notational
ceiling in which ordinals at least as large as that ceiling
will be needed in order to describe that ceiling. O-K, so
then you define "4-variable" Gamma-type ordinals. Then
"5-variable" ones, and so on. Taking the supremum of
all the finite-variable Gamma-types (evaluated at all 1's,
say) will leap-frog you into what might be called
"w-variable" Gamma-type ordinals. And you can continue.
At some dizzying height you'll confront an ordinal b such
that it is not possible to describe b using any variable
Gamma-type ordinals with fewer than b variables, with
inputs of less than b. So we're confronted with another
notational jam.
I *think* the plateau reached in the previous paragraph
is Veblen's E(1) [Oswald Veblen, "Continuous increasing
functions of finite and transfinite ordinals", Trans.
Amer. Math. Soc. 9 (1908), 280-292.], but I'm not really
sure. Perhaps an expert in this subject knows. (The topics
that I'm discussing are not my field of expertise.)
Proof-theorists often use much larger ordinals in their work.
There are several highly technical notational systems that
have been developed to deal with naming the ordinals they
work with. [What I did above was just a quickie "made-up"
system that falls far short of their needs.]
A nice survey (a bit dated now) of various systems of
naming large proof-theoretic ordinals is given in:
Larry W. Miller, "Normal functions and constructive
ordinal notations", J. Symbolic Logic 41 (1976), 439-459.
An introductory survey of these topics is:
Frederick Gass, "Constructive ordinal notation systems",
Mathematics Magazine 57 (1984), 131-141.
Incidentally, *all* of the natural number valued functions
f_a, corresponding to every ordinal a that I've alluded to thus
far, is recursive. We can do better, still. There is an
upper bound on the growth rates of recursive functions.
[The Busy Beaver function falls into this category. (Tibor
Rado, "On non-computable functions", Bell System Tech. J.
41 (1962), 877-884.)] Indeed, since every countable set of
ordinals has a countable supremum, and only countable many
ordinals can be described recursively, then there will be
non-recursive countable ordinals. [Recall that there are
uncountably many countable ordinals. (Hence, we actually
have that "most" countable ordinals cannot be reached by
any recursive means.)] For any non-recursive ordinal a, the
function f_a fails to be recursive, and conversely.
Because any nonempty set of ordinals has a least element,
there is a least non-recursive ordinal. Let's include, as part
of our naming tools, this least non-recursive ordinal and
denote it by kappa_0. If we employ all the methods above to
generate new ordinals, we can get well past kappa_0:
(kappa_0)^w, ..., epsilon_{kappa_0}, ..., (f_{kappa_0}) (w),
..., Gamma_{kappa_0}, ...
But there will be a least ordinal not reachable using
kappa_0 and recursive means. Call this kappa_1. There will
now be a least ordinal not reachable using kappa_1 and
recursive means. Call this kappa_2. Keep going. Let
kappa_w = sup{ kappa_0, kappa_1, kappa_2, ...}, and so
on. Will there ever be an ordinal b such that kappa_b = b?
Yes, because the way I'm defining the map a |---> kappa_a makes
it a normal function (non-decreasing and continuous at limit
ordinals a). We could enumerate its fixed points, and
go on and on and on and on . . . [But I think I've gone
on long enough.]
Dave L. Renfro
David Libert
The long article by Dave Renfro to which I am replying is very
interesting, with lots of great references, and as Dave says, it
absolutely blows out of the water all the other numbers in the "world's
largest number" thread. Maybe more along the lines if the other thread
continues developing its ideas at the current pace for the next 1000
years it will still fall short of Dave's first article.
I generally agree with everything in Dave's article, except a couple of
points I wanted to question. So I will concentrate on those for this
article.
I don't think this is true. Here is an attempted argument. As
background I need the fact (?) that for each non-negative integer m the
sequence < (f_{n}) (m) | n non-negative integer> is strictly monotonic
increasing. Ie each finite level slice of the Ackermann function
strictly dominates the earlier slices everywhere. Prove this by
induction on n, with an inner induction on m, using the fact that each
f_{n} is strictly increasing, ie for each fixed n (f_{n}) (m) is
strictly increasing as m increases. This subclaim is also proven by a
double induction on n and m.
So pick some ordinal notation a, denoting an ordinal strictly larger
than w = omega. a is assumed to be an ordinal notation, so it has its
own system of fundamental sequences, so f_{a} is defined.
I want to construct an alternative notation for the ordinal w, call my
notation W, so that f_{W} dominates f_{a} everywhere. So by
supping up to "omega" in a fast enough way, I can make the associated
f_{W} exceed the f_{a} at a higher ordinal.
We will begin with the standard notations for the finite ordinals.
These did not involve taking any sups and so have a unique notation. So
f_{n} for n finite are known and fixed.
I will define a sequence <n_i | i non-negative integer> which is an
increasing sequence of these finite notations. This sequence will
determine the notation W, which will therefore be an ordinal notation for
omega.
I define n_i by recursion on i. For i=0, consider the number
(f_{a}) (0) . Since < (f_{n}) (0) | n non-negative integer> is strictly
increasing, we can define n_0 to be the notation of the least integer n
s.t. (f_{n}) (0) > (f_{a}) (0) .
Similarly define n_1 to be the notation of the least integer n s.t.
n > (the integer denoted by n_0) & (f_{n} (1)) > (f_{a}) (1).
In general, n_(i+1) is the notation of the least integer k s.t.
k > (the integer denoted by n_i) & (f_{k}) (i+1) > (f_{a}) (i+1) .
By construction n_i 's denote strictly increasing integers as i
increases. As Dave notes, for a a recursive ordinal notation, f_{a} is a
total recursive function, so the n_i sequence is actually a recursive
sequence, ie the function mapping i to n_i is a total recursive function.
So we can make a recursive ordinal notation W for omega, based on this
sequence.
f_{W} diagonalizes throught the finite f_{n} 's according to this
sequence, so for each non-negative integer m:
(f_{W}) (m) = (f_{n_m}) (m) > (f_{a}) (m) . So f_{W} dominates
f_{a} everywhere.
This concludes my comment on the quoted passage above about choice of
fundamental sequences. Dave continues with a long section about Gamma
numbers. As he notes these are still recursive notations and give rise
to recursive functions on the natural numbers. Next Dave writes about
further extensions:
> Because any nonempty set of ordinals has a least element,
> there is a least non-recursive ordinal. Let's include, as part
> of our naming tools, this least non-recursive ordinal and
> denote it by kappa_0. If we employ all the methods above to
> generate new ordinals, we can get well past kappa_0:
>
> (kappa_0)^w, ..., epsilon_{kappa_0}, ..., (f_{kappa_0}) (w),
>
> ..., Gamma_{kappa_0}, ...
If my example above was correct, it shows the choice of specific
ordinal notation with associated choice of fundamental sequences through
earlier notations is crucial. To have important information about a
function, it is not enough to know the associated ordinal, you must also
know the notation used for that ordinal.
For the recursive ordinals, the very notion of the notations for them
provided fundamental sequences through the smaller notations, to be used
in defining the functions, telling you how to diagonalize at limit steps.
So my question is about the extension of this to the least
non-recursive ordinal kappa_0. I don't know of any canonical fundamental
sequence leading up to kappa_0. Even for the recursive ordinals, we
don't get a fundamental sequence by just picking the ordinal, we must
also choose one from among the many recursive notations for that ordinal.
But kappa_0 is defined to be the least ordinal for which there is no
recursive notation.
I can guess at one possibility. Maybe higher complexity notations than
recursive, and a choice of such provides a fundamental sequence for
kappa_0. I don't know if much has been written about such notations.
Anyway, extending these definitions to kappa_0 seems to involve some
complications beyond everything earlier in the article.
> But there will be a least ordinal not reachable using
> kappa_0 and recursive means. Call this kappa_1. There will
> now be a least ordinal not reachable using kappa_1 and
> recursive means. Call this kappa_2. Keep going. Let
> kappa_w = sup{ kappa_0, kappa_1, kappa_2, ...}, and so
> on. Will there ever be an ordinal b such that kappa_b = b?
> Yes, because the way I'm defining the map a |---> kappa_a makes
> it a normal function (non-decreasing and continuous at limit
> ordinals a). We could enumerate its fixed points, and
> go on and on and on and on . . . [But I think I've gone
> on long enough.]
>
> Dave L. Renfro
The same comment about each of the kappa_b 's. Do these have a
notation system, and if so what is it since it can't be recursive? If
they don't have a notation system how to get a fundamental sequence to do
the diagonalization?
That was all the real questions I had about the article. I will close
with a joke question that I originally planned to open this article with
and then thought the better. Sure to provoke a groan after all Dave's
work of the article.
"So your article seems to define some big numbers, but do any of them
reach up to be as big as one million?"
--
David Libert (ah...@freenet.carleton.ca)
1. I used to be conceited but now I am perfect.
2. "So self-quoting doesn't seem so bad." -- David Libert
3. "So don't be a morron." -- Marek Drobnik bd308 rhetorical salvo IRC sig
Dave L. Renfro
[sci.math 26 Dec 1999 11:30:16 GMT]
<http://forum.swarthmore.edu/epigone/sci.math/gunsnersteh>
wrote
[snip]
> I generally agree with everything in Dave's article,
>except a couple of points I wanted to question. So I
>will concentrate on those for this article.
I agree completely with David's two points.
1. My comment that it doesn't matter how one diagonalizes
at the limit ordinals is wrong and I should have known
better. In fact, at one time I *did know* better, but
for some reason this entirely escaped my mind when writing
that essay. Here's a shorter version of David's point,
followed by what I should have said.
The "Ackermann level" f_w is defined by diagonalizing this
way: (f_w)(n) = (f_n)(n). But if the sequence {n} is
replaced by a sufficiently rapidly increasing sequence of
positive integers, then diagonalization can produce something
that grows arbitrarily faster than f_w. Of course, it will
still be the case that the iterations of this new function
grow much faster than this new function does, but one no
longer has a well defined hierarchy of growths when this is
allowed. Although "arbitrarily faster" seems vague, I think if
you pick whatever measure of domination you want (eventual
domination, differences between successive terms approach
infinity, ratios of successive terms approach infinity, etc.),
that you'll find this argument will take care of it:
Take any monotone increasing sequence of positive integers b_n
and define an w'th level by diagonalizing this way:
(g_w)(n) = (f_{b_n}) (b_n).
What is true, I believe, is that as long as you don't diagonalize
in such a manner that makes use of a faster rate of growth
than what you have available via the functions f_b for b
less than the limit ordinal you're presently working with, that
you'll wind up with "essentially" the same growth rate at the
limit ordinal level. [There is an ever weakening scale of
"grows the same rate as" equivalence relations that is used to
to make this precise, I think.]
The following passage is from C. Smorynski, " 'Big' news from
Archimedes to Friedman", Notices of the American Mathematical
Society 30 (1983), 251-256.
###############################################################
Ooops! The definition of F_a, for a a limit ordinal, depends on
the path a_0 < a_1 < ... by which we choose to reach a: No matter
how slowly this sequence grows, F_a will dominate all F_b's for
b < a; but if we pick a rapidly growing sequence, F_a could become
a much more rapidly growing function than we intended: It could
become, for example, what we intended F_{a+1} to be! In the first
problematic case, a=w, we defined F_w by choosing a_n = n; we
could have chosen a_n = (F_n)(n) [= (f_w)(n)] or a_n = (F_{w+1}) (n).
With the former choice we would get something much bigger than F_w
relative to dominance, but of roughly the same rate of growth
relative to our rough equivalence; with the latter we would
violate even the rough equivalence. The idea of this example
is this: If we try to get beyond all F_n's by diagonalising and
only allow ourselves access to the rates of growth already at
hand--i.e. the F_n's--then we will get something like F_w; to
get beyond F_w, we must use something of already more rapid growth.
###############################################################
For ordinals less than epsilon_0 there is the Cantor normal
form. For larger ordinals, say up to Gamma_0, I believe you
can make use of the earlier constructed functions to obtain
"canonical" fundamental sequences for the limit ordinals.
As the ordinals get larger and larger, though matters become
more and more mysterious (to me, at least).
[snip]
> If my example above was correct, it shows the choice of
>specific ordinal notation with associated choice of fundamental
>sequences through earlier notations is crucial. To have important
>information about a function, it is not enough to know the
>associated ordinal, you must also know the notation used for
>that ordinal.
[snip rest]
Yes, it seems clear to me (this IS NOT my field of expertise,
by the way!) that the definition of f_a does *not* depend only
on the ordinal a, but in fact it depends additionally on the
system of notation for ordinals being used--specifically,
which fundamental sequences are being used for each limit
ordinal.
2. The other point was that this doesn't make sense when you get
to the nonrecursive ordinals. I think I forgot what I was doing
and just got carried away with getting larger and larger countable
ordinals. On the other hand, I seem to recall reading somewhere
that Stan Wainer (and maybe also Wilfried Buchholz?) had managed
to somehow non-constructively continue this hierarchy through
all the countable ordinals. But I'm getting in over my head at
this point. Maybe an expert can clarify this.
Dave L. Renfro
David Libert
Dave L. Renfro (dlre...@gateway.net) writes:
>
> What is true, I believe, is that as long as you don't diagonalize
> in such a manner that makes use of a faster rate of growth
> than what you have available via the functions f_b for b
> less than the limit ordinal you're presently working with, that
> you'll wind up with "essentially" the same growth rate at the
> limit ordinal level. [There is an ever weakening scale of
> "grows the same rate as" equivalence relations that is used to
> to make this precise, I think.]
Yes, I had never thought along these lines before, but this seems
right. To discuss this further I will paste from Dave's first article
where he wrote about "essentially the same growth rate":
>However, it can
>be shown that (at least, for any of the *recursive* ordinals
>I'll be dealing with) all the various functions you get by
>diagonalizing over various fundamental sequences
>representing a particular limit ordinal will have
>"essentially the same growth rate". In particular, all
>of them will grow much faster than any of the functions
>corresponding to smaller ordinals (this half is trivial)
>and all of them will grow much slower than any of the
>functions obtained by an iteration of any of the limit
>ordinal variations.
So following the comments above, given an ordinal notation a for some
recursive ordinal, and writing a+1 for the canonical unique notation
for the successor of a (ie no new sups involved beyond those already in
a, so a unique notation), we have a hierarchy of f_{b} 's defined
for b ordinal notations up to and including a+1. We have already
just selected the notations a & a+1 for those respective denoted
ordinals. For the ordinals below these, even though in general there is
no canonical way to pick notations for arbitrary ordinals, there is a
unique path of notations leading up the notation for a, which can be
recovered from the fundamental sequences. So we can get a sequence of
ordinal notations and hence functions f_{b} .
With this background we will define what it means for a function g from
naturals to naturals to have the essential growth rate of f_{a}. Namely
such a g has the same essential growth rate of f_{a} iff for each
ordinal notation b from our sequence strictly less than a, g
eventually dominates (ie is strictly larger than for sufficiently large
inputs) f_{b}, and also f_{a+1} eventually dominates g. This
definition was inspired by Dave's comments above. It says that g and
f_{a} are allowed considerable leeway to leapfrog past each other, but g
must be squeezed between the same bounds the sequence provided for f_{a}.
Supposing now that a denotes a limit ordinal, given our original
f_{a}, let us consider alternate versions that are built from the same
f_{b} b<a, but based on a different fundamental sequence through these b
notations up to a. I will consider such alternatives of a special form,
in order to be able to relate them to the f_{b} 's along the lines of
Dave's comments.
Namely the notation a provided a fundamental sequence <b_i | i
non-negative integer> of increasing smaller notations supping to the
ordinal denoted by a. For g a strictly increasing function from
non-negative integers to non-negative integers, we will define the
g-speedup of <b_i | i non-negative integer> to be the sequence
<b_g(i) | i non-negative integer>.
Given such a g, the g-speedup sequence determines an alternate ordinal
notation for the ordinal denoted by a, call this notation n(g). So for
such n(g) we can form f_{n(g)}.
If f_{a} eventually dominates g then f_{a} has essentially the same
growth rate as f_{n(g)}.
Namely, since g was strictly increasing, the g-speedup is everywhere >=
the original fundamental sequence, so f_{n(g)} eventually dominates
f_{b} for b < a. (This is like a comment of Dave's about one direction
being easy from the original article).
To see the other direction, namely that f_{a+1} eventually dominates
f_{n(g)}, consider that f_{a} was based on diagonalizing the original
fundamental sequence. So we get for i non-negative integer:
f_{n(g)} (i) = f_{b_g(i)} (i) .
From the definition of the g-speedup and the fact that f_{n(g)} was
also defined by diagonalizing over the speeded up fundamental sequence:
f_{b_g(i)} (i) = f_{n(g)} (i).
So f_{n(g)} is the composition: f_{n(g)} = f_{a} o g .
But g was eventually dominated by some f_{b} for b<a, and such f_{b}
is eventually dominated by f_{a}, so f_{a} o g is eventually
dominated by f_{a} o f_{a}, ie 2 compositions of f_{a}. Since
f_{a+1} is defined by iterations of f_{a} on 2, we get for i>2
f_{a+1} (i) = [f_{a} o f_{a}] ([f_{a} ^(i-2)] (2) )
Since f_{a} dominates the successor function (ie a is a limit ordinal),
[f_{a} ^(i-2)] (2) > (i-2) + 2 = i, ie the argument on the RS
above is > i. Since f_{a} is stricly increasing we therefore get:
[f_{a} o f_{a}] ([f_{a} ^(i-2)] (2) ) > [f_{a} o f_{a}] (i) .
Combining these f_{a+1} (i) > [f_{a} o f_{a}] (i) for i>2, and
combining these with the earlier eventual dominances we get f_{a+1}
eventually dominates g.
So this says reasonable speedups preserve the essential growth rate.
>
> The following passage is from C. Smorynski, " 'Big' news from
> Archimedes to Friedman", Notices of the American Mathematical
> Society 30 (1983), 251-256.
>
> ###############################################################
> Ooops! The definition of F_a, for a a limit ordinal, depends on
> the path a_0 < a_1 < ... by which we choose to reach a: No matter
> how slowly this sequence grows, F_a will dominate all F_b's for
> b < a; but if we pick a rapidly growing sequence, F_a could become
> a much more rapidly growing function than we intended: It could
> become, for example, what we intended F_{a+1} to be! In the first
> problematic case, a=w, we defined F_w by choosing a_n = n; we
> could have chosen a_n = (F_n)(n) [= (f_w)(n)] or a_n = (F_{w+1}) (n).
> With the former choice we would get something much bigger than F_w
> relative to dominance, but of roughly the same rate of growth
> relative to our rough equivalence; with the latter we would
> violate even the rough equivalence. The idea of this example
> is this: If we try to get beyond all F_n's by diagonalising and
> only allow ourselves access to the rates of growth already at
> hand--i.e. the F_n's--then we will get something like F_w; to
> get beyond F_w, we must use something of already more rapid growth.
> ###############################################################
This passage suggests a more direct proof of bad cases of excessive
speedup than my proof last post. Namely just take the speedup function
to directly be F_w+1 for example.
> For ordinals less than epsilon_0 there is the Cantor normal
> form. For larger ordinals, say up to Gamma_0, I believe you
> can make use of the earlier constructed functions to obtain
> "canonical" fundamental sequences for the limit ordinals.
> As the ordinals get larger and larger, though matters become
> more and more mysterious (to me, at least).
Yes. As you say up to Gamma_0 is not too bad, and then it gets murkier
as notations become more complicated. I will post later on an alternate
notation system of mine that can do these out very far.
> [snip]
>
>
>> If my example above was correct, it shows the choice of
>>specific ordinal notation with associated choice of fundamental
>>sequences through earlier notations is crucial. To have important
>>information about a function, it is not enough to know the
>>associated ordinal, you must also know the notation used for
>>that ordinal.
>
> [snip rest]
>
> Yes, it seems clear to me (this IS NOT my field of expertise,
> by the way!) that the definition of f_a does *not* depend only
> on the ordinal a, but in fact it depends additionally on the
> system of notation for ordinals being used--specifically,
> which fundamental sequences are being used for each limit
> ordinal.
Yes.
> 2. The other point was that this doesn't make sense when you get
> to the nonrecursive ordinals. I think I forgot what I was doing
> and just got carried away with getting larger and larger countable
> ordinals. On the other hand, I seem to recall reading somewhere
> that Stan Wainer (and maybe also Wilfried Buchholz?) had managed
> to somehow non-constructively continue this hierarchy through
> all the countable ordinals. But I'm getting in over my head at
> this point. Maybe an expert can clarify this.
>
> Dave L. Renfro
I hadn't heard of this but it sounds interesting. Also interesting
that Wainer's name arises, because I about to post another followup
article about a loosely related paper of his.
David Libert
I just posted a first followup in this thread responding directly to
Dave's last article. Now I am writing to the same thread because this
will be a related result to the previous but still branching off
somewhat.
This is along the lines of the general theme of speeding up given
functions and iterating that speedup through ordinal notations. I am
just reporting on an interesting paper about this general theme, but one
using different speedups than the Ackermann style we have been discussing
so far.
The paper is:
E.A. Cichon & S.S. Wainer The Slow-growing and the Grzegorczyk
Hierarchies
Journal of Symbolic Logic Vol 48, number 2, June 1983 pp 399-408
They define three hierarchies of functions, each in the style as above
of functions from non-negative integers to non-negative integers, each
family indexed by recursive ordinal notations, with diagonalization over
the fundamental sequences at limit ordinals, a starting function at 0,
and some form of speedup at successor steps. The 3 hierarchies differ
according to the speedups.
The slow-growing hierarchy is the slowest possible:
G_0 (x) = 0; G_a+1 (x) = G_a (x) +1 .
Next the Hardy hierarchy (origanally defined by G.H. Hardy in 1904):
H_0 (x) = x; H_a+1 (x) = H_a (x+1) .
Finally the Grzegorczyk hierarchy (they refer to their version as
transfinitely extended over the real Grzegorgzyk hierarchy, so maybe it
was originally for finite index):
F_0 (x) = x+1; F_a+1 (x) = F_a ^x (x) .
(Note: the Grzegorczyk hierarchy is notated with an F. Couldn't use G,
since that was already used for the slow-growing hierarchy, which
naturally needed to be called G and not S).
So F's are similar to Ackermann, except they don't have the shift by 1
from Ackermann, also Ackermann is iteration over a common base value of
2, while F makes x the base of the x iteration, so faster that way.
They note a relation showing how slow G moves compared to the others:
for x>0 G_(epsilon_0) (x) < F_3 (x) = H_(w^3) (x) .
The main result of the paper is to give a new proof of an original
result of Girard, namely identifying which ordinal in the G hierarchy has
approximately the same rate of growth as F_(epsilon_0).
The answer turns out to be... The Howard Ordinal. This is a recursive
ordinal, but it is so large it is hard to grasp. It is bigger than all
the recursive ordinals mentioned by Dave in his first post.
For what it is worth, if this gives any point of comparison, and if I
am remembering comments I have read correctly, in the same way that
epsilon_0 is the ordinal corresponding to PA (ie Gentzen's proof),
Gamma_0 that Dave wrote about corresponds to predicative analysis. This
is a system Fefferman writes about a lot. It is like PA with a level of
set variables above, ie sets of non-negative integers, except the
comprehension axioms to define such sets must be predicative. That is,
the sets are indexed by orders like from Principia Mathematica, and each
level is only allowed to quantify over the earlier levels of sets. Level
0 can't quantifiy over any sets, only over integers. The levels are I
think indexed by ordinal notations, and in order to use a level you must
first prove the putative notation is really well-founded. (Maybe).
So that is epsilon_0 and Gamma_0. Then the Howard ordinal is the
corresponding ordinal for te theory of one inductive definition. This is
I think again a theory of integers and sets of integers, where you also
have an operator that lets you define sets by induction, as for example
fixed points of monotonic operators.
In any event, it is a remarkable result, to relate G to F. G is
growing as slow as possible, and F is similar looking to the Ackermann
hierarchy.
David Libert
This post is continuing the recent discussion in this thread about how
sufficiently small speedups in the fundamental sequence used don't
essentially affect the resulting f_{a} defined. Dave posted a couple of
articles ago suggesting this, and I replied agreeing with this, sketching
what was supposed to be an argument supporting it.
I still agree with the basic claim, but my "proof" was messed up in some
details. I think an appropriate variant of it can show the result. I will
be writing about that here.
Since that last post I have also realized the claim can be strengthened
to apply to more cases. I will also discuss that after discussing the
original proof.
The gist of the attempted argument last post was I think correct, but the
presentation messed up some details. In the long run these details don't
matter though, because the claimed inequalities are so extreme that they
are not sensitive to minor tinkering. In general if mistakes are corrected
it is likely that the corrected expressions won't mess up claimed
inequalities, those tend to hold by such a wide margin that there is room
for error.
I will mention at the outset one mixup. Dave's original article in this
thread quotes an earlier post of Dave Seaman's giving the usual finite
level Ackermann's function. Dave is generalizing this to indices as
ordinal notation, but inheriting the successor step from ... hey from Dave
(Seaman).
So Dave Seaman's definition:
> f(0,y) = y + 1
> f(x+1,0) = f(x,1)
> f(x+1,y+1) = f(x,f(x+1,y))
One of my mistakes was as above I was considering the f 's being defined
as from non-negative integers to non-negaitve integers, but in the middle
of the proof I recalled instead alternate versions of Ackermann's based on
positive integers, so that middle line would become f(x+1,1) = f(x,2).
This was inconsistent by me, because elsewhere I was explicitly taking the
domain to be non-negative integers. So I wrote about iterating over 2, but
it should have been iterating over 1. As I wrote above, this are fiddly
details that upon correction won't change the final claim being proved.
There were some other problems, but we will so this in context of the
quote:
David Libert (ah...@FreeNet.Carleton.CA) writes:
> Dave L. Renfro (dlre...@gateway.net) writes:
>>
>> What is true, I believe, is that as long as you don't diagonalize
>> in such a manner that makes use of a faster rate of growth
>> than what you have available via the functions f_b for b
>> less than the limit ordinal you're presently working with, that
>> you'll wind up with "essentially" the same growth rate at the
>> limit ordinal level. [There is an ever weakening scale of
>> "grows the same rate as" equivalence relations that is used to
>> to make this precise, I think.]
>
> Yes, I had never thought along these lines before, but this seems
> right. To discuss this further I will paste from Dave's first article
> where he wrote about "essentially the same growth rate":
... a quote motivating the definition to follow ...
Now I write some nonsense. I had made a first pass at the proof that I
tried to revise by editting. I managed to delete and retain the wrong
lines from what I intended.
I had a few such erroneous lines which I now delete leading me to the
conclusion:
> So f_{n(g)} is the composition: f_{n(g)} = f_{a} o g .
I now think the correct conclusion at this point is f_{n(g)} is
everywhere <= f_{a} o g .
I will give a new argument from scratch for this, not trying to relate it
to the last attempt.
For i a non-negative integer, I seek to show
f_{n(g)} (i) <= [f_{a} o g] (i).
From the f_{n(g)} definition for limit ordinal notation as a
diagonalization, and from the fact that n(g) was the notation arising
from the g-speedup of the original "b_i" fundamental sequence:
[1]: f_{n(g)} (i) = f_{b_g(i)} (i) .
g was strictly increasing, so i <= g(i). f_{b_g(i)} was a level of the
transfinite Ackermann hierarchy, so f_{b_g(i)} is strictly increasing.
(Provable by transfinite induction on indices).
From i <= g(i) & f_{b_g(i)} strictly increasing we get:
[2]: f_{b_g(i)} (i) <= f_{b_g(i)} (g(i)) .
The expression on [2] RS is moving along to position g(i) in the
"b_j" fundamental sequence, and applying that "f_" to argument g(i). This
the the diagonaliztion in the definition of f_{a} (not f_{n(g)} )
applied to argument g(i): by definition of f_{a} at g(i):
[3]: f_{b_g(i)} (g(i)) = f_{a} (g(i)).
RS of [3] can be rewritten as a composition:
[4]: f_{a} (g(i)) = [f_{a} o g] (i) .
The respective RS & LS 's of [1]-[4] match and [2] was <= and the
others were ='s so we get as desired:
[5]: f_{n(g)} (i) <= [f_{a} o g] (i) .
In the previous flawed post I had this <= as =.
The revision of = to <= will not matter for what is to follow, since I
was establishing in the end an iequality, and this corrected <= is going in
the right direction for the purposes to follow.
My argument continues by putting upper bounds on [5] RS, which is still
useful for bounding [5] LS even recognizing [5] is <= and not =.
So returning to the previous:
> But g was eventually dominated by some f_{b} for b<a, and such f_{b}
> is eventually dominated by f_{a}, so f_{a} o g is eventually
> dominated by f_{a} o f_{a}, ie 2 compositions of f_{a}.
Actually my original premise in the claim to be proven was g is
evnetually dominated by f_{a}, so above I should have quoted that
premise directly instead of routing it through some f_{b}, a claim I
don't even have from the premise. Only using f_{a} directly makes this
argument apply to more cases.
Note also, to get from f_{a} evnetually dominates g to f_{a} ^2
eventually dominates f_{a} o g , I am using that f_{a} is strictly
increasing.
> Since
> f_{a+1} is defined by iterations of f_{a} on 2, we get for i>2
>
> f_{a+1} (i) = [f_{a} o f_{a}] ([f_{a} ^(i-2)] (2) )
This is the "2" problem. (i-2) was correct, but (2) should be (1).
> Since f_{a} dominates the successor function (ie a is a limit ordinal),
> [f_{a} ^(i-2)] (2) > (i-2) + 2 = i, ie the argument on the RS
> above is > i.
So now we only get (i-2) + 1 instead of (i-2) + 2, so the estimate
above becomes RS > i-1. I really did want > i though. But my simple
argument above was based on only using the weak property that f_{a}
diminates the successor function. a is at least omega, so f_{a} is at
least the usual Ackermann function, and I only need the > for sufficiently
large i, so "obviously" i-2 iterations of the Ackermann function on 1
dominates i for sufficiently large i.
With that the rest is ok:
> Since f_{a} is stricly increasing we therefore get:
(Not only is it "stricly" increasing, it is strictly increasing.
(Wow I just spelling flamed myself!))
> [f_{a} o f_{a}] ([f_{a} ^(i-2)] (2) ) > [f_{a} o f_{a}] (i) .
>
> Combining these f_{a+1} (i) > [f_{a} o f_{a}] (i) for i>2, and
> combining these with the earlier eventual dominances we get f_{a+1}
> eventually dominates g.
In the revised version the chain of inequalities has the extra [5]
inequality that used to be =.
>
> So this says reasonable speedups preserve the essential growth rate.
So that completes correcting the argument of the last post.
Now a strengthening. The argument above got a strict < with the
dominance of the i-2 iterations of f_{a} on 1 over i. So the above proof
still produces the desired strict < even if the eventual relation of g to
f_{a} is <= rather than <.
So my original claim was that if f_{a} eventually dominates g then f_{a}
and f_{n(g)} have the same essential rate of growth. Eventual dominance I
defined as eventual strict <. So by the last comments with the argument
above I could weaken the premise to eventual <=.
David Libert
I just posted an article correcting and strengthening my previous
article about speeding up fundamental sequences:
David Libert (ah...@FreeNet.Carleton.CA) writes:
> This post is continuing the recent discussion in this thread about how
> sufficiently small speedups in the fundamental sequence used don't
> essentially affect the resulting f_{a} defined. Dave posted a couple of
> articles ago suggesting this, and I replied agreeing with this, sketching
> what was supposed to be an argument supporting it.
Etc. Just after sending it I thought of a strange example of an f_{a}
sequence. It doesn't invalidate anything from the last article, but it
shows how surprising things can become with this construction.
My original post in this thread was about taking a strange fundamental
sequence to make the corresponding f_{W} surprisingly large. The last
articles were about how restrictions on the fundamental sequences keep
the resulting function from getting too large.
My new example of this post will be strange fundamental sequences to
make the resulting functions surprisingly small.
My previous example stated with an ordinal notation a, and the
anamalous notaton I produced W was based on a strange fundamental
sequence supping to w = omega, but the lesser notations below W were the
standard notations, not anamalous. (In fact this was unavoidable since
they were notations for finite ordinals).
My new example uses unusual fundamental sequences not just for the top
ordinal, but for many ordinals below.
So to start the example, suppose that w is the obvious notation for
the ordinal omega. Namely for the finite ordinals there are unique
notations, and for w we take the obvious fundamental sequence through
those notations: i goes to the notation for i.
So f_{w} is defined, and is the usual Ackermann function, ie the
diagonal through the two variable function.
I am going to define further ordinal notations beyond w, denoting up
to and including the ordinal omega^2, so that W2 the notation for
omega^2 has f_{W2} = f_{w}.
I will be defining the notations by recursion, because notations for
higher ordinals will involve fundamental sequences through the earlier
notations.
Having the notation w for omega, we can canonically pick notations
w+1, w+1+1, etc for all ordinals between omega and omega*2. There are
no extra sups involved for these. I will refer to such notations as w+n
for n an positive integer.
Having all such notations for ordinals below omega*2, we now define
w2, a notation for omega*2, by choosing a fundamental sequence through
the earlier notations. I must pick a strictly increasing sequence of
notations supping to omega*2, and I do so with the following twist on the
obvious sequence: <0, 1, 2, w+3, w+4, w+5, ...> . That
enumeration is understood to indicate a function from naturals =
non-negative integers = finite ordinals. So for i>2 the sequence
assigns w+i, but for i<3 the sequence assigns the notation for i.
We define w2+n as usual for n natural.
Next to define w3, a notation for omega*3. <0, 1, 2, 3, w2+4, w2+5,
...>.
w3+n as usual. w4 for omega*4 is <0,1,2,3,4, w3+5, w3+6, ...> .
And so on below omega^2. wn starts off looking like it works below w,
and only at stage n+1 does it really get to work.
Finally W2 the notation for omega^2 (as oppoed to w2 for omega*2) is
defined by the sequence <0, w, w2, w3, w4, ...> .
Consider f_{a} for these various notations. For a = wn, f_{a} is
defined by diagonalization and so for arguments <=n f_{wn} agrees with
f_{w}. Only at n+1 does f_{wn} finally get to serious work.
But f_{W2} diagonalizes over f_{wn} 's, where for each f_{wn} f_{W2}
uses the "slacker" portion of f_{wn}, f_{W2} never looks far enough to
see f_{wn} take off. So f_{W2} pieces together sections of function
puttering around below f_{w}, and we get f_{W2} = f_{w}.
It would be a challenge to make higher versions of such examples well
beyond omega^2. Reminds me of Jensen's box, cohering sequences together.
This raises the possibility of small functions at very high ordinals.
But if "reasonable" fundamental sequences are used this sort of thing
won't happen. As Dave indicated a few posts ago, for the small ordinals
there are obvious ways to make notations and choose fundamental
sequences. For these you do get proper growth of functions paralleling
ordinals, unlike this example.
David Libert
fundamental sequence in ordinal notations on f_{a} the transfinite
version of the Ackermann hierarchy. My second last article of the thread
presented a claimed proof that speeding up the top level fundamental
sequence by small enough does not change the essential rate of growth of
the last f_{a}. My last post presented an example of a strange system of
ordinal notations up to including omega^2 with notation W2, with
f_{W2} = f_{w}, w the usual notation for omega.
That last post wrote that its example did not undermine the previous
proof, but I have since realized that is not correct.
The proof of two posts ago about speedups of fundamental sequence not
changing essential growth rates used two properties of the f_{a} 's that
were cited in passing and not proved. One property was that for b and a
two notations from the same sequence of notations and b < a that f_{a}
eventually dominates f_{b}. The other property was that all f_{a} 's
are strictly increasing.
I think these two properties do hold for the standard notations built
from Cantor normal form and its higher analogues. But allowing
considering alternate notations with more varied fundamental sequences,
my omega^2 example of the last post already refuted the first property.
Namely my example had standard notations up to and including w, so
f_{a} is the standard hierarchy for a up to and including w. For
notations strictly between omega and omega^2, at limit stages my
functions only departed from the standard ones at a finite initial
segment, so for asymptotic comparisons like eventual dominances this
hierarchy at these levels acts like the standard one. So below omega^2
my hierarchy has eventual dominance between all levels.
But my W2 notation for omega^2 has f_{W2} = f_{w}, so for notations a
strictly between omega and omega^2, f_{a} eventually dominates f_{W2},
a reversal of direction demanded by the first property.
Regarding the second property, that all f_{a} 's are strictly
increasing, it can be shown that for all notations based on any choice of
fundamental sequence, the notations a denoting ordinals less that
omega*2 are strictly increasing.
My example from last post only provides strictly increasing f_{a} 's,
for all notations up to and including W2 for omega^2.
On the other hand, since last post I have realized how to make another
example, based on changing low values of the fundamental sequence, as the
last one was, which produces an example with f_{a} not increasing, for
a the notation for omega*2. So this example is sharp against the claimed
result above about increasing functions below omega^2.
I still think my proof of 2 posts ago shows that for notations having
both the assumed properties, the conclusion about speedups follows as
stated. This result is still of interest, since the notations that get
commonly used for specific recursive ordinals do have these two
properties. But the general proof is invalidated by counterexamples to
each of the two assumed properties.
This raises the question of whether the conclusion is still true in
general. With these similar methods of changing fundamental sequences in
low parts and making later diagonalizations pick from there, I think I
can prove the following, which if true provides lots of counterexamples
to the original claim about small fundamental sequence speedups not
essentially changing growth rates.
For this claim, let g be any strictly increasing function from
naturals to naturals which has no fixed points. This is equivalent to g
is strictly increasing and for all naturals i g(i) > i.
I also want to consider two target functions f1 and f2, given as
follows. We have f_{n} for n finite, since finite ordinals have unique
notations. Let h1 and h2 be two functions, each of which is everywhere
>= the identity function: for all naturals i h1(i) >= i and similarly
for h2. Then f1 is defined by for all naturals i:
f1(i) = f_{h1(i)} (i). Similarly f2(i) = f_{h1(i)} (i).
What this says in pictures is fill in an infinite matrix with the nth
row being a listing of f_{n} values on respective column numbers.
Choose a path through this matrix, picking one cell in each column, where
the cell is on or above the diagonal, and take the values of the cells in
increasing column numbers to enumerate the f1 or f2 values.
So we are considering all pairs of functions f1 and f2 that can be
produced this way, by choosing arbitrary pairs h1 and h2. No relatation
is assumed between h1 and h2, so either one of f1 or f2 may be bigger, or
they could leapfrog back and forth over each other in whatever pattern we
want to create by suitable choice of h1 and h2.
The claim will be about all triples g, f1 and f2 that can arise this
way. The claim is that for such g, f1 and f2, I can explicitly define
an ordinal notation system up to and including omega^3, so that for W3
the notation for omega^3 f_{W3} = f1 and for n(g) the g-speedup
of W3, f_{W3} = f2.
What this allows is g could be as small as the successor function, and
yet even this tiny speedup by g changes the function at omega^3 from f1
to f2, which we can make as large a change as we want. f2 could be made
a speedup of f1 by any amount, or f2 could slow down, or they may even be
incomparable w.r.t. eventual dominance.
So the claim from 2 posts ago can fail very badly.
That is as much as I will write now about that example. Though maybe
if I try to write this up later I will discover an error in the
construction.
A final different example I will describe without details. Last post I
gave the example up to W2 for omega^2 with f_{W2} = f_{w}. I have
since realized how to extend this example to ordinals beyond omega^2.
The extended version will have the same notations as the previous version
up to and including omega^2. For each recursive ordinal alpha I can
produce a notation system for ordinals up to and including alpha, using
the last example up to omega^2, with the property that the f_{a} 's
produced are periodic with period omega^2, each block of omega^2 ordinals
repeating the f_{a} values from [omega, omega^2) .
So this particular notation system assigns to very large ordinals
functions eventually dominated by the function usually assigned to
omega^2.
Dave L. Renfro
[sci.math 2 Jan 2000 08:57:55 GMT]
<http://forum.swarthmore.edu/epigone/sci.math/gunsnersteh>
has recently written several posts in response to an earlier
post of mine, his Jan. 2 post being the latest I've seen as of
noon CST Tuesday Jan. 4. My purpose with this post is to mention
that I have not fallen off the face of the Earth, nor have I been
silenced by Y2K problems. Rather, I've been away from my own
computer and resources for the past week or so and I will not
return for another couple of weeks. This is the first time I've
been able to access the internet (there are 3 computers at the
public library in the town I'm staying at), so I haven't had
a chance to think about David Libert's posts. When I get back
to my own apartment in a couple of weeks I'll respond in more
detail if I feel that I can add anything to David's efforts.
For now I'll just say that I've encountered the "slow-growing"
and "fast-growing" hierarchies that David mentions, and probably
others as well, and the paradoxical fact that the slow-growing
hierarchy will eventually (for certain *very large* ordinals)
catch up with the fast-growing hierarchy. I've also seen references
to the Howard ordinal, but this is one of those ordinals that lies
beyond my previous feeble attempts in studying these matters.
Dave L. Renfro
Bill Taylor
|>
|> > f(0,y) = y + 1
|> > f(x+1,0) = f(x,1)
|> > f(x+1,y+1) = f(x,f(x+1,y))
That's more or less standard for the 2-argument function. But when you look
at the values, it has those annoying plus-and-minus threes everywhere.
A much smoother form is given by this, which looks "just as natural",
...perhaps even more so!
f(1,y) = y + 2
f(x+1,1) = 2
f(x+1,y+1) = f(x,f(x+1,y))
Cheers,
-------------------------------------------------------------------------------
Bill Taylor W.Ta...@math.canterbury.ac.nz
-------------------------------------------------------------------------------
A Creationist is just a flat-earther without the courage of his convictions.
-------------------------------------------------------------------------------
P.S. You can set your students to calculate f(n,n) through to n=6.
Offer escalating prizes (if you don't mind shelling out a dollar or
two for the littlies). It's a grand waste of computer time!
(You must specify that answers must be legible and in standard decimal form.)