# Let $(P,<),(Q,\prec)$ be countable, dense, and linearly ordered sets without endpoints. Then $(P,<),(Q,\prec)$ are order-isomorphic

This theorem is usually proved constructively by Cantor's back-and-forth method.

Is there other proofs for this well-known theorem? Especially, the proofs that don't define an explicit isomorphism between $$(P,<)$$ and $$(Q,\prec)$$. Instead, the proofs just prove the existence of the isomorphism between $$(P,<)$$ and $$(Q,\prec)$$.

Let $$(P,<)$$ and $$(Q,\prec)$$ be countable, dense, and linearly ordered sets without endpoints. Then $$(P,<)$$ and $$(Q,\prec)$$ are order-isomorphic.

Throughout this article, let $$(P,\prec)$$ be any countable, dense, and linearly ordered set without endpoints enumerated by $$(p_n)_{n \ge 0}$$.

Proposition 1: There exist an injective morphism $$f: \mathbb Z \to P$$ with the property that

$$\tag 1 f(0) = p_0 \text{ and for every } p \in P \text{ there exist } b \in \mathbb N \text{ such that } f(-b) \le p \le f(b)$$.
Proof
We will define a sequence of injective morphisms,

$$\tag 2 f_k:[-k,+k] \to P \text{ such that }$$ $$\quad \quad \quad \text{ for every } p_n \text{ with } n \le k,\; p_n \text{ lies between } f_k(-k) \text{ and } f_k(+k)$$

and each $$f_{k+1}$$ is an extension of $$f_{k}$$.

We start with $$f_0(0) = p_0$$. Assume that $$\text{(1)}$$ holds for a fixed $$k$$. If $$f_k(-k) \le p_{k+1} \le f_k(+k)$$, we just choose any extension. If, say, $$p_{k+1} \gt f_k(k)$$, we define $$f_{k+1}(k+1) = p_{k+1}$$ and select an extension defining $$f_{k+1}(-(k+1))$$. A similar argument extends $$f_k$$ to $$f_{k+1}$$ satisfying $$\text{(1)}$$ when $$p_{k+1} \lt f_k(-k)$$.

The union of all the $$f_k$$ is the function $$f$$ we are seeking. $$\quad \blacksquare$$

Let $$U = \{m2^{-n} \; | \; \text{ with } m \in \mathbb Z \text{ and } n \in \mathbb N\}$$. It is easy to see that the set $$U$$ is a countable, dense, and linearly ordered without endpoints under the usual $$\lt$$ relation.

Observe that by setting $$U_k = \{m2^{-k} \; | \; m \in \mathbb Z\}$$ we can assert that $$U_0 = \mathbb Z$$, $$\,U_k \subset U_{k+1}$$ and that

$$\tag 3 U = \bigcup_{k \ge 0} \, U_k$$

Set $$F_0 = f$$, where $$f: U_0 \to P$$ is any injective morphism satisfying $$\text{(1)}$$.

Lemma: If $$F_k : U_k \to P$$ is an injective morphism that extends $$F_0$$ such that the elements $$(p_n)_{0 \le n \le k}$$ are all in the image of $$F_k$$, then we can extend $$F_k$$ to an injective morphsim $$F_{k +1}: U_{k+1} \to P$$ such that $$p_{k+1} \in F_{k+1}(U_{K+1})$$.
Proof
Note first that the set $$U ∖ U_k$$ can be partitioned into 'open intervals', and the same can be said about $$P ∖ F_k(U_k)$$. Also, between any two consecutive points in $$U_k$$ we can find a midpoint of the form

$$\quad \beta_{(m,k+1)} = \frac{m}{2^{k}}+\frac{1}{2^{k+1}}$$

and these are precisely the points in $$U_{k+1}$$ that are not in $$U_{k}$$. For each one of these points, we can choose an element $$q_{(m,k+1)}$$ in $$P$$ between $$F_k(\frac{m}{2^{k}})$$ and $$F_k(\frac{m+1}{2^{k}})$$ and then map $$\beta_{(m,k+1)} \mapsto q_{(m,k+1)}$$.

With this in mind, we see how to extend $$F_k$$ if $$p_{k+1}$$ is already in the range of $$F_k$$. But when $$p_{k+1} \notin F_k(U_k)$$, it is in exactly one 'open interval' of $$P ∖ F_k(U_k)$$ and that interval contains an element $$q_{(m,k+1)}$$. So all we have to do to take care of business by swapping out our selected $$q_{(m,k+1)}$$ and replacing it with $$p_{k+1}$$,

$$\quad \beta_{(m,k+1)} \mapsto p_{k+1}$$

and thereby ensure $$p_k$$ is in the range of $$F_k$$. $$\quad \blacksquare$$

