Author |
Topic: Another (unusual) Number Game (Read 4294 times) |
|
Barukh
Uberpuzzler
Gender: 
Posts: 2276
|
 |
Another (unusual) Number Game
« on: May 4th, 2005, 10:19am » |
 Quote  Modify
|
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:
129 = 27 + 1 = 22^2+2+1 + 1.
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, …
|
|
 IP Logged |
|
|
|
SMQ
wu::riddles Moderator
Uberpuzzler
Gender:
Posts: 2084
|
|
Re: Another (unusual) Number Game
« Reply #1 on: May 4th, 2005, 12:13pm » |
Quote Modify
|
Don't you mean 467? 
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
|
| « Last Edit: May 4th, 2005, 12:19pm by SMQ » |
IP Logged |
--SMQ
|
|
|
SMQ
wu::riddles Moderator
Uberpuzzler
Gender:
Posts: 2084
|
|
Re: Another (unusual) Number Game
« Reply #2 on: May 4th, 2005, 4:41pm » |
Quote Modify
|
I believe that, surprisingly, the game is not winnable!
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
|
|
IP Logged |
--SMQ
|
|
|
Deedlit
Senior Riddler
Posts: 476
|
|
Re: Another (unusual) Number Game
« Reply #3 on: May 4th, 2005, 5:43pm » |
Quote Modify
|
Hmmm... I'll pick 16, then demand that the computer run the whole procedure if he claims a win.
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
|
| « Last Edit: May 4th, 2005, 6:01pm by Deedlit » |
IP Logged |
|
|
|
Deedlit
Senior Riddler
Posts: 476
|
|
Re: Another (unusual) Number Game
« Reply #4 on: May 4th, 2005, 6:04pm » |
Quote Modify
|
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.
|
|
IP Logged |
|
|
|
Deedlit
Senior Riddler
Posts: 476
|
|
Re: Another (unusual) Number Game
« Reply #5 on: May 4th, 2005, 6:33pm » |
Quote Modify
|
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?
|
|
IP Logged |
|
|
|
Leo Broukhis
Senior Riddler
Gender:
Posts: 459
|
|
Re: Another (unusual) Number Game
« Reply #6 on: May 5th, 2005, 11:54am » |
Quote Modify
|
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.
|
|
IP Logged |
|
|
|
Deedlit
Senior Riddler
Posts: 476
|
|
Re: Another (unusual) Number Game
« Reply #7 on: May 5th, 2005, 3:58pm » |
Quote Modify
|
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}.
|
| « Last Edit: May 5th, 2005, 4:28pm by Deedlit » |
IP Logged |
|
|
|
Barukh
Uberpuzzler
Gender:
Posts: 2276
|
|
Re: Another (unusual) Number Game
« Reply #8 on: May 6th, 2005, 3:17am » |
Quote Modify
|
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.
on May 4th, 2005, 12:13pm, SMQ wrote:| Don't you mean 467? |
|
Yes, of course. Sorry for the typo.
The statement of the problem is a re-formulation of 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 (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 May 4th, 2005, 4:41pm, SMQ wrote:| 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. |
|
The “Hercules and Hydra” game is of the same type. I suggest strongly reading the following 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 May 4th, 2005, 6:04pm, Deedlit wrote:| I'll continue if someone is curious. |
|
Yes, please! What about other hierarchies of functions?
|
|
IP Logged |
|
|
|
SMQ
wu::riddles Moderator
Uberpuzzler
Gender:
Posts: 2084
|
|
Re: Another (unusual) Number Game
« Reply #9 on: May 6th, 2005, 5:49am » |
Quote Modify
|
on May 6th, 2005, 3:17am, Barukh wrote:| [Peano Arithmetic] doesn’t include transfinite ordinals, which are essential in theorem’s proof . That means SMQ’s nice argument also uses them somewhere; |
|
Most likely here:
Quote:| Continuing in the manner of Lemma 2 above |
|
That statement is a nice bit of hand-waving, isn't it?
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
|
| « Last Edit: May 6th, 2005, 6:50am by SMQ » |
IP Logged |
--SMQ
|
|
|
Deedlit
Senior Riddler
Posts: 476
|
|
Re: Another (unusual) Number Game
« Reply #10 on: May 6th, 2005, 7:31am » |
Quote Modify
|
on May 6th, 2005, 5:49am, SMQ wrote:
Most likely here:
That statement is a nice bit of hand-waving, isn't it?
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 |
|
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?
|
|
IP Logged |
|
|
|
SMQ
wu::riddles Moderator
Uberpuzzler
Gender:
Posts: 2084
|
|
Re: Another (unusual) Number Game
« Reply #11 on: May 6th, 2005, 10:45am » |
Quote Modify
|
on May 6th, 2005, 7:31am, Deedlit wrote:| Actually, you _can_ prove it without any omegas! |
|
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
|
|
IP Logged |
--SMQ
|
|
|
Deedlit
Senior Riddler
Posts: 476
|
|
Re: Another (unusual) Number Game
« Reply #12 on: May 6th, 2005, 3:17pm » |
Quote Modify
|
on May 6th, 2005, 10:45am, SMQ wrote:
Hmm, wouldn't that mean it was provable in PA, then? --SMQ |
|
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.
|
|
IP Logged |
|
|
|
Deedlit
Senior Riddler
Posts: 476
|
|
Re: Another (unusual) Number Game
« Reply #13 on: May 6th, 2005, 4:45pm » |
Quote Modify
|
on May 6th, 2005, 3:17am, Barukh wrote: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.
|
|
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. 
Quote:
The statement of the problem is a re-formulation of Goodstein’s Theorem. Besides its counter-intuitive nature, it may be also considered as a pretty simple demonstration of Godel’s incompleteness theorem (GIT).
|
|
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:
The Peano Arithmetic 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.
|
|
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:
That means SMQ’s nice argument also uses them somewhere; maybe in the following passage:
|
|
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.
|
|
IP Logged |
|
|
|
Deedlit
Senior Riddler
Posts: 476
|
|
Re: Another (unusual) Number Game
« Reply #14 on: May 6th, 2005, 4:56pm » |
Quote Modify
|
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".
|
|
IP Logged |
|
|
|
Deedlit
Senior Riddler
Posts: 476
|
|
Re: Another (unusual) Number Game
« Reply #15 on: May 6th, 2005, 8:44pm » |
Quote Modify
|
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.
|
| « Last Edit: May 7th, 2005, 12:40am by Deedlit » |
IP Logged |
|
|
|
Barukh
Uberpuzzler
Gender:
Posts: 2276
|
|
Re: Another (unusual) Number Game
« Reply #16 on: May 7th, 2005, 5:31am » |
Quote Modify
|
on May 6th, 2005, 4:45pm, Deedlit 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! |
|
That’s exactly the point: the intellectual power of this forum is big, that posting a really hard problem is a really hard problem
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?
|
|
IP Logged |
|
|
|
Barukh
Uberpuzzler
Gender:
Posts: 2276
|
|
Re: Another (unusual) Number Game
« Reply #17 on: May 7th, 2005, 9:41am » |
Quote Modify
|
on May 4th, 2005, 6:04pm, Deedlit wrote:| epsilon_0 = w + w^w + w^(w^w) + ... |
|
I saw the following definition: epsilon0 is the smallest ordinal satisfying the transfinite equation wa = a.
|
|
IP Logged |
|
|
|
Deedlit
Senior Riddler
Posts: 476
|
|
Re: Another (unusual) Number Game
« Reply #18 on: May 7th, 2005, 5:15pm » |
Quote Modify
|
on May 7th, 2005, 5:31am, Barukh 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
|
|
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:
You know, it’s very difficult not to post if you learn something new and feel it’s interesting…
|
|
So far, it's been a lot of fun. 
Quote:
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?
|
|
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:| I saw the following definition: epsilon0 is the smallest ordinal satisfying the transfinite equation wa = a. |
|
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!
|
|
IP Logged |
|
|
|
Barukh
Uberpuzzler
Gender:
Posts: 2276
|
|
Re: Another (unusual) Number Game
« Reply #19 on: May 8th, 2005, 4:13am » |
Quote Modify
|
on May 7th, 2005, 5:15pm, Deedlit wrote:| Why doesn't what happen? It seems we could phrase different questions to make each ordinal be the answer... |
|
Or, sorry, I wasn’t specific enough. The question I asked was with respect to the following statement:
on May 6th, 2005, 3:17pm, Deedlit wrote:| …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. |
|
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:| 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! |
|
Great idea! Paper is better, since I won't be able to attend the talk . I am going to read thoroughly all your posts; it will take some time.
|
|
IP Logged |
|
|
|
Deedlit
Senior Riddler
Posts: 476
|
|
Re: Another (unusual) Number Game
« Reply #20 on: May 8th, 2005, 9:12pm » |
Quote Modify
|
on May 8th, 2005, 4:13am, Barukh 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?
|
|
Well, it has to happen sometime! 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.
|
|
IP Logged |
|
|
|
Deedlit
Senior Riddler
Posts: 476
|
|
Re: Another (unusual) Number Game
« Reply #21 on: May 9th, 2005, 4:06am » |
Quote Modify
|
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.
|
|
IP Logged |
|
|
|
Deedlit
Senior Riddler
Posts: 476
|
|
Re: Another (unusual) Number Game
« Reply #22 on: May 9th, 2005, 10:37pm » |
Quote Modify
|
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.
|
|
IP Logged |
|
|
|
Deedlit
Senior Riddler
Posts: 476
|
|
Re: Another (unusual) Number Game
« Reply #23 on: May 9th, 2005, 10:51pm » |
Quote Modify
|
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.
|
| « Last Edit: May 9th, 2005, 11:02pm by Deedlit » |
IP Logged |
|
|
|
Deedlit
Senior Riddler
Posts: 476
|
|
Re: Another (unusual) Number Game
« Reply #24 on: May 9th, 2005, 11:32pm » |
Quote Modify
|
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.
|
| « Last Edit: May 10th, 2005, 12:26am by Deedlit » |
IP Logged |
|
|
|
|
RIDDLES SITE
WRITE MATH!
Home 
Help 
Search 
Members 
Login 
Register
Reply
Notify of replies
Send Topic
Print