Order type

After we’ve properly defined the natural numbers, it’s time do define arithmetics on ordinals – such as addition, multiplication and exponentiation. However, we need to do a little bit of work first.

However, what I am going to discuss about today is improtant regardless my goal to define arithmetics.

I am going to show a really strong connection between well-ordered sets and ordinals.

Some reminders

So we have the term of an ordinal which is a \in-transitive set which is well ordered with respect to the relation \in.

We have proved many thing about ordinals, and you can always read everything (with proofs) I’ve discussed about them here.

After we’ve defined ordinals, we’ve met the term of a lower set, which you can read about here.

One theorem that we proved and I want you to remember is: If A,B are both well ordered, then they are isomorphic to each other or one of them isomorphic to a proper lower set of the other.

During the proof of that result, we’ve also proved a really important statement:

If f:A\to B is an order-isomorphism and a\in A, then a_{\downarrow}\cong f(a)_{\downarrow}.

Ok, enough with the reminders, let’s begin:

Meet the order type

Here is a great theorem:

Supposet that A is well ordered set. Them there exists some ordinal \alpha such that: [latexm]A\cong \alpha[/latex].

Why is it so great? Since with this theorem we now know, that any well-ordered set is order-isomorphic to some ordinal. This theorem shows how strong and fundamental ordinals are.

Moreover, Assuming that we proved this theorem, we can conclude even a stronger proposition – This \alpha from the theorem is unique. There is only one ordinal a well-ordered set is isomorphic to. Why?

Suppose that A is well-ordered and it is isomorphic to both \alpha,\beta. Thus:

\alpha\cong A\cong  \beta\Rightarrow\alpha\cong\beta

And we’ve proved that if two ordinals are isomorphic to each other, then they are the same – thus, \alpha = \beta.

The ordinal \alpha that is isomorphic to A is called it’s order-type and we denote it by:


That’s a really important term, as we will see in the in the near future.

A small remark

When I first saw this theorem I thought:

“Wait, if any well ordered set is isomorphic to an ordinal – does that mean it is an ordinal itself? I don’t think that makes sense at all, cause I already know well-ordered sets which are not ordinals. Then what is going on here?”

My problem was that I thought that order isomorphism is ‘too strong’. It is indeed preserves the structure of the set, however ordinals are ordered with a specific orde – the \in order, and it has to be \in-transitive. When looking on other well-ordered set, that may not be the case at all!

For example, Let A be the set:


(Those are closed intervals) Where the order is \subsetneq. Of course this set is well ordered, but it is not \in-transitive, and not well-ordered with respect to the order \in.

On the other hand, it’s not hard to see (and prove) that A\cong 3, which is it’s order type:


Cool, now that this point is clear, we are ready for the proof:

The proof

Let A be a well ordered set. We are going to deal pairs of the form:


where x\in A and \alpha is an ordinal such that:


Let’s denote the set of all those pairs as F. Notice that the set is not empty! A is well ordered, thus it has a first element a\in A. Therefore:


Thus (a,0)\in F.

I am going to prove that we can create an order-isomorphism from the set F.

(The proof is going to be really similar to the one where I proved that two well ordered sets are isomorphic to each other or one is a lower set of the other).

Let’s begin with poperties:

F is ‘functional’

That is, if (x,\alpha),(x,\beta)\in F then \alpha = \beta.

Thats easy, since by the assumption:

x_{\downarrow}\cong \alpha,x_{\downarrow}\cong \beta\Rightarrow \alpha\cong\beta\Rightarrow \alpha=\beta
F is ‘one-to-one’

That is, if (x,\alpha),(y,\alpha)\in F then x = y.

By the assumption:

x_{\downarrow}\cong \alpha,y_{\downarrow}\cong \alpha\Rightarrow x_{\downarrow}\cong y_{\downarrow}

Both x_{\downarrow},y_{\downarrow} are well-ordered. Aiming for contradiction, suppose that x\neq y. Then, WLOG x<y (since A is in particular linearly ordered) So:

x_{\downarrow}\subsetneq y_{\downarrow}

