8
$\begingroup$

Recently I have watched the following Numberphile video featuring Asaf Karagila. To give a bit of background; the title of the video is "Ordinal numbers", and as one might expect it mainly presents the concept of ordinal numbers. In the video (@ 0:38) Asaf describes a very simple thought experiment; which is simply a bunch of people (only finitely many at the stage) queueing. He says

"With finite length we get something interesting, if I ask you "how many people are in the queue?" the answer is $n$. If I ask you "how long is the queue?" you would have said $5$ (assuming here that $n=5$). In that sense, cardinals How many people, and ordinals How long is the queue, are the same." - @ 1:09.

Up to this point everything is clear to me. The video proceeds considering the same thought experiment, only this time assuming the queue contains infinity many people (by infinity he means $\infty$ - in the broad sense) queueing. Assuming $\square$ is the thing they are queueing for, one can imagine the queue looking like this:

$$\square \,\,\,\, \overset{0}{!} \,\, \overset{1}{!} \,\, \overset{2}{!} \,\, \overset{3}{!} \,\, \overset{4}{!} ,\ldots, \overset{n}{!},\ldots \overset{\infty}{)}$$

Then Asaf says

"Imagine if you will, that this poor guy @ $0$ gets a phone call. So he's stepping out of the queue, and everybody moves by $1$." - @2:32.

now the queue looks like this (where the upper number represents the new position in the queue after the person @$0$ stepped out):

$$\square \,\, \color{red}{\overset{0}{!}} \,\, \overset{\overset{0}{1}}{!} \,\, \overset{\overset{1}{2}}{!} \,\, \overset{\overset{2}{3}}{!} \,\, \overset{\overset{3}{4}}{!} ,\ldots, \overset{\overset{n-1}{n}}{!},\ldots \overset{\infty}{)}$$

My point of confusion is what follows next. Assuming the person @$0$ returns to the back of the queue, i.e considering the following queue:

$$\square \,\, \overset{\overset{0}{1}}{!} \,\, \overset{\overset{1}{2}}{!} \,\, \overset{\overset{2}{3}}{!} \,\, \overset{\overset{3}{4}}{!} ,\ldots, \overset{\overset{n-1}{n}}{!},\ldots \overset{\infty}{)} \,\, \color{red}{\overset{0}{!}}$$

Asaf asks Brady (@4:11)

Asaf - "How is the queue now?"
Brady - "Same length as before"

To which Asaf answers by:

"It's not the same length as before, it has the same number of people - the cardinality of the queue is the same, but the ordinal number that this queue represents is now different.

Which I simply don't understand. I took a course is set theory hence, to some extent I am familiar with the concept of ordinals and cardinals. I understand that this queue represents a limit ordinal, and that $\omega < \omega + 1$. However I am still not able to make sense Asaf's words.

Beyond the confusion I raised above, I am truly fascinated by the analogy. So please, do not hesitate to give an "overkill" answer, even if it is a bit off topic. Set theory is not my strongest suit but, definitely one of the more interesting parts of maths in my eyes.

(I don't want this post to be overloaded, but I am really interested in this beautiful analogy between ordinals & cardinals to queues. If you know of a good reference on that, I’d greatly appreciate it.)

Thanks in advance for any thoughtful comments or answers.

$\endgroup$
9
  • 2
    $\begingroup$ I'd say the analogy, though beautiful, is incomplete (as any analogy is, of course). The second queue is different in that it has a guy who must wait for infinitely long, and there was no such guy in the first queue. To call that length is somewhat of a stretch. $\endgroup$ Commented yesterday
  • 2
    $\begingroup$ @Ivan: It is absolutely not a stretch. We use ordinals to describe lengths of processes all the time in set theory. $\endgroup$ Commented yesterday
  • 2
    $\begingroup$ And it's not just in set theory :) The ordinal length of a game in game theory, the ordinal length of a hypercomputation in computability theory, etc. $\endgroup$ Commented yesterday
  • $\begingroup$ Briefly said, ordinals correspond to positions (with respect to a given order), while cardinals measure volumes. $\endgroup$ Commented yesterday
  • 3
    $\begingroup$ I understand that this queue represents an inaccessible ordinal -- I think you're using the word "inaccessible" in a natural language sense, but unfortunately it has a very well known technical meaning in set theory, and for this meaning what you said is nowhere near correct (but for what it's worth, it's not what I'd call "not even wrong"). $\endgroup$ Commented yesterday

