I was visiting my mom, and discovered that I didn’t leave my set theory book on the train; I left it at her house. So I’ve been happily reunited with my old text, and I’m going to get back to a few more posts about the beautiful world of set theory.

When you talk about set theory, you’re talking about an extremely abstract notion, one which is capable of representing all sorts of structures: topological spaces, categories, geometries, graphs, functions, relations, and more. And yet, almost every description of set theory plunges straight into the cardinal and ordinal numbers. Why? That’s a question that mystified me for quite a long time. Why do we take this beautiful structure, which can do so many things, and immediately jump in to these odd things about infinities?

I didn’t find it out until last year, when I wrote my post about zero. That started me doing

some reading about the history of math, and it’s in the historical context that the reason for

this is found. If you’re interested in this sort of thing, I recommend the book Labyrinth of Thought: A History of Set Theory and Its Role in Modern Mathematics, which

is the most complete, detailed history of math in the 19th and 20th centuries that I know about.

During the 19th century, when math really started to take the shape that we’re familiar with, one of

the really big questions was: what *is* math really? There was a lot of debate about it, but the

most common answer was some variation on “the science of measurement”: that is, that math was really about

measuring things, and manipulating those measurements. Things like algebra and calculus were considered

important because of the way that they let you compute measurements.

So when mathematicians were trying to get to the roots of things, they were focused on the

idea of *measurement*. But what is measurement? It comes down to two different kinds of

things: you can measure *how big* something is, or *where* something is. All measurements

of any property can ultimately be reduced to either a measurement of a size, or a measurement of a position, or some combination. For example, to measure the velocity of an object in a plane, you’ve got two things you need to measure. Speed – which is the *size* or magnitude of the velocity; and direction, which is the angle (or position) within a circle in which the object is moving.

So Cantor, in his invention of set theory, quite naturally formulated it as an abstract way of talking about the ideas of sizes and positions – which results in two basic kinds of numbers: numbers which describe the *size* of something, and numbers which describe the *position* of something. Sets provided a totally abstract way of talking about what those two kinds of numbers meant, and why there was a distinction. And so we got the cardinals for size, and the ordinals for position.

The next step is to try to see what the differences between the two kinds of numbers are. Are they really always the same thing? Or is there some essential semantic difference between an ordinal and a cardinal, between a number that measures size, and a number that measures position? When you sit down and

work it out, you *do* get a difference – the difference between ω_{0} and ℵ_{0}, and the fact that cardinals are much larger than the ordinals: the ordinals

are all inevitably countable: position is always a countably infinite value.

Aaron Bergmanthe ordinals are all inevitably countableUmmmm….

http://en.wikipedia.org/wiki/Ordinal_number