So x_{\downarrow} is a proper lower set of y_{\downarrow}. From that we conclude that they are not isomorphic to each other (a well ordered set is not order isomorphic to a proper lower set of it). And that’s a contradiction to our assumption.

Thus, x=y as we wanted.

\text{dom}(F) is a lower set of A

Suppose that x\in \text{dom}(F) and y<x. We want to show that y\in \text{dom}(F) as well.

Since x\in \text{dom}(F) we know that x_{\downarrow}\cong \alpha for some ordinal \alpha.

Let f be the order-isomorphism:


b<a thus, b\in x_{\downarrow}=\text{dom}(f). Using the fact that I mentioned in the beginning we know that:

b_{\downarrow}\cong f(b)_{\downarrow}

However, f(b)\in \alpha is an ordinal as an element of one. Thus, it equals to the lower set it genarates:

f(b)_{\downarrow} = f(b)

Therefore, we now have:

b_{\downarrow}=f(b)\Rightarrow(b,f(b))\in F\Rightarrow b\in\text{dom}(F)
F is ‘order preserving

We need to show that if x,y \in \text{dom}(F) such that:

(x,\alpha),(y,\beta)\in F, x< y


\alpha < \beta

But we’ve already seen that in the latest part (try to prove it yourself in a similar way to the previous part – use the isomorphism between y_{\downarrow} and \beta).

\text{Im}(F) is a transitive set of ordinals

Well, it is already a set of ordinals, we only need to prove that:

\beta\in\alpha\in\text{Im}(F)\Rightarrow\beta\in \text{Im}(F)

Since \alpha \in \text{Im}(F) then there exists some x\in A such that:

(x,\alpha)\in F

That is: x_{\downarrow}\cong \alpha. Let f be the isomorphism:


Since \beta\in \alpha and f is onto, there is some y\in x_{\downarrow} such that:


However, using the fact from the beginning we know that:

y_{\downarrow}\cong f(y)_{\downarrow}=\beta_{\downarrow}\overset{\beta\in\text{ON}}{=}\beta

So (y,\beta)\in F\Rightarrow \beta\in \text{Im}(F).

\text{Im}(F) is an ordinal

A trasitive set of ordinals is an ordinal as well.

We’ll denote it by \alpha.


That is, every element a of A has some ordinal \beta such that (a,\beta)\in F.

Suppose that it is not true. Recall that we have proved that \text{dom}(F) is a lower set. Thus, it must be a proper lower set. We’ve proved that any proper lower set in a well-ordered set is generated by an element. Thus:

\text{dom}(F)=a_{\downarrow}\text{ for some }a\in A

In fact, we have proved that F is a function from \text{dom}(F) to \text{Im}(F). In addition, it is one-to-one and order preserving from a well-ordered set. Thus, it is an order isomorphism. Therefore:


But we’ve also proved that \text{Im(F)} is an ordinal! therefore:

(a,\text{Im}(F))\in F\Rightarrow a\in\text{dom}(F)=a_\downarrow

And that’s obviously a contradiction, since a can’t be an element of the lower set genarated by it (a\notin a_{\downarrow}).

Completing the proof

Since F is an isomorphism from \text{dom}(F)=A to \text{Im}(F)=\alpha which is an ordinal, we found that:

A\cong \alpha

As we wanted!

Successor and limit ordinals

After we’ve proved this marvelous theorem, I want to define two types of ordinals.

Recall that a few posts ago (in this one), I’ve defined the ‘function’ S, which ‘genarates’ ordinals:


In fact, an ordinal \alpha that we can express as:


for some ordinal \beta is called a successor ordinal.

For example, the natural number are all successors.

On the other hand, \omega which is the set of all the naturals is not a successor as we’ve seen in the post on the natural numbers.

Moreover, 0 is not a successor as well, since it is the first ordinal!

Such ordinals like 0 and \omega – which are not succesors, are called limit ordinals.

(Note that \omega + 1 is indeed a successor).

Those terms will play a big role in the future (and in particular, in the next post).


After meeting the term of an order type of a well ordered set, we are now finally ready to start discussing about arithmetics of ordinals. So that’s my plan for now.

In the next post, I am going to discuss about addition – which is not as simple as you may think…

Leave a Reply

%d bloggers like this: