# Simple (even toy) examples for uses of Ordinals?

I want to describe Ordinals using as much low-level mathematics as possible, but I need examples in order to explain the general idea. I want to show how certain mathematical objects are constructed using transfinite recursion, but can't think of anything simple and yet not artificial looking. The simplest natural example I have are Borel sets, which can be defined via transfinite recursion, but I think it's already too much (another example are Conway's Surreal numbers, but that again may already be too much).

• Would proving Zorn be too much? Or special cases, like a Hamel basis for $\mathbb{R}$ over $\mathbb{Q}$ and additive nonlinear functions? – Chris Eagle May 24 '11 at 7:13
• Have you seen dpmms.cam.ac.uk/~wtg10/ordinals.html ? – Qiaochu Yuan May 24 '11 at 7:47
• It is not a bad idea to go back to the original motivation of Cantor. As usual let $A'$, the derived set of $A$, as the set of limit points of $A$. Then we can define the $n$-th derived set $A^{(n)}$ of $A$, and wish to continue the idea beyond the finite. One can then mention the result about trigonometric series that he obtained. – André Nicolas May 24 '11 at 12:40
• 6312 - Thanks, this was exactly my first example, but I want another, maybe a little more "clean". – Gadi A May 24 '11 at 12:45
• I posted some introductory notes on ordinal numbers at groups.google.com/group/sci.math/msg/24bd786487c5b493 and I intended to follow these up as explained at groups.google.com/group/sci.math/msg/1b9648b625951c95 Perhaps something there can be of use, as many of the arithmetic results I stated can be proved by transfinite induction. I wound up not posting the rest of my handwritten notes because I got busy at work and also I decided that I was wasting way too much time trying to format things like this in ASCII, rather than putting my efforts towards LaTeX'ing my writings. – Dave L. Renfro Nov 8 '11 at 22:04

You might find something useful in this post by Tim Gowers: http://www.dpmms.cam.ac.uk/~wtg10/ordinals.html. Especially his first example, with (countable) ordinals introduced as a convenient notation for indexing an increasing sequence of bounded increasing sequences (and so on in many levels perhaps), was quite illuminating for me.

That is, if $a_n \nearrow a$, and $a < b_n \nearrow b$, and $b < c_n \nearrow c$, etc., we will have the notational problem of running out of letters after a while. But we can instead write $a_{\omega}$ instead of $a$, and $a_{\omega+n}$ instead of $b_n$, and $a_{2\omega}$ instead of $b$, and $a_{2\omega+n}$ instead of $c_n$, etc., and thus index all the numbers using a single symbol $a$ with ordinals attached as subscripts. Even countably many sequences will not be a problem, since then we just denote the limit of the sequence $(a_{n\omega})_{n=1}^{\infty}$ by $a_{\omega^2}$. And so on...

• There really should be a "new comments have been posted" notification... Qiaochu's comment wasn't there when I started writing. Well, I'll leave the answer as it is anyway. – Hans Lundmark May 24 '11 at 8:12
• I like his game-based example most and I think I'll use it. Thanks for the link - it's a very good post. – Gadi A May 25 '11 at 6:58

I have only just found this question, but here is a "practical" application.

Suppose I say something will be ready within 7 days. That is represented by number 7. Each following day I say a number smaller than the day before, and when I say zero, that something is ready. On the second day I may say 6, or 3, or even 0.

How about if I say: "I'll tell you tomorrow how long it will take." or "Within 3 days I'll tell you how long it will take." - can that be represented by a generalized form of a number? Yes, it can: ordinal numbers.
First example: today I say $\omega$. That means tomorrow I will have to give you a finite number (let's call it $n$) because only finite numbers are smaller than $\omega$. Therefore you'll know tomorrow that it will be ready within $n$ days
Second example: today I say $\omega+2$. (No, it's not $\omega+3$.)

We can go further: within 7 days I will tell you when I will know how long it will take ($\omega\cdot2+6$) or even tomorrow I'll know when I'll know when I'll know when I'll know when it's ready ($\omega\cdot4$).
If we call the last one taking 4 stages, then imagine this: tomorrow I'll tell you how many stages it will take. That's $\omega^\omega$.

So ordinal numbers can express information about unknown waiting time that is definitely finite. Can everyone see why it is so? Or why the following is true? Start the sequence with any ordinal number and follow each number by a smaller one; it will eventually come to zero (in finite steps).

• This is really cute; as revivals to 3-year-old posts go, this one is pretty good. – Eric Stucky Jan 8 '15 at 17:29
• This is one of the best popularizations of abstract math I have ever seen! Original to you Heimdall? I like this a lot. – Trevor Richards Jan 8 '15 at 17:34
• @TrevorRichards I don't know how original it is, but I haven't seen it anywhere else yet. I have thought of it myself over the last few months while at work (doing a really boring job) and have finally decided to share it. – Heimdall Jan 8 '15 at 17:43

Some accessible applications transfinite induction could be the following (depending on what the audience already knows):

• Defining the addition, multiplication (or even exponentiation) of ordinal numbers by transfinite recursion and then showing some of their basic properties. (Probably most of the claims for addition and multiplication can be proved easier in a non-inductive way.)

• $a.a=a$ holds for every cardinal $a\ge\aleph_0$. E.g. Cieselski: Set theory for the working mathematician, Theorem 5.2.4, p.69. Using the result that any two cardinals are comparable, this implies $a.b=a+b=\max\{a,b\}$. See e.g. here

• The proof that Axiom of Choice implies Zorn's lemma. (This implication is undestood as a theorem in ZF - in all other bullets we work in ZFC.)

• Proof of Steinitz theorem - every field has an algebraically closed extension. E.g. Antoine Chambert-Loir: A field guide to algebra, Theorem 2.3.3, proof is given on p.39-p.40.

• Some constructions of interesting subsets of plane are given in Cieselski's book, e.g. Theorem 6.1.1 in which a set $A\subseteq\mathbb R\times\mathbb R$ is constructed such that $A_x=\{y\in\mathbb R; (x,y)\in A\}$ is singleton for each $x$ and $A^y=\{x\in\mathbb R; (x,y)\in A\}$ is dense in $\mathbb R$ for every $y$.

• Assume the axiom of countable choice, then $A$ is infinite implies $|A|\ge\aleph_0$. Since your second exercise means that $|A|=|A\times A|$ we can deduce the full axiom of choice. However we already know that this is very far from being true. – Asaf Karagila Nov 8 '11 at 12:40
• @Asaf: I meant to work in ZFC there. Perhaps I should have written something like if you have already shown instead of if we know. – Martin Sleziak Nov 8 '11 at 12:43
• Ah, it seemed as though you derive that from the assumption $|A|\ge\aleph_0\rightarrow |A|=|A\times A|$. :-) – Asaf Karagila Nov 8 '11 at 12:55

There's a classic puzzle in which a professor thinks of two positive integers $x$ and $y$, and tells Alice $x+y$ and Bob $xy$. They cannot tell eachother the information they got, and must work out $x$ and $y$. Alice says "I don't know.", Bob says "I don't know.", Alice again says "I don't know.", and then Bob says "Oh, now I know!". The idea here is that if $x$ and $y$ had been $1$ and $1$, Alice would have had $x+y=2$ and known that the only possibility was $(1, 1)$. So when she says she doesn't know, this rules out $(1, 1)$ as an answer. Thus, when Alice and Bob hear eachother say "I don't know", they gain information.

We can ask the question: could the professor find a pair $(x, y)$ which would produce any number $n$ of iterations before Alice and Bob work it out? If he could, then notice that instead of forcing Alice and Bob to sit there saying "I don't know" for hours, he could just tell them in advance "It will take you exactly $10^7$ iterations to figure this out". This gives them exactly the same information that they would have if they actually heard eachother say "I don't know" $10^7$ times, and so they could deduce $(x, y)$. immediately.

Could the professor come up with a pair $(x, y)$ such that Alice and Bob will never be able to figure it out? Maybe. And if he could... if he were to tell them "There is no number $n$ such that after $n$ iterations, you will be able to deduce $(x, y)$", he's giving them information: he's ruling out certain pairs $(x, y)$ as possibilities. Is it possible that that information would then be enough for them to work out $(x, y)$? If so, you could say that the professor has a pair which keeps Alice and Bob playing for exactly $\omega$ iterations. If he found a pair such that:

1. There is no number $n$ such that after $n$ iterations, you will be able to deduce $(x, y)$.
2. If told (1), Alice and Bob still can't deduce $(x, y)$.
3. However, after saying "I don't know" another $7$ times after being told (1), they can then work it out.

then he could claim that the pair $(x, y)$ keeps them playing for exactly $\omega + 7$ iterations.

Thus we have a natural (ish) situation in which we actually need to use ordinals and not cardinals: we need to distinguish between $\infty$ and $\infty + 1$, because the players have strictly more information after $\infty + 1$ turns than after $\infty$ turns.

You can read a more lively presentation of this topic at the Puzzling.SE question I asked here, along with some interesting answers giving examples of how to actually construct a game in which Alice and Bob can be made to play for large countable ordinal numbers of turns. In the comments on that question, a user also posted this article, which discusses the same topic.