4 Answers 4

Reset to default
8
$\begingroup$

The analogy to queues was something that I developed when I was teaching as a Ph.D. student, and it was further reinforced when I worked with Azriel Levy who introduced an ad-hoc mathematical definition of a "queue":

We say that $(A,<)$ is a queue, if every non-empty end-segment has a minimum.

Of course, this is the same as a well-ordered set, but if you think about a queue at the supermarket, or to the bathroom in a Taylor Swift concert, or to play with the new Star Wars™ Lego™, or whatever, it doesn't matter that there is a minimum in every non-empty set, just in every tail segment.

Now, to your actual question. In mathematics we abstract concepts to produce definitions. If you try to think of a good definition for the concept of "number", you'll find that it is an abstract quantitative concept. That is to say, we measure something. This gets confusing sometimes, since we can use the same numbers to measure a lot of different things, and sometimes there's good overlap between those. The natural numbers are an excellent example: we can measure how many letters are in the word "three" and represent that with $5$, and we can measure the distance between two points on the Euclidean plane which form a right angle with a third point and have distances $3$ and $4$ from that point ($3^2+4^2=5^2$ is what I'm getting at).

While the Euclidean plane is infinitely divisible, and distance is therefore continuous, letters in a word are not infinitely divisible. There are no $\sqrt2$-letters-long words.

Ordinals, in their very name, measure order. Ordinals, abstractly, are the order types of well-ordered sets. And well-ordered sets are just queues, as Azriel would put it with his ad-hoc (introductory) definition.

My goal in that video (and in a few others I've done with Brady) was to bring attention to the fact that "infinity" is not just a singular concept. It's not just "oh, this is infinitely long" or "oh, there's infinitely many of something". It is more refined, it is just like if you asked your bank how much money you have "a positive number" would not be a satisfying answer either (although "infinity" would, technically, be a great answer to hear, even though from a financial point of view it would erode all value to the money and therefore make the money useless, but maybe that's your goal, I don't know, whatever).

In the case of natural numbers, they measure both lengths of a queue and the size of the queue. But infinite sets are different, they are "weird". And they are weird because you can shuffle them in ways that change the order significantly.

All linear orders on a finite set are pairwise isomorphic, whereas on an infinite set this is far from true. And even for a nice class like well-orders, this is still false.

And this means that the measurements of "length" and "size" split up. We can, and should, absolutely think of cardinality as a measurement of size. And we should absolutely think of ordinals as measurements of lengths.

A well-founded set has rank $\alpha$ means that recursion over that set might take $\alpha$ many steps. If I am iterating forcing extensions, I can absolutely talk about something taking $\alpha$ many steps to complete. This is a sound mathematical concept once you allow yourself to think of infinity as a mathematical concept that is granular and not just a "RUN AWAY!!!!" kind of reaction à la Galileo's solution to his "paradox".

$\endgroup$
5
  • 1
    $\begingroup$ It is clear why the queue is different after moving one person from the front to the back. But “length” still doesn’t click with me. Position in a sequence makes more sense to me. $\endgroup$ Commented yesterday
  • $\begingroup$ @DavidK: See my (shorter) answer. =P $\endgroup$ Commented yesterday
  • 1
    $\begingroup$ Same: a little confused here, too. Does this have to do with the different sizes of infinity - eg., natural vs. real numbers? ... since both sets are infinite, one might argue that they all have the "same number of elements", even though there is an infinite number of rational numbers between any two natural numbers, thus the reals "have more elements"? In that case, both sets would have the same ordinal count but the reals would have a larger cardinality? $\endgroup$ Commented yesterday
  • $\begingroup$ Looking at some comments under the question, I see the term ordinal length, which (in contrast to the single word length) makes perfect sense to me. But that’s because “ordinal” already means something to me. It’s perfectly good terminology, it’s just that comfort with the terminology comes after understanding the concept of ordinals, not the other way around. $\endgroup$ Commented 15 hours ago
  • $\begingroup$ @DavidK: I don't really see your point in the second comment. But perhaps the words of someone much smarter than I am can help. "In mathematics you don't understand things, you get used to them". $\endgroup$ Commented 9 hours ago
4
$\begingroup$

Length is just the position where a new item added to the back would be.

Size is just the shortest possible sequence you can squeeze it all into.

Why?

If you say a queue has length $k$, you are saying that if you join the queue you will have to wait for $k$ people to exit the queue before you. That means that your position in the queue would be $k$.

But size is about trying to squeeze everyone into the shortest queue possible so that everyone is as pleased as possible. For example, if you can fit everyone into a queue of length $ω$, why would you want to put them into a queue of length $ω+1$ and make the last person unhappy? Hm? See?

$\endgroup$
3
  • 1
    $\begingroup$ Wait, what is the shortest queue you can put an amorphous set into? :P $\endgroup$ Commented 20 hours ago
  • $\begingroup$ @AsafKaragila: I choose to have my choice cake and eat it too! But is that really the reason for the downvote? $\endgroup$ Commented 19 hours ago
  • 1
    $\begingroup$ Right. The reasoning breaks if one rejects the axiom of choice. Also, user, I edited your LaTeX for a reason. Your refusal to use \omega leads to incredibly ugly output on Safari. $\endgroup$ Commented 4 hours ago
3
$\begingroup$

The two queues clearly aren't the same:

  • In the first queue, every person has a finite number of people ahead of them.
  • In the second queue, there's one unfortunate person at the back who has an infinite number of people ahead of them.

Does that mean that the two queues have a different length? Well, maybe — it depends on how you choose to define length for infinite queues. But at least it means that the two queues could have different lengths, since they're not the same queue.

And indeed it turns out that there is a way to consistently define a "length" for infinite queues that captures the difference between these two queues and the fact that the first queue is in some fundamental sense shorter than the second. (Specifically, that there is a person in the second queue such that the part of the queue in front of them is equal in length to the first queue.)

And the way to do that is to measure the length of the queues using ordinals.

Which might sound a bit circular, since ordinals basically are infinite queues, just defined in more "mathematical" terms, with one queue defined as being shorter than another exactly when it's equal to a proper prefix of the longer queue. But if you want a definition of "length" that best captures the differences between different infinite queues, then well, why not use the queues themselves as yardsticks for measuring and comparing their length?

(And, of course, the whole point of imagining infinite queues in this mental exercise in the first place was to motivate the definition of ordinals. Which I'd say they do quite admirably.)

$\endgroup$
-2
$\begingroup$

At the initial stage of understanding these concepts, one should remember that the concept of cardinal does not require order, in other words sets are identified as representing the same cardinal as long as they are in a bijective correspondence.

On the other hand the notion of ordinal requires order, in fact well ordering. Thus two well ordered sets are considered to be the same ordinal if there is an order preserving bijective correspondence between them. From this, you can see that every cardinal is an ordinal...

Verbal/mental representation of these concepts is individual -- one man's good representation is another man's confusion...

$\endgroup$
2
  • 5
    $\begingroup$ Rado: You wrote "every ordinal is a cardinal". This is completely bogus. $\endgroup$ Commented 19 hours ago
  • 1
    $\begingroup$ @user21820 Where do you see that? ;) $\endgroup$ Commented 4 hours ago

You must log in to answer this question.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.