Well order & transitive sets

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

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

Some examples for well-ordered sets are:

$\mathbb{N}$ – every subset has a minimum, which is the first element
$\{1,2,3,\dots,n\}$ with the ‘natural’ order
Every finite linearly ordered set.

Some counter examples:

$\mathbb{R}$ – for example, the set $(0,1)$ has no last element – it’s infimum is zero, which is not in the set.
$\mathbb{Q}$ – from similar argument, we can think of the set $(0,1)\cap \mathbb{Q}$ as one without first element.

Notice that every well-ordered set is also linearly ordered, why? Suppose $A$ is well ordered, and pick two arbitrary elements $a,b\in A$ . such that $a\neq b$ Now, consider the subset $\{a,b\}$ , it has a first element since $A$ is well-ordered, thus, $a<b$ or $b<a$ .

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 $A$ is well ordered, and $B\subseteq A$ . Now Let $C\subset B$ be a subset of $B$ , in fact, $C$ is also a subset of $A$ , thus it has a first element, and that implies that $B$ 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 $f:A\to A$ is an order-preserving map and $A$ is well ordered, then $a\leq f(a)$ for every $a\in A$ . 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 $a\in A$ such that $f(a)<a$ . Therefore, the set:

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

is non-empty. Since $A$ is well ordered, it has a first element, let’s call it $d$ . Thus, $f(d)<d$ and it is the smallest element with this property in $A$ . I’ll try to find some $c\in B$ such that $c<d$ and that will be a contradiction for $d$ being the first element of $B$ .

How can we find such an element, well, let’s try to work with what we have: We know that $f(d)<d$ and that $f$ is order preserving, so we can apply the function on the inequality to get: $f(f(d))<f(d)$ . I am going to define now $c:=f(d)$ , since $f(d) < d$ we have $c<d$ . On the other hand, we saw that $f(f(d))<f(d)$ , thus: $f(c)<c$ . This implies that $c\in B$ , 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 $f$ is an order-isomorphism. Then by the previous statement, we know that $a\leq f(a)$ . However, since $f$ – is an order-isomorphism, we also know that $f^{-1}$ is order-preserving, thus for every $c\in A$ , we have $c\leq f^{-1}(c)$ . Subsitute $c := f(a)$ to get: $f(a)\leq f^{-1}(f(a))=a$ . In conclusion, we know that $a\leq f(a)$ and on the other hand, $f(a)\leq a$ , thus, $a=f(a)$ , and since it’s true for any $a\in A$ , we got that $f$ is the identity.

This one allows us to prove a really strong statement:

Suppose that $A,B$ 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 $f,g:A\to B$ are both order-isomorphism. in fact, $g^{-1}:B\to A$ is also an order-isomorphism. Since the composotion of two order-isomophism is an order-isomophism as well, then $g^{-1}\circ f: A\to A$ is an order-isomophism as well. We just proved that an isomorphism from a well ordered set to itself must be the identity, thus $g^{-1}\circ f=Id_A$ therefore, $f=g$ , which completes the proof.

$\in$ -transitive sets

I am now making progress towards the definition of an ordinal, however, we must be familiar with $\in$ -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 $A$ . However, $A$ is a set of sets. i.e. it’s elements are also sets. For example:

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

Here, the set $A$ has 3 elements, which are the sets $\{1,2\},\{3,4\}$ and $\{1\}$ .

Ok so we $A$ 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: $1\in\{1,2\}\in A$ , So this is how i am going to define the order:

x< y \iff x\in y

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

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:

$\{1,2\}$ and $\{1,2,3\}$ : no one is an element of the other then we can’t compare them, even though $\{1,2\}\subseteq \{1,2,3\}$ .
$\{1,2\}$ and $\{\{1,2\},3\}$ here $\{1,2\}$ is indeed an element of $\{\{1,2\},3\}$ , thus $\{1,2\} < \{\{1,2\},3\}$ .
$\{1,2,3\}$ and $\{\{1,2\},3\}$ – 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 $A$ is $\in$ -transtive if:

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

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

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

It is basically saying:

“if $y$ is an element of $A$ , and $x$ is an element of $y$ , then $x$ is also an element of $A$ “.

Let’s give an example for a transitive set:

$A=\{\emptyset, \{\emptyset\}\}$ : $A$ has two elements: $\emptyset$ (which doesn’t have elements in it) and $\{\emptyset\}$ , which is a set that contains the empty set.

In order to prove that $A$ is $\in$ -transitive we need to prove that all the element of $\emptyset$ and $\{\emptyset\}$ are also in $A$ .

For the $\emptyset$ , there is nothing to check, since it has not elements.
For the set $\{\emptyset\}$ we only need to check that $\emptyset \in A$ , and we know it’s true.

Thus, $A$ is indeed a $\in$ -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 $\in$ -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 $A$ is a transitive set, and consider the set $A\cup\{A\}$ . I state that this is a transitive set as well:

Suppose that $x\in y\in A\cup\{A\}$ . There are two options now:

$y\in A$ – Since $A$ is $\in$ -transitive, then $x\in A$
$y\in \{A\}$ – thus $y=A$ , therfore $x\in y =A\Rightarrow x\in A$ .

Both cases shows that $x\in A$ , thus $x\in A\cup\{A\}$ which proves that $A\cup\{A\}$ is $\in$ -transitive.

I want to prove two more statements: Suppose that $\mathcal{F}=\{A_i\}$ is a set of transitive sets then:

$\bigcap F=\bigcap_{i\in I}A_i$ is a transtive set.
$\bigcup F=\bigcup_{i\in I}A_i$ 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.

Well order & transitive sets

How ‘strong’ is well-order?

$\in$ -transitive sets

Summary

Like this:

Leave a Reply Cancel reply

How ‘strong’ is well-order?

<img data-lazy-fallback="1" src="https://s0.wp.com/latex.php?latex=%5Cin&#038;bg=ffffff&#038;fg=394d55&#038;s=0&#038;c=20201002" alt="&#92;in" class="latex" />-transitive sets

Summary

Share

Like this:

Leave a Reply Cancel reply

$\in$ -transitive sets