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 $\mathfrak{A}$ and $\mathfrak{B}$ be such structures with $|\mathfrak{A}|=\{a_{0},a_{1},\ldots\}$ and $|\mathfrak{B}|=\{b_{0},b_{1},\ldots\}$ . Construct an isomorphism in stages; at stage $2n$ be sure $a_{n}$ is paired with some suitable $b_{j}$ , and at stage $2n+1$ be sure $b_{n}$ is paired with some suitable $a_{i}$ .

We use the axioms on page 159. As suggested, we construct an isomorphism of $\mathfrak{A}$ onto $\mathfrak{B}$ in stages. Before we do that, let us introduce a definition and lemma.

If $\mathfrak{A}$ is a dense linear ordering without endpoints, $A\subseteq|\mathfrak{A}|$ is finite, and $a\in|\mathfrak{A}|$ , then we temporary call an index of $a$ in $A$ , $I(a,A)=|\{a'\in A|a'<a\}|$ , i.e. the number of elements of $A$ that are lower than $a$ .

If $\mathfrak{A}$ is a dense linear ordering without endpoints, and $A\subseteq|\mathfrak{A}|$ is finite subset of size $n$ , then for each $k=0,\ldots,n$ , there is $a\in|\mathfrak{A}|-A$ such that $I(a,A)=k$ .

Indeed, for $k=0$ , we need to find $a$ that is lower than all elements in $A$ , which is possible due to the “no endpoints” and transitivity axioms. Similarly, for $k=n$ , we need to find $a$ that is greater then all elements in $A$ , which is again possible due to the “no endpoint” and transitivity axioms. Finally, if $0<k<n$ , then let $c\in A$ and $d\in A$ be the $k$ th and $(k+1)$ th minimum elements of $A$ . For every $a$ such that $c<a<d$ (which exists by the “density” axiom) we have $b\in A$ and $b<a$ iff $b<c$ or $b=c$ (by transitivity), meaning that $I(a,A)=k$ .

In general, at stage $n$ , we are going to define, first, $h(a_{n})=b_{j}$ for some $b_{j}$ , and then, $b_{n}=h(a_{i})$ for some $i$ . We are also going to maintain two sets $A_{n}$ and $B_{n}$ to keep track of those elements in $|\mathfrak{A}|$ and $|\mathfrak{B}|$ that are already assigned values from the other set.

At stage $0$ , we simply define $h(a_{0})=b_{0}$ , $A_{0}=\{a_{0}\}$ and $B_{0}=\{b_{0}\}$ . At stage $n$ , if $h(a_{n})$ is not yet defined (i.e. if $a_{n}\notin A_{n-1}$ ), we, first, define $h(a_{n})=b_{j}$ where $b_{j}$ is the first (with the lowest index) such that $b_{j}\notin B_{n-1}$ and $I(b_{j},B_{n-1})=I(a_{n},A_{n-1})$ (according to the lemma, there is at least one such $b_{k}$ , and, hence, there is one with the lowest index). The equality ensures that for all $a_{k}\in A_{n-1}$ , $a_{k}<a_{n}$ iff $h(a_{k})<h(a_{n})$ . We define $A_{n}=A_{n-1}\cup\{a_{n}\}$ , and $B_{n}=B_{n-1}$ or $B_{n}=B_{n-1}\cup\{b_{j}\}$ if the new value was defined. Second, if $b_{n}\notin B_{n-1}$ , we define $h(a_{i})=b_{n}$ where $a_{i}$ is the first such that $a_{i}\notin A_{n-1}$ and $I(a_{i},A_{n-1})=I(b_{n},B_{n-1})$ (which exists by the lemma). The equality, again, ensures that for all $a_{k}\in A_{n-1}$ , $a_{k}<a_{i}$ iff $h(a_{k})<h(a_{i})$ . We define $A_{n}=A_{n-1}$ or $A_{n}=A_{n-1}\cup\{a_{i}\}$ if the new value was defined, and $B_{n}=B_{n-1}\cup\{b_{n}\}$ .

From the procedure it is clear that a) $h$ is a function, because for each $a_{n}$ the value $h(a_{n})$ is defined at least at stage $n$ , and we never assign two values to any $a_{n}$ , b) $h$ is injective and onto, because for each $b_{n}$ the value $b_{n}$ is assigned to some $h(a_{i})$ at least at stage $n$ , and we never assign it twice, c) $h$ preserves the ordering, due to the way we define it at each stage. Therefore, $h$ is an isomorphism of $|\mathfrak{A}|$ onto $|\mathfrak{B}|$ .

Subpages

Section 2.6: Problem 4 Solution

Section 2.6: Problem 4 Solution