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:

  1. a_1=a_2 so b_1 = b_2 which is a contradiction.
  2. 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 q_1 < q_2 be two rationals, suppose that: f(q_1)=g_1(q_1),f(q_2)=g_2(q_2) for some specific g_1,g_2\in Z. since Z is linearlly ordered, we can compare g_1 and g_2.
    • 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!

Leave a Reply

%d bloggers like this: