Ordinals

In the last post we prepared the ground by defining Well-ordered sets, $\in$ –transitive sets, and talked about the order $\in$ .

What is it?

It is now finally time to define what ordinals are: A set $A$ is called an ordinal if it is:

$\in$ -transitive
well ordered by the order ‘ $\in$ ‘ ( $x< y \iff x\in y$ )

Ok, in first sight, this definition doesn’t look that interesting or intuitive. The best way to feel what ordinals are is by examples:

Who are the ordinals?

The most basic ordinal I can think of is the $\emptyset$ , which is a trivial example, What about the set $\{\emptyset\}$ ? It is transitive since there are no elements in the only element of the set (which is the empty set), and it is well order since the only susbet of $A$ is $A$ itself (excluding the empty set) which is well ordered, thus, it is an ordinal.

Let’s proceed, what about the set: $A=\{\emptyset,\{\emptyset\}\}$ . This set is indeed transitive ( $\emptyset\in\{\emptyset\}$ and $\emptyset\in A$ ) and well ordered, thus, it is an ordinal.

Well, I think I got it, from the same logic I think that the set $O=\{\emptyset, \{\emptyset\}, \{\{\emptyset\}\}\}$ should also be an ordinal, let’s check: in this set we have:

\emptyset\in \{\emptyset\}\in\{\{\emptyset\}\}

Hold up for a moment, $\{\{\emptyset\}\}$ , then $\emptyset\notin \{\{\emptyset\}\}$ . Thus, ‘ $\in$ ‘ is not even transitive, therefore, this is not even a valid order! and certainly not an ordinal! As it turns out, my intuition betrayed me! However, Now I know that I need to be carefull, and create a set where $\in$ is indeed an order, Let’s try this one:

O=\{\emptyset, \{\emptyset\}\ ,\{\emptyset, \{\emptyset\}\}\}

That one is going to work, trust me, I checked! This leads me to the next logic, We start with some ordinal $A$ , and create another ordinal by taking $A$ and add itself to it. i.e. $A\cup\{A\}$

\begin{array}{c} \emptyset\\ \{\emptyset\}\\ \{\emptyset,\{\emptyset\}\}\\ \{\emptyset,\{\emptyset\},\{\emptyset,\{\emptyset\}\}\}\\ \{\emptyset,\{\emptyset\},\{\emptyset,\{\emptyset\}\},\{\emptyset,\{\emptyset\},\{\emptyset,\{\emptyset\}\}\}\}\\ \{\emptyset,\{\emptyset\},\{\emptyset,\{\emptyset\}\},\{\emptyset,\{\emptyset\},\{\emptyset,\{\emptyset\}\}\},\{\emptyset,\{\emptyset\},\{\emptyset,\{\emptyset\}\},\{\emptyset,\{\emptyset\},\{\emptyset,\{\emptyset\}\}\}\}\} \end{array}

Those are the first 6 ordinals according to this logic. However, I still need to justify this logic formally.

Before I’ll prove it I want you to notice that: If $A$ is an ordinal, then $A\notin A$ , why?

Suppose that $A\in A$ , since the order on $A$ is $\in$ we have $A<A$ which is a contradiction to the order’s first axiom : anti-reflexive.

The ordinals genarator

so let’s prove my ‘conjecture’: If $A$ is an ordinal, then $A\cup\{A\}$ is also an ordinal. In order to prove that we need to show few things:

$A$ is $\in$ -transitive : I proved in the last post that if $A$ is transitive, then $A\cup\{A\}$ is transitive as well.

$\in$ is a valid well-order:

Anti-reflexive

Suppose that $B\in A\cup\{A\}$ . Then we have two options:

$B\in A$ : Then since $A$ is ordered with respect to $\in$ , we get that $B\notin B$ .

$B\in \{A\}$ :Then $B=A$ and I just proved that since $A$ is an ordinal, then $A\notin A$ .

Transitive

Suppose that $x,y,z\in A\cup\{A\}$ such that $x\in y\in z$ . Again, we have two options:

If $z\notin \{A\}$ : thus $z\in A$ .:

Since $A$ is transitive and $y\in z$ we get that $y\in A$ . We know now that $x\in y\in A$ , thus $x\in A$ .

Therefore $x,y,z\in A$ . Recall that $A$ is an ordinal, then, from the transitivity of ‘ $\in$ ‘ we get that $x\in z$ .

On the other hand, if $z\in \{A\}$ : Then $z=A$ . Since $A$ is transitive we know that $x\in y\in A \Rightarrow x\in A$ , therefore $x\in z$ .

Well ordered

Let’s pick an arbitrary subset $B\subseteq A\cup\{A\}$ . And once again, we are facing two options:

