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$.

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$.

## 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.