In the last post, I’ve introduced the term of an **ordinal** recall that an ordianl is a well ordered (By the order ‘‘) and -trasnsitive set . We’ve also seen some interesting results on ordinals, such as :

- If is an ordinal, then so as .
- is an ordinal and is transitive is an ordinal.
- An
**element**of an ordinal is an ordinal as well. - is a set of ordinal is an ordinal and (i.e it is a first element).

All of these facts allowed us to conclude one major result: If are two ordinals, then there are **only three options**:

A\in B,A=B,B\in A

This means we can **compare** two ordinals, **any** two ordinals! Those facts leads us to new a comfortable symbols (From now on, I am going to denote ordinals with greek letters such as . Those are the common symbols for ordinals, so I want to line up with them):

- We will refer to as .
- If , then we will write (since is an ordinal, then as a subset of one, it must be the whole set, or an element of the ordinal).
- If then we will write .

Those symbols makes perfect sense and they reflect the nice properties of ordinals.

## The “set” of ordinals

First things first, I want to start by proving a little lemma:

Suppose that is a -transitive set of ordinals. Then is an ordinal as well.

The proof is pretty straightforward, we will just prove that is an ordinal by definition:

Since is -transtive set, we only need to show that the relation -transtive is an order realtion, but that’s not all, we need to prove that it is a well order.

Since for two differenet ordinals or , we can define such on order on the set.

Moreover, the order is transitive as well: Suppose that are three ordinals in , since is an ordinal – it is a transitive set, thus, .

It’s not hard to show that the order is also anti-reflexive, since we’ve seen that an ordinal can’t be an element of itself ().

The last thing remaining is to prove that is well ordered. Notice that a subset of is just a set of ordinals, and we have proved that a set of ordinals has a first element – it’s intersection .

#### Weird result

So after we have proved this lemma, we are now ready for another interesting result. I am going to denote the collection of all the ordinal as . I state that **can’t** be a **set**! What? if it is not a set then what it is? how can it not be a set? Well, let’s see:

Suppose that is indeed a set. By the lemma we’ve just proved, we conclude that is an ordinal. However, is the collection of **all the ordinals**, therefore, . But that’s a contradiction, since an ordinal can’t be an element of itself!

Umm… If it is not a set, then what is it? How can we deal with such a thing? I’ll talk about in the future, since we can’t really give an answer for that right now. We haven’t even defined what a **set** is! But we are going to though, so don’t worry, we are going to find a reasonable explanation for this fact.

## Lower set

Suppose that is a poset. A **Lower set** of is a subset such that:

\forall b\in B,\forall a< b \Rightarrow a\in B

In other words: If an element is smaller than some element , then must be an element of as well. If , we say that is a **proper** Lower set.

I like to think of as a **barrier**, it won’t let ‘small’ elements get out of it.

We can define for every the **Lower set generated by ** as:

a_\downarrow=\{b\in A|b< a\}

It is indeed a Lower set: If , then and by transitivity, we get that , thus: .

#### Quick lemma

Notice that if is a **well-ordered** set, then every proper Lower set is also generated by some element. Why? Suppose that is a Lower set, since it is a proper Lower set we can conclude that . Since is well ordered, then has a first element, which we refer to as . Now I state that , I’ll show it by two sided inclusion:

- Suppose that and , then and – That’s a contradiction to being first element. Thus , and
- On the other hand, suppose that . Since is well ordered, it is in particular linearly ordered, so there are 3 cases:
- , then since is a Lower set, we get that which is a contradiction to .
- , then , and again we have a contradiction to .
- The only case left is , whcih implies that as we wanted. Thus .

#### Connection with ordinals

This definition of a lower set didn’t come out nowhere, it is connected to ordinals in a way. To see this, first notice that in a poset with the order ‘‘, if is a poset and , then:

- The order is ‘‘, thus .
- is a lower set, thus, by definition, .

We got that if then . Therefore, when the relation on is ‘‘, then:

B\subseteq A\text{ is a lower set}\iff B\text{ is }\in\text{-transitive}

Recall that a -transitive set of an ordinal is also an ordinal and it is the whole set, or an element of it. We can now rephrase this stamement using Lower sets:

A Lower setof an ordinal is an ordinal, and if it is a **proper** lower set, then it is an **element **of the ordinal.

Notice that if are both ordinals then is a proper lower set of . This one follows from the fact that an element of ordinal is also a subset of it (since an ordinal is -transitive, we have implies . Thus ).

#### Another strong property

Now I want to prove a theorem about lower sets that will allow us to conclude another **super** strong property of ordinals:

Suppose that is well-ordered and is a proper lower set of . Then is **not** order-isomorphic to .

