Determine which pairs of linearly ordered sets are order isomorphic

Question

Hi I've got an exam this Saturday and I don't understand this question at all. Could someone please explain it to me please? It would be much appreciated.

Here is the question:

and here is the answer:

Answer 1

We are given the lexicographical ordering $<_{\text{lex}}$, defined on $\mathbb{R}^2$ as

$$(a,b) <_{\text{lex}} \iff a < c \text{ or ($a = c$ and $b < d$)}$$

where $<$ is just the usual ordering of real numbers.

This ordering is called lexicographical because it is a generalisation of the standard alphabetical ordering used in, for example, a dictionary. If we have two words and want to decide which one should come first, we look at the first letter and base our ordering on this. If both letters are the same, then we look at the second letter and use that to determine the ordering, and so on. In this case, we are just comparing two 2-tuples which you can imagine being two-letter words in our dictionary.

Now, we are being asked which pairs of the given linearly ordered sets are order isomorphic.

Order isomorphic means that there exists an order isomorphism between the two sets. An order isomorphism between two partially ordered sets, $(P, <_{P})$ and $(Q, <_{Q})$, is formally defined as a bijective function $f: P \to Q$ such that $\forall x, y \in P, x <_{P} y \iff f(x) <_{Q} f(y)$. Informally, this means that the two sets can be put into correspondence such that any two elements that are in a certain order in $P$ retain this order in $Q$. Of course, the elements in each set may not be the same, but the point is that by simply renaming them we can make the two sets virtually identical.

Let’s consider the first two sets.

$$(\mathbb{N}, <)\text{ and }(\mathbb{N} \times \{0,1\}, <_{\text{lex}})$$

The question is, can we construct a bijection between these sets so that our ordering is preserved?

Define $f: \mathbb{N} \to \mathbb{N} \times \{0,1\}$ such that $ x \mapsto \left\{ \begin{array}{ll} \{\frac{n}{2}, 0\}, & x \text{ even} \\ \{\frac{n-1}{2}, 1\}, & x \text{ odd} \end{array} \right. $

It is relatively easy to verify that this is indeed a bijection.

$$0 \to \{0, 0\}$$ $$1 \to \{0, 1\}$$ $$2 \to \{1, 0\}$$ $$3 \to \{1, 1\}$$ $$4 \to \{2, 0\}$$ $$\vdots$$

and so every pair in $\mathbb{N} \times \{0,1\}$ will be covered exactly once (no need to formally prove it here).

Now we can quickly consider whether our other condition is met. Namely, we require $\forall x,y \in \mathbb{N}, x < y \iff f(x) <_{\text{lex}} f(y)$.

If x and y are both even, we want $x < y \iff \{\frac{x}{2}, 0\} <_{\text{lex}} \{\frac{y}{2}, 0\}$, which is true.

If $x$ and $y$ are both odd, we have a similar situation.

If $x$ is even and $y$ is odd, we want $x < y \iff \{\frac{x}{2}, 0\} < \{\frac{y-1}{2}, 1\}$. In this case, it is clearly true if $x$ and $y$ are far apart. However, consider when $y = x + 1$. Then the first element of these two sets are equal. But, according to our lexicographical ordering, we look at the second element and decide that $f(x) <_{\text{lex}} f(y)$, so the order is preserved.

The case where $x$ is odd and $y$ is even is similar.

Since we have an order isomorphism between the two sets, we say they are order isomorphic.

Now, consider the second pair.

$$(\mathbb{N} \times \{0,1\}, <_{\text{lex}}) \text{ and } (\{0,1\} \times \mathbb{N}, <_{\text{lex}})$$

Can we construct a bijection here? Well, if we map each pair in the first set to its ‘swapped version’ in the second, defining $f: \mathbb{N} \times \{0,1\} \to \{0,1\} \times \mathbb{N}$ such that $\{x,y\} \mapsto \{y,x\}$, then this is a bijection. However, when we check if order is preserved, things break down. For example, it is indeed true that $\{2, 0\} <_{\text{lex}} \{3, 0\}$ and $\{0, 2\} <_{\text{lex}} \{0, 3\}$, but if we consider a slightly different pair we have $\{2,1\} <_{\text{lex}} \{3,0\}$ but $\{1,2\} \not <_{\text{lex}} \{0,3\}$. Maybe we could find another bijection that does meet the extra condition required to be order isomorphism, but it doesn't seem obvious. Indeed, according to the answers, the two sets are not order isomorphic.

Hopefully you should be able to consider the other sets and apply similar logic to reach a conclusion. As the question states, you do not have to justify your answers, so using intuition is especially useful here.