Lower sets

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

If $A$ is an ordinal, then so as $A\cup\{A\}$ .
$A$ is an ordinal and $B\subseteq A$ is transitive $\Rightarrow (B\subseteq A \lor B=A)\land B$ is an ordinal.
An element of an ordinal is an ordinal as well.
$\mathcal{F}$ is a set of ordinal $\Rightarrow$ $\bigcap\mathcal{F}$ is an ordinal and $\bigcap \mathcal{F} = \min F$ (i.e it is a first element).

All of these facts allowed us to conclude one major result: If $A,B$ 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 $\alpha,\beta,\gamma,\delta$ . Those are the common symbols for ordinals, so I want to line up with them):

We will refer to $\alpha\cup\{\alpha\}$ as $\alpha+1$ .
If $\alpha \subseteq \beta$ , then we will write $a\leq \beta$ (since $B$ is an ordinal, then as a subset of one, it must be the whole set, or an element of the ordinal).
If $\alpha \in \beta$ then we will write $\alpha<\beta$ .

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 $A$ is a $\in$ -transitive set of ordinals. Then $A$ is an ordinal as well.

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

Since $A$ is $\in$ -transtive set, we only need to show that the relation $\in$ -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 $\alpha \in \beta$ or $\beta \in \alpha$ , we can define such on order on the set.

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

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 ( $\alpha\notin \alpha$ ).

The last thing remaining is to prove that $A$ is well ordered. Notice that a subset of $A$ is just a set of ordinals, and we have proved that a set of ordinals $\mathcal{F}$ has a first element – it’s intersection $\bigcap{F}$ .

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 $\text{On}$ . I state that $\text{On}$ 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 $\text{On}$ is indeed a set. By the lemma we’ve just proved, we conclude that $\text{On}$ is an ordinal. However, $\text{On}$ is the collection of all the ordinals, therefore, $\text{On}\in \text{On}$ . 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 $A$ is a poset. A Lower set of $A$ is a subset $B\subseteq A$ such that:

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

In other words: If an element $a\in A$ is smaller than some element $b\in B$ , then $a$ must be an element of $B$ as well. If $B\neq A$ , we say that $B$ is a proper Lower set.

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

We can define for every $a\in A$ the Lower set generated by $a$ as:

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

It is indeed a Lower set: If $c< b\in a_\downarrow$ , then $c<b<a$ and by transitivity, we get that $c < a$ , thus: $c\in a_\downarrow$ .

Quick lemma

Notice that if $A$ is a well-ordered set, then every proper Lower set is also generated by some element. Why? Suppose that $B\subset A$ is a Lower set, since it is a proper Lower set we can conclude that $A\setminus B\neq \emptyset$ . Since $A$ is well ordered, then $B\setminus A$ has a first element, which we refer to as $a$ . Now I state that $B=a_\downarrow$ , I’ll show it by two sided inclusion:

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

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 ‘ $\in$ ‘, if $B$ is a poset and $a<b\in B$ , then:

The order is ‘ $\in$ ‘, thus $a\in b\in B$ .
$B$ is a lower set, thus, by definition, $a\in B$ .

We got that if $a\in b\in B$ then $a\in B$ . Therefore, when the relation on $A$ is ‘ $\in$ ‘, then:

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

Recall that a $\in$ -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 $\alpha\in \beta$ are both ordinals then $\alpha$ is a proper lower set of $\beta$ . This one follows from the fact that an element of ordinal is also a subset of it (since an ordinal is $\in$ -transitive, we have $x\in\alpha\in\beta$ implies $x\in\beta$ . Thus $\alpha\sub\beta$ ).

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 $A$ is well-ordered and $B\subseteq A$ is a proper lower set of $A$ . Then $B$ is not order-isomorphic to $A$ .

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 $A$ is well-ordered, we’ve just proved that every lower set of it is generated by some element, thus, $B=b_\downarrow$ , for some $b\in A$ .

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

f:A\to B

Notice that in particular, $f(b)\in B$ . We shall now composite it with the inclusion map from $B$ to $A$ :

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

Obviously, $i$ 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, $i\circ f (b) \geq b$ .

On the other hand, since $f(b)\in B=b_\downarrow$ , then by definition $f(b)< b$ . Thus, $i\circ f(b) < b$ 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 $\alpha,\beta$ we know that they are the same, or one in an element of the other. If WLOG, $\alpha \in \beta$ we saw that it implies that $\alpha$ is a proper lower set of $\beta$ . We can now use the theorem to conclude that $\alpha$ and $\beta$ can’t be order isomorphic!

What is the conclusion then? If $\alpha\cong \beta$ then $\alpha = \beta$ ! 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 $A,B$ 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 $(a,b)$ where $a\in A, b\in B$ and $a_\downarrow \cong b_\downarrow$ , and denote the collection of all those pairs as $D$ .

Notice that $D\neq \emptyset$ , since we can pick the pair $(a,b)$ where $a,b$ are first elements of the sets $A,B$ respectively.

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

It is functional

I’ll show that if $(a,b_1),(a,b_2)\in D$ then $b_1=b_2$ .

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, $b_1 < b_2$ then ${b_1}_\downarrow$ is a proper lower set of ${b_2}_\downarrow$ . 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, $b_1 = b_2$ as desired.

It is one-to-one

