How do you prove that all countable, densely ordered sets without endpoints are isomorphic to the rationals?

Question

I've looked online for a proof of this and have found several references to Canter's isomorphism theorem and the "back-and-forth method." However, I haven't been able to find any explicit proofs anywhere. I've only found outlines of how such proofs might work, such as this one. Unless I'm misunderstanding something, proofs like the one linked above indicate how to construct an order-preserving bijection but don't actually prove that it is one. Does anyone know of a proof that involves explicitly proving the property of isomorphism?

Answer 1

So we have two countable linear orders $A$, $B$. Both are unbounded and dense. The author writes down

$$A=\{a_1,a_2,\ldots\}$$ $$B=\{b_1,b_2,\ldots\}$$

The construction of a order preserving bijection $f:A\to B$ goes like this. The author first says that it is the same as constructing a sequence of pairs $P$ by the following procedure

• Step 1. $(a_1,b_1)\in P$
• Step 2. Let $i$ be the smallest $i$ such that $a_i$ is not paired with anything from $B$. Pair $a_i$ with any $b_j$ such that $b_j$ is not yet paired with anything and the ordering is consistent. Meaning if $a_s<a_t$ then the corresponding $b$s are in the same order. Such choice can always be made because until this step we only chose finitely many elements, and $B$ is infinite, dense and unbounded from both sides.
• Step 3. Similarly let $j$ be the smallest $j$ such that $b_j$ is not paired with anything from $A$. Analogously consistently pair $b_j$ with some $a_i$.
• Step 4. Go back to step 2.

Now each step 2 and each step 3 reduces both $A$ and $B$ by one element. And since in step 2 we pick "smallest (in the sense of index) element of the remaining" we can easily conclude that every element of $A$ will be ultimately be picked. Analogously step 3 guarantees that every element of $B$ will ultimately be picked up. In fact element at index $i$ (in both sets) will be picked up after at most $i$ iterations of the loop. This means that if our function is well defined, then it is surjective.

Being well defined follows from the observation that every $a\in A$ will eventually be picked up, and will be picked up exactly once. Being injective follows from the observation that every $b\in B$ is picked exactly once.