|
||||||||
|
Title: Another (unusual) Number Game Post by Barukh on May 4th, 2005, 10:19am The game you are going to play involves representation of natural numbers in superbase-n notation. To make this, the number is firstly written in an ordinary base-n notation, and then each exponent is written recursively in base-n notation. For instance, the superbase-2 notation of 129 is: It shouldn’t come then as a surprise that you play the game against a supercomputer. You just pick a natural number N, and then the supercomputer executes the following program: 1. Put n equal to 2. 2. If N = 0, stop. 3. Represent number N in superbase-n notation. 4. Replace every occurrence of n in that notation by (n+1). Subtract 1 from the number obtained and let it be the new number N. 5. Increase n by 1 and go to step 2. If this program ever halts, you loose. If it runs forever, you win. What is the minimal number N you must choose to win the game? Example: If you pick number 5, the game starts as follows: N = 5, 27, 255, 465, … |
||||||||
|
Title: Re: Another (unusual) Number Game Post by SMQ on May 4th, 2005, 12:13pm Don't you mean 467? ;D N = 5 = 22+1 --> 33 = 27 --> 44-1 = 3*43+3*42+3*4+3 = 255 --> 3*53+3*52+3*5+2 = 467 --> 3*63+3*62+3*6+1 = 775 --> 3*73+3*72+3*7 = 1197 --> 3*83+3*82+3*8-1 = 3*83+2*82+7*8+7 = 1727 --> ... --SMQ |
||||||||
|
Title: Re: Another (unusual) Number Game Post by SMQ on May 4th, 2005, 4:41pm I believe that, surprisingly, [hide]the game is not winnable[/hide]! Terms: Let P be the polynomial in n comprising the superbase-n notation of a natural number N. Call P "sub-n" if all exponents of P are < n -- i.e. N < nn. Call P "super-1-n" if all exponents of P are sub-n polynomials in n -- i.e. N < nn^n. Similarly call P "super-2-n" if all exponents of P are super-1-n polynomials in n, etc. Note: Let i be the degree of the term of P with least degree -- i.e. the coefficients of all terms of P with degree < i are 0. Decrementing N only affects terms of P with degree <= i. Axiom 1: Under the rules of the game, any N < n will decrement to 0 -- because there are no occurrances of n in the superbase-n notation of N it cannot grow, only decrement until it is 0. Lemma 1: Under the rules of the game, any N with sub-n representation will eventually decrement to 0. Proof by induction: Take a polynomial of degree 0 as the base case; by Axiom 1 it will eventually decrement to 0. Consider a polynomial of degree 1 <= i < n, the sum of a term Cini of degree i and a polynomial, Pi-1 of degree i-1. 1) The exponents of P will remain unchanged by the rules of the game since they are all < n. 2) Under the rules of the game Ci cannot increase since it is less than n. Thus if polynomial Pi-1 goes to 0, the next iteration will decrement Ci, and so Pi will also go to 0. Since P0 goes to 0 (the base case), all Pi eventually go to 0 as well. Correllary 1: nn goes to 0. Decrementing nn results in a sub-n polynomial which, by Lemma 1, goes to 0. Correllary 2: C*nn where C < n goes to 0. While n itself grows, the coefficient of the term of P with degree n remains constant through iterations of the game rules except when no terms of degree < n remain. In that case C is decremented and a sub-n polynomial is added. This sub-n polynomial eventually goes to 0 leaving the term of dgreee n as again the term of least degree in P. Lemma 2: Under the rules of the game, any N with super-1-n representation will eventually decrement to 0. 1) By induction as above, with Correllary 2 as a base case, we can prove that a polynomial of degree n+1 <= n+i < n+n = 2n goes to 0. 2) By the argument of Correllary 2, any polynomial of degree 2n <= i*n+j < n2 goes to 0. 3) We can continue in like manner for all polynomials of sub-n degree. Lemma 3: Under the rules of the game, any N will eventually decrement to 0! Continuing in the manner of Lemma 2 above, drawing from inductive proofs of degrees whose superbase-n represenation has a term of degree 0, and from the rationale of Correllary 2 that the coefficient of a term of degree >= n will eventually be decremented, we can extend Lemma 2 indefinitely to higher super-x-n representations as needed. Not exactly a formal proof, I know, but I'm reasonably sure of its correctness, though more so up to Correllary 2 than beyond. --SMQ |
||||||||
|
Title: Re: Another (unusual) Number Game Post by Deedlit on May 4th, 2005, 5:43pm Hmmm... I'll pick 16, then demand that the computer run the whole procedure if he claims a win. ;D And now for something completely different: the Hardy hierarchy. This is a sequence of functions {Halpha} indexed by ordinals alpha, defined by: H0(n) = n Halpha+1(n) = Halpha(n + 1) Halpha(n) = Halpha(n)(n) when alpha is a limit ordinal That last line needs explaining. A limit ordinal is an ordinal of the form w*alpha; that is, it doesn't end in "+ n" for some positive integer n. The ordinals that do are called successor ordinals, and are handled by the second line. To handle limit ordinals, we need to define a sequence alpha(n), which is called the "fundamental sequence" of alpha; this is just some natural sequence of increasing ordinals that converge to alpha. For ordinals less than or equal to epsilon_0, there is a rather natural definition for the fundamental sequence; just find the "key" appearance of w, and replace it with n. Just use the following rules: 1. [wa1 + ... + wam] (n) = wa1 + ... + wam-1 + (wam) (n) 2. (wa+1)(n) = wa * n 3. wa(n) = wa(n) when a is a limit ordinal. For epsilon0, let epsilon0(n) = w^w^...^w with n w's. This defines the Hardy hierarchy. To get an idea of the sizes: Ackermann(n,x) is a little less than Hwn(x) Graham's number is about Hw(w+1) (66) Conway notation with n numbers is about Hww*n Extended Ackermann notation with n numbers is about Hww^n |
||||||||
|
Title: Re: Another (unusual) Number Game Post by Deedlit on May 4th, 2005, 6:04pm This second post is a quick crash course in the smaller ordinals. I don't know how many of you are familiar with ordinals, but they are basically the order types of well-ordered sets. (Sets for which every subset has a minimum element. The positive integers are well-ordered, but not the nonnegative reals, since the positive reals are a subset, and they have no smallest element.) Put more casually, ordinals are the lengths of sequences that are allowed to extend into the transfinite. The smallest ordinals are nonnegative integers, representing finite sequences. The next smallest is omega (which I'll just write as w), which represents your typical infinite sequence. But that's not the end: the next ordinal is w + 1, which has a regular sequence, plus another element which is greater than the entire sequence! This is clearly a different order type than w (w doesn't have a maximal element), so there is more than one countable "infinity" when we are talking about ordinals. The ordinals continue: w+2 w+3 ... w+w = w*2 (two sequences, one greater than the other) w*2 + 1 ... w*3 ... w*4 ... w*w = w^2 (this is a two-dimensional array, or alternatively, ordered pairs considered in lexicographical order) w^2 + 1 ... w^3 (3D array) ... w^w (infinite dimensional array, or the set of polynomials with positive integer coefficients, ordered by domination) w^w + 1 ... w^(w+1) ... w^(w*2) ... w^(w^2) ... w^(w^w) (thinking in terms of lattices is too confusing now; just think of this as the set of polynomials, whose exponents are themselves regular polynomials) ... w^(w^(w^w)) w^(w^(w^(w^w))) ... epsilon_0 = w + w^w + w^(w^w) + ... I'll continue if someone is curious. ;D |
||||||||
|
Title: Re: Another (unusual) Number Game Post by Deedlit on May 4th, 2005, 6:33pm Very nice, SMQ! When I heard this problem, I also got the answer at the same time, so I don't know if I could have solved it myself. The next question is: how long does it take to go to zero? |
||||||||
|
Title: Re: Another (unusual) Number Game Post by Leonid Broukhis on May 5th, 2005, 11:54am This reminded me of a game with (rooted) graphs in a very old issue of Scientific American. The rules were something along the lines of "if you remove an edge, you have to replicate some part of the graph some number of times, unless you have removed a level 0 edge leading to a leaf node" that would seemingly lead to a infinitely growing graph. But the analysis showed that the graph will eventually become very bushy but only 1 level tall, after which point it will be trimmed down. What was the name of the game, I cannot remember for the life of me. |
||||||||
|
Title: Re: Another (unusual) Number Game Post by Deedlit on May 5th, 2005, 3:58pm This is "Hercules versus the Hydra", named after the story from Greek mythology. The "hydra" is a rooted tree. Each turn, Hercules can cut off any head (a leaf of the tree). But the hydra then splits the immediate higher subtree into n pieces. If I represent a rooted tree as a nested set, like {0, [0, {0, 0}, 0}, 0, 0}, {0, {0, 0], 0} Then I can remove any of the zeroes, but if the zero belongs to an inner set, the set to which the zero belongs gets repeated n times. On the third turn, if we remove the first zero we get: { [0, {0, 0}, 0}, 0, 0}, {0, {0, 0], 0}, If we remove the second, we get: {0, { { {0, 0}, 0}, { {0, 0}, 0}, { {0, 0}, 0}, 0, 0}, {0, {0, 0], 0}, and removing the third gives: {0, [0, {0}, {0}, {0}, 0}, 0, 0}, {0, {0, 0], 0}. Prove that Hercules will always kill the hydra. Interesting question: what if Hercules is smart, how quickly can he kill the hydra? EDIT: I forgot to mention that 0 is just shorthand for {}. So if I remove the zero from [0], it reduces to [] = {0}. |
||||||||
|
Title: Re: Another (unusual) Number Game Post by Barukh on May 6th, 2005, 3:17am That’s amazing! Every time I post a problem which is IMHO sufficiently hard, there is a solution next day! I should probably stop posting problems to the Hard forum. ;D on 05/04/05 at 12:13:28, SMQ wrote:
Yes, of course. Sorry for the typo. The statement of the problem is a re-formulation of Goodstein’s Theorem (http://en.wikipedia.org/wiki/Goodstein's_theorem). Besides its counter-intuitive nature, it may be also considered as a pretty simple demonstration of Godel’s incompleteness theorem (GIT). The Peano Arithmetic (http://en.wikipedia.org/wiki/Peano_arithmetic) (PA) is an axiomatic system on which most of finite math may be constructed, and is powerful enough to be covered by GIT. The Goodstein’s theorem’s statement belongs to a finite domain, and still cannot be proved in PA: the latter doesn’t include transfinite ordinals, which are essential in theorem’s proof . That means SMQ’s nice argument also uses them somewhere; maybe in the following passage: on 05/04/05 at 16:41:26, SMQ wrote:
The “Hercules and Hydra” game is of the same type. I suggest strongly reading the following (http://www2.maths.bris.ac.uk/~maadb/research/seminars/online/fgfut/index.html) excellent on-line presentation that covers both problems and more. It also contains an answer to Deedlit’s question about termination time in the original game. on 05/04/05 at 18:04:14, Deedlit wrote:
Yes, please! What about other hierarchies of functions? |
||||||||
|
Title: Re: Another (unusual) Number Game Post by SMQ on May 6th, 2005, 5:49am on 05/06/05 at 03:17:42, Barukh wrote:
Most likely here: Quote:
That statement is a nice bit of hand-waving, isn't it? ;D While it seems "obvious" that a proof can be constructed for any desired P, the structure of the full proof resembles the structure of the game itself, and so requires a very large number of more elementary proofs to formally prove anything more significant than about nn^2, which is why I stopped there... And while a proof for any given initial N could be constructed in a finite (albeit excedingly large) number of steps, the formal induction from N to N+1 fails if the "form" of P changes, so the general case remains formally unprovable without those pesky omegas. --SMQ |
||||||||
|
Title: Re: Another (unusual) Number Game Post by Deedlit on May 6th, 2005, 7:31am on 05/06/05 at 05:49:45, SMQ wrote:
Actually, you _can_ prove it without any omegas! Of course, the same proof will work for transfinite ordinals as well, since the differences are cosmetic - but we don't have to have any ordinals. We want to prove the following statements: P(k) = any super-k-n polynomial eventually goes to zero. We prove this by induction, of course. Assume P(k), and let p be a super-(k+1)-n polynomial. That is, p = np1 + np2 + ... + npi, where all the pj are super-k-n polynomials. We wish to prove the above expression must eventually decrement to zero. Does this help? |
||||||||
|
Title: Re: Another (unusual) Number Game Post by SMQ on May 6th, 2005, 10:45am on 05/06/05 at 07:31:48, Deedlit wrote:
Hmm, wouldn't that mean it was provable in PA, then? Or would there still be some other aspect of the proof which isn't expressible in PA? --SMQ |
||||||||
|
Title: Re: Another (unusual) Number Game Post by Deedlit on May 6th, 2005, 3:17pm on 05/06/05 at 10:45:41, SMQ wrote:
No, for any theory there are an infinite number of axioms and rules of inference that you can use to go outside the theory. There seems to be an idea germinating here that it is the notion of transfinite ordinals that fall outside of PA. Not so - the point is that PA can prove the well-ordering of a lot of ordinals, but eventually you hit an ordinal that PA cannot prove the well-ordering of - epsilon0. In a famous paper, Gentzen proved the consistency of PA by assuming the well-ordering of epsilon0. Basically, he did this by assigning to each PA-proof an ordinal in epsilon0, then performing a process known as "cut-elimination" that decreases the associated ordinal each time. This insures that the process ends after finitely many steps. Well, you know from Godel that no recursive theory that encodes basic arithmetic can prove its own consistency! So it follows that PA cannot prove the well-ordering of epsilon0. We call epsilon0 the "proof-theoretic ordinal" of PA. There are actually multiple definitions of proof-theoretic ordinal, but the most common definition is simply the first ordinal that the theory cannot prove the well-ordering of. More specifically, an ordinal alpha is considered "provable" if there exists a primitive recursive relation < on the natural numbers with order type alpha, such that the theory proves that < codes up a well-ordering. (An alternate definition is the smallest ordinal that proves the consistency of the theory; for PA both are epsilon0.) What are the possible values of the proof-theoretic ordinal? Well, if the theory is inconsistent, then all statements are provable, and the provable ordinals are all ordinals that we can define as above, which are exactly the recursive ordinals. So the proof-theoretic ordinal of an inconsistent theory is the first nonrecursive ordinal w1CK. For any consistent Sigma-1-1 theory - without describing Sigma-1-1, let me say that it includes recursively enumerable, and all the usual theories are recursively enumerable - the provable ordinals are an initial segment of the recursive ordinals, so the proof-theoretic ordinal is recursive. Sorry, rambled on a bit long there. ;D |
||||||||
|
Title: Re: Another (unusual) Number Game Post by Deedlit on May 6th, 2005, 4:45pm on 05/06/05 at 03:17:42, Barukh wrote:
I would say this is certainly sufficiently hard, and that SMQ was quite clever even to have the idea of how to solve it! Even so, we still don't have the full proof yet, and there are lots of interesting ways to go from here, so I say success. :D Quote:
These theorems are actually more than simply simple demonstrations of GIT. Although Godel rocked the mathematical world with his incompleteness theorems, a lot of people thought that perhaps the unprovability came about from the rather contrived nature of the unprovable statements; one was a codified version of the Epimenides paradox, and the other is clearly referential to the theory in question. So people wondered if there could be a natural finitary statement that was unprovable in PA. It was then that Paris and Harrington discovered their celebrated theorem: Call a set of natural numbers "large" if the size of the set is larger than the smallest element of the set. P-H Theorem: For any natural numbers n, k, and r, there is a natural number m such that, no matter how you color the k-subsets of the natural numbers in the interval [n,m] using r colors, there is a large subset of [n,m] with all k-subsets the same color. This is, in fact, just a minor alteration of the quite famous Ramsey theorem, and it clearly satisfies both requirements of simplicity and naturalness. A bit later, it was discovered that Goodstein had given a theorem back in 1958 that also turned out to be unprovable; the Goodstein theorem is perhaps not quite as natural as P-H, but the transendence over PA is a little clearer, I think. Quote:
As I have discussed above with SMQ, I don't really think so. For example, we could use "x" instead of "omega" and consider the ordinals to be exponential polynomials instead. If this name and conceptual change is enough to avoid the use of ordinals, then clearly we don't really need "actual" ordinals for anything. On the other hand, if the exponential structures we are discussing are considered "essentially" ordinals, one could say that the exponential structures are embedded in the original theorem and there's no way to really avoid them! Even in the latter case, though, I don't think anyone would consider the easiest proof of the P-H theorem as making essential use of ordinals. With your general background, Barukh, I'll bet you are familiar with Ramsey's theorem, whose infinite version goes like this: For any natural numbers k and r, if we color the k-subsets of the natural numbers with r colors, there will always be an infinite set of natural numbers all of whose k-subsets are the same color. You can probably find a proof of this in one of your references. The infinite version is a close cousin of the finite version For any natural numbers k, r, and t, we can find an n such that, if we color the k-subsets of a set of n elements with r colors, there will always be an subset of cardinality t all of whose k-subsets are the same color, and this theorem certainly falls well within the realm of PA. (The associated function is bounded by a tower of exponents, which is nowhere near the level of Hepsilon_0!) The proof of the infinite version follows basically the same reasoning as the finite version. But from the infinite version we can prove P-H! Proof: Given n, k, and r, color the k-subsets of [n, infinity) using r colors. By the Infinite Ramsey Theorem, there exists an inifinte subset of [n, infinity) with all k-subsets the same color. So we can clearly find an large finite subset of this. By the compactness principle, there is an m such that we can always find a large monchromatic subset in [n,m]. Whoops, we also need the compactness principle - but this doesn't go anywhere near ordinals either! All this can be found in "Ramsey Theory" by Graham, Rothschild, and Spencer. It is true that both theorems imply transfinite induction up to epsilon0 - the Goodstein theorem is clearly equivalent, I'm not sure if P-H is stronger or not. Quote:
Well, if we replace the "n"s by "omega"s, we get exactly the ordinals up to epsilon0! But I would say "essential" use of ordinals is undefined. |
||||||||
|
Title: Re: Another (unusual) Number Game Post by Deedlit on May 6th, 2005, 4:56pm I realize I didn't answer SMQ's question specifically. Well, we don't have the full solution to the problem yet, but basically the problem is it uses quantification over infinite sets. In PA, we are allowed to consider infinite sets as properties of the natural numbers, i.e. "x is prime". But we are not allowed to say things like "for all sets of natural numbers" or "there exists a set of natural numbers". |
||||||||
|
Title: Re: Another (unusual) Number Game Post by Deedlit on May 6th, 2005, 8:44pm Some more on ordinal hierarchies: Another important ordinal hierarchy is the Grzegorczyk-Wainer hierarchy, or fast-growing hierarchy. Actually I've seen multiple definitions, but I'll pick this one: F0 (x) = x + 1 Fa+1 (x) = Fa (Fa (... (x)...)), with x applications of Fa Fa (x) = Fa(x) (x) for limit ordinals a. And I'll also mention the slow-growing hierarchy, which is certainly true to its name! G0 (x) = 0 Ga+1 (x) = Ga(x) + 1 Ga (x) = Ga(x) (x) for limit ordinals a. Question: Of the three ordinal hierarchies I've just mentioned, which two are the closest together? I'll let you think about that for a second. The answer is, the Hardy and Grzegorczyk hierarchies are much closer to each other than either is to the slow-growing hierarchy! First, let's compare the first two hiearchies. Exercise: Show that for a < epsilon0, Fa (x) = Hwa (x). To prove that, the following is useful: Exercise: Prove that if a = (w ^ g) * d, and b < w ^ (g + 1) (everything is an ordinal here), then Ha+b(x) = Ha (Hb (x)) Certainly, that seems to be a rather huge gulf between H and F; 1, 2, and 3 are much less than infinity, infinity squared, and infinity cubed! But if we try to find at what point the F hierarchy passes all Ha for a < epsilon0, we find that it never does - for all a < epsilon0, w^a < epsilon0 as well. So it seems reasonable that Hepsilon_0 is of the same order as Fepsilon_0, and in fact Fepsilon_0 (x) = Fw^^x (x) = Hw^^(x+1) (x), which lies between Hepsilon_0 (x) = Hw^^x(x), and Hepsilon_0 (x+1) = Hw^^(x+1)(x+1). More generally, we find that the Hardy hierarchy "catches up" to the Grzegorczyk hiearchy at every epsilon number. What about the slow-growing hierarchy? Exercise: What is the slow-growing hierarchy for a < epsilon0? You'll notice the pattern rather quickly. We see that Gepsilon_0(x) < F3(x) = Hw^3(x), so we're still nowhere close. In fact, G does not catch up to Hepsilon_0 until a much larger ordinal, known as the Bachmann-Howard ordinal. Does the slow-growing hierarchy eventually catch up to the larger ones? Yes, at an even larger ordinal known as H(1). The ordinals for which the slow-growing hierarchy catches up are known as the subrecursive ordinals. I'll describe these larger ordinals in a later post. I might as well mention where the Ackermann function fits in all this; if we extend the Ackermann function into the transfinite A0 (x) = x + 1 Aa+1 (x) = Aa (Aa (... (1)...)), with x applications of Aa Aa (x) = Aa(x) (x) for limit ordinals a, this turns out to have the same growth rate as the Grzegorczyk. I've only seen this in "Ramsey Theory", though. I've also seen these hierarchies refer not just to functions, but also classes of functions. You may have seen the class of primitive recursive functions defined as a set of initial functions closed under the operations of composition and induction. The Grzegorczyk hierarchy is similar, but each induction takes you to the next class. In this case Fw are exactly the primitive recursive functions, Fepsilon_0 are exactly the functions provably recursive in PA. |
||||||||
|
Title: Re: Another (unusual) Number Game Post by Barukh on May 7th, 2005, 5:31am on 05/06/05 at 16:45:53, Deedlit wrote:
That’s exactly the point: the intellectual power of this forum is big, that posting a really hard problem is a really hard problem ;D Deedlit, generally replying to your extremely interesting and illuminating posts: this is the domain I learn and post about at the same time. You know, it’s very difficult not to post if you learn something new and feel it’s interesting… When thinking about this, I came to the following question: what makes this epsilon0 so special? Why this doesn’t happen with smaller limiting ordinals like ww? |
||||||||
|
Title: Re: Another (unusual) Number Game Post by Barukh on May 7th, 2005, 9:41am on 05/04/05 at 18:04:14, Deedlit wrote:
I saw the following definition: epsilon0 is the smallest ordinal satisfying the transfinite equation wa = a. |
||||||||
|
Title: Re: Another (unusual) Number Game Post by Deedlit on May 7th, 2005, 5:15pm on 05/07/05 at 05:31:23, Barukh wrote:
Well, it varies... I didn't think the seven helicopter problem was so bad, but now it's gathering dust unsolved. :'( Of course, a simple way to flummox the board is to ask something computationally intractable. The recent questions about maximizing the number of chain reactions, or minimizing the number of prisoners you have to shoot, seem likely to fall in this category. (but you never quite know if there isn't some clever way to solve everything!) I'm pretty sure the full solution of the number game is also, but there are some patterns that we can still prove... If you want something that you know is provable in a few pages or less - probably the average theorem in any math book will work. I'd be very impressed if you posted, say, the Lovasz Local Lemma or the Graham-Leeb-Rothschild theorem, and someone could solve it from scratch! Quote:
So far, it's been a lot of fun. :) Quote:
Why doesn't what happen? It seems we could phrase different questions to make each ordinal be the answer... For example: Which ordinals alpha are the alphath limit ordinal? Which ordinals alpha are the alphath additively principle ordinal? The first answer to the first question is w^w; the first answer to the second is epsilon0. Actually, I haven't defined additively principle yet: An ordinal alpha is additively principle if for any ordinals beta, gamma < alpha, we have beta + gamma < alpha. Exercise: The additively principle ordinals are just the ordinals of the form w^a Hint: Like a lot of theorems involving ordinals, the easiest method is by induction. Unlike induction on the natural numbers, there are three cases: the base case 0, alpha => alpha + 1, and then limit alpha assuming all beta < alpha. (the second case can sometimes be handled by the third case). epsilon0 has a certain stature as the proof-theoretic ordinal of PA. w^w is also a proof-theoretic ordinal, of PRA (primitive recursive arithmetic) and its second-order analogue RCA0. I'll post some more stuff on ordinals - while there are some similarities with building up larger numbers, a big difference is that there are clearly some ordinals which are "important" - basically because they are much "rounder" than others, and satisfy stronger closure properties. It's no surprise that proof-theoretic ordinals tend to be one of these. Quote:
Yes, I'll get more into this later. I've been defining things more constructively, to try to give a better "feel" into the relative sizes of these ordinals - but it makes it not the cleanest development. Feel free to critique anything I say here, I'm thinking of keeping this stuff to put into an expository paper or perhaps a talk, so any feedback is much appreciated! |
||||||||
|
Title: Re: Another (unusual) Number Game Post by Barukh on May 8th, 2005, 4:13am on 05/07/05 at 17:15:08, Deedlit wrote:
Or, sorry, I wasn’t specific enough. The question I asked was with respect to the following statement: on 05/06/05 at 15:17:42, Deedlit wrote:
I understand that it follows from the famous Gentzen’s proof, but why it happens for the first time for epsilon0, and not for any smaller or bigger ordinal? Quote:
Great idea! Paper is better, since I won't be able to attend the talk :D. I am going to read thoroughly all your posts; it will take some time. |
||||||||
|
Title: Re: Another (unusual) Number Game Post by Deedlit on May 8th, 2005, 9:12pm on 05/08/05 at 04:13:03, Barukh wrote:
Well, it has to happen sometime! :D The best answer would probably be to read Gentzen's proof. This should give you an idea of the relationship between PA and epsilon0; however, I haven't seen the full treatment myself. I guess PA is probably the most talked about formal theory after ZF or ZFC, which makes epsilon0 rather special. |
||||||||
|
Title: Re: Another (unusual) Number Game Post by Deedlit on May 9th, 2005, 4:06am OK, first let me talk about the definition of ordinals. As I said before, the ordinals were originally conceived as equivalence classes over sets having the same order type. It would me more convenient, however, to have a canonical choice of a set representing an ordinal. It turns out the natural sets consists of ordinals themselves! 0 = {} 1 = {0} = [] 2 = {0, 1} = { {}, [] } 3 = {0, 1, 2} = { {}, [], { {}, [] } } 4 = {0, 1, 2, 3} = { {}, [], { {}, [] }, { {}, [], { {}, [] } } } ... w = {0, 1, 2, 3, ... } w + 1 = {0, 1, 2, 3, ..., w} In fact, the set of all ordinals less than an ordinal alpha, ordered by set inclusion, has exactly the order type corresponding to alpha! (Try to show this by ordinal induction) So the natural definition of ordinal is simply the set of all ordinals less than it. The ordinals using this definition are called the von Neumann ordinals. This is an inductive definition, which isn't really the ideal way to define something. However, people have come up with some clever non-inductive definitions of the ordinals: A set is called transitive if every element in the set is a subset of the set. A set is an ordinal if it is transitive and every element is transitive. A set is an ordinal if it is tranistive and its elements form a linear order under set inclusion. In fact, the ordinals are transitive "all the way down", and its elements are well-ordered under set inclusion. (This is actually a fun little exercise to prove from either definition.) Simple exercise: prove the class of ordinals are well-ordered. This allows us to give a nice definition for the cardinals as well; since having the same order type is a stronger property than having the same cardinality, each cardinal corresponds to a set of ordinals of that cardinality. So we can define a cardinal as the smallest ordinal in that set. (why does there have to be one?) So we have w = aleph0, and generally walpha = alephalpha, and the version we use generally indicates whether we're thinking about them as ordinals or cardinals. Of course, if we don't assume the axiom of choice, then we don't know that every set can be well-ordered (a statement that is equivalent to the axiom of choice). In that case, we have to use an equivalence class definition of some sort. The cardinals that can be well-ordered are then called the alephs. |
||||||||
|
Title: Re: Another (unusual) Number Game Post by Deedlit on May 9th, 2005, 10:37pm Some more basics on ordinals: First, let's talk about how we compare ordinals (and well-ordered sets in general). We say that alpha <= beta if there exists an order-preserving injection f from alpha into beta. That is, for x, y in alpha: 1. x < y <=> f(x) < f(y) 2. f(x) = f(y) => x = y We say that alpha = beta if there is an order preserving bijection from alpha to beta. For general alpha < beta, there will be many possible order-preserving injections; however, if we require that ordinals in the range not be "skipped", that removes all choice in the mapping. This is described by the Trichotomy Law: A subset X of a well-ordered set S is called an initial segment of S, if there is an element x of S such that X = {y | y < x}. Trichotomy Law For any ordinals alpha and beta, precisely one of the following is true: 1. There is an order preserving bijection from an initial segment of alpha into beta. 2. There is an order preserving bijection from alpha into beta. 3. There is an order preserving bijection from alpha into an initial segment of beta. These correspond to alpha < beta, alpha = beta, and alpha > beta respectively. Corollary: alpha <= beta and alpha >= beta <=> alpha = beta. |
||||||||
|
Title: Re: Another (unusual) Number Game Post by Deedlit on May 9th, 2005, 10:51pm Ordinal addition is simple enough; alpha + beta is just the order type of the sum set where every element of beta is greater than every element of alpha. We can also give the definition inductively: The successor to alpha, S(alpha), is the smallest ordinal that is larger than alpha. The supremum of a set of ordinals, sup{ai}, is the smallest ordinal greater than or equal to all ai. Note that from the definition of ordinals, this is the same as the union of the ai! 1. alpha + 0 = alpha 2. alpha + S(beta) = S(alpha + beta) 3. For limit ordinals beta, alpha + beta = sup {alpha + gamma | gamma < beta} Note that this operation is not commutative! We get the order type of 1 + w by sticking an element in front of an w sequence: x, 0, 1, 2, 3, ... which clearly has the same order type as omega. If we stick the element at the end, though, we get: 0, 1, 2, 3, ... , x which is clearly a different order type than w, since it has a maximal element. However, ordinal addition is associative. This is easiest to see with the first definition; a + b + c is simply putting the three ordinals in the order above, and it doesn't matter whether we combine a and b first or b and c first. The additively principle ordinals are the ordinals alpha for which beta, gamma < alpha => beta + gamma < alpha. The additively principle ordinals cannot be decomposed into the sum of two smaller ordinals. Theorem: The additively principle ordinals are exactly the ordinals of the form walpha for some ordinal alpha. This leads directly too... Cantor's Normal Form Theorem: Every ordinal a has a unique representation in the following form: a = wa1 + wa2 + ... + wan, with a1 >= a2 >= ... >= an. A hint for the proof: it's just the well-ordering of the ordinals again. (no infinite decreasing sequences!) Lemma: if alpha < beta, and beta is additively principle, alpha + beta = beta. Addition of ordinals: Given a = wa1 + wa2 + ... + wai, and b = wb1 + wb2 + ... + wbj, then a + b = wa1 + wa2 + ... + wak + wb1 + wb2 + ... + wbj, where k is the largest natural number such that ak >= b1. |
||||||||
|
Title: Re: Another (unusual) Number Game Post by Deedlit on May 9th, 2005, 11:32pm Ordinal multiplication: For ordinals alpha and beta, the product alpha * beta has the same order type as the set of ordered pairs (x, y) with x in beta and y in alpha (note the change in order), ordered lexicographically. That is (a, b) <= (c, d) if either a < c, or a = c and b <= d. Pictorially, we can think of a collection of identical structures with order type beta, with each structure having order type alpha. Again, there's an inductive defintion: 1. alpha * 0 = 0 2. alpha * (beta + 1) = alpha * beta + alpha 3. for limit beta, alpha * beta = sup {alpha * gamma | gamma < beta} Ordinal multiplication is not commutative; the ordinal 2*w has the order type of x1, y1, x2, y2, ... which is the same as w, whereas w*2 has the order type of x1, x2, ..., y1, y2, ... However, it is associative; again, the pictorial description explains it. a * b * c can be represented as a three level hierarchy of structures, with c on the outside, b in the middle and a on the inside; we arrive at this regardless of whether we take a * b first or b * c first. The ordinals satisfy the distributive law a * (b + c) = a * b + a * c, but not (a + b) * c = a * c + b * c; for example, for nj nonnegative integers, (wn1 + wn2 + ... + wni) * ww = sup {(wn1 + wn2 + ... + wni) * wn | n < w} <= sup {wn1 + 1 * wn | n < w} = sup {wn1 + 1 + n | n < w} = ww. More generally, if we define an ordinal alpha is multiplicatively principle if beta, gamma < alpha => beta * gamma < alpha, then Theorem: the multiplicatively principle ordinals are precisely the ordinals of the form ww^alpha for ordinals alpha. Theorem: if alpha < ww^gamma <= beta, and beta is additively principle, then alpha * beta = beta. This can be used evaluate the multiplication of ordinals using Cantor's Normal Form, but I'll leave that as an exercise. |
||||||||
|
Title: Re: Another (unusual) Number Game Post by Barukh on May 13th, 2005, 2:56am Finally, I have read the whole thread to the point that I can ask some questions. on 05/06/05 at 15:17:42, Deedlit wrote:
Now I understand better what stroke me about this: does PA have a notion of ordinals at all? Don’t we need something like the set theory to deal with them (notice the von Neumann’s definition). Quote:
What does than mean “finitely many steps” when considering transfinite ordinals? I assume it’s using the “successor” and “limit” ordinals rule a finite number of times. Is that correct? on 05/04/05 at 17:43:41, Deedlit wrote:
That is very interesting and new to me. It took me some time to comprehend it and still I think I don’t get it right. In what follows I describe my view on this. Please correct me. For any ordinal alpha, Halpha(n) is a function N -> N. 1. The first two rules give the Hardy hierarchy for finite ordinals Hm(n) = n+m. 2. Because w(n) is simply n, I get Hw(n) = Hn(n) = 2n. 3. Proceeding, I get: Hw*m(n) = 2mn Hw^2(n) = 2nn Hw^3(n) = 22n 2n … Hw^m(n) = 2^(2m-2n) 2m-2n … I don’t know whether this agrees with your estimates: :-/ Quote:
If that's correct, we can proceed to slowly-growing hierarchy. |
||||||||
|
Title: Re: Another (unusual) Number Game Post by Deedlit on May 13th, 2005, 6:52pm on 05/13/05 at 02:56:52, Barukh wrote:
Well, don't have a stroke! Let me first talk a little bit about formal theories. Keep in mind that a formal theory is a syntactical object. Meaning, you have an some alphabet of characters, and a language consisting of some subset of the finite strings of that alphabet. A formal theory consists of some subset of that language, representing the formulas that are considered to be derivable. Generally, you have some base formulas known as axioms, and some procedures for generating new theorems known as rules of inference. The theorems are simply all formulas that can be generated. So a theory is just a bunch of strings of characters, and there is no question of them being "true" or "false". (Sorry for all the italics, I thought it might be helpful to highlight all the technical terms.) Of course, this doesn't really mean anything until we attach an interpretation to the theory. (This part is known as the semantics of the theory.) More specifically, we define a structure we will call a model of the theory, and define every symbol in the language of the theory in terms of objects and properties in the model (these definitions are called the interpretation.). We require that every theorem of the theory be true for the model. (Now that we have a model, "true" and "false" have meanings!) But not that every non-theorem be false! Now, typically a theory will have many different models. (In fact, a first order theory will have models of every possible infinite cardinality!) But when we define a theory, usually we have a specific model in mind, and that model is known as the standard model. You probably know this, but a theory was formed back in the 1930's that was designed to provide a fundamental basis for basically all mathematics. This theory is called ZFC, an abbreviation for Zermelo-Fraenkel set theory with Choice. The standard model for ZFC is known as V, defined by: V0 = {}. Valpha+1 = P(Valpha), the power set of Valpha. for lambda limit, Vlambda = U Valpha over all alpha < lambda. V = U Valpha over all ordinals alpha. This construction is known as the iterative hierarchy. In a sense, this shows that ordinals are the most fundamental objects in mathematics, since you need them to define all other mathematical objects! The standard model for PA is of course N, the natural numbers. (However, nonstandard models are often referred to as nonstandard natural numbers.) The most obvious way to embed N in V is to associate each natural number to its corresponding ordinal. This injects N into Vomega, which of course does not contain any transfinite ordinals, so at seems at first that what you are saying is true. However, there is no reason we cannot use the language of PA to talk about ordinals, if we attach a different interpretation to the ordinals! Obviously, we cannot have the full class of ordinals that we have in ZFC, but we can talk about orderings of the integers, and restrict our attention to when the ordering is a well-ordering. Since any such ordering is defined by a finite formula, we are restricted to recursive ordinals only; also, these "ordinals" are coded up as predicates, not variables, so we cannot quantify over them. Still, we can ask, in the metatheory, what are the possible well-orderings of the natural numbers that PA can prove to be well-ordered? This is what is meant by the proof-theoretic ordinal of PA. |
||||||||
|
Title: Re: Another (unusual) Number Game Post by Deedlit on May 13th, 2005, 7:25pm on 05/13/05 at 02:56:52, Barukh wrote:
No, you need to apply the successor and limit operations infinitely many times to get to transfinite ordinals. Every omega length represents an infinite number of successor operations, and every w^w length represents an infinite number of limit operations. But the surprising thing is that, no matter how ridiculously high you go up the ordinal scale (even to large cardinals, say), they are always finite in the downward direction! Theorem: A linearly ordered set S is well-ordered if and only if there does not exist an infinite strictly decreasing sequence of elements of S. Remember a set S is linearly ordered if, for any a, b in S, either a < b, a > b, or a = b. Proof: If a0, a1, ... is an infinite strictly decreasing sequence of S, then the set {ai} is a subset of S with no minimal element. Therefore, S is not well ordered. Assuming that S is not well-ordered, we can find a subset T of S with no minimal element. We can choose a strictly decreasing sequence of T randomly; after choosing {a0, a1, ..., ai}, we know that ai is not minimal, so we can choose some element ai+1 less than it. If we just look at the ordered sets (not necessarily linearly ordered sets) with the "no infinite decreasing sequence" property, these sets are called well-founded. We know the ordinals are well-ordered by set inclusion; which sets are well-founded by set inclusion? It turns out, all of them! This was done on purpose, by the Axiom of Foundation: x != 0 => Ey (y in x and y intersect x = 0) Also, if you look at the iterative hierarchy, you can prove by induction that at each level we only add well-founded sets; the key being the well-foundedness of the ordinals. The well-foundedness of the ordinals is precisely why functional hierarchies are well-defined. If I just made a definition over reals x: f(0) = c. f(x) = h(f(x/2)) this wouldn't be a proper definition, since the reduction step just goes on infinitely. But for structures defined by induction over ordinals, we know that the reduction step needs only to be applied a finite number of times before we reduce to zero. Quote:
Correct so far. Quote:
These are much less than the correct values! If Hw^2(n) = 2nn, then Hw^2+m(n) = 2n+m(n+m), and so Hw^2+w(n) = 22n(2n) |
||||||||
|
Title: Re: Another (unusual) Number Game Post by Deedlit on May 23rd, 2005, 4:03pm Ordinal exponentiation: For ordinals alpha and beta, we define Fin(beta, alpha) to be the set of functions f from beta to alpha, such that f(b) = 0 for all but finitely many b in beta. For f, g in Fin(beta, alpha) we say that f < g if f(b) < g(b), where b is the largest ordinal in beta for which f and g differ. Exercise: Fin(beta, alpha) is well-ordered by the above ordering. Define alphabeta to be the ordinal order-isomorphic to Fin(beta, alpha) with the above ordering. Inductively: alpha0 = 1 alphabeta + 1 = alphabeta * alpha For limit beta, alphabeta = sup {alphagamma for gamma < beta} Exponentiation satisfies the following: alphabeta+gamma = alphabeta alphagamma alphabeta * gamma = (alphabeta)gamma alpha < beta => alphagamma <= betagamma alpha < beta and gamma > 1 => gammaalpha < gammabeta The exponentially principal ordinals are precisely the epsilon numbers. That is, (beta, gamma < alpha => betagamma < alpha) if and only if (gamma < alpha => wgamma < alpha) if and only if (walpha = alpha) Exercise: Compute alphabeta in terms of the Cantor normal forms for alpha and beta. Note that ordinal exponentiation is different from cardinal exponentiation, which is defined as the cardinality of the set of all functions from beta to alpha (no condition that all but finitely many go to zero). In fact, they are about as far apart as one can imagine! Not only alphabeta is countable for countable alpha and beta, but even diagonalizing out to far more powerful notations, we stay within the countable regime. On the other hand, the cardinal exponent 2aleph0 is uncountable; not only that, but by a theorem of Solovay, it is consistent with ZFC that 2aleph0 be just about any uncountable cardinal there is! (there's a single restriction, but it doesn't limit the value from above - it could be any successor cardinal for instance) So a minor modification made all the difference in the world. |
||||||||
|
Title: Re: Another (unusual) Number Game Post by Deedlit on May 23rd, 2005, 4:11pm Ordinal notations part 2: the Veblen hierarchy Continuing on past epsilon0, we know have notations for any ordinal we can build up using the ordinals 1, w, and epsilon0, and using the operations +, *, and ^. The first ordinal we don't have a notation for is epsilon0 ^ epsilon0 ^ epsilon0 ^ ... which happens to be epsilon1, the second ordinal satisfying wa = a. You see where this is going; we keep going until we reach an ordinal that we have no notation for, and that ordinal is the next epsilon number. For a limit ordinal like w, we have that epsilonw = epsilon0 + epsilon1 + epsilon2 + ... and epsilonw is the smallest ordinal not representable by a notation using +, *, ^, and the epsilonn's for n finite. As we climb to higher ordinals, this gives us subscripts for more epsilons, in a self-feeding loop. Does this ever end? Yes, when we get to: epsilon_epsilon_epsilon_... So, we need to define a different operation to extend beyond epsilon. I could pick a new Greek letter, but we are starting to see a pattern emerging here, so I will define: phi (0,beta) = wbeta. These are the ordinals alpha that satisfy "gamma, delta < alpha => gamma + delta < alpha"; in other words, each new w^beta goes beyond the notation with all previous ordinals and the operation +. phi (1,beta) = epsilonbeta. These are the ordinals alpha that satisfy "gamma < beta => wgamma < alpha", or more simply, walpha = alpha. In other words, each new epsilon_beta goes beyond the notation with all previous ordinals and the operations + and w^alpha. So next up is: phi (2,beta) = the betath ordinal gamma that satisfies epsilon_gamma = gamma. or more generally, phi (alpha + 1, beta) = the betath ordinal gamma that satisfies phi (alpha, gamma) = gamma. We have to define the limit ordinals somewhat differently, but it's based on the same idea; to define phi (alpha, beta), we have at our disposal all ordinals phi (alpha, delta) with delta < beta (and of course 0), and we can use all functions phi (gamma, x) for all gamma < alpha (and of course +). The smallest number we still don't have a notation for is phi(alpha, beta). For alpha limit, we get phi (alpha, beta) = the betath ordinal that belongs to the range of phi (gamma, x) for all gamma < alpha. This notation is known as the Veblen hierarchy, and was defined by Oswald Veblen way back in 1908, years before people found any use for these ordinals! |
||||||||
|
Title: Re: Another (unusual) Number Game Post by Barukh on May 24th, 2005, 6:20am on 05/13/05 at 19:25:21, Deedlit wrote:
Let me see if I got it right: once you get to the limit ordinal downward, you “remove” it in one step (because it’s represented as an infinite set in its entirety). So, for instance, starting from w + n, takes n+1 steps to reach zero. What about wm + n? According to your definition, the first term is a limit ordinal. (Please let me know if my questions are too stupid). |
||||||||
|
Title: Re: Another (unusual) Number Game Post by Deedlit on May 24th, 2005, 11:11am on 05/24/05 at 06:20:03, Barukh wrote:
No, by downward I just meant that you need to take a lower ordinal each step. So, starting from w, you need to take a finite ordinal on the next step, so you're guaranteed to reach zero in a finite number of steps. Of course, it's not a *bounded* number of steps; you can make the sequence as long as you want, you just can't make it go on forever. It follows that you will reach zero in a finite number of steps starting from w + n, and hence w * 2, hence w * n, hence w2, hence wn, hence ww, hence epsilon0, and so on up the entire class of ordinals. Quote:
Well, any infinite ordinal written in Cantor Normal Form will have a limit ordinal for it's first term. I'm not sure what you're asking here; wm + n is a successor ordinal, because of the + n, and any decreasing sequence of elements will be finite, because that's true of all ordinals. Quote:
Don't be stupid. :P |
||||||||
|
Title: Re: Another (unusual) Number Game Post by Deedlit on May 25th, 2005, 12:40am Ordinal notations part 3: Gamma0 and the extended Veblen hierarchy Of course, the smallest ordinal we still don't have a notation for is defined by: a0 = 0 an+1 = phi(an, 0) a = a0 + a1 + ... This ordinal a is another important ordinal known as Gamma0, or the Schutte-Feferman ordinal. Just as epsilon_0 is the proof-theoretic ordinal for "finitary mathematics" (PA), Gamma0 is the proof-theoretic ordinal for "predicative mathematics" (ATR). A definition or property is called "impredicative" if the definition depends on the entire set that you are defining over. This is considered a "bad thing" by some people (particularly Poincare) because it leads to problems such as Russell's paradox (and probably for philisophical objections as well). When the limits of predicativity were studied by people such as Feferman and Schutte, it was concluded that the theory ATR best encapsulates predicative reasoning, and the ordinals up to Gamma0 are the predicatively definable ordinals. Although it doesn't _seem_ like the definition of Gamma0 does anything we haven't done before, there is a sense in which it is the first ordinal that cannot be defined without some sort of circular reasoning! Going further, Gamma_alpha is the alphath ordinal beta such that phi(beta,0) = beta. But it's more useful to define: phi (1,0,alpha) = the alphath ordinal beta such that phi(beta,0) = beta. This gives us a new Veblen hierarchy starting on top of the first one; we can keep on adding more Veblen hierarchies with phi (gamma + 1, 0, alpha) = the alphath ordinal beta such that phi (gamma, beta, 0) = beta. For limit gamma, phi (gamma, 0, alpha) = the alphath ordinal that is contained in the range of phi (delta, beta, 0) for all delta < gamma. And then of course phi (1, 0, 0, alpha) = the alphath ordinal beta such that phi (beta, 0, 0) = beta. We can continue adding more places up to infinity; the smallest ordinal not expressible using phi with arbitrarily many places is called the small Veblen ordinal, or Ackermann's ordinal. |
||||||||
|
Title: Re: Another (unusual) Number Game Post by Deedlit on Jun 1st, 2005, 11:17pm Ordinal notations part 4: the Schutte Klammersymbolen In a sense, the extended phi notation stops at a rather strange place; we go up to the omegath variable, and then stop, when normally we keep iterating an ordinal procedure until we reach a fixed point of some type. This is due to the notation, of course; we can hardly write phi with infinitely many variables! The Schutte Klammersymbolen solves this problem. The Klammersymbolen are generally written as n x 2 matrices; however, due to formatting limitations, I will write them as vectors of ordered pairs: [(a1, b1), (a2, b2), ..., (an, bn), (0, b)] The idea is that bi is in the ai th "place". Note that I've distinguished the zeroth place here; this is to keep in mind that we are basically considering these notations as functions over the last coordinate. The definition extends that of the extended Veblen function; the only new wrinkle is what to do when the smallest nonzero place is a limit ordinal. In that case: For limit an, [(a1, b1), (a2, b2), ..., (an, bn + 1), (0, b)] = the bth ordinal beta such that [(a1, b1), (a2, b2), ..., (an, bn), (alpha, beta), (0, 0)] = beta for all alpha < an. For limit an and limit bn, [(a1, b1), (a2, b2), ..., (an, bn), (0, b)] = the bth ordinal beta such that [(a1, b1), (a2, b2), ..., (an, gamma), (alpha, beta), (0, 0)] = beta for all alpha < an, gamma < bn. Note that it is important that only finitely many places are nonzero, not only for having a finite notation, but also for keeping the structure well-ordered; if we were to create an infinite variable extended phi function with no restrictions, then the following sequence phi (..., 1, 1, 1, 1, 0) phi (..., 1, 1, 1, 0, 0) phi (..., 1, 1, 0, 0, 0) phi (..., 1, 0, 0, 0, 0) ... would be an infinite decreasing sequence of ordinals, which is impossible. Summarizing the entire definition: [(0,b)] = wb. [(a1, b1), (a2, b2), ..., (1, bn + 1), (0, b)] = the bth ordinal beta such that [(a1, b1), (a2, b2), ..., (1, bn), (0, beta)] = beta. For limit bn, [(a1, b1), (a2, b2), ..., (1, bn), (0, b)] = the bth ordinal beta such that [(a1, b1), (a2, b2), ..., (1, alpha), (0, beta)] = beta for all alpha < bn. [(a1, b1), (a2, b2), ..., (an + 1, bn + 1), (0, b)] = the bth ordinal beta such that [(a1, b1), (a2, b2), ..., (an+1, bn), (an, beta), (0, 0)] = beta. For limit, bn, [(a1, b1), (a2, b2), ..., (an + 1, bn + 1), (0, b)] = the bth ordinal beta such that [(a1, b1), (a2, b2), ..., (an+1, alpha), (an, beta), (0, 0)] = beta for all alpha < bn. For limit an, [(a1, b1), (a2, b2), ..., (an, bn + 1), (0, b)] = the bth ordinal beta such that [(a1, b1), (a2, b2), ..., (an, bn), (alpha, beta), (0, 0)] = beta for all alpha < an. For limit an and limit bn, [(a1, b1), (a2, b2), ..., (an, bn), (0, b)] = the bth ordinal beta such that [(a1, b1), (a2, b2), ..., (an, gamma), (alpha, beta), (0, 0)] = beta for all alpha < an, gamma < bn. The limit of this notation is known as the Veblen-Schutte ordinal, or the large Veblen ordinal. |
||||||||
|
Powered by YaBB 1 Gold - SP 1.4! Forum software copyright © 2000-2004 Yet another Bulletin Board |