Order-preserving maps

In the last post, I have shown what is an order relation, what are posets, while also proving nice results such as relations between a cofinal sets and last elements.

In this post I want to start looking for a connection between two posets, and find a way to map two posets – one into the other, without losing their properties. First, we need to think what is the property we want to preserve when mapping one poset to another. The answer for that is simple, the property is order of course, since that is the only property we have. This leads me to a definition. Let $\langle A, <_A \rangle, \langle B, <_B \rangle$ be two posets, and $f:A\to B$ a map between them. we say that $f$ is order-preserving if for every $a_1,a_2\in A$ such that $a_1 < a_2$ ,

f(a_1)< f(a_2)

That simple definition is exactly what we wanted! It makes a lot of sense too, it says that a map is order presevring if it preserves the order (They couldn’t name it better!).

It turns out that that if $A$ is linearly ordered, the map has to be one-to-one! Let’s see why is that: if $a_1\neq a_2$ , since $A$ is linearly ordered, we can assume WLOG that $a_1 < a_2$ . Now, recall that $f$ is order-preserving, thus $f(a_1) < f(a_2)$ , and because an order-relation in anti-reflexive, we get $f(a_1) \neq f(a_2)$ which complets the proof.

Notice that from the same arguments we can conclude that if we can compare between two elements in $A$ , i.e. $a_1 < a_2$ , then those elements will be sent to different element of $B$ .

Let’s see what happens when we also assume that $f$ is onto (in addition to the fact that $A$ is linearlly ordered): we can pick two arbitrary elements, $b_1,b_2\in B$ and since $f$ is onto, there are $a_1,a_2 \in A$ such that $f(a_1) = b_1, f(a_2) = b_2$ . We also Know that $A$ is linearlly ordered, so WLOG $a_1 < a_2$ , and because $f$ is order preserving, we get that $f(a_1) < f(a_2)$ , and we can write that as: $b_1 < b_2$ .

Notice what just happend, we took 2 arbitrary element of $B$ , and found out that they are comparable! Thus, $B$ is also linearlly ordered. Ok, Let’s take it one step forward, we now know that $f$ is one-to-one and onto, thus there exits an inverse map, $f^{-1}$ . A natural question to ask might be something like: ‘is $f^{-1}$ is order-preserving as well?’ Let’s check by picking two elements $b_1 < b_2$ in $B$ , and see if $f^{-1}(b_1)<f^{-1}(b_2)$ . We know that $f^{-1}(b_1)=a_1, f^{-1}(b_2)=a_2$ . $A$ is linearly ordered, now there are three cases:

$a_1=a_2$ so $b_1 = b_2$ which is a contradiction.
$a_1 > a_2$ so $b_1 > b_2$ which is a contradiction.

The only case left is $a_1 < a_2$ , or $f^{-1}(b_1) < f^{-1}(b_2)$ as desired.

But there is one more question that teases me, if $A$ is not linearlly ordered, is it still true? Well, turns out that it isn’t true, I can find an order-preserving map $f:A\to B$ which is one-to-one and onto, however, it’s inverse is not order-preserving. Consider the set $A=\{a_1, a_2\}$ with the empty realtion (it’s elemetns are not comparable). On the other hand take $B=\{1,2\}$ with the ‘regular’ order – $1 < 2$ . the map will be defined as $f(a_1)=1,f(a_2)=2$ . It is order-preserving since there is no order to preserve, however $f^{-1}$ is not order preserving since $f^{-1}(1) \nless f^{-1}(2)$ .

Order Isomorphism

We have seen that the inverse map doesn’t not need to be order-preserving. However, when it is, we get a complete correspondence between two sets, which leads us to the next definition:

Let $\langle A, <_A\rangle$ , $\langle B, <_B\rangle$ be some arbitraty posets and $f:A\to B$ a map between them. We say that $f$ is Order Isomorphism if it is:

Order preserving
One-to-one
onto
The inverse $f^{-1}$ is also order preserving

As always, if such a map exits, we say that $A$ is order isomorphic to $B$ and write

\langle A, <_A \rangle \cong \langle B, <_B \rangle

Recall that we have seen that proving that the inverse is order-preserving is unnecessary when $A$ is linearly ordered, that is another advantage of linear order.

