# 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:

\text{otp}(A)=\alpha

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:

A=\{[0,1],[0,2],[0,3]\}

(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:

\text{otp}(A)=3

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:

(x,\alpha)

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

x_\downarrow\cong\alpha

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:

a_\downarrow=\{\emptyset\}=0

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$$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$$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 (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)$$\text{dom}(F)$ is a lower set of $A$$A$

Suppose that $x\in \text{dom}(F)$ and $y. 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:

f:x_{\downarrow}\to\alpha

$b 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$$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

Then:

\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)$$\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:

f:x_{\downarrow}\to\alpha

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

f(y)=\beta

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)$$\text{Im}(F)$ is an ordinal

A trasitive set of ordinals is an ordinal as well.

We’ll denote it by $\alpha$.

##### $\text{dom}(F)=A$$\text{dom}(F)=A$

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:

a_{\downarrow}=\text{dom}(F)\cong\text{Im}(F)

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:

S(\alpha)=\alpha+1=\alpha\cup\{\alpha\}

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

s(\beta)=\alpha

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).

## Summary

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…