I recently encountered transfinite induction and ordinal numbers for the first time in a real analysis text (Bruckner, Bruckner, and Thomson) and I am still coming to grips with these tools and their significance. After a bit of digging online, I have some conceptual questions about ordinals, and I hope I can make them sufficiently clear.

First, suppose we have a sequence of (say) real numbers $(x_n)_{n \in \mathbb{N}}$, convergent. Would it be appropriate to write (or at least think of) their limit as $x_\omega$? If my intuition is correct here, $x_{\omega+1}$, $x_{\omega^\omega}$, $x_{\omega_1}$, etc. would be meaningless in this context because our index set is $\mathbb{N}$ which has order type $\omega$. Does it make sense to think of the natural numbers as converging to $\omega$?

Now, suppose we have a function $f: \mathbb{R} \rightarrow \mathbb{R}$ and $\lim_{x\rightarrow\infty}{f(x)} = c$ for some constant $c \in \mathbb{R}$. Would we then describe its limit as $c = f(x_{\omega_1})$? If this is not the right way to think about the limit of a real-valed function on $\mathbb{R}$, is that because the reals are not well-ordered under their usual ordering, or is there some other reason? In general, do ordinal numbers only describe the order type of well-ordered sets? Is there a proper way to use ordinal numbers to describe the limiting behavior of functions that are not sequences and, if so, in what areas of mathematics is it used? If not, is there some related idea I might be getting at here?

Second, I have a question about a specific proof I encountered in the text. The authors use transfinite induction to prove the following lemma:

Lemma 1.17: Let $\mathcal{C}$ be a family of subintervals of $[a,b)$ such that for every $a \le x < b$, there exists $y$ satisfying $x < y < b$ so that $[x,y) \in \mathcal{C}$. Then there is a countable disjoint subfamily $\mathcal{E} \subset \mathcal{C}$ so that $$\bigcup_{[x,y) \in \mathcal{E}} [x,y) = [a,b).$$

Proof. Set $x_0 = a$ and choose $x_1 < b$ so that $[x_0, x_1) \in \mathcal{C}$. Suppose that for each ordinal $\alpha$ we have chosen $x_\beta < b$ in such a way that $[x_\beta,x_{\beta+1}) \in \mathcal{C}$ for every $\beta$ with $\beta + 1 < \alpha$. Then we can choose $x_\alpha$ as follows:

(i) If $\alpha$ is a limit ordinal, take $x_\alpha = \sup_{\beta < \alpha}x_\beta$.

(ii) If $\alpha$ is not a limit ordinal, let $\alpha_0$ be the immediate predecessor of $\alpha$ and suppose that $x_{\alpha_0} < b$. take $x_\alpha < b$ so that $[x_{\alpha_0},x_\alpha) \in \mathcal{C}$. The process stops if $x_{\alpha_0} = b$.

Inside each interval $[x_{\alpha-1},x_\alpha)$ we can choose distinct rationals. Hence this process must stop in a countable number of steps. The family $\mathcal{E} = \{[x_{\alpha-1},x_\alpha)\}$ is a countable disjoint subfamily of $\mathcal{C}$ so that $\bigcup_{[x,y) \in \mathcal{E}} [x,y) = [a,b). \blacksquare$

In this proof, transfinite induction is used to construct the subfamily $\mathcal{E}$. The book gives a wrong example using normal induction:

Set $x_0 = a$ and choose $x_1 < b$ so that $[x_0, x_1) \in \mathcal{C}$ and then an interval $[x_1, x_2) \in \mathcal{C}$, and so on. If $x_n \rightarrow b$ take $\mathcal{E} = \{[x_{i-1},x_i)\}$ and we are done. Otherwise, $x_n \rightarrow c$ for some $c < b$. Then we can carry on with $[c,y_1), [y_1,y_2),$ and so on until we eventually reach $b$.

The authors assert that this method is insufficient, and I will admit that it seems fishy to me, but it is still not clear to me exactly what extra work the transfinite induction is doing. Is the number $c$ to which the $x_n$ converge in fact $x_\lambda$ for some limit ordinal $\lambda$? If that is the case, is the transfinite induction taking care of all such numbers $c$, $d$, $e$, i.e., the "intermediate limits" in the process? I think that once I understand the underlying machinery of this proof, I will better understand when it is appropriate to use transfinite induction.

