From: dlrenfro@gateway.net (Dave L. Renfro) Subject: LARGE NUMBERS--The Gloves Come Off! Date: 24 Dec 1999 00:58:36 -0500 Newsgroups: sci.math Summary: The biggest numbers (Ackermann functions et al) OX2X [sci.math 22 Dec 1999 20:54:41 GMT] 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 [sci.math 22 Dec 1999 17:11:56 -0500] 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] Re: Progression of operators? (expanded answer) [3 POSTS: Sept. 5, 1999, Sept. 5, 1999, Sept. 6, 1999] Problems in (0,1/e) [Sept. 9, 1999] 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 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 ============================================================================== From: ah170@FreeNet.Carleton.CA (David Libert) Subject: Re: LARGE NUMBERS--The Gloves Come Off! Date: 26 Dec 1999 11:30:16 GMT Newsgroups: sci.math 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. Dave L. Renfro (dlrenfro@gateway.net) writes: > > 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. 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 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 (ah170@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 ============================================================================== From: dlrenfro@gateway.net (Dave L. Renfro) Subject: Re: LARGE NUMBERS--The Gloves Come Off! Date: 29 Dec 1999 14:56:51 -0500 Newsgroups: sci.math Keywords: [missing] David Libert [sci.math 26 Dec 1999 11:30:16 GMT] 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 ============================================================================== From: ah170@FreeNet.Carleton.CA (David Libert) Subject: Re: LARGE NUMBERS--The Gloves Come Off! Date: 30 Dec 1999 09:47:02 GMT Newsgroups: sci.math Dave L. Renfro (dlrenfro@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 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 to be the sequence . 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 b2 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 (ah170@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 ============================================================================== From: ah170@FreeNet.Carleton.CA (David Libert) Subject: Re: LARGE NUMBERS--The Gloves Come Off! Date: 30 Dec 1999 10:45:33 GMT Newsgroups: sci.math 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 (ah170@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 ============================================================================== From: ah170@FreeNet.Carleton.CA (David Libert) Subject: Re: LARGE NUMBERS--The Gloves Come Off! Date: 31 Dec 1999 08:37:37 GMT Newsgroups: sci.math 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 (ah170@FreeNet.Carleton.CA) writes: > Dave L. Renfro (dlrenfro@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 ... > > 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 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 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 to be the sequence > . > > 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: 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 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 (ah170@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 ============================================================================== From: ah170@FreeNet.Carleton.CA (David Libert) Subject: Re: LARGE NUMBERS--The Gloves Come Off! Date: 31 Dec 1999 09:52:26 GMT Newsgroups: sci.math I just posted an article correcting and strengthening my previous article about speeding up fundamental sequences: David Libert (ah170@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 (ah170@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 ============================================================================== From: ah170@FreeNet.Carleton.CA (David Libert) Subject: Re: LARGE NUMBERS--The Gloves Come Off! Date: 2 Jan 2000 08:57:55 GMT Newsgroups: sci.math This thread has lately been about the effect of choice of the 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. -- David Libert (ah170@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