If $B=\{A\}$ : Then $A$ is the first element in $B$ .

Else, $B\neq\{A\}$ . Since $B\cap A \subseteq A$ and $A$ is well ordered, then $B\cap A$ has a first element $b$ .

In fact, $b\in A$ , then even if $A\in B$ , $b$ is ‘still’ the first element of $B$ .

Proof review

And that’s it, we’ve proved that $A\cup\{A\}$ is indeed an ordinal. I think this proof forced me to ‘get my hand dirty’ and play with the definitions carefully. A good practice for you would be to try and prove it again by yourself, it’s a really good test for yourself that checks if you understand the definitions and know how to use them.

This theorem allows me to define a function which is kind of an ‘ordinal generator’. It’s input is some ordinal $A$ and it’s output is $A\cup\{A\}$ , which is also an ordinal.

S(A)=A\cup\{A\}

I’ll come back to this function later.

Comparing ordinals

In this post I have one main goal: I want to prove a super strong property of ordinals: If $A,B$ are two ordinals, then $A\in B$ or $B\in A$ or $B=A$ .

That’s it, those are all the options! this theorem shows that you can ‘compare‘ two ordinals, any two ordinals! This property will be extremely useful for us, and I think you can already imagine why such a property is useful.

However, proving this theorem won’t be a walk in the park, I have to prove some more theorems first in order to prove the desired property.

Some properties of ordinals

Transitive subset

Let’s pick some ordinal $A$ and a transitive subset $B\subseteq A$ . If you recall, I have proved in the last post that a subset of a well-ordered set, is also well-ordered, thus $B$ is well-ordered, then we found that $B$ is also an ordinal.

However, we can take this one step forward: obviously, it is possible that $B$ will be $A$ itself, but what if it doesn’t?

That means the subset $A\setminus B \subseteq A$ is non-empty and since $A$ is well ordered, it has a first element which I’ll denote by $b$ .

Notice that $b\in A$ (since $b\in B\setminus A\subseteq A$ ).

Let’s pick now some element $a\in b$ . Since $a\in b\in A$ we get from transitivity that $a\in A$ , and recall that by definition, $b$ is the ‘smallest’ element which is not in $B$ , thus $a\in B$ , and we just proved that $b\subseteq B$ .

Now, we can pick another $a\in B(\subseteq A)$ , we know that $a\in A$ , and we also know that $b\in A$ . Since $A$ is well-ordered, it is in particular linearly ordered as well. This gives us $3$ options:

$b = a (\in B)$ which is impossible since $b\notin B$ .
$b\in a\in B$ , and from the transitivity of $B$ we get that $b\in B$ which is, again, impossible.

Thus $a\in b$ and we proved that $B\subseteq b$ . Combinig the to results to get that $B=b$ , and $b\in A$ , thus $B\in A$ .

I just proved that a transitive subset of an ordinal is also an ordinal and even more than that: I proved that it has to be the whole set (which is the original ordinal) or an element of the original ordinal – And if that is the case, the element is the smallest one which doesn’t belong to the subset!

To summarize it shortly – we found that a subset $B\subsetneq A$ of an ordinal $A$ , is an ordinal itself, and it is also an element of $A$ .

Element of an ordinal

Let’s try something a little different now, again we are starting with some ordinal $A$ , however, we are picking an element $B\in A$ . Let’s see what we can learn about such an element:

Suppose that $x\in y\in B$ since $B\in A$ , we can conclude (as we did here in the first case of ‘transitive’) that $x,y\in A$ . Since ‘ $\in$ ‘ is an order on $A$ , from transitivity, we get that $x\in B$ , thus, $B$ is a transitive set.

Moreover, since $A$ is transitive and $B\in A$ , we know that if $a\in B$ then $a\in A$ as well, thus, $B\subseteq A$ , and we can now use our latest result to get that $B$ is an ordinal as well.

This allows us to conclude something even stronger: If $A$ is an ordinal, then proper subsets (not the whole set) of $A$ and elements of $A$ are the same thing!

Set of ordinals

I need to prove just one more theorem to reach my goal for this post: Suppose that $\mathcal{F}$ is a set of ordinals, then $\bigcap \mathcal{F}$ is an ordinal

In addition, it is the first element in $\mathcal{F}$ with respect to the order $\in$ .

moreover, it is an element of all the elements of $\mathcal{F}$ ( $\bigcap \mathcal{F} \in A$ for every $A\in\mathcal{F}$ ).

I’ll prove it in three steps:

Step 1: $\bigcap \mathcal{F}$ is an ordinal

Iv’e proved that intersection of transitive sets is also transitive in the last post. Thus $\bigcap \mathcal{F}$ is transitive.