Rémi Vanicatthe fact that cardinals are much larger than the ordinalsWell it seem that: “Formally, assuming the axiom of choice, the cardinality of a set X is the least ordinal α such that there is a bijection between X and α.” (from http://en.wikipedia.org/wiki/Cardinal_number#Formal_definition), so this is not the difference (in fact, in some sense there are far more ordinals than cardinal : there are ℵn+1 ordinal that have ℵn element). By the way ω0 and ℵ0 are the same set.

Pantufla MilgrosaSorry if this is somewhat redundant.

No, it is *not* true that ordinals must be countable. There is nothing in the ZF axioms of set theory precluding uncountable ordinals. In fact, if you take also the axiom of choice (as is now “mainstream”), then you can prove that they exist. The axiom of choice is actually equivalent to the statement that every set admits a well-ordering, implying that there is at least one ordinal having any given cardinality.

As to there being more or less ordinals than cardinals—to answer this, we must put both in the same context. The standard way of doing this is to associate a cardinal with the smallest ordinal having the same cardinality as it. This identifies each cardinal with a special kind of ordinal. Under this embedding, there are vastly more ordinals than cardinals.

Rémi Vanicat’s quote from Wikipedia rubs me the wrong way because it appears to be stating a result. The identification of cardinals as being special types of ordinals is a matter of definition, not a theorem.

(With respect to misstating basic set theory facts, you’re in good company. The classic example is “One two three… infinity” by George Gamow, which shrugs away the whole continuum hypothesis problem by stating implicitly that 2^aleph_0 = aleph_1.)

AnonymousBesides the fact that (as everyone else has also pointed out) you got ordinals wrong, you are also misrepresenting history:

Cantor didn’t just start doing set theory as a abstract or philosophical exercise. He was led to it naturally by studying trigonometric series, in particular subtle issues such as convergence. You can easily create examples that show problems (such as divergence) at a single point, or any finite set of points. In fact, you can run into trouble at countable sets of points. Thinking about questions like this led Cantor to wonder whether every set of real numbers was countable. Furthermore, these sorts of constructions can be naturally indexed by countable ordinals, which also led Cantor to start thinking about infinite ordinals. From there, everything developed naturally and Cantor moved off into pure set theory. However, the beginning was firmly rooted in 19th century mathematics.

Nowadays this is often presented ahistorically, since in hindsight it is easier to motivate it by sweeping philosophical questions than by real analysis. This probably is the best way to present it to beginners. However, it’s not what actually happened historically.

Harald Hanche-OlsenPantufla Milgrosa: If the formal definition in the wikipedia article rubs you the wrong way, I suspect you didn’t read the whole paragraph. The first sentence rubs me the wrong way too, but only when read in isolation. I think the context makes it clear that there are other choices.

But by all means, if you think you can improve on it, go edit the wikipedia text yourself.

MattFWhile it’s true that all cardinal numbers are also ordinal numbers (assuming AC), I’d like to know how you can use this fact to do induction on uncountable sets. What’s the successor of 2**(aleph-0)?

AnonymousAs a physical scientist, I think of position as a real number, and so it would be uncountable.

Chad GroftTo #3: Technically, you don’t need AC to show that uncountable ordinals exist. You just need the Hartogg aleph function: if X is a set, then Aleph(X) is the set of all order types of well-orderings of subsets of X; i.e., Aleph(X) is the first ordinal bigger than any ordinal which can be embedded in X as a set. If you start with X = N, you get the first uncountable ordinal, omega_1 (or Aleph_1).

Also, I don’t know about that embedding of the cardinals into the ordinals as “the standard way of [determining whether there are more ordinals or cardinals]”. Certainly the cardinals are sparse in the ordinals, in a certain naïve sense pointed out in comment #2. However, they form a proper class, and it’s pretty easy to define a class bijection between the ordinals and the cardinals. So really there are just as many cardinals as ordinals. In fact, the cardinals are a closed unbounded subclass of the ordinals, so it could be argued that “most” ordinals are cardinals.

#6: I don’t think one would prove some sentence of the form “for all real x…” by induction on x, for example, because the well-ordering on the reals doesn’t have any connection to the algebraic or topological structure on R. (There may be an exception if one also assumes CH, since at any given point only countably many reals have been “handled” so far; that knowledge may often be helpful. I can’t recall any examples offhand.) The well-ordering is mostly useful for constructing weird objects. Having a well-ordering on R is enough to get nonmeasurable sets and the Banach-Tarski paradox, even if you don’t assume full AC.

I don’t understand your second question. If we don’t know which ordinal is 2**(aleph_0), we certainly won’t know its successor. In any case, we generally can do induction over a well-ordering etc., but it may be necessary to collect an infinite number of results and proceed from there, and do so again, and again,

etc.DougMark,

As anonymous pointed out “Cantor didn’t just start doing set theory as a abstract or philosophical exercise. He was led to it naturally by studying trigonometric series, in particular subtle issues such as convergence.” Although, perhaps one might argue that the acceptance of set theory came for the reasons you pointed out.

You also said “position is always a countably infinite value.” As already pointed out one can think of actual position as a real number within a scientific framework. If we want to talk about actual physically measured position, since all physical measurements have finite resolution, then all the possibilities of position comes out as a countably infinite value (since the set of possible positions comes out as the set of rational numbers). Of course though, since there exists a margin of uncertainty on such measurements, one can always claim that there exists non-rational number positions of objects.

Lastly, and maybe I’m wrong on this, you wrote “For example, to measure the velocity of an object in a plane, you’ve got two things you need to measure. Speed – which is the size or magnitude of the velocity; and direction, which is the angle (or position) within a circle in which the object is moving.” Couldn’t we measure the velocity vector just by specifying a co-ordinate system, and a specific location (a, b, c)? Of course one implies the other, but can’t one just use the second method to specify the velocity vector, instead of specifying direction and angle?

Torbjörn Larsson, OMVery close. If you add that we measure against measure references so we approximate the underlying real observable (or real part of a complex observable, if you wish) as you described earlier to the uncertainty you see that we can quantify both by repeating the measurement.

I think Lorentz invariance trivially shoots down any claims on observables being rational.

Doug[If you add that we measure against measure references so we approximate the underlying real observable (or real part of a complex observable, if you wish) as you described earlier to the uncertainty you see that we can quantify both by repeating the measurement.]

Can you elaborate or give an example?

Torbjörn Larsson, OMWe simply model our observations with systematic errors and the precision acquired. The precision will encompass both rounding errors and part of the uncertainty, systematic errors capture remaining uncertainty.

(Maybe you will object that we assume the underlying observable is a real, but I gave one out of several reasons for that.)

Matt HeathI’m a functional analyst so naturally I’m pro-choice wrt set theory, but I’m fairly sure you can show that there are uncountable ordinals even in ZF. You can’t show that R can be put in bijection with any ordinal but the union of all countable ordinals is still an uncountable ordinal (right?)

AnonymousYes, ZF alone suffices to prove the existence of uncountable well-ordered sets. More generally, it’s a theorem of ZF (due to Hartogs) that for every set, there is an ordinal that has no injective map into that set. Intuitively, there are arbitrarily large well-ordered sets, although the idea of “arbitrarily large” gets screwy if you don’t assume choice, since different formulations of this idea may be equivalent under ZFC but not ZF.

Jonathan Vos Post“arbitrarily large” gets screwy…” puts it mildly.

Anyone skeptical of transfinite arithmetic should avoid the oozing, eldritch, weirdness of large cardinals, namely those whose existence cannot be proved in ZFC.

Even Solomon Feferman’s “Small Large Cardinals” are screwy. The name alone invokes (to me) the oxymorons “giant shrimp” and “dwarf mammoth.”

Wikipedia has 42 pages in the category “Large cardinals”.

Large cardinals are “traditionally” understood in the context of the von Neumann universe V, which is built up by transfinitely iterating the powerset operation.

Examples include weakly inaccessible cardinals and inaccessible cardinals. There are many other large cardinals.

Inaccessible Cardinal (Tarski, 1930)

k is inaccessible iff k is uncountable, regular, and a strong limit cardinal.

Every inaccessible cardinal is a weakly inaccessible cardinal and the least inaccessible cardinal is not less than the least weakly inaccessible cardinal. In ZF+GCH every weakly inaccessible cardinal is an inaccessible cardinal, or, to put it another way, the weakly inaccessible cardinals are exactly the inaccessible cardinals.

The “infinite ink” web page, as of 1997, mentioned:

Types of Cardinal Numbers Ordered By Consistency Strength

If cardinal type m is listed above cardinal type n in the list below then:

Con(ZFC+a type m cardinal exists) ==> Con(ZFC+a type n cardinal exists)

* rank-into-rank

* n-huge (n

LucasWhat about the downward Lowenheim-Skolem theorem? I’ve always thought that this implies something interesting about the notion of uncountability. By completeness, if ZFC is consistent, then it has a model, and so by Lowenheim-Skolem must have a countable model M.

Of course, we have that M|=”the reals are uncountable”, but that can be viewed as an illusion we all suffer from. For all we know, our usual intuitive model is in fact countable when viewed from the outside. I even consider this a reasonable assumption given the limited nature of our cognition.

Jonathan Vos Post“… viewed from the outside…”

Outside of what?

No, I’m too sleepy to start on that notion.

Typos signify sleep deprivation. In #15, for instance:

“murky beyong human comprehension?”

==> “murky beyond human comprehension?”

“At least, in discussion with Gregory Chaitin earlier this month in Boston, there was copious beer to kkae it all seem plausible”

==>

“At least, in discussion with Gregory Chaitin earlier this month in Boston, there was copious beer to make it all seem plausible”

Really, got to get some sleep now.

I’m subpoenaed as a victim/eyewitness in a criminal case in Pasadena Superior later today (Wednesday 14 Nov 2007): People v Charles Rodman Martin, where the perp is the City Attorney and City Manager of Temple City, who ran numerous red lights and stop signs, narrowly missed killing several people, smashed some cars, totaled my legally parked car just after I left it, in the middle of the Caltech campus, then fled the scene, was pursued by outraged eyewitnesses, and the cops refused to charge him with any of the witnessed misdemeanors, even when he lied to them.

That was in 23 January 2006, approaching 2 years ago. It took me a year to get him criminally charged, and he outwaited the retiring of the deputy city prosecutor (who promised me there’s be no plea bargain, and said the perp was “very, very drunk”), said deputy determined to sentence the grotesque Charles R. Martin. Who? Google his name and “fax.com”, or that someone with an identical name and location and attorney practice had a Private Eye license revoked for proven fraud, for an inkling.

The former Deputy City Prosecutor of Pasadena, as I was saying, wanted to make sure Charles R. “Charlie” Martin never killed anyone with his car, and to strip him of his law license, but he seems to have bribed his way out of that now. Long story. Multimillion dollar real estate deals in smoke-filled rooms, identity theft, i.e. Califoria politics as usual.

Matt Heath@Mark: Seriously, that last bit of the OP is very, very wrong. Wrong enough that if someone else had written it I would expect you to give it as an example of Bad Math to squash. Leaving it up there hurts your credibility a little

Pantufla MilagrosaHarald Hanche-Olsen: you’re right. What the Wikipedia article is doing is defining the cardinality of a set in terms of an ordinal (the least ordinal having a bijection to the set). Since the notion of cardinality is simpler than that of ordinal number, it seems odd to do that, but I suppose it must be the convention in some quarters.

My personal preference is not to define “cardinality” but rather to define the notion of two sets “having the same cardinality;” in this way you don’t need to worry about the question of what kind of object a cardinality is.

Requiring a cardinality to be an ordinal is artificial, not to mention that you need axioms beyond ZF (say, Choice) for the ordinal in question to even exist. A lot of modern set theory explores alternatives to this axiom.

I’m perfectly content to criticize Wikipedia from the sidelines without feeling the need to go and fix it myself. I prefer to spend my energy in other thankless endeavors.

Chad Groft: thanks for clarifying that full-strength AC is not necessary to prove that uncountable ordinals exist. 🙂

The embedding of ordinals into cardinals I stated is as standard a way of putting both in the same context as it gets. The most useful answer to “are there more of X than Y?” isn’t always one that considers just cardinality. This embedding provides a sensible answer to that vague question. But point taken.

Pantufla MilagrosaCorrection to my own #19, last paragraph: I meant “embedding of cardinals into ordinals,” not the other way around. D’uh.