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 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.
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)}<p_i\}$$
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)}<p_{g(n+1)}$ and thus $f_1$ is injective. Let $A:=f_1[\Bbb N]$.
$p_0=f_1(0)<f_1(1) \implies A$ 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)}<p_{n+1} \implies$ $\min \{i\in\Bbb N\mid p_{g(n_0)}<p_i\}=n+1 \implies g(n_0+1)=n+1 \implies$ $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<x$. 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}<z<\dfrac{m+1}{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}})<p_i<F_k(\frac{m+1}{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$.
Then $p_{n+1}\in P'$.
Then there is a unique $m\in\Bbb Z$ such that $F_k(\frac{m}{2^k})<p_{n+1}<F_k(\frac{m+1}{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}})<p_i<F_k(\frac{m+1}{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})<p_{n+1}<F_k(\frac{m+1}{2^{k}}) \implies n+1\in \{i\in\Bbb N\mid F_k(\frac{m}{2^{k}})<p_i<F_k(\frac{m+1}{2^{k}})\}$ $\implies n+1=\min \{i\in\Bbb N\mid F_k(\frac{m}{2^{k}})<p_i<F_k(\frac{m+1}{2^{k}})\} \implies F_{k+1}(z)=p_{n+1}$ where $z\in U_{k+1}\setminus U_k$ such that $\dfrac{m}{2^k}<z<\dfrac{m+1}{2^k} \implies p_{n+1}\in F_{k+1}[U_{k+1}] \implies p_{n+1}\in P'$.
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$
