The rational numbers $\Q$ are a countable, totally ordered set, so any subset of the rationals is also countable and totally ordered. In fact, the subsets of the rationals are the `only' countable, totally ordered sets!
Example 5.6.1 Let $A=\N\times \N$ using the lexicographic ordering. Under this ordering, $A$ is totally ordered (in fact, well ordered). We show that $A$ is isomorphic to a subset of $\Q$. Let $f\colon A\to \Q$ be the function $$ f((n,m))= 2n-{1\over m}, $$ and let $B$ be the image of $f$. Clearly $f\colon A\to B$ is surjective. To convince yourself that $f$ is an isomorphism, look at some values: $$ \matrix{ f((1,1)) = 2-1, & f((1,2))= 2-1/2, & f((1,3))=2-1/3, &…,\cr f((2,1)) = 4-1, & f((2,2))= 4-1/2, & f((2,3))=4-1/3, &…,\cr f((3,1)) = 6-1, & f((3,2))= 6-1/2, & f((3,3))=6-1/3, &…,\cr} $$ In general, if we fix $n$, then $f((n,m))$ is a sequence that increases from $2n-1$ toward $2n$. These rational numbers are ordered just like the lexicographic ordering of $\N\times \N$. $\square$
This example may seem surprising at first, because the rationals seem "one-dimensional'' while $\N\times \N$ seems "two-dimensional.''
Theorem 5.6.2 Suppose $A$ is any countable, totally ordered set. Then $A$ is isomorphic to a subset of the rational numbers.
Proof. Since $A$ is countable, we can arrange it in a sequence $a_1, a_2, a_3, …$. We describe a procedure to define $f(a_i)$ for each $a_i$ in turn. Let $f(a_1)$ be any rational. Suppose we have defined $f(a_1), f(a_2), …, f(a_n)$ in such a way that all order relations are preserved (that is, for all $i,j\le n$, $a_i\le a_j$ if and only if $f(a_i)\le f(a_j)$). We want to define $f$ on $a_{n+1}\in A$. Partition the set $\{a_1,…, a_n\}$ into two subsets: $$ X=\{a_i:i\le n \hbox{ and } a_i< a_{n+1}\}, Y=\{a_i:i\le n \hbox{ and } a_i>a_{n+1}\}. $$ In $\Q$, every element of $f(X)$ is smaller than every element of $f(Y)$. Choose $q$ strictly larger than the elements of $f(X)$ and strictly smaller than the elements of $f(Y)$. For each $i\le n$, the relationship between $q$ and $f(a_i)$ is the same as the relationship between $a_{n+1}$ and $a_i$. Therefore, letting $f(a_{n+1})=q$, we have extended the function to one more element in such a way that all order relations are preserved. The resulting function defined on all of $A$ is thus an isomorphism from $A$ to the range of $f$. $\qed$
Exercises 5.6
Ex 5.6.1 Show that the positive rationals, $\Q^+$ are isomorphic to the negative rationals, $\Q^-$. (Hint: $-1/x$.)
Ex 5.6.2 Show that $\{0,1\}\times \Z$ (using the natural ordering on each factor and the lexicographic ordering on the product) is isomorphic to $$\{…, -4, -2, -1, -1/2, -1/4,…, 1/4, 1/2, 1, 2, 4, …\}.$$
Ex 5.6.3 Let $I=\{q\in \Q:0\le q< 1\}$. Show that $\Z\times I$ (with the lexicographic ordering) is isomorphic to $\Q$. (Hint: add.)
If $A$ and $B$ are partially ordered sets, then $f\colon A\to B$ is an embedding if for all $x,y\in A$, $x\le y$ iff $f(x)\le f(y)$.
Ex 5.6.4 Show that an embedding is necessarily an injection, and hence $A$ is isomorphic to the image of $f$.
Ex 5.6.5 Verify that the identity function is an embedding and that the composition of two embeddings is an embedding.
Suppose $A$ and $B$ are partially ordered sets and there is an embedding of $A$ in $B$ and an embedding of $B$ in $A$. We would like to conclude that $A$ and $B$ are isomorphic—sort of a Schröder-Bernstein theorem for partial orders.
Ex 5.6.6 Show that this is true if $A$ is finite.
Ex 5.6.7 Show that this does not hold in general by finding two totally ordered sets that can be embedded in each other but are not isomorphic. (Hint: try intervals.)
In spite of this, it can be proved that when $A$ and $B$ are well ordered and each can be embedded in the other, then they are isomorphic.