Proposition 2: There exist an isomorphism between $$U$$ and $$P$$.
Proof
Our recursion starts out with $$F_0$$ defined on $$\mathbb Z$$ and satisfying $$\text{(1)}$$ so that $$F_0(0) = p_0$$. The lemma allows us to recursively extend to a function $$F_k$$ that is an injective morphism that contains $$p_j$$ for $$j \le k$$. By applying the lemma and taking the union of all the $$F_k$$ (their graphs), we get an isomorphism $$F$$ between $$U$$ and $$P$$.$$\quad \blacksquare$$

The following is an immediate consequence of proposition 2.

Theorem 3: Let $$P$$ and $$Q$$ be any two countable, dense, and linearly ordered sets without endpoints. Then they must be isomorphic.

Note: We do not have to use the axiom in choice to prove the lemma. To 'crank out' $$q_{(m,k+1)}$$, we can define it to be correspond to $$p_j$$ where $$j$$ is the smallest natural number satisfying $$F_k(\frac{m}{2^{k}}) \lt p_j \lt F_k(\frac{m+1}{2^{k}})$$.

The same goes for proposition 1. When we state 'choose any extension' we can put the enumeration $$p_n$$ to 'double use' and make it concrete.

So we can arrive at Theorem 4 without using the axiom of choice. The back-and-forth algorithm doesn't use it, so this is not surprising; see Back and forth and the axiom of choice.

A good exercise is to carefully prove proposition 1 without using the axiom of choice.

• I'm unable to understand some points in your proof sketch. Please elaborate more! 1. what is injective morphism? 2. It seems that the gist of your approach is to prove Proposition 2: There exist an isomorphism between $U$ and $P$. I'm unable to prove this Proposition. Please give me some hints! Commented Oct 11, 2018 at 13:55
• Getting busy now, so will prove proposition 2 later. A morphism is just an order preserving mapping. Try to work out the details of proposition 1. If you can't, I'll do that first. Commented Oct 11, 2018 at 14:08
• The idea is that we can inject an ''Archimedean grid/chain' into $P$, and then we can use density and countabilty to 'flesh it out'. Commented Oct 11, 2018 at 14:11
• Is that $q_{(m,k+1)}=p_{i_0}$ where $i_0=\min \{n\in\Bbb N\mid F_k(\frac{m}{2^{k}})<p_n<F_k(\frac{m+1}{2^{k}})\}$? Commented Oct 12, 2018 at 5:43
• So yes, your explicit formulation for $q_{(m,k+1)}=p_{i_0}$ is 'right on' and obviates the need of using the axiom of choice. Commented Oct 12, 2018 at 12:15

I once saw a proof that went like this: Consider the partial order $$\mathbb{P}$$ of all finite order-preserving partial functions between $$P$$ and $$Q$$, ordered by reverse inclusion. Now the sets $$D_p = \{ f \in \mathbb{P}: p \in \text{dom}(f) \} (p \in P)$$ and $$E_q = \{ f \in \mathbb{P}: q \in \text{ran}(f) \} (q \in Q)$$ are dense in $$\mathbb{P}$$(why?). Choose a $$\mathbb{P}\text{-generic}$$ filter over these sets like $$G$$. Now $$f = \cup G$$ is the desired function.

• I have not learned about Filter yet. Is there a more elementary proof? Commented Oct 3, 2018 at 15:58
• @Akira, Maybe there are other proofs but i don't know. Commented Oct 3, 2018 at 19:25
• Thank you so much! I will come back to your proof after I grasp Filter and Ultrafilter :) Commented Oct 3, 2018 at 23:51

Let $$(p_n\mid n\in\Bbb N)$$ be a enumeration of $$P$$.

Proposition 1: Let $$(P,<)$$ be countable, dense, and linearly ordered set without endpoints. Then there is a order embedding $$f:\Bbb Z \to P$$ such that $$f[\Bbb Z]$$ is unbounded from above and from below in $$P$$.

Proof:

