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 be two posets, and a map between them. we say that is **order-preserving** if for every such that ,

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 is linearly ordered, the map has to be **one-to-one!** Let’s see why is that: if , since is linearly ordered, we can assume WLOG that . Now, recall that is order-preserving, thus , and because an order-relation in anti-reflexive, we get which complets the proof.

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

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

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

- so which is a contradiction.
- so which is a contradiction.

The only case left is , or as desired.

But there is one more question that teases me, if is not linearlly ordered, is it still true? Well, turns out that it isn’t true, I can find an order-preserving map which is one-to-one and onto, however, it’s inverse is **not order-preserving.** Consider the set with the empty realtion (it’s elemetns are not comparable). On the other hand take with the ‘regular’ order – . the map will be defined as . It is order-preserving since there is no order to preserve, however is **not **order preserving since .

## 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 , be some arbitraty posets and a map between them. We say that is **Order Isomorphism** if it is:

- Order preserving
- One-to-one
- onto
- The inverse is also order preserving

As always, if such a map exits, we say that is order isomorphic to 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 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 is dense if for every two elements there exits some such that .

This property exactly the property that 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 . This theorem shows how unique 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 or not!

In order to prove it, we will need a small lemma first: Let be a poset and cofinal subsets of . Then there is a linearlly ordered subset such that for every .

The proof is done by induction, first notice that if has a last element he must be in every cofinal set, thus we can pick .

If that is not the case, we will just start by picking .as our first element. At the step, after we chose such that , we use the fact that is cofinal thus there is some such that . Using this method creates the desired set .

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 and a poset with the properties in the above. Recall that since 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 which is the set of all the **order isomorphisms** between **finite** subsets of to **finite** subsets of .

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 since we can choose and and is an order isomorphism.

I am going to define an order on , 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 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 is in their **domain**. Since is countable, there are **countably many** sets like the above.

In order to use the lemma, I’ll show that each is cofinal in . Pick a function . if , then . If not, we have 3 cases:

- is
**smaller**than all the element of . now, since is finite by definition and linearly ordered as a subset of one, it has a first element . However, this elements is**not**a first element of , SInce there isn’t one. That means we can pick such that . and define a function: with a domain which is an order preserving extenstion of , and . - is
**bigger**than all the element of . The process is similar to the previous case. - There are elemets in the domain that are
**smaller**than , and some are**bigger**than . 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 . From similar argument, the set of all the bigger elements has a**minimun**, which we will denote by . We now have . since is an order isomorphism, . Recall that is**dense**, so there is such that . we shall now expand to with similar domain as before, where .

In all those cases we have found which is bigger or equals an arbitray function . We can conclude that is cofinal as desired.

Now I want to match a set to each element of , 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 is in their image. With similiar arguments as before, we can show that each 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 **and **the sets of the form . The lemma gives us a linearlly ordered set such that .

Now it is finally time to define an order isomorphism:

f:\mathbb{Q}\to A

such that if there is some function such that .

I like to think of as a function that gets a rational , then it looks for a function such that . After that, it checks what is and returns the output.

This function seems a little bit problematic, what if there are two or more functions such as ? 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 such that then since is linearly ordered, then one is an extention of the other, WLOG then and .

We just showed here that it doesn’t matter which function from we pick to figure out what 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 be some rational. from the definition of , , thus, there is such that . Thus, .

Ok, we now only need to show that is onto and order presevering, since is linearly ordered we **do not need** to show that is one-to-one and it’s inverse is order-preserving.

**Onto**: pick , we know by the lemma that , thus, there is a function such that . In other words, there is some such that .**Order preserving**: Let be two rationals, suppose that: for some specific . since is linearlly ordered, we can compare and .- then since , it is an order isomorphism, and which completes this case
- WLOG , then thus and we are done here.

That’s it! We have proved that 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!