Cantor's isomorphism theorem

Remarks

A standard proof is the back-and-forth method. List $A = \set{a_0, a_1, \dots}$ and $B = \set{b_0, b_1, \dots}$, and build finite order-preserving partial maps step by step. At even steps, the first element of $A$ not yet in the domain gets an image. At odd steps, the first element of $B$ not yet in the range gets a preimage. Density and the lack of endpoints guarantee that a suitable partner exists at each step. The union of the finite maps is the isomorphism. For example, the dyadic rationals $\set{m / 2^k : m \in \Z, k \in \N}$ and the rationals in the open interval $(0, 1)$ are both order isomorphic to $\Q$. Countability is needed: $\R$ satisfies the other hypotheses but is not order isomorphic to $\Q$, because $\R$ is uncountable. The condition on endpoints is needed: $\Q \cap [0, 1]$ has a least element and $\Q$ has none. Density is needed: $\Z$ is countable without endpoints but not dense. In model theory, the theorem says that the theory of dense linear orders without endpoints is $\aleph_0$-categorical.

Going deeper

For a student

The theorem is the basic example of the back-and-forth method, which is used widely in model theory. It shows that the order type $\eta$ of $\Q$ is the unique countable dense order type without endpoints. Every countable total order embeds into $\Q$; the proof is the "forth" half of the same argument. The analogous question for uncountable orders is much harder; Suslin's problem is a famous case.