Much thanks,


2 Answers 2


The natural numbers are order isomorphic to $\omega$, therefore thinking about a sequence in terms of ordinal-indexed sequences is perfectly fine. So thinking about the limit as $x_\omega$ is okay. However as you are saying, we only care about $\Bbb N$ so there is no point in talking about larger ordinals, in which case there is little sense of insisting using $x_\omega$ for the limit rather than $x$ or $x_\infty$ or otherwise.

As for the convergence of $\Bbb N$ to $\omega$, the answer is delicate. It's both yes and no. In the ordinals if $\delta$ is a limit ordinal then the sequence of length $\delta$ whose members are exactly the ordinals below $\delta$ (ordered by the usual order of the ordinals, of course) does in fact converge to $\delta$. This is what it means when we say that $\delta$ is a limit ordinal.

We often think about $\Bbb N$ as a subset of the real numbers, in which talking about convergence to $\omega$ is meaningless because in that context the natural numbers and the real numbers both have the same "endpoint" $\infty$. That infinity is different than the one of the ordinals and the cardinals. It merely represents that we've gone beyond any natural number, or beyond any real number.

Therefore it's a bit misleading and confusing to say that $\Bbb N$ converges to $\omega$, because it's a matter of context.

To the second question about considering limits as $\omega_1$ sequences, this is exactly why I insist that $\Bbb N$ and $\omega$ are distinct concepts. While $\Bbb R$ (and in fact $\Bbb Q$) can embed all the countable ordinals as ordered sets, there is no embedding of $\omega_1$ into $\Bbb R$.

Moreover, if $f\colon\omega_1\to\Bbb R$ is a continuous function (and $\omega_1$, as an ordered set has a topology) then $f$ is eventually constant. This means that $x_{\omega_1}$ is actually $x_\alpha$ for some much smaller $\alpha$.

Recall that $\lim_{x\to\infty} f(x)=y$ if and only if for every unbounded sequence of real numbers, $x_n$, we have $\lim_{n\to\infty}f(x_n)=y$. This means that the convergence is decided by the convergence of all countable subsets.

On the other hands, in $\omega_1$ note that $\lim_{\alpha\to\omega_1}\alpha=\omega_1$ whereas every countable subset of $\omega_1$ is bounded, so its limit is some countable ordinal. The reason for this is that $\omega_1$ and $\Bbb R$ have different cofinalities as ordered sets.

So while thinking about ordinal indexed sequences is a good thing, it is utmost important to remember that $\omega_1$ and $\Bbb R$ are very very different in terms of order, and the topology that order induces.

To the last question, the point is that the given assumptions are quite weak. We would have liked to pick some increasing sequence $x_n$ such that $x_0=a$ and $x_n\to b$, and $[x_n,x_{n+1})\in\cal C$. However we can only assert the existence of some $y$ such that $[x_n,y)\in\cal C$. We have no ability to conclude that this $y$ must be $x_n$ itself.

Consider the case where $a=0,b=1$. Then there is some $y$ such that $[0,y)\in\cal C$. And suppose this $y=\frac13$. Then there is some $y_1$ such that $[y,y_1)\in\cal C$, and $y_1=\frac25$, and so on, the sequence of right endpoints converges to $\frac12$ rather than to $1$. In that case, normal induction on $\Bbb N$ would be insufficient.

However, by using transfinite induction, even if we got stuck at $\frac12$ we can continue by taking the $\omega$-th step to be $\frac12$ and continuing by the given property of $\cal C$. Then we argue that the induction must halt at a countable step, rather than at some uncountable ordinal. Now we can a postriori choose a sequence $x_n$ as we would have liked to, by picking the endpoints of some cofinal subsequence of our defined sequence.

