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 -transitive set which is well ordered with respect to the relation .

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 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 is an order-isomorphism and , then .

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

Meet the order type

Here is a great theorem:

Supposet that is well ordered set. Them there exists some ordinal 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 from the theorem is unique. There is only one ordinal a well-ordered set is isomorphic to. Why?

Suppose that is well-ordered and it is isomorphic to both . 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, .

The ordinal that is isomorphic to 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 order, and it has to be -transitive. When looking on other well-ordered set, that may not be the case at all!

For example, Let be the set:

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

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

On the other hand, it’s not hard to see (and prove) that , 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 be a well ordered set. We are going to deal pairs of the form:

(x,\alpha)

where and is an ordinal such that:

x_\downarrow\cong\alpha

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

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

Thus .

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

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

is ‘functional’

That is, if then .

Thats easy, since by the assumption:

x_{\downarrow}\cong \alpha,x_{\downarrow}\cong \beta\Rightarrow \alpha\cong\beta\Rightarrow \alpha=\beta

is ‘one-to-one’

That is, if then .

By the assumption:

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

Both are well-ordered. Aiming for contradiction, suppose that . Then, WLOG (since is in particular linearly ordered) So:

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

So is a proper lower set of . 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, as we wanted.

is a lower set of

Suppose that and . We want to show that as well.

Since we know that for some ordinal .

Let be the order-isomorphism:

f:x_{\downarrow}\to\alpha

thus, . Using the fact that I mentioned in the beginning we know that:

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

However, 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)

is ‘order preserving‘

We need to show that if 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 and ).

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 then there exists some such that:

(x,\alpha)\in F

That is: . Let be the isomorphism:

f:x_{\downarrow}\to\alpha

Since and is onto, there is some 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 .

is an ordinal

A trasitive set of ordinals is an ordinal as well.

We’ll denote it by .

That is, every element of has some ordinal such that .

Suppose that it is not true. Recall that we have proved that 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 is a function from to . 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 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 can’t be an element of the lower set genarated by it (a\notin a_{\downarrow}).

Completing the proof

Since is an isomorphism from to 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’ , which ‘genarates’ ordinals:

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

In fact, an ordinal that we can express as:

s(\beta)=\alpha

for some ordinal is called a successor ordinal.

For example, the natural number are all successors.

On the other hand, 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 – which are not succesors, are called limit ordinals.

(Note that 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…