# Section 2.6: Problem 4 Solution

Working problems is a crucial part of learning mathematics. No one can learn... merely by poring over the definitions, theorems, and examples that are worked out in the text. One must work part of it out for oneself. To provide that opportunity is the purpose of the exercises.

James R. Munkres

Prove that any two countable dense linear orderings without endpoints are isomorphic (Theorem 26K).

*Suggestions*: Let and be such structures with and . Construct an isomorphism in stages; at stage be sure is paired with some suitable , and at stage be sure is paired with some suitable .
We use the axioms on page 159. As suggested, we construct an isomorphism of
onto
in stages. Before we do that, let us introduce a definition and lemma.

If
is a dense linear ordering without endpoints,
is finite, and
, then we temporary call an index of
in
,
, i.e. the number of elements of
that are lower than
.

If
is a dense linear ordering without endpoints, and
is finite subset of size
, then for each
, there is
such that
.

Indeed, for
, we need to find
that is lower than all elements in
, which is possible due to the “no endpoints” and transitivity axioms. Similarly, for
, we need to find
that is greater then all elements in
, which is again possible due to the “no endpoint” and transitivity axioms. Finally, if
, then let
and
be the
th and
th minimum elements of
. For every
such that
(which exists by the “density” axiom) we have
and
iff
or
(by transitivity), meaning that
.

In general, at stage
, we are going to define, first,
for some
, and then,
for some
. We are also going to maintain two sets
and
to keep track of those elements in
and
that are already assigned values from the other set.

At stage
, we simply define
,
and
. At stage
, if
is not yet defined (i.e. if
), we, first, define
where
is the first (with the lowest index) such that
and
(according to the lemma, there is at least one such
, and, hence, there is one with the lowest index). The equality ensures that for all
,
iff
. We define
, and
or
if the new value was defined. Second, if
, we define
where
is the first such that
and
(which exists by the lemma). The equality, again, ensures that for all
,
iff
. We define
or
if the new value was defined, and
.

From the procedure it is clear that a)
is a function, because for each
the value
is defined at least at stage
, and we never assign two values to any
, b)
is injective and onto, because for each
the value
is assigned to some
at least at stage
, and we never assign it twice, c)
preserves the ordering, due to the way we define it at each stage. Therefore,
is an isomorphism of
onto
.