I want to present now the term of a dense set. We say that a poset $A$ is dense if for every two elements $a,b\in A$ there exits some $c\in A$ such that $a<c<b$ .

This property exactly the property that $\mathbb{Q},\mathbb{R}$ have. we can always pick a number between two arbitrary numbers (by taking their average, for example).

It turns out that if a poset is:

linearlly ordered
countable
dense
without first and last element

Then it has to be order Isomorphic to $\mathbb{Q}$ . This theorem shows how unique $\mathbb{Q}$ is, and gives the set of rational an exact criteria that will help us to determine whether or not the poset we are working with is $\mathbb{Q}$ or not!

In order to prove it, we will need a small lemma first: Let $\langle A, <\rangle$ be a poset and $\{D_n\}_{n\in\mathbb{N}}$ cofinal subsets of $A$ . Then there is a linearlly ordered subset $B$ such that $B\cap D_n \neq \emptyset$ for every $n\in\mathbb{N}$ .

The proof is done by induction, first notice that if $A$ has a last element $a$ he must be in every cofinal set, thus we can pick $B=\{a\}$ .

If that is not the case, we will just start by picking $b_0 \in D_0$ .as our first element. At the $n^{th}$ step, after we chose $b_i\in D_i, 0\leq i < n$ such that $b_1 < b_2 < .... < b_{n-1}$ , we use the fact that $D_n$ is cofinal thus there is some $b_n\in D_n$ such that $b_{n-1} < b_n$ . Using this method creates the desired set $B=\{b_k\}_{k\in\mathbb{N}}$ .

Now I’ll prove the theorem. Of course we will want to use the lemma, the goal here is to find an order isomorphism between $\mathbb{Q}$ and a poset $A$ with the properties in the above. Recall that since $\mathbb{Q}$ is linearlly ordered, we won’t need to check if the inverse is order-preserving.

This proof is going to be pretty long, make sure you understand every step of it you won’t understand the upcoming steps (just like any long proof). I’ll try to write this proof as organized as possible, in order to make it easier to understand.

Kind of a long proof ahead

First I want to define a set $B$ which is the set of all the order isomorphisms between finite subsets of $\mathbb{Q}$ to finite subsets of $A$ .

B=\{g:C\to A^\prime :C\subset\mathbb{Q},|C|<\infty,\ \ A^\prime\sub A, |A^\prime|<\infty\}

Make sure that you understand what this set is! Also notice that $B\neq \emptyset$ since we can choose $\{q\}\sub \mathbb{Q}$ and $\{a\}\sub A$ and $f:\{q\}\to\{a\}$ is an order isomorphism.

I am going to define an order on $B$ , which is going to be the order I have presented on functions in the previous post (…one function is an extenstion of the other…).

Now I am going to assign each rational number $q$ a set

q\leftrightarrow D_q=\{g\in B | q\in\text{dom}(g)\}\subset B

This is the set of all the functions which $q$ is in their domain. Since $\mathbb{Q}$ is countable, there are countably many sets like the above.

In order to use the lemma, I’ll show that each $D_q$ is cofinal in $B$ . Pick a function $g\in B$ . if $q\in\text{dom}(g)$ , then $g\in D_q$ . If not, we have 3 cases:

$q$ is smaller than all the element of $\text{dom}(g)$ . now, since $\text{Im}(g)$ is finite by definition and linearly ordered as a subset of one, it has a first element $a$ . However, this elements is not a first element of $A$ , SInce there isn’t one. That means we can pick $c\in A$ such that $c < a$ . and define a function: $g^\prime$ with a domain $\text{dom}(g)\cup\{q\}$ which is an order preserving extenstion of $g$ , and $g^\prime (q)=c$ .
$q$ is bigger than all the element of $\text{dom}(g)$ . The process is similar to the previous case.
There are elemets in the domain that are smaller than $q$ , and some are bigger than $q$ . Now the set of all the smaller elements is finite while also being a subset of linearly ordered set, thus it has a maxium which we will denote by $x$ . From similar argument, the set of all the bigger elements has a minimun, which we will denote by $y$ . We now have $x<q<y$ . since $g$ is an order isomorphism, $g(x)<g(y) \in A$ . Recall that $A$ is dense, so there is $a\in A$ such that $g(x) < a < g(y)$ . we shall now expand $g$ to $g^\prime$ with similar domain as before, where $g^\prime(q)=a$ .