I want to show that if $(a_1,b),(a_2,b)\in D$ then $a_1=a_2$ , but the proof for that is almost identical to what we’ve just done (So, indeed, $a_1=_2$ )!

It is order preserving

Suppose that $a_1 < a_2$ and $(a_1,b_1),(a_2,b_2)\in D$ , then I want to prove that $b_1 < b_2$ .

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

Sub-statement

Suppose that $f:A\to B$ is an order-isomorphism and $a\in A$ . Then $a_\downarrow \cong f(a)_\downarrow$ .

Consider $f|_{a_\downarrow}$ . It is one-to-one since $f$ is one-to-one. It is also order-preserving since $f$ is order-preserving.

Now, if $x\in a_\downarrow$ , then $x < a$ , so $f(x)<f(a)$ , therefore, $f(x)\in f(a)_\downarrow$ . Thus, $f(a_\downarrow)\subseteq f(a)_\downarrow$ .

On the other hand, since $f$ is an order-isomorphism, then so as $f^{-1}$ . Now, If $y\in f(a)_{\downarrow}$ , then $y<f(a)$ , so $f^{-1}(y)<f^{-1}(f(a))=a$ ,therefore $f^{-1}(y)\in a_\downarrow$ . This one proves the other direction, thus:

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

and we know that $a_\downarrow \cong f|_{a\downarrow}(a_\downarrow) =f(a_\downarrow)= f(a)_\downarrow$ .

Back to the proof

By our assumption $a_1 < a_2$ then $a_1\in {a_2}_\downarrow$ . By the construction, $a_2\cong b_2$ so there is an order-isomorphism :

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

However, $a_1\in {a_2}_\downarrow$ , then by the lemma:

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

Therefore $({a_1},{\varphi(a_1)})\in D$ . From functionality we conclude that $b_1 = {\varphi(a_1)}$ since $\varphi(a_1)\in b_{\downarrow}$ , $b_1=\varphi(a_1) <b_2$ as we wanted!

The inverse relation is order preserving

I want to prove that if $(a_1,b_1),(a_2,b_2)\in D$ and $b_1 < b_2$ then $a_1 < a_2$ . However, the proof is very similar to the one in the above!

$\text{Dom}(D)$ is a lower set of $A$

I want to show that if $(a_1,b_1)\in D$ and there exist $a_2\in A$ such that $a_2<a_1$ then there is some $b_2\in B$ such that $(a_2,b_2)\in D$ .

Well, $a_1\cong b_1$ and $a_2\in a_1$ . Consider now the isomorphism $\varphi: {a_1}_{\downarrow}\to {b_1}_{\downarrow}$ . By the lemma, since $a_2\in {a_1}_\downarrow$ : ${a_2}_\downarrow \cong {\varphi(a_2)}_\downarrow$ . Thus, $(a_2,\varphi(a_2))\in D$ as we wanted.

$\text{Range}(D)$ is a lower set of $B$

Similar to the proof in the above…

$\text{Dom}(D),\text{Range}(D)$ can’t be both proper lower sets

Aiming for contradiction, suppose that both of them are proper lower sets. Since $A,B$ 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 $D$ is an order-isomorphism form $A$ to $B$ , thus, $a_\downarrow \cong b_\downarrow$ . Therefore, by definition, $(a,b)\in D$ . This implies that: $a\in\text{Dom}(D)=a_\downarrow$ , but that’s impossible.

Last effort!

As I said in the above, all the previous steps proved that $\text{Dom}(D)\cong \text{Range}(D)$ . There are 3 cases now:

$\text{Dom}(D) =A, \text{Range}(D)=B$ : Then $A\cong B$ .
$\text{Dom}(D) =A$ and $\text{Range}(D)$ is a proper lower set: Then $A$ is isomorphic to a proper subset of $B$ .
$\text{Range}(D) = B$ and $\text{Dom}(D) =A$ is a proper lower set, then $B$ is isomorphic to a proper subset of $A$ .

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!

The “set” of ordinals

Weird result

Lower set

Quick lemma

Connection with ordinals

Another strong property

One last statement on lower setsfor now

The proof

Constructing pairs

It is functional

It is one-to-one

It is order preserving

Sub-statement

Back to the proof

The inverse relation is order preserving

$\text{Dom}(D)$ is a lower set of $A$

$\text{Range}(D)$ is a lower set of $B$

$\text{Dom}(D),\text{Range}(D)$ can’t be both proper lower sets

Last effort!

Summary

Like this:

Leave a Reply Cancel reply

The “set” of ordinals

Weird result

Lower set

Quick lemma

Connection with ordinals

Another strong property

One last statement on lower setsfor now

The proof

Constructing pairs

It is functional

It is one-to-one

It is order preserving

Sub-statement

Back to the proof

The inverse relation is order preserving

<img data-lazy-fallback="1" src="https://s0.wp.com/latex.php?latex=%5Ctext%7BDom%7D%28D%29%2C%5Ctext%7BRange%7D%28D%29&#038;bg=ffffff&#038;fg=394d55&#038;s=0&#038;c=20201002" alt="&#92;text{Dom}(D),&#92;text{Range}(D)" class="latex" /> can’t be both proper lower sets

Last effort!

Summary

Share

Like this:

Leave a Reply Cancel reply

$\text{Dom}(D),\text{Range}(D)$ can’t be both proper lower sets