« Longhorn piracy 'coup'? | Main | The economics of usability »

December 05, 2003

When infinities attack

Mark Pilgrim writes up Hilbert's hotel, a classic metaphor for the weird stuff that happens when you start dealing with mathematical infinities.

Infinities are my mathematical first love. I read Ian Stewart's "Concepts of Modern Mathematics" at an impressionable age, and the strange antics of the alephs, the sheer elegance of cardinality proofs and the enigmas of the continuum hypothesis and the large cardinals pretty much settled the core of my mathematical interests for the rest of my life.

What I didn't learn about until much later was the equal strangeness of ordinal infinities. Cardinals deal with "how many." If you can map two sets onto each other, by no matter how distorting a mapping, they have the same cardinality. So, as illustrated by the Hilbert hotel, all countable sets get flattened to the same cardinality, aleph-null.

Ordinals, however, are concerned with the order in which you count. So you can have different countable ordinals, and the rules are quite different from cardinals.

In the cardinal world, for example, aleph-null + 1 = aleph-null (moving one guest into Hilbert's hotel). In the ordinal world, 1 + omega = omega, but omega + 1 does not equal omega.

Why is this? Well, look at the three sets and, more importantly, their orders:

omega = { item1, item2, item3... }

1 + omega = { newitem, item1, item2... }

omega + 1 = { item1, item2... newitem }

We can map between 1 + omega and omega in a way that preserves the order structure. We can't do that with omega + 1, because in omega + 1 newitem is after every other item. omega and 1 + omega have no member with that property.

So the omega (ordinal) family offers a much richer view of countable infinities than the cardinal view, where's it's all just aleph-null. You have omega + n, omega + omega, omega * 2 (but not 2 * omega -- that's { a1, b1, a2, b2, ... } which is just the same as omega (I hope I've got that the right way round)), omega * omega, omega ^ omega, omega ^ omega ^ omega ^ ...

... and it's all still countable. In fact if you go far enough you eventually find ordinals not expressible in terms of omega, and they're still countable. The first such ordinal is known as epsilon-0. I guess there is an epsilon-1 and various epsilon-ns and presumably epsilon-omega and eventually an epsilon-epsilon-0. But, like Mark, I find myself tapped out just thinking about it. Perhaps someone more knowledgeable can educate me further.

December 5, 2003 in Science | Permalink


TrackBack URL for this entry:

Listed below are links to weblogs that reference When infinities attack:

» Hilbert's Hotel: Infinity != Infinity from Jason E. Shao
Mark Pilgrim wrote up Hilbert's Hotel an example of using a diagonal argument that uses the metaphor of an infinite hotel to discuss the difference between countable and uncountable infinite quantities (e.g. the fact that the Real numbers is a... [Read More]

Tracked on Dec 21, 2003 5:07:33 AM


Here is an ordinal spiel:

You know that between any two infinite cardinals there are many ordinals. That is, the first infinite cardinal (aleph_0) is the first infinite ordinal (omega), but the second infinite cardinal (the smallest uncountable cardinal aleph_1) is not the second infinite ordinal (this is omega+1, where as aleph_1 corresponds to epsilon_0). Thus each succesor cardinal is a huge leap in terms of ordinals.

Then it is should be surprising that there are ordinals k, such that k is simultaneously the k^th infinite ordinal and the k^th uncountable cardinal
Intuitively, I can't explain (understand) this at all, but in fact the proof is not difficult.

Intriguingly, the smallest ordinal with shocking property above is the "giant"


where it is just omegas all the way down, omega times.

Of course the ordinals we can discuss are very small. In fact, transitions occur which fundamentally change things as much as the transition from finite ordinals to omega. When this happens, we say that such ordinals are inaccessible. This means they cannot be constructed from within ZF, just as omega cannot be constructed in ZF without the axiom of infinity.

Posted by: Crosson at Dec 6, 2006 8:06:20 PM