- Here's a link I ought to have included, giving an explanation of Goodstein Sequences, the basic idea behind the Hydra problem.
- A point I don't think I made sufficiently clear in that post is that, while the basic notion of using hierarchies of functions to define ordinals is widely shared, the higher up you go the less agreement there is on what hierarchies ought to look like. There's no one natural or universally accepted representation, at least not one that's been identified to date. Veblen's phi hierarchy, introduced back in 1908, seems to have attracted general use anymore, but there's no reason you couldn't ignore it entirely and define your own equally valid representation if it suits your needs better. This recent paper discusses a number of concerns, including the ongoing problem of "proper" ordinal notation. As you can see in that paper, the state of the art as of ten years ago was well beyond anything I mentioned in that previous post. I'll try to fill that gap if I ever get a better handle on the material. Right now it's Greek to me. One interesting tidbit is that some recent notational innovations go beyond the existing trick of using 'big' ordinals (w1/Omega/aleph-1 and larger) to help describe "normal", countable ordinals (generally beyond Gamma_0), which makes some mathematicians uneasy, or at least they find the practice unsatisfying. I think the justification has something to do with the big ordinals merely being indexes into the hierarchy of functions, and not being part of the functions themselves. I think. Regardless, the state of the art moves beyond alephs into the land of large cardinals, up to at least supercompact cardinals. Which is pretty damn big, if you ask me.
- I'd intended to spend some time pondering the relationship (if any) between ordinals and hyperreal numbers in that post, and just didn't get to it. It's not a topic I've seen a lot of discussion about, although here's a somewhat recent Usenet thread discussing the idea. I think for the most part it just doesn't come up in the course of normal mathematical work. If you're using hyperreals, you don't really need or care about ordinals, and vice versa, so positing any relationship between the two would just be unnecessary.
To me, things would seem generally nicer and tidier if you could regard the countable ordinals as a subset of the hyperreals, for example. Or more precisely, as a subset of the hypernaturals, themselves a subset of the hyperreals. Identifying the sequence (1,2,3,...,n,...) with the ordinal omega (denoted here by 'w') doesn't seem like that big of a stretch. Venturing off to one side for a moment, the surreal numbers are intended to be all-encompassing, and it's been stated that the surreals include the class of all ordinals, plus the set of hyperreals, with the surreal number (1,2,3,...|) being explicitly identified as 'w'. Surreals and hyperreals are similar enough that it seems logical (to me) to identify the surreal 'w' with the hypernatural (1,2,3...n...), and call it 'w' as well. Further, you could identify the sequence f(n) = (a_1,a_2,a_3,...) as f(w), so that n+1 = (2,3,4,...) = w+1, n^2 = (1,4,9,16,25...) = w^2, n^^n = epsilon_0, and so forth.
So you could do this, but let's take a step back and merely argue that ordinals and hypernaturals look pretty similar in a lot of ways, so that there may be interesting ideas to carry back and forth between them. This is because they aren't exactly the same, and you run into a few rough edges if you try to fit them together.
Recall that arithmetic works differently on hyperreals than it does on ordinals, and then there's a third arithmetic for cardinal numbers. And further, IIRC arithmetic on surreals isn't quite the same as arithmetic on hyperreals, either. One could take the position that these are merely three different views of the same object, expressing various properties that happen to coincide and give the same answers so long as we limit ourselves to finite numbers. Because of this difference, there are several kinds of hyperreal that aren't also ordinals. Obviously infinitesimals are out (no 1/w), as are any non-"integers" (no w+pi). 2^w and w!, in hyperreal terms, both define "integers" that aren't also ordinals, since in ordinal terms both expressions are equal to 'w'. No such thing as a negative ordinal, either. And infinite numbers less than 'w' are right out, like w-1. Meanwhile, the ordinals stretch far, far past w1, the first uncountable ordinal, which appears to be the upper bound on the usual realm of hyperreals, which is why I'm limiting the discussion to countable ordinals.
A correspondence like this does let you ask some (possibly) interesting questions, like what hyperreal sequence, in other words what function from N to N, would correspond to Gamma_0, or various other 'large' ordinals. And going the other way, one of the common objects of study in the area of function hierarchies is the so-called "slow growing hierarchy", where G_0(n) = n+1, G_m+1(n) = G_m(n)+1. Clearly, if you can increment by less than 1, you can get a hierarchy that increases much more slowly, even infinitesimally if you like, say G_0(n) = n + 1/n, G_m+1(n) = G_m(n)+ 1/G_m(n), so that I suppose you'd eventually get w+1/w, w^w+(1/w^w), Gamma_0+(1/Gamma_0), etc., unless perhaps that hierarchy converges to a limit somewhere. Either way, I don't know how useful it would really be.
Also, it's possible everything I just said is complete nonsense.
- On a different note, I've finally managed to piece together part of the puzzle about "supernatural numbers", for which I'd come across several apparently incompatible definitions. The PlanetMath definition just referenced doesn't mention this, but the same product-of-primes thing is used for Godel numbering. So it becomes clear that these are the same supernatural numbers that Hofstadter talks about, but doesn't properly explain or give references for, in Godel, Escher, Bach. GEB goes on to mention infinitely large supernatural numbers as an example of nonstandard arithmetic or number theory. Again, the book doesn't explain what's meant by "nonstandard", but thanks to the magic of the Internet it's possible to find out. The axioms of Peano arithmetic were intended to give a succinct, complete, and unique definition of the natural numbers, but Lowenheim-Skolem theorem demonstrates that the axioms do not, and cannot, uniquely define the natural numbers, and it's possible in principle to create sets of objects, of any cardinality you like, that fulfill precisely the same axioms. And you can't get to a unique definition by adding more axioms, or using a different set of axioms. It's just an unavoidable fact of life. Instead of freaking out or getting depressed by this result, the math world simply decided to call the desired model "standard" and all the others "nonstandard", and study all of them. The supernaturals are just one nonstandard model, one which includes the naturals as a subset. The word "nonstandard" as it appeared later in connection with hyperreals is an analogy: Nonstandard analysis is to regular analysis as nonstandard number theory is to regular number theory. Both add additional "useful" numbers to the usual set, supernaturals being "useful" because, as infinite products of primes, by definition they fall under the fundamental theorem of arithmetic, so you can do all the usual number-theoretical stuff with them, I guess. Maybe some of them are even prime themselves. That's a weird idea.
If we're going to assume the supernaturals fit into the hyperreals (which may or may not be justifiable, see the previous discussion), I think they'd all fit within the range starting at 2^w and less than w^w, which would mean there'd be no overlap between them and the ordinals. Although again, this is just a guess.
Monday, February 20, 2006
Some followup notes about my recent math-heavy Hercules vs. Hydra post. If you didn't find that one very interesting, this one will definitely bore you to tears.