In the last post, Iv’e talked about **order-isomorphism** and presented a nice criteria for the set of rationals . I want to start talking about **well-order** today, and then make progress toward the definition of a **-transitive sets** which both are going to play a big role in the future. Let’s start:

Suppose that is poset. We say that is **well-ordered** (and the order is called **well-order**) if for every non-empty subset , there exists a **first element** (If you recall, this is the ‘smallest’ one).

Some examples for well-ordered sets are:

- – every subset has a minimum, which is the first element
- with the ‘natural’ order
- Every finite linearly ordered set.

Some counter examples:

- – for example, the set has no last element – it’s infimum is zero, which is not in the set.
- – from similar argument, we can think of the set as one without first element.

Notice that every well-ordered set is also linearly ordered, why? Suppose is well ordered, and pick two arbitrary elements . such that Now, consider the subset , it has a first element since is well-ordered, thus, or .

One more thing I want to you to notice is that every subset of a well-ordered set, is also a well-ordered set: Indeed, Suppose that is well ordered, and . Now Let be a subset of , in fact, is also a subset of , thus it has a first element, and that implies that is well-ordered.

## How ‘strong’ is well-order?

As you can see, a well-order is quite a strong condition, having a first element in every subset is not trivial at all! I want to show now some more facts that will demonstrate how strong a well-order is:

Suppose that is an order-preserving map and is well ordered, then for every . This statement shows that you can’t really be wild when trying to map a well-ordered set to itself, you must make the elements ‘bigger’.

Let’s prove it, aiming for contradiction, suppose that there is such that . Therefore, the set:

B=\{a\in A:f(a)< a\}\sub A

is non-empty. Since is well ordered, it has a **first element**, let’s call it . Thus, and it is the smallest element with this property in . I’ll try to find some such that and that will be a contradiction for being the first element of .

How can we find such an element, well, let’s try to work with what we have: We know that and that is order preserving, so we can apply the function on the inequality to get: . I am going to define now , since we have . On the other hand, we saw that , thus: . This implies that , and we have found such an element as we wanted which gives us a contradiction.

Let’s raise it up a little bit. Suppose now that is an **order-isomorphism**. Then by the previous statement, we know that . However, since – is an order-isomorphism, we also know that is order-preserving, thus for every , we have . Subsitute to get: . In conclusion, we know that and on the other hand, , thus, , and since it’s true for any , we got that is the **identity**.

This one allows us to prove a really strong statement:

Suppose that are well-ordered, and order-isomorphic. then the order-isomorphism between them is **unique**. This is a really strong statement, it demonstrates how you can’t ‘go wild’ when dealing with isomorphic well-ordered sets. The proof is not that comlicated:

Suppose that are both order-isomorphism. in fact, is also an order-isomorphism. Since the composotion of two order-isomophism is an order-isomophism as well, then is an order-isomophism as well. We just proved that an isomorphism from a well ordered set to itself must be the identity, thus therefore, , which completes the proof.

## -transitive sets

I am now making progress towards the definition of an ordinal, however, we must be familiar with -transitive sets first. Heads up first – this definition is **really, really confusing** so I’ll try to make it as simple as I can.

First, we start with some set . However, is a **set of sets**. i.e. it’s elements are also sets. For example:

A=\{\{1,2\},\{3,4\},\{1\}\}

Here, the set has 3 elements, which are the sets and .

Ok so we which is a set of sets, and I want to define some order on it. Since the elements are sets, I can ask if some element is in the other element. In the example above, we have: , So this is how i am going to define the order:

x< y \iff x\in y

In simpler words: (which is a set) is ‘smaller’ than (which is also a set) if is an element of .

For example, consider the set:

A=\{\{1,2\},\{1,2,3\},\{\{1,2\},3\}\}

We have 3 elements in the set, can we compare them? Let’s try one pair at a time:

- and : no one is an
**element**of the other then we**can’t**compare them, even though . - and here is
**indeed an element**of , thus . - and – can’t be compared (convince yourself)

We are now equipped with this order and I hope it gave us some intuitio for the next defintion:

We say that is -transtive if:

x\in y,y\in A\Rightarrow x\in A

Let’s try to understand it better: as we said, is a set of sets, we can compare between sets using the relation ‘‘. What this definition says, is exactly the familiar transtive property, if we replace ‘‘ with ‘‘ the definition looks like that:

x< y, y< A\Rightarrow x< A

It is basically saying:

“if is an element of , and is an element of , then is also an element of “.

Let’s give an example for a transitive set:

: has two elements: (which doesn’t have elements in it) and , which is a set that contains the empty set.

In order to prove that is -transitive we need to prove that all the element of and are also in .

- For the , there is nothing to check, since it has not elements.
- For the set we only need to check that , and we know it’s true.

Thus, is indeed a -transtive set.

I want to give now a more concrete and intuitive example: Our set is going to be the **united states**, it’s elements are going to be the **states**, and all of the US residents. Each resident lives in some state of the united states, thus, he belongs to the state. This set is indeed a -transitive set, since each element of the state (which is some resident) is also in the set, and we can assume that each resident is an empty set (imagine that you can tell the difference between them, even though they are all empty sets – this is just for the sake of the example).

Make sure you understand this definition, and that you feel comfortable with it, since it is super important for the future.

Let’s play with this definition a bit. Suppose that is a transitive set, and consider the set . I state that this is a transitive set as well:

Suppose that . There are two options now:

- – Since is -transitive, then
- – thus , therfore .

Both cases shows that , thus which proves that is -transitive.

I want to prove two more statements: Suppose that is a set of transitive sets then:

- is a transtive set.
- is a transtive set.

The proofs are pretty straightforward once you understand the definition:

For the first statement:

x\in y\in \bigcap \mathcal{F}\Rightarrow y\in A_i \text{ for every }i\in I\Rightarrow x\in A_i \text{ for every }i\in I\Rightarrow x\in\bigcap\mathcal{F}

And for the second:

x\in y\in \bigcup \mathcal{F}\Rightarrow y\in A_i \text{ for some }i\in I\Rightarrow x\in A_i \text{ for some }i\in I\Rightarrow x\in\bigcup\mathcal{F}

## Summary

Wev’e met the term of a well order, and saw how ‘strong’ it is, then I presented the term of a transitive set, which is kind of hard to process, but on the other hand, very intuitive (there is a nice example in the wikipidea for a sequence of transitive sets, check it out!). processing and understanding the definition of a transitive set is super impotant since we are now ready to define the term of an **ordinal** – which is a special case of a transitive set, and one of the most important things in this series of posts on set theory.