Author |
Topic: Another (unusual) Number Game (Read 4307 times) |
|
Barukh
Uberpuzzler
Gender: 
Posts: 2276
|
 |
Re: Another (unusual) Number Game
« Reply #25 on: May 13th, 2005, 2:56am » |
 Quote  Modify
|
Finally, I have read the whole thread to the point that I can ask some questions.
on May 6th, 2005, 3:17pm, Deedlit wrote:| 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. |
|
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:| 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. |
|
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 May 4th, 2005, 5:43pm, Deedlit wrote: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 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: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
|
|
If that's correct, we can proceed to slowly-growing hierarchy.
|
|
 IP Logged |
|
|
|
Deedlit
Senior Riddler
Posts: 476
|
|
Re: Another (unusual) Number Game
« Reply #26 on: May 13th, 2005, 6:52pm » |
Quote Modify
|
on May 13th, 2005, 2:56am, Barukh 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).
|
|
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.
|
|
IP Logged |
|
|
|
Deedlit
Senior Riddler
Posts: 476
|
|
Re: Another (unusual) Number Game
« Reply #27 on: May 13th, 2005, 7:25pm » |
Quote Modify
|
on May 13th, 2005, 2:56am, Barukh wrote:
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?
|
|
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:
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
|
|
Correct so far.
Quote:
Hw^3(n) = 22n 2n
…
Hw^m(n) = 2^(2m-2n) 2m-2n
…
|
|
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)
|
| « Last Edit: May 13th, 2005, 7:43pm by Deedlit » |
IP Logged |
|
|
|
Deedlit
Senior Riddler
Posts: 476
|
|
Re: Another (unusual) Number Game
« Reply #28 on: May 23rd, 2005, 4:03pm » |
Quote Modify
|
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.
|
|
IP Logged |
|
|
|
Deedlit
Senior Riddler
Posts: 476
|
|
Re: Another (unusual) Number Game
« Reply #29 on: May 23rd, 2005, 4:11pm » |
Quote Modify
|
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!
|
| « Last Edit: May 23rd, 2005, 4:20pm by Deedlit » |
IP Logged |
|
|
|
Barukh
Uberpuzzler
Gender:
Posts: 2276
|
|
Re: Another (unusual) Number Game
« Reply #30 on: May 24th, 2005, 6:20am » |
Quote Modify
|
on May 13th, 2005, 7:25pm, Deedlit wrote:| 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! |
|
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).
|
|
IP Logged |
|
|
|
Deedlit
Senior Riddler
Posts: 476
|
|
Re: Another (unusual) Number Game
« Reply #31 on: May 24th, 2005, 11:11am » |
Quote Modify
|
on May 24th, 2005, 6:20am, Barukh 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.
|
|
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:
What about wm + n? According to your definition, the first term is a limit ordinal.
|
|
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:
(Please let me know if my questions are too stupid).
|
|
Don't be stupid. 
|
|
IP Logged |
|
|
|
Deedlit
Senior Riddler
Posts: 476
|
|
Re: Another (unusual) Number Game
« Reply #32 on: May 25th, 2005, 12:40am » |
Quote Modify
|
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.
|
| « Last Edit: May 25th, 2005, 12:41am by Deedlit » |
IP Logged |
|
|
|
Deedlit
Senior Riddler
Posts: 476
|
|
Re: Another (unusual) Number Game
« Reply #33 on: Jun 1st, 2005, 11:17pm » |
Quote Modify
|
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.
|
| « Last Edit: Jun 1st, 2005, 11:42pm by Deedlit » |
IP Logged |
|
|
|
|
RIDDLES SITE
WRITE MATH!
Home 
Help 
Search 
Members 
Login 
Register
Reply
Notify of replies
Send Topic
Print