This theorem shows that proper subsets of a well ordered set is actually **different** from the original set, it is not isomorphic to it and it’s structure is not the same as the structure of the original set. Can you guess now where I am heading with this therorem? Hint: an ordinal is well-ordered.

Ok, let’s prove it and then I’ll present the result:

First, since is well-ordered, we’ve just proved that every lower set of it is generated by some element, thus, , for some .

Aiming for contradiction, suppose that there is an order-isomorphism:

f:A\to B

Notice that in particular, . We shall now composite it with the inclusion map from to :

i:B\to A,i(\hat{b})=\hat{b}

Obviously, is order preserving, and since a composition of order preserving maps is also order preserving, we get that:

i\circ f:A\to A

is also order preserving.

Recall that an order-preserving map from a well-ordered set to itself must satisfy:

g(a)\geq a

(You can find the proof for it here) therefore, .

On the other hand, since , then by definition . Thus, which is a contradicition to the above.

Great, so after we have proved this theorem, we can conclude the desired result:

for any two ordinals we know that they are the same, or one in an element of the other. If WLOG, we saw that it implies that is a proper lower set of . We can now use the theorem to conclude that and can’t be order isomorphic!

What is the conclusion then? If then ! This property is **really** strong – this means that ordinals are so unique and special that they can’t even be isomorphic to each other – each ordinal is different and has a different structure!

**One last statement on lower setsfor now**

I want to prove in this post just one more theorem about lower sets and stop. However, the proof for this theorem is going to be kind of long, so prepare yourself:

Suppose that are well-ordered. Then they are order-isomorphic or one of them is order-isomorphic to a **lower set** of the other.

This theorem shows us a special connection between two well-ordered set and shows how, in a way, they are actually more connected then we may think.

### The proof

I am going to prove this theorem step-by-step in order to make it easier to understand, since in long proofs you are usually more likely to get lost.

#### Constructing pairs

Consider all the pairs of the form where and , and denote the collection of all those pairs as .

Notice that , since we can pick the pair where are first elements of the sets respectively.

I shall prove now a sequence of properties of those pairs:

#### It is functional

I’ll show that if then .

By the construction of the pairs we know that:

{b_1}_\downarrow\cong a_\downarrow\cong {b_2}_\downarrow\Rightarrow{b_1}_\downarrow\cong {b_2}_\downarrow

If, WLOG, then is a proper lower set of . But that’s impossible, since we have seen that a proper lower set of a well-ordered set can’t be isomorphic to the set. Thus, as desired.

#### It is one-to-one

I want to show that if then , but the proof for that is almost identical to what we’ve just done (So, indeed, )!

#### It is order preserving

Suppose that and , then I want to prove that .

To do so, I want to prove a sub-statement:

**Sub-statement**

Suppose that is an order-isomorphism and . Then .

Consider . It is one-to-one since is one-to-one. It is also order-preserving since is order-preserving.

Now, if , then , so , therefore, . Thus, .

On the other hand, since is an order-isomorphism, then so as . Now, If , then , so ,therefore . This one proves the other direction, thus:

f(a_\downarrow)= f(a)_\downarrow

and we know that .

**Back to the proof**

By our assumption then . By the construction, so there is an order-isomorphism :

\varphi:{a_2}_\downarrow\to{b_2}_\downarrow

However, , then by the lemma:

{a_1}_\downarrow\cong{\varphi(a_1)}_\downarrow

Therefore . From functionality we conclude that since , as we wanted!

#### The inverse relation is order preserving

I want to prove that if and then . However, the proof is very similar to the one in the above!

#### is a lower set of

I want to show that if and there exist such that then there is some such that .

Well, and . Consider now the isomorphism . By the lemma, since : . Thus, as we wanted.

#### is a lower set of

Similar to the proof in the above…

#### can’t be both proper lower sets

Aiming for contradiction, suppose that both of them are proper lower sets. Since are well-ordered, they are both generated by some element:

\text{Dom}(D)=a_\downarrow,\text{Range}(D)=b_{\downarrow}

In fact, all the previous steps proved that is an order-isomorphism form to , thus, . Therefore, by definition, . This implies that: , but that’s impossible.

#### Last effort!

As I said in the above, all the previous steps proved that . There are 3 cases now:

- : Then .
- and is a proper lower set: Then is isomorphic to a proper subset of .
- and is a proper lower set, then is isomorphic to a proper subset of .

And that’s it!

## Summary

In this post we’ve met the term of a **lower set**, which helped us learn more about ordinals and the connection between well-ordered set. In the next post I am going to do something great, I am going to **define the natural number** using ordinals!