In all those cases we have found $g^\prime \in D_q$ which is bigger or equals an arbitray function $g\in B$ . We can conclude that $D_q$ is cofinal as desired.

Now I want to match a set to each element of $A$ , the sets will be defined as:

a\leftrightarrow E_a=\{g\in B | a\in\text{Im}(g)\} \sub B

those are all the functions that $a$ is in their image. With similiar arguments as before, we can show that each $E_a$ is cofinal, and there are countably many sets of this form.

We are now finally ready to use the lemma. The collection of cofinal sets is going to be all the sets of the form $D_q$ and the sets of the form $E_a$ . The lemma gives us a linearlly ordered set $Z\sub B$ such that $Z\cap E_a \neq \emptyset , Z\cap D_q \neq \emptyset$ .

Now it is finally time to define an order isomorphism:

f:\mathbb{Q}\to A

such that $f(q) = a$ if there is some function $g\in Z$ such that $g(q)=a$ .

I like to think of $f$ as a function that gets a rational $q$ , then it looks for a function $g\in Z$ such that $q\in \text{dom}(g)$ . After that, it checks what is $g(q)$ and returns the output.

This function seems a little bit problematic, what if there are two or more functions such as $g$ ? We shall prove that their output must be the same. So before even checking if this function is an order isomorphism, we have to validate that this is even a function:

Well defined: if $g_1, g_2 \in Z$ such that $g_1(q)=a_1, g_2(q)=a_2$ then since $Z$ is linearly ordered, then one is an extention of the other, WLOG $g_1<g_2$ then $g_2|_{\text{dom}(g_1)}=g_1$ and $g_1(q)=g_2(q)$ .

We just showed here that it doesn’t matter which function from $Z$ we pick to figure out what $f(q)$ is, we will always get the same output.

Serial: we need to show that every input has an output (which is not trivial at all). Let $q\in\mathbb{Q}$ be some rational. from the definition of $Z$ , $Z\cap D_q \neq \emptyset$ , thus, there is $g\in Z$ such that $q\in\text{dom}(g)$ . Thus, $f(q)=g(q)$ .

Ok, we now only need to show that $f$ is onto and order presevering, since $\mathbb{Q}$ is linearly ordered we do not need to show that $f$ is one-to-one and it’s inverse is order-preserving.

Onto: pick $a\in A$ , we know by the lemma that $Z\cap E_a\neq\emptyset$ , thus, there is a function $g\in Z$ such that $a\in\text{Im}(g)$ . In other words, there is some $q\in\text{dom}(g)$ such that $f(q)=g(q)=a$ .
Order preserving: Let be two rationals, suppose that: for some specific . since is linearlly ordered, we can compare and .
- $g_1 = g_2$ then since $g_1\in B$ , it is an order isomorphism, and $g_1(q_1)<g_1(q_2)$ which completes this case
- WLOG $g_1 < g_2$ , then $\text{dom}(g_1)\sub \text{dom}(g_2)$ thus $f(q_1)=g_1(q_1)=g_2(q_1)<g_2(q_2)=f(q_2)$ and we are done here.

That’s it! We have proved that $f$ is an order isomorphism which means:

\mathbb{Q}\cong A

Sorry for the misleading heading up there, that was a really long proof. Let’s summarize

Wow, that was really long, though I like really like this proof. It is elegant and it deals with only basic concepts to prove a really non-trivial result. I really hope you survived it, If you do, I’ll just let you know that in the next post I am going to present the concept of well ordered set which is even a stronger condition than linearlly ordered set. See you in the next one!

Order Isomorphism

Kind of a long proof ahead

Sorry for the misleading heading up there, that was a really long proof. Let’s summarize

Like this:

Leave a Reply Cancel reply

Order Isomorphism

Kind of a long proof ahead

Sorry for the misleading heading up there, that was a really long proof. Let’s summarize

Share

Like this:

Leave a Reply Cancel reply