Order Theory 169
Theorem 128 (Cantor). The rational line
Q, ≤
!
is universal for all countable linear or-
ders. That is, every countable linear order
L, ≤
!
is isomorphic to a suborder of the rational
line.
Proof. Since L is countable, we may enumerate it as p
0
, p
1
, p
2
, and so on. This enumer-
ation may not necessarily agree with the ≤
L
order, and the enumeration may jump around
quite a lot in the L order. But that will be fine. We plan to build the isomorphism π from L
to a suborder of Q in stages. Let q
0
be any rational number, and define π : p
0
→ q
0
. This
defines the isomorphism on the first point of L.
Q
L
p
0
q
0
p
1
Consider the next point p
1
in L. It is either above p
0
or below it in the L order. We may
choose a rational number q
1
that relates to q
0
in just the same way, and define π : p
1
→ q
1
.
This defines π on the first two points of L.
Q
L
p
0
q
0
p
1
q
1
p
2
In this way, we gradually associate each point p
n
in L with a rational number q
n
, such that
the map π : p
n
→ q
n
preserves the order. At each stage, the next point p
n
is either above
all earlier points p
k
, below them all, or else in between two of them; and there will always
be a corresponding rational number q
n
relating to the previous q
k
in exactly the same way.
Q
L
p
0
q
0
p
1
q
1
p
2
q
2
p
3
q
3
p
4
q
4
p
5
q
5
It follows that π is an isomorphism of
L, ≤
L
!
with the corresponding image set {q
0
, q
1
, q
2
,...},
which constitutes a suborder of the rational line. So every countable linear order is isomor-
phic to a suborder of the rational line.