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 .