But the point is that the given assumptions are insufficient to directly conclude that there is such sequence of length $\omega$.

  • $\begingroup$ I see. So it is correct to say that that the natural numbers converge to $\omega$ insofar as they are also the finite ordinal numbers? $\endgroup$
    – Omar Agha
    Jul 21, 2013 at 7:53
  • $\begingroup$ @Omar: Yes, it is. $\endgroup$ Jul 21, 2013 at 12:05
  • $\begingroup$ @Omar: It's not wrong, but as I point out -- it's not very correct either. The reason is that without setting the correct context (i.e. treating $\Bbb N$ as a set of ordinals, rather than a set of real numbers), it is very easy to infer from that that $\infty$ from calculus is $\omega$. That would be incorrect. $\endgroup$
    – Asaf Karagila
    Jul 21, 2013 at 12:07
  • $\begingroup$ Alright, I understand. Thanks! $\endgroup$
    – Omar Agha
    Jul 21, 2013 at 21:38
  • $\begingroup$ Do you have any insights about the second part of my question? $\endgroup$
    – Omar Agha
    Jul 21, 2013 at 21:39

I will give some thoughts on your first few questions (I don't see exactly why the author is using transfinite induction in that proof either, so maybe someone else can answer that).

For a sequence $(x_n)_{n \in \mathbb{N}}$ I think for intuition, it is better think of the limit as $x_\infty$ instead of $x_\omega$, but as Asaf says below it is not uncommon to think of it as $x_\omega$ . And yes as you point out, it does not make sense to talk about $x_{\omega+1}$ or $x_{\omega^\omega}$.

When you say the natural numbers are converging to $\omega$ I think you are a little confused of what an ordinal is. (Actually, in set theory $\mathbb{N} = \omega$). Ordinals are sets with a (specific) well-order on them, so actually we should use $(\alpha, <)$ when we mean the ordinal $\alpha$. The $<$ on ordinals carries the same nice properties of the $<$ on $\mathbb{N}$ (it is linear and well-founded) and so in a way you can think of ordinals as simply extending $\mathbb{N}$. (Which is another reason we say $\omega = \mathbb{N}$).

Each well-order $(A, R)$ is isomorphic to a unique ordinal $\alpha$ and so ordinals are the "canonical" characterization of well-orders. By definition, ordinals are well-orders so yes it only makes sense to talk about the order-type of a well-order.

It seems like when you right $c = f(\omega_1)$ you are thinking that $|\mathbb{R}| = \omega_1$ which is not true (this is the Continuum Hypothesis), but moreover you are confusing cardinals and ordinals. Cardinals measure the "size" of sets whereas, ordinals measure the "length" of certain sets, namely well-orders. They are two different notions and should not be confused. For example, $\omega \neq \omega +1 \neq \omega + \omega$ however, $|\omega| = |\omega+1| = |\omega+ \omega|$.

Ordinals are used all the time in set theory and other areas of logic. In a way, they are the basic building blocks of the set theoretical universe. In number theory, induction is an invaluable tool for proving things; similarly, in set theory ordinal induction is used all the time.

One more thing: induction can be done on set with any relation given that it is well-founded.

  • $\begingroup$ Actually in the sense of sequences $\omega$ is a better fit than $\infty$, although the latter would be more acceptable as most people are less comfortable with ordinals. $\endgroup$
    – Asaf Karagila
    Jul 21, 2013 at 7:24
  • $\begingroup$ Ok, yes while I was writing that I started to think about that more and thought that might be the case. I will edit my answer to reflect that. Thanks! $\endgroup$ Jul 21, 2013 at 7:27
  • $\begingroup$ Thank you for the clarification! I think I was confused by the notation the authors were using, and I got the wrong idea about the relationship between limit ordinals and limits in analysis. $\endgroup$
    – Omar Agha
    Jul 21, 2013 at 7:33
  • $\begingroup$ Sure, no problem, glad I could help a little. Ordinals are tricky at first, this may help : members.shaw.ca/quadibloc/math/inf01.htm. One way to think about ordinals is a drawing like this: any $n \in \mathbb{N}$ is going to be $n$ dots. $\omega$ is a line-segment. Then $\omega+1$ is a line segment and a dot, $\omega+2$ is a line segment and two dots (and so on). Then $\omega + \omega$ is two line segments, $\omega + \omega + 2$ is two line segments and then two dots . . . $\endgroup$ Jul 21, 2013 at 7:42

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .