The rational numbers \(\mathbb{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=\mathbb{N}\times \mathbb{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 \(\mathbb{Q}\). Let \(f\colon A\to \mathbb{Q}\) be the function \[f((n,m))= 2n-\frac{1}{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: \[\begin{matrix} f((1,1)) = 2-1, & f((1,2))= 2-\frac{1}{2}, & f((1,3))=2-\frac{1}{3}, &\dots,\\ f((2,1)) = 4-1, & f((2,2))= 4-\frac{1}{2}, & f((2,3))=4-\frac{1}{3}, &\dots,\\ f((3,1)) = 6-1, & f((3,2))= 6-\frac{1}{2}, & f((3,3))=6-\frac{1}{3}, &\dots, \end{matrix}\] 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 \(\mathbb{N}\times \mathbb{N}\). \(\square\)
This example may seem surprising at first, because the rationals seem “one-dimensional” while \(\mathbb{N}\times \mathbb{N}\) seems “two-dimensional”.
Theorem 5.6.2Every countable, totally ordered set is embeddable into the rational numbers.
Proof
Since \(A\) is countable, we can arrange it in a sequence \(a_1, a_2, a_3, \dots\). 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), \dots, 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,\dots, a_n\}\) into two subsets: \[X=\{a_i:i\le n \text{ and } a_i< a_{n+1}\}, Y=\{a_i:i\le n \text{ and } a_i>a_{n+1}\}.\] In \(\mathbb{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, \(\mathbb{Q}^+\) are isomorphic to the negative rationals, \(\mathbb{Q}^-\). (Hint: \(-1/x\).)
Ex 5.6.2
Show that \(\{0,1\}\times \mathbb{Z}\) (using the natural ordering on each factor and the lexicographic ordering on the product) is isomorphic to\[\{\dots, -4, -2, -1, -1/2, -1/4,\dots, 1/4, 1/2, 1, 2, 4, \dots\}.\]
Ex 5.6.3
Let \(I=\{q\in \mathbb{Q}:0\le q< 1\}\). Show that \(\mathbb{Z}\times I\) (with the lexicographic ordering) is isomorphic to \(\mathbb{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.