Now pick some $A\in \mathcal{F}$ . We know that $\bigcap \mathcal{F} \subseteq A$

Moreover, we’ve proved that $\bigcap \mathcal{F}$ must also be an ordinal as a transitive subset of one, while also being an element of $A$ or $A$ itself!

Step 2: $\bigcap \mathcal{F}\in \mathcal{F}$

As I just said, we know that for every $A\in \mathcal{F}$ , we have two options:

$\bigcap \mathcal{F} \in A$
$\bigcap \mathcal{F}=A$ .

Suppose that $\bigcap \mathcal{F} \in A$ for every $A\in \mathcal{F}$ .

Then it is also an element of their intersection, thus $\bigcap\mathcal{F} \in \bigcap \mathcal{F}$ . However, since $\bigcap \mathcal{F}$ is an ordinal, we already know that such a thing is impossible.

Thus, $\bigcap \mathcal{F}= A$ for some $A\in \mathcal{F}$ , which proves that $\bigcap \mathcal{F}\in \mathcal{F}$ .

Step 3: $\bigcap \mathcal{F}$ is the first element of the set

Since for any $A\in \mathcal{F}$ (such that $A\neq \bigcap \mathcal{F}$ ), we’ve seen that $\bigcap\mathcal{F}\in A$ .

Thus, it is indeed the first element of $\mathcal{F}$ , as desired.

Finally reached my goal!

That’s it, we are now ready to prove that if $A,B$ are ordinals then $A\in B$ or $A=B$ or $B\in A$ :

Consider the set $\{A,B\}$ and the intersection $A\cap B$ . using the last theorem, we know that $A\cap B$ is an ordinal and it is the first element of the set $\{A,B\}$ . Thus, we have two options:

$A\cap B = A$ , then $A$ is the first element and we get that $A \in B$ or $A=B$ .
$A\cap B = B$ , then $B$ is the first element and we get that $B \in A$ or $B=A$ .

Therefore, the only three options are $A\in B$ or $B\in A$ or $A=B$ , and that’s what we wanted to prove!

Summary

We’ve reached and proved the main goal in this post, and I think we’ve got some more sense about ordinals.

For me, they give me a sense of, well…. order, and order is everything I’ve been talking so far. In fact, I also feel like they behave really well, like they are super well defined or something like that… And if you know how to work with them properly and obey their strict rules, they won’t let you down.

In the next post, we will start reaping the benefits of ordinals and we will get to know the strength ordinals have even more.

What is it?

Who are the ordinals?

The ordinals genarator

Anti-reflexive

Transitive

Well ordered

Proof review

Comparing ordinals

Some properties of ordinals

Transitive subset

Element of an ordinal

Set of ordinals

Step 1: $\bigcap \mathcal{F}$ is an ordinal

Step 2: $\bigcap \mathcal{F}\in \mathcal{F}$

Step 3: $\bigcap \mathcal{F}$ is the first element of the set

Finally reached my goal!

Summary

Like this:

Leave a Reply Cancel reply

What is it?

Who are the ordinals?

The ordinals genarator

Anti-reflexive

Transitive

Well ordered

Proof review

Comparing ordinals

Some properties of ordinals

Transitive subset

Element of an ordinal

Set of ordinals

Step 1: <img data-lazy-fallback="1" src="https://s0.wp.com/latex.php?latex=%5Cbigcap+%5Cmathcal%7BF%7D&#038;bg=ffffff&#038;fg=394d55&#038;s=0&#038;c=20201002" alt="&#92;bigcap &#92;mathcal{F}" class="latex" /> is an ordinal

Step 2: <img data-lazy-fallback="1" src="https://s0.wp.com/latex.php?latex=%5Cbigcap+%5Cmathcal%7BF%7D%5Cin+%5Cmathcal%7BF%7D&#038;bg=ffffff&#038;fg=394d55&#038;s=0&#038;c=20201002" alt="&#92;bigcap &#92;mathcal{F}&#92;in &#92;mathcal{F}" class="latex" />

Step 3: <img data-lazy-fallback="1" src="https://s0.wp.com/latex.php?latex=%5Cbigcap+%5Cmathcal%7BF%7D&#038;bg=ffffff&#038;fg=394d55&#038;s=0&#038;c=20201002" alt="&#92;bigcap &#92;mathcal{F}" class="latex" /> is the first element of the set

Finally reached my goal!

Summary

Share

Like this:

Leave a Reply Cancel reply

Step 1: $\bigcap \mathcal{F}$ is an ordinal

Step 2: $\bigcap \mathcal{F}\in \mathcal{F}$

Step 3: $\bigcap \mathcal{F}$ is the first element of the set