July 26, 2006 This Week's Finds in Mathematical Physics (Week 236) John Baez
This week I'd like to catch you up on some papers about categorification and quantum mechanics.
But first, since it's summer vacation, I'd like to take you on a little road trip - to infinity. And then, for fun, a little detective story about the history of the icosahedron.
Cantor invented two kinds of infinities: cardinals and ordinals. Cardinals are more familiar. They say how big sets are. Two sets can be put into 1-1 correspondence iff they have the same number of elements - where this kind of "number" is a cardinal.
But today I want to talk about ordinals. Ordinals say how big "well-ordered" sets are. A set is well-ordered if it's linearly ordered and every nonempty subset has a smallest element.
For example, the empty set
{}
is well-ordered in a trivial sort of way, and the corresponding ordinal is called
0.
Similarly, any set with just one element, like this:
{0}
is well-ordered in a trivial sort of way, and the corresponding ordinal is called
1.
Similarly, any set with two elements, like this:
{0,1}
becomes well-ordered as soon as we decree which element is bigger; the obvious choice is to say 0 < 1. The corresponding ordinal is called
2.
Similarly, any set with three elements, like this:
{0,1,2}
becomes well-ordered as soon as we linearly order it; the obvious choice here is to say 0 < 1 < 2. The corresponding ordinal is called
3.
Perhaps you're getting the pattern - you've probably seen these particular ordinals before, maybe sometime in grade school. They're called finite ordinals, or "natural numbers".
But there's a cute trick they probably didn't teach you then: we can *define* each ordinal to *be* the set of all ordinals less than it:
0 = {} (since no ordinal is less than 0) 1 = {0} (since only 0 is less than 1) 2 = {0,1} (since 0 and 1 are less than 2) 3 = {0,1,2} (since 0, 1 and 2 are less than 3)
and so on. It's nice because now each ordinal *is* a well-ordered set of the size that ordinal stands for. And, we can define one ordinal to be "less than or equal" to another precisely when its a subset of the other.
Now, what comes after all the finite ordinals? Well, the set of all finite ordinals is itself well-ordered:
{0,1,2,3,...}
So, there's an ordinal corresponding to this - and it's the first *infinite* ordinal. It's usually called omega. Using the cute trick I mentioned, we can actually define
omega = {0,1,2,3,...}
Now, what comes after this? Well, it turns out there's a well-ordered set
{0,1,2,3,...,omega}
containing the finite ordinals together with omega, with the obvious notion of "less than": omega is bigger than the rest. Corresponding to this set there's an ordinal called
omega+1
As usual, we can simply define
omega+1 = {0,1,2,3,...,omega}
(At this point you could be confused if you know about cardinals, so let me throw in a word of reassurance. The sets omega and omega+1 have the same "cardinality", but they're different as ordinals, since you can't find a 1-1 and onto function between them that *preserves the ordering*. This is easy to see, since omega+1 has a biggest element while omega does not.)
Now, what comes next? Well, not surprisingly, it's
omega+2 = {0,1,2,3,...,omega,omega+1}
Then comes
omega+3, omega+4, omega+5,...
and so on. You get the idea.
What next?
Well, the ordinal after all these is called omega+omega. People often call it "omega times 2" or "omega 2" for short. So,
It would be fun to have a book with omega pages, each page half as thick as the previous page. You can tell a nice long story with an omega-sized book. But it would be even more fun to have an encyclopedia with omega volumes, each being an omega-sized book, each half as thick as the previous volume. Then you have omega^2 pages - and it can still fit in one bookshelf!
You can probably imagine a bookcase containing omega encyclopedias, each with omega volumes, each with omega pages, for a total of omega^3 pages.
I'm skipping more and more steps to keep you from getting bored. I know you have plenty to do and can't spend an *infinite* amount of time reading This Week's Finds, even if the subject is infinity.
So, if you don't mind me just mentioning some of the high points, there are guys like omega^4 and omega^5 and so on, and after all these comes
omega^omega.
And then what?
Well, then comes omega^omega + 1, and so on, but I'm sure that's boring by now. And then come ordinals like
This actually reminds me of something that happened driving across South Dakota one summer with a friend of mine. We were in college, so we had the summer off, so we drive across the country. We drove across South Dakota all the way from the eastern border to the west on Interstate 90.
This state is huge - about 600 kilometers across, and most of it is really flat, so the drive was really boring. We kept seeing signs for a bunch of tourist attractions on the western edge of the state, like the Badlands and Mt. Rushmore - a mountain that they carved to look like faces of presidents, just to give people some reason to keep driving.
Anyway, I'll tell you the rest of the story later - I see some more ordinals coming up:
We're really whizzing along now just to keep from getting bored - just like my friend and I did in South Dakota. You might fondly imagine that we had fun trading stories and jokes, like they do in road movies. But we were driving all the way from Princeton to my friend Chip's cabin in California. By the time we got to South Dakota, we were all out of stories and jokes.
Anyway, back to my story. For the first half of our half of our trip across the state, we kept seeing signs for something called the South Dakota Tractor Museum.
Oh, wait, here's an interesting ordinal - let's slow down and take a look:
This is pretty boring; we're already going infinitely fast, but we're still just picking up speed, and it'll take a while before we reach something interesting.
Anyway, we started getting really curious about this South Dakota Tractor Museum - it sounded sort of funny. It took 250 kilometers of driving before we passed it. We wouldn't normally care about a tractor museum, but there was really nothing else to think about while we were driving. The only thing to see were fields of grain, and these signs, which kept building up the suspense, saying things like "ONLY 100 MILES TO THE SOUTH DAKOTA TRACTOR MUSEUM!"
At this point we need to stop for gas. Our notation for ordinals runs out at this point!
The ordinals don't stop; it's just our notation that gives out. The set of all ordinals listed up to now - including all the ones we zipped past - is a well-ordered set called
epsilon_0
or "epsilon-nought". This has the amazing property that
epsilon_0 = omega^{epsilon_0}
And, it's the smallest ordinal with this property.
In fact, all the ordinals smaller than epsilon_0 can be drawn as trees. You write them in "Cantor normal form" like this:
using just + and exponentials and 1 and omega, and then you turn this notation into a picture of a tree. I'll leave it as a puzzle to figure out how.
So, the set of (finite, rooted) trees becomes a well-ordered set whose ordinal is epsilon_0. Trees are important in combinatorics and computer science, so epsilon_0 is not really so weird after all.
Another cool thing is that Gentzen proved the consistency of the usual axioms for arithmetic - "Peano arithmetic" - with the help of epsilon_0. He did this by drawing proofs as trees,
As a kind of followup to "week236", here's a question:
It's easy to map the ordinal omega^2 into the real numbers in a one-to-one and order-preserving way. Here's an artist's conception, which uses the second dimension to make things easier to see:
It's also easy to do this for omega^n for any finite n. I think I can also do it for omega^omega. After that I get tired.
Which ordinals can we do this for?
Questions slightly like this were what got Cantor interested in ordinals in the first place - for example, he noticed that a Fourier series must have coefficients going to zero if its sum converges on [0,2pi] - S, where S is any set whose nth derived set is empty. The set shown above is one whose 2nd derived set is nonempty but whose 3rd derived set is empty.
Then he went wild and started thinking about the kth derived set where k is any ordinal.
(The 0th derived set of S is S; the (k+1)st derived set is the set of limit points of the kth derived set, and when k is a limit ordinal we define the kth derived set to be the intersection of all the jth derived sets with j < k.)
But, while some examples of ordinals embedded in R in an order-preserving way are also nice examples of sets whose kth derived set is nonempty for big k, I don't know any stricter relation between my question and Cantor's.
John Baez <b...@math.removethis.ucr.andthis.edu> wrote: >Logicians including Feferman and Schuette have carried out a detailed >analysis of this subject. They know a lot about how much induction >up to different ordinals buys you. And apparently, induction up to >Gamma_0 lets us prove the consistency of a system called "predicative >analysis". I don't understand this, nor do I understand the claim >I've seen that Gamma_0 is the first ordinal that cannot be defined >predicatively - i.e., can't be defined without reference to itself. >Sure, saying Gamma_0 is the first solution of
>phi_x(0) = x
>is non-predicative. But what about saying that Gamma_0 is the union >of all ordinals in the Veblen hierarchy? What's non-predicative >about that?
>If anyone could explain this in simple terms, I'd be much obliged.
The situation is somewhat akin to the situation with the Church-Turing thesis, in that one is tentatively equating an informal notion (predicativity or computability) with a precise mathematical notion. Therefore there is no definitive answer to your question, and Feferman himself has articulated potential objections to the "standard view" that Gamma_0 marks the boundary of predicativity.
Having said that, I'll also say that one of the reasons for the standard view is that Gamma_0 marks the boundary of "autonomous progressions" of arithmetical theories. The book by Torkel Franzen that you cited is probably the most accessible introduction to this subject. Roughly speaking, the idea is that if anyone fully accepts first-order Peano arithmetic PA, then implicitly he accepts its consistency Con(PA), as well as Con(PA+Con(PA)), etc. If one tries to articulate exactly what is "implicitly" involved in accepting PA in this sense, then one can make a plausibility argument that Gamma_0 is a natural stopping point. I think you have a better shot at grasping the underlying intuition via this approach than by staring at Gamma_0 itself and trying to figure out what is non-predicative about its definition. -- Tim Chow tchow-at-alum-dot-mit-dot-edu The range of our projectiles---even ... the artillery---however great, will never exceed four of those miles of which as many thousand separate us from the center of the earth. ---Galileo, Dialogues Concerning Two New Sciences
On 26-Jul-2006, b...@math.removethis.ucr.andthis.edu (John Baez) wrote in message <ea83ig$qm...@news.ks.uiuc.edu>:
[...]
> But as you might have suspected, not *all* ordinals can be written > in this way. For one thing, every ordinal we've reached so far is > *countable*: as a set you can put it in one-to-one correspondence > with the integers. There are much bigger *uncountable* ordinals - > at least if you believe you can well-order uncountable sets.
? Is that last a reference to the Well-Ordering Theorem (equivalent in ZFC to the Axiom of Choice)? Of course, you do need the WOT to prove that /every/ set can be well-ordered, but ZF alone proves the existence of uncountable ordinals.
John Baez in litteris <ead71m$et...@news.ks.uiuc.edu> scripsit:
> It's easy to map the ordinal omega^2 into the real numbers > in a one-to-one and order-preserving way. Here's an artist's > conception, which uses the second dimension to make things > easier to see:
If you're asking which ordinals are order-isomorphic to a subset of the real numbers, the answer is simple (at least, assuming the axiom of choice): exactly the countable ordinals. First, any well-ordered subset of the reals is countable because between any element of the subset and the next ("the next" makes sense, of course, since the set is well-ordered) there is a rational. Conversely, we can prove by transfinite induction that any countable ordinal can be embedded in the reals: it is true of 0, if it is true of alpha it is true of alpha+1, and if it is true of every ordinal alpha<delta for a limit ordinal delta, choose an increasing sequence alpha_n leading up to delta, embed each alpha_n between (n-1)/n and n/(n+1) and put them together... the details are left to the reader (it may be necessary to remove some elements since we took the sum of the alpha_n rather than the limit, but it can also be arranged so that the two coincide).
In fact, every countable ordinal can be embedded in the reals as a closed set (then the embedding is a homeomorphism from the ordinal with the order topology to the subset of the reals with the induced topology), or as a discrete set, but obviously not both (except up to omega).
[I won't bet on what happens in the absence of Choice, but it wouldn't at all surprise me it were consistent that some large countable ordinals can't be embedded in the real line.]
I had produced a graphical representation of epsilon_0, once, but it's actually entirely uninteresting to look at, it's just a mess.
Any finite linear ordering can be embedded in Q. Any countable model of Th(Q) is isomorphic to Q. Hence any countable linear ordering can be embedded into Q, by compactness and lowenheim skolem using the above, and the diagram of the l.o. in question.
So all countable well orderings (i.e. < omega_1). Of the top of my head (on my first coffee of the day), I'd say you'd have problems with point whose cofinality was greater than omega, since R is forst countable.
John Baez <b...@math.removethis.ucr.andthis.edu> wrote:
[snip]
> At first these numbers seem to keep getting bigger! So, it seems > shocking at first that they eventually reach zero. For example, > if you start with the number 4, you get this Goodstein sequence:
Although this number 3 x 10^{60605351} is the number quoted on the website above, I did a back of an envelope calculation which seemed to indicate that it took about (that number)^2 steps to reach zero. In fact the website only claims that the sequence *increases* until the 3 x 10^{60605351}th term, but it's not hard to check that once the sequence has stopped increasing, it starts decreasing very soon afterwards. Did I made a slip? I think that the (2^n*2*n-2)'th term is zero, where n=24*2^24.
John Baez wrote: > As a kind of followup to "week236", here's a question:
> It's easy to map the ordinal omega^2 into the real numbers > in a one-to-one and order-preserving way. Here's an artist's > conception, which uses the second dimension to make things > easier to see:
> It's also easy to do this for omega^n for any finite n. > I think I can also do it for omega^omega. After that I > get tired.
> Which ordinals can we do this for?
As other correspondents have pointed out any countable ordinal, indeed any countable totally ordered set, can be (order-preserving) embedded in Q.
I give a simple proof.
Let A = {a_1, a_2, ... } be a countable totally ordered set. We need an order-preserving injection f: A -> Q. Clearly f is order preserving iff its restriction to A_n = {a_1,...,a_n} is order preserving for all n. Now it is easy to extend an order preserving map A_n -> Q to an order preserving map A_{n+1} -> Q, simply by mapping a_{n+1} into the appropriate one of the n+1 intervals defined by the endpoints f(a_1),...,f(a_n).
By recursion there is an order preserving map from A to Q.
On the other hand there is no embdedding of an uncountable ordinal O into R. To see this, for each m in O take a rational between f(m) and f(m+1). These are all distinct.
In article <eadai0$g3...@news.ks.uiuc.edu>, David Madore
<david.mad...@ens.fr> wrote: > > Which ordinals can we do this for?
> If you're asking which ordinals are order-isomorphic to a subset of > the real numbers, the answer is simple (at least, assuming the axiom > of choice): exactly the countable ordinals.
And more generally: any countable totally ordered set can be imbedded in the rationals.
David Madore <david.mad...@ens.fr> wrote: >John Baez in litteris <ead71m$et...@news.ks.uiuc.edu> scripsit: >> It's easy to map the ordinal omega^2 into the real numbers >> in a one-to-one and order-preserving way. Here's an artist's >> conception, which uses the second dimension to make things >> easier to see:
Thanks! I didn't check to see who made it. The phrase "artist's conception" was intended as a slight joke, since in pop science magazines one often reads things like "here is an artist's conception of romance among australopithecines" adorning pictures that required a lot of imagination to draw - but this time, it was actually a mathematically precise picture!
>> Which ordinals can we do this for? >If you're asking which ordinals are order-isomorphic to a subset of >the real numbers, the answer is simple (at least, assuming the axiom >of choice): exactly the countable ordinals.
Yay! Great! That's exactly what I was asking.
>I had produced a graphical representation of epsilon_0, once, but it's >actually entirely uninteresting to look at, it's just a mess.
If you still have it around, I would be interested to see it - and maybe even attach it to week236. I can see why it would be a mess, though.
I suppose drawing it bigger wouldn't help, but it might be fun to take some large ordinal and draw it in your style on the scale of this artist's conception of a hydrogen atom:
This may be the world's biggest webpage: it's 18 kilometers wide! (That's 50 million pixels at 72 pixels per inch.)
I hadn't known my webbrowser could scroll that far. My wrist didn't even get tired. So, it might be possible to draw omega^omega or something and have it look interesting, even if epsilon_0 is too big.
<david.corfi...@tuebingen.mpg.de> wrote: >> For that, we'd need a generalization of finite sets whose cardinality >>can be be complex. >Has anyone since done anything with the idea >http://groups.google.co.uk/group/sci.math.research/browse_frm/thread/... >that the set of Motzkin paths has cardinality i?
Maybe you meant Motzkin *trees*. In case anyone is wondering, these are rooted planar trees where each node has one or two daughter nodes. The set M of Motzkin trees is equipped with an obvious isomorphism
M = 1 + M + M^2
since every Motzkin tree is either a one-node tree, a node connected by an edge to another Motzkin tree, or a node connected by two edges to two Motzkin trees.
Using the techniques of Schanuel, Gates, Leinster and Fiore, the "generalized cardinality" |M| of the set of Motzkin trees satisfies
|M| = 1 + |M| + |M|^2
so
|M| = +-i
This sort of reasoning seems completely insane at first, but it leads to many valid and interesting results; for details see
Jeff Morton and I put a lot of work into this idea when we were trying to categorify the quantum harmonic oscillator. The Motzkin trees are a categorification of the Gaussian integers; the "+-i" hints that Galois theory is relevant. We figured out how to categorify the algebraic integers in any algebraic extension of the rationals, getting an "algebraic extension" of the category of finite sets. We figured out the beginnings of a theory that associates a "Galois 2-group" to any such algebraic extension. I was pretty excited about this, but Jeff was eager to reach ideas connected to physics, and this seemed like a long way around. In particular, one needs not just algebraic numbers but also transcendentals to make sense of the "exp(-itH)" in quantum mechanics.
So, we dropped this project and came up with a much simpler category of "U(1)-sets" whose "cardinalities" are complex: a U(1)-set is simply a finite sets of points ("quanta") labelled by phases. Here we are putting the phases in "by hand" instead of seeing them emerge from category-theoretic considerations. This is a bit unfortunate, but the advantage is that everything works quite quickly and smoothly, and there's a clear physical meaning to it all.
If anyone who knows categories, combinatorics and Galois theory wants to become a math grad student at UCR and work on the project Jeff and I dropped, they should contact me.
In article <ead71n$et...@news.ks.uiuc.edu>, <tc...@lsa.umich.edu> wrote: >In article <ea83ig$qm...@news.ks.uiuc.edu>, >John Baez <b...@math.removethis.ucr.andthis.edu> wrote: >>Logicians [...] know a lot about how much induction >>up to different ordinals buys you. And apparently, induction up to >>Gamma_0 lets us prove the consistency of a system called "predicative >>analysis". I don't understand this, nor do I understand the claim >>I've seen that Gamma_0 is the first ordinal that cannot be defined >>predicatively - i.e., can't be defined without reference to itself. >>Sure, saying Gamma_0 is the first solution of
>>phi_x(0) = x
>>is non-predicative. But what about saying that Gamma_0 is the union >>of all ordinals in the Veblen hierarchy? What's non-predicative >>about that? >The situation is somewhat akin to the situation with the Church-Turing >thesis, in that one is tentatively equating an informal notion >(predicativity or computability) with a precise mathematical notion. >Therefore there is no definitive answer to your question, and Feferman >himself has articulated potential objections to the "standard view" >that Gamma_0 marks the boundary of predicativity.
There's also someone named Nik Weaver who has debated Feferman on this subject:
He seems to claim that Gamma_0 and even larger ordinals have predicative definitions. However, I'm too ignorant to follow this debate. Usually in physics I have a sense for when people are being reasonable even if I don't follow the details. In this debate I can't even do that.
>Having said that, I'll also say that one of the reasons for the standard >view is that Gamma_0 marks the boundary of "autonomous progressions" of >arithmetical theories. The book by Torkel Franzen that you cited is >probably the most accessible introduction to this subject.
This summer I'm in Shanghai without any academic affiliation, so it's hard to get that book. When I return to Riverside in the fall I'll try to read it. But my curiosity is burning right now, so I'll take the liberty of asking some more questions.
>Roughly >speaking, the idea is that if anyone fully accepts first-order Peano >arithmetic PA, then implicitly he accepts its consistency Con(PA), as >well as Con(PA+Con(PA)), etc.
I assume that by "etcetera" you mean there's one theory like this per ordinal. I browsed a paper by Franzen where he was trying to explicate how these theories actually let you prove interesting new stuff.
It's a bit mysterious: I imagine a guy sitting there thinking "Peano arithmetic is true, so I know it's consistent, and I know *that's* consistent too, and I know *that's* consistent...", and so on - and after pondering this way for an transfinite amount of time, all of a sudden he can do new stuff like prove that Goodstein sequences approach zero!
I think Franzen was trying to dispel this naive conception. He said the real action happens at limit ordinals, where the interpretation of everything changes in some sneaky way.
But, my understanding of his comments like an impressionist painting of a surreal painting - Dali's "Sacrament of the Last Supper" as reworked by Monet.
(Hey, I managed to sneak a docahedron into the discussion!)
>If one tries to articulate exactly what >is "implicitly" involved in accepting PA in this sense, then one can >make a plausibility argument that Gamma_0 is a natural stopping point.
It would be really great if you could say more about this plausibility argument.
>I think you have a better shot at grasping the underlying intuition via >this approach than by staring at Gamma_0 itself and trying to figure out >what is non-predicative about its definition.
Jim Heckman <weu_rznvy-hfr...@lnubb.pbz.invalid> wrote: >On 26-Jul-2006, b...@math.removethis.ucr.andthis.edu (John Baez) >wrote in message <ea83ig$qm...@news.ks.uiuc.edu>: >> But as you might have suspected, not *all* ordinals can be written >> in this way. For one thing, every ordinal we've reached so far is >> *countable*: as a set you can put it in one-to-one correspondence >> with the integers. There are much bigger *uncountable* ordinals - >> at least if you believe you can well-order uncountable sets. >? Is that last a reference to the Well-Ordering Theorem (equivalent >in ZFC to the Axiom of Choice)? Of course, you do need the WOT to >prove that /every/ set can be well-ordered, but ZF alone proves the >existence of uncountable ordinals.
That's interesting; I don't know if I ever knew that! The last time I really studied axiomatic set theory was decades ago.
Anyway, I can easily imagine reasonable people who are comfy up to omega or epsilon_0 (say) but don't believe you can well-order any uncountable sets. So, I didn't want to get into a fight by claiming bluntly that there *are* uncountable ordinals, without any sort of caveat. I didn't want to be advocating ZFC - but now that you bring it up, I don't even want to be advocating ZF.
But, I don't want to argue *against* them, either.
In fact, these days to get my back up you'd need to take a fairly drastic position, like my friend Henry Flynt, who argues that "mathematical knowledge amounts to the crystallization of officially endorsed delusions in an intellectual quicksand":
John Baez <b...@math.removethis.ucr.andthis.edu> wrote: >At first these numbers seem to keep getting bigger! So, it seems >shocking at first that they eventually reach zero. For example, >if you start with the number 4, you get this Goodstein sequence:
he pointed out they actually say the sequence "can increase for approximately 2.6 * 10^{60605351} steps", not that it reaches zero at this point.
Kevin then worked out the details himself, and I checked his calculations. We now seem to agree that the sequence reaches zero at the kth term, where
k = 24 * 2^24 * 2^{24 * 2^{24}} - 2
or approximately
k = 6.9 * 10^{121210694}
Please check and see if we've done it right.
You may also enjoy trying to figure out what the folks at the National Curve Bank meant, and whether *they* were right.
Here is Kevin's email, prettied up by me, but perhaps with some mistakes added:
> apparently it takes about 3 x 10^{60605351} steps to reach zero!
You write this as if it were some kind of mystery. I remember working out this number explicitly when I was a graduate student! There is some nice form for it, as I recall. Let's see if I can reconstruct what I did.
If I've understood the sequence correctly, it should be (where "n)" at the beginning of a line denotes we're working in base n on this line, so strictly speaking it's probably the n-1st term in the sequence)
2) 2^2 = 4 3) 3^3-1 = 2.3^2+2.3+2 = 26 [note: base 3, ends in 2, and 3+2=5] 4) 2.4^2+2.4+1 = 41 [note: base 4, ends in 1, and 4+1=5] 5) 2.5^2+2.5 = 60 [we're at a limit ordinal here, note 3+2=4+1=5] 6) 2.6^2+2.6-1 = 2.6^2+6+5 = 83 [note: base 6, ends in 5] 7) 2.7^2+7+4 [note: base 7, ends in 4] 8) 2.8^2+8+3 [note: base 8, ends in 3, so we next get a limit ordinal at...] . . 11) 2.11^2+11 12) 2.12^2+12-1 = 2.12^2+11 13) 2.13^2+10 . . . 23) 2.23^2 (as 23 = 12+11 = 13+10= ...) 24) 24^2+23.24+23 . . . 47) 47^2+23.47 48) 48^2+22.48+47 . . . 95) 95^2+22.95 96) 96^2+21.96+95 . . .
and now we spot a pattern: we're just doubling---getting a limit ordinal at bases 24-1, 48-1, 96-1 and so on. Let's look again at those limit ordinals:
where m = n2^{n-1} - 1. The sequence now looks like
m+1) (m+1)-1 = m m+2) m-1 m+3) m-2 . . . 2m+1) 0
So the sequence becomes zero at base n2^n - 1, where n = 24 * 2^24. If 2^2 is the first term in the sequence, I guess this is the (n2^n - 2)th term. I make this about 6.9*10^{121210694} - curses, you got something else! Actually, I have about the square of what you wrote and hence I have most likely made a slip. On the other hand you can see that it's not a mystery at all, it's just an elementary exercise. It really helps you learn about why the countable ordinals are well-ordered too: as you continue working out the numbers, you always have this impending sense of doom telling you that your gut feeling that the sequence tends to infinity might just be wrong...
Discussion subject changed to "graphical representation of epsilon_0 (was: Re: Order-preserving embeddings of ordinals in the real numbers)" by David Madore
John Baez in litteris <eag2eg$bc...@news.ks.uiuc.edu> scripsit:
> In article <eadai0$g3...@news.ks.uiuc.edu>, > David Madore <david.mad...@ens.fr> wrote: >>I had produced a graphical representation of epsilon_0, once, but it's >>actually entirely uninteresting to look at, it's just a mess.
> If you still have it around, I would be interested to see it - and maybe > even attach it to week236. I can see why it would be a mess, though.
Try <URL: http://www.madore.org/~david/.tmp/eps0-2.ps.gz > (gzipped PostScript file). And if you replace ".ps.gz" by ".c" you have the (pretty much unreadable) C program which might have been used to generate it... except that it doesn't seem to generate exactly the same thing, so I don't really know (I presume some parameter was set to a different value). As the URL indicates, these files might not stay long, but you're welcome to do what you wish with them.
John Baez <b...@math.removethis.ucr.andthis.edu> wrote: >I assume that by "etcetera" you mean there's one theory like this >per ordinal. [...] >>If one tries to articulate exactly what >>is "implicitly" involved in accepting PA in this sense, then one can >>make a plausibility argument that Gamma_0 is a natural stopping point.
>It would be really great if you could say more about this >plausibility argument.
Let's look more closely at what the notion of "one theory like this per ordinal" means. There's no difficulty figuring out what "Con(PA)" means or how to express that statement in the first-order language of arithmetic. Ditto with "Con(PA+Con(PA))". However, once you start ascending the ordinal hierarchy, a difficulty appears. The language of arithmetic doesn't let you talk about "ordinals" directly---that's a set-theoretical concept. In order to express a statement like "Con(T)" for some theory T, you need at minimum to be able to give some sort of "recursive description" or "recursive axiomatization" of T (where here I use the word "recursive" in the technical sense of recursive function theory) in the first-order language of arithmetic. This observation already yields the intuition that we're not going to be able to ascend beyond the Church-Kleene ordinal, because we won't even be able to figure out how to *say* "T is consistent" for a theory T that requires that many iterations to reach from PA.
There are other problems, though, that potentially get in the way before we reach the Church-Kleene ordinal. Once we realize that what we need is a system of "ordinal notations" to "fake" the relevant set theory, we may (if we are predicavists) worry about issues such as:
1. As we ascend the ordinal hierarchy, isn't it illegitimate to make a jump to an ordinal alpha unless we've already proved, at the level of some ordinal beta that we've already reached, that an ordinal of type alpha exists?
2. And isn't it illegitimate to create sets by quantification over things other than the natural numbers themselves and sets that we've already created?
Condition 1 goes by the name of "autonomy" and condition 2 goes by the name of "ramification." If one formalizes these notions in a certain plausible manner, then one arrives at Gamma_0 as the least upper bound of theories that you can get to, starting with (for example) PA.
One can of course wonder whether 1 and 2 above really capture the concept of "predicativity." Some secondary evidence has accumulated of the following form: Some argument that intuitively seems to be predicative but that is not immediately seen to be provable in the Feferman-Schuette framework is shown, after some work, to indeed be provable below Gamma_0.
It's still possible, of course, for someone---you mentioned Nik Weaver---to come along and argue that our intuitive notion of predicativism, fuzzy though it is, can't possibly be identified with the level Gamma_0. The reason you can't seem to decide immediately whether Weaver's position is nonsensical or not is probably because the critical questions are not mathematical but philosophical, and of course it's usually harder to arrive at definitive answers in philosophy than in mathematics. -- Tim Chow tchow-at-alum-dot-mit-dot-edu The range of our projectiles---even ... the artillery---however great, will never exceed four of those miles of which as many thousand separate us from the center of the earth. ---Galileo, Dialogues Concerning Two New Sciences
But of course there are loads of combinatorial interpretations, including the trees you mention (which was actually the way I found the link between Leinster and Fiore's construction and the Motzkin numbers.)
> If anyone who knows categories, combinatorics and Galois theory > wants to become a math grad student at UCR and work on the project > Jeff and I dropped, they should contact me.
In article <1154275307.024570.110...@h48g2000cwc.googlegroups.com>,
<david.corfi...@tuebingen.mpg.de> wrote: >> Maybe you meant Motzkin *trees*. >No, I did mean paths...
Okay, whoops - I'd forgotten all about that!
>But of course there are loads of combinatorial interpretations, >including the trees you mention (which was actually the way I found the >link between Leinster and Fiore's construction and the Motzkin >numbers.)
Sorry, I even forgot your role in this. It winds up that trees are more useful than paths, because if we have any polynomial fixed-point equation with natural number coefficients, like
X = 349X^7 + 3X^4 + 2
we can interpret it as defining a set of "colored trees". To do this, we interpret the equal sign as an isomorphism.
For example, the above equation defines the set X of planar, rooted, finite trees where the root is colored in one of 2 ways, and each node either has 4 branches coming out of it (in which case this node is colored in one of 3 ways) or 7 branches coming out of it (in which case it's colored in one of 349 ways).
By the work of Schanuel, Gates, Fiore and Leinster, it makes sense to assign a cardinality to this set which is a root of the above polynomial.
A good example is the "Golden Object" discovered by Robin Houston:
The golden number is usually defined by the equation
G^2 = G + 1 (1)
which is not of the fixed-point form described above. However, Houston made the substitution
G = H + 2 (2)
and notes that
H = H^2 + 4H + 1 (3)
is of the desired fixed-point form. So, H is a set of colored trees and G is the disjoint union of H and the 2-element set.
So, we can think of G as a set of "colored trees" of a slightly more general type. (Houston gives another interpretation.)
Anyway, using this sort of trick we might able to cook up a category of colored trees containing the category of finite sets, but also objects having cardinality equal to any algebraic number! This would be a candidate for a categorified version of the algebraic closure of Q.
> >> But as you might have suspected, not *all* ordinals can be written > >> in this way. For one thing, every ordinal we've reached so far is > >> *countable*: as a set you can put it in one-to-one correspondence > >> with the integers. There are much bigger *uncountable* ordinals - > >> at least if you believe you can well-order uncountable sets.
> >? Is that last a reference to the Well-Ordering Theorem (equivalent > >in ZFC to the Axiom of Choice)? Of course, you do need the WOT to > >prove that /every/ set can be well-ordered, but ZF alone proves the > >existence of uncountable ordinals.
> That's interesting; I don't know if I ever knew that! The last > time I really studied axiomatic set theory was decades ago.
> Anyway, I can easily imagine reasonable people who are comfy up > to omega or epsilon_0 (say) but don't believe you can well-order > any uncountable sets. So, I didn't want to get into a fight by > claiming bluntly that there *are* uncountable ordinals, without > any sort of caveat. I didn't want to be advocating ZFC - but now > that you bring it up, I don't even want to be advocating ZF.
> But, I don't want to argue *against* them, either.
OK, but I'd be interested to know which ZF axioms your "imagine[d] reasonable people" don't believe. Or is their problem with mathematical logic?
On Mon, 31 Jul 2006 21:46:52 +0000, Jim Heckman wrote: > I'd be interested to know which ZF axioms your "imagine[d] reasonable > people" don't believe.
For some people it's not a case of "believing" or "not believing" ZF axioms. It's rather a matter of not believing in a single objective world of sets.
Compare the situation with Euclidean/non-Euclidean geometry: we don't have to declare that we "believe" or "don't believe" the parallel postulate. (Such a declaration would only mean anything if we were referring to some objective world, e.g. our physical universe.) You simply study whatever geometrical system fits your purpose. Similarly, you can study whatever set-theoretic system fits your purpose.
For example, if you're writing about combinatorics you might declare "in this paper, all sets will be assumed finite". You might only be doing this in order to save having to write the word "finite" over and over again. On the other hand, the chances are you'd be doing various operations on your finite sets (forming products, taking power-sets, etc), and that would depend on the fact/supposition that the world of finite sets admits such operations - obeys some of the ZF axioms, if you like. In terms of belief, it could be said that you've temporarily suspended your belief in the axiom of infinity. But I don't think "belief" is a good way to look at it.
One variant of your question is: in what ways could you modify the ZF axioms and still reasonably call them axioms for "sets"? Obviously this is a fuzzy question, but it's not so fuzzy as to be meaningless. E.g. I suppose most people would agree that if you add the Axiom of Choice then you could still reasonably say that the result (i.e. ZFC) is a system of axioms for some kind of set theory, but no one would agree that if you threw out all the ZF axioms and replaced them with axioms for the complex numbers then those could be called axioms for a set theory.
David Madore <david.mad...@ens.fr> wrote: >John Baez in litteris <eag2eg$bc...@news.ks.uiuc.edu> scripsit: >> David Madore <david.mad...@ens.fr> wrote: >>>I had produced a graphical representation of epsilon_0, once, but it's >>>actually entirely uninteresting to look at, it's just a mess. >> If you still have it around, I would be interested to see it - and maybe >> even attach it to week236.
>Try <URL: http://www.madore.org/~david/.tmp/eps0-2.ps.gz > (gzipped >PostScript file). And if you replace ".ps.gz" by ".c" you have the >(pretty much unreadable) C program which might have been used to >generate it... except that it doesn't seem to generate exactly the >same thing, so I don't really know (I presume some parameter was set >to a different value). As the URL indicates, these files might not >stay long, but you're welcome to do what you wish with them.
Thanks. Could it be that this PostScript file shows a picture, not of epsilon_0, but of omega^omega?
There's a countable sequence of really big lines. The first one is clearly 0. The second is clearly omega. It looks to me like the third could be omega^2... and so on.
Hmm, but maybe the third really big line is omega^omega. Clearly if you're drawing epsilon_0 we should see big lines for omega, omega^omega, omega^omega^omega and so on.
Between the second and third really big lines I see a countable sequence of "pretty big" lines. I thought these were omega 2, omega 3, and so on... leading up to omega^2. But now, looking more carefully, I see some fine structure which suggests they could be higher ordinals, perhaps leading up to omega^omega.
ANYWAY:
If any hacker out there creates nice pictures of omega^omega and/or epsilon_0, I'll put them on my website. If you do both and I think they're really nice, I'll also give you a signed copy of the new (corrected) version of "Gauge Fields, Knots and Gravity", as soon I can buy it from World Scientific (I got my copy a while ago, so it should be coming out soon.) Or, if you prefer, some other book of comparable price.
Fine print: if a bunch of people attempt this, I'll give prizes for the one or two that look the best. To be cool, the picture should be in David Madore's style:
unless you can think of something better. The main problem with the second picture above is that the fine structure gets too small too fast, so it's hard to see what's going on.
To be *really* cool, the picture will be an impressively tall or wide webpage, along these lines:
Jim Heckman <weu_rznvy-hfr...@lnubb.pbz.invalid> wrote: >OK, but I'd be interested to know which ZF axioms your "imagine[d] >reasonable people" don't believe. Or is their problem with >mathematical logic?
I can imagine all sorts of reasonable people who believe all sorts of things. And, I even know some of them.
For example, I can imagine various sorts of reasonable constructivists:
and my former student Toby Bartels (who just got his PhD) is one. Most such people don't believe in the law of excluded middle, so ZF is right out. And, I believe most of them don't believe you can well-order uncountable sets, because I've never heard of any way to "construct" a well-ordered uncountable set, in the technical sense of "construct".
I can also imagine various sorts of reasonable finitists:
meaning people who don't believe in unbelievably large finite numbers. Unfortunately, it seems hard to develop good axioms formalizing this view, perhaps because the normal concept of proof allows arbitrarily long proofs. I know Christer Hennix and Alexander Esenin-Volpin have tried, but I don't know how far they've gotten. Edward Nelson hasn't worked much on ultrafinitism, but he has expressed sympathetic views in his book "Predicative Arithmetic". In his article "Mathematics and Faith":
I must relate how I lost my faith in Pythagorean numbers. One morning at the 1976 Summer Meeting of the American Mathematical Society in Toronto, I woke early. As I lay meditating about numbers, I felt the momentary overwhelming presence of one who convicted me of arrogance for my belief in the real existence of an infinite world of numbers, leaving me like an infant in a crib reduced to counting on my fingers. Now I believe in a world where there are no numbers save that human beings on occasion construct.
Personally I don't advocate any of these positions, and like Tom Leinster I am happy that you can do mathematics without "believing in" any specific axiom system.
Personal stuff:
Edward Nelson is a mathematical physicist at Princeton who like me was a student of Irving Segal. I never discussed logic with him, though he read and critiqued my senior thesis when I was an undergrad, and this thesis was on applications of recursive function theory to quantum mechanics.
I used to argue heatedly with Christer Hennix, because he regarded all mathematics using infinity as a sham. I should have spent my time asking him how Esenin-Volpin's alternative system was supposed to work. But our discussions weren't a total waste, because I met my wife through a friend of his - Henry Flynt:
known as the inventor of "concept art", musician, and cognitive nihilist. I'm not sure Henry Flynt would want to be characterized as a "reasonable person".
I only met Esenin-Volpin a couple of times. Besides being the son of the famous Russian poet Sergey Yesenin and the main proponent of ultra-intuitionism, he is known for being a topologist, a dissident during the Soviet era, and a political prisoner who spent a total of 14 years in jail and was exiled to Kazakhstan for 5. His imprisonments were supposedly for psychiatric reasons, but Vladimir Bukovsky has been quoted as saying that Volpin's diagnosis was "pathological honesty":
John Baez wrote: > If any hacker out there creates nice pictures of omega^omega > and/or epsilon_0, I'll put them on my website. If you do > both and I think they're really nice, I'll also give you a > signed copy of the new (corrected) version of "Gauge Fields, > Knots and Gravity", as soon I can buy it from World Scientific > (I got my copy a while ago, so it should be coming out soon.) > Or, if you prefer, some other book of comparable price.
Just an idea for how it might be done with omega^omega:
First, here's a nice 1-1 order-preserving map f from omega^omega onto a subset S of the dyadic rationals: map 0 to 0, and given the ordinal
x = a_n*omega^n + a_(n-1)*omega^(n-1) + ... + a_0
where a_i < omega and a_n>0,
write down a (binary) point, followed by n 1s, followed by a 0, followed by (a_n)-1 1s, followed by a 0, followed by a_(n-1) 1s, followed by a 0, followed by a_(n-2) 1s, followed by a 0, followed by ... a_0 1s.
Call this number f(x).
Then, find some way to represent the 'visibility' of x (the heights of the lines): for example,
where 0<k,c<1 (there may be prettier ways to do it).
Then, plot v(x) against f(x), where x ranges over some subset of omega^omega constructed so that it includes all x with v(x) > delta > 0 (this is where the hacking comes in and I give up!)
Could binary expansions be used in a similar (but more complex) way to represent epsilon_0?
|