We define a mapping $$g:\Bbb N \to \Bbb N$$ recursively by $$g(0)=0 \text{ and }g(n+1)=\min \{i\in\Bbb N\mid p_{g(n)}

We define a mapping $$f_1:\Bbb N \to P$$ by $$f_1(n)=p_{g(n)}$$

It follows from the definition of $$f_1$$ that $$\forall n\in\Bbb N:p_{g(n)} and thus $$f_1$$ is injective. Let $$A:=f_1[\Bbb N]$$.

$$p_0=f_1(0) is unbounded above by $$p_0$$. Assume that $$A$$ is unbounded above by $$p_i$$ for all $$i\le n$$. Then $$\exists n_0\in \Bbb N,\forall i\le n:p_i \le f_1(n_0)= p_{g(n_0)}$$.

• If $$p_{n+1}\le p_{g(n_0)}=f_1(n_0)$$: $$A$$ is unbounded above by $$p_{n+1}$$.

• If $$p_{n+1} > p_{g(n_0)}$$: We have $$\forall i\le n:p_i\le p_{g(n_0)}$$ and $$p_{g(n_0)} $$\min \{i\in\Bbb N\mid p_{g(n_0)} $$p_{g(n_0+1)} = p_{n+1} \implies f_1(n_0+1)=p_{n+1}$$. Thus $$A$$ is unbounded above by $$p_{n+1}$$.

Hence $$f_1[\Bbb N]$$ is unbounded from above in $$P$$.

We define a reverse-order $$<^*$$ on $$P$$ by $$\forall x,y\in P:x <^* y \iff y. Then $$(P,<^*)$$ is a countable, dense, and linearly ordered set without endpoints.

In a similar manner, we obtain $$f_2:\Bbb N \to P$$ which is an order embedding from $$\Bbb N$$ to $$P$$ such that $$f_2(0)=p_0$$ and that $$f_2[\Bbb N]$$ is unbounded from above in $$P$$ with respect to $$<^*$$. Thus $$f_2[\Bbb N]$$ is unbounded from below in $$P$$ with respect to $$<$$.

Let $$f=f_1\cup f_2$$. It is easy to verify that $$f:\Bbb Z \to P$$ is order embedding from $$\Bbb Z$$ to $$P$$ such that $$f[\Bbb Z]$$ is unbounded from above and from below in $$P$$.$$\quad \blacksquare$$

Proposition 2: There exists an order isomorphism between $$U = \left\{\dfrac{m}{2^n} \mid m \in \mathbb Z \text{ and } n \in \mathbb N\right\}$$ and $$P$$.

Proof:

Let $$U_k = \left\{\dfrac{m}{2^k} \mid m \in \mathbb Z\right\}$$ for all $$k\in\Bbb N$$. It's clear that $$U_0=\Bbb Z$$, that $$U_k\subsetneq U_{k+1}$$ for all $$k\in\Bbb N$$, and that $$U_k$$ is unbounded from above and from below in $$\Bbb Q$$.

We define recursively a family of mappings $$(F_k\mid k\in\Bbb N)$$ such that $$F_k$$ is an order embedding from $$U_k$$ to $$P$$, and that $$F_k\subsetneq F_{k+1}$$ for all $$k\in\Bbb N$$.

Let $$F_0=f$$.

Assume that we have defined $$F_k$$, we define $$F_{k+1}$$ as follows:

• $$F_{k+1}\restriction U_k:=F_k$$.

• For each $$z\in U_{k+1}\setminus U_k$$, there is a unique $$m\in\Bbb Z$$ such that $$\dfrac{m}{2^k} since $$U_k$$ is unbounded from above and from below in $$\Bbb Q$$. Let $$F_{k+1}(z):=p_{i_0}$$ where $$i_0=\min \{i\in\Bbb N\mid F_k(\frac{m}{2^{k}}). Since $$P$$ is dense, such $$i_0$$ does exists. Thus $$F_{k+1}(z)$$ is well-defined for all $$z\in U_{k+1}\setminus U_k$$.

Let $$F=\bigcup_{k\in\Bbb N}F_k$$. It is easy to verify that $$F$$ is an order embedding from $$\bigcup_{k\in\Bbb N}U_k=U$$ to $$P$$.

Let $$\bigcup_{k\in\Bbb N}F_k[U_k]=P'$$. We next prove that $$\forall n\in\Bbb N:p_n\in P'$$ by strong induction on $$n$$.

It's clear that $$p_0\in f[\Bbb Z]=F_0[U_0]$$. Thus $$p_0\in P'$$. Assume that $$p_i\in P'$$ for all $$i\le n$$. Then there exists $$k\in\Bbb N$$ such that $$p_i\in F_k[U_k]$$ for all $$i\le n$$.

1. $$p_{n+1} \in F_k[U_k]$$

Then $$p_{n+1}\in P'$$.

1. $$p_{n+1} \notin F_k[U_k]$$

Then there is a unique $$m\in\Bbb Z$$ such that $$F_k(\frac{m}{2^k}) where$$\frac{m}{2^k}\in U_k$$ by the fact that $$F_k[U_k]$$ is unbounded from above and from below in $$P$$.

We have $$\forall i\le n:p_i\in F_k[U_k] \implies \forall i\le n:i\notin \{i\in\Bbb N \mid F_k(\frac{m}{2^{k}}) by the fact that $$F_k$$ is an order isomorphism between $$U_k$$ and $$F_k[U_k]$$, and that $$\frac{m}{2^{k}}$$ and $$\frac{m+1}{2^{k}}$$ are two consecutive members of $$U_k$$.

Moreover, $$F_k(\frac{m}{2^k}) $$\implies n+1=\min \{i\in\Bbb N\mid F_k(\frac{m}{2^{k}}) where $$z\in U_{k+1}\setminus U_k$$ such that $$\dfrac{m}{2^k}.

By principle of strong induction, $$P\subseteq P'$$. Furthermore, $$P'\subseteq P$$. Thus $$P=P'$$. Hence $$F$$ is an order isomorphism between $$U$$ and $$P$$.

Finally, $$U$$ and $$P$$ are order-isomorphic, and $$U$$ and $$Q$$ are order-isomorphic. Thus $$P$$ and $$Q$$ are order-isomorphic.$$\quad \blacksquare$$