I am asked to prove that if I have two models of dense linear orders DLOs WITH the minimum and maximum. must be izomorpic to each other by fining direct izomorphy.

I seem to always get stuck because the desity i just cannot understand how to count them

im trying something like this: assuming $$M_1=\{a_1 ... a_2 ...\}$$ assuming $$M_1=\{b_1 ... b_2 ...\}$$

I choose $$a_i$$ but if I choose $$H(a_1)=b_i$$

how can I know its in the same order?

sorry for my bad english - translating from hebrew


You are referring to a standard back and forth argument that goes back to Cantor.

The result is that if $A$ and $B$ are densely ordered countable sets with first and last element, then $A$ and $B$ are order-isomorphic.

If $A$ and $B$ are densely ordered with first and last element, and $A$ and $B$ have the same uncountable cardinality, then $A$ and $B$ need not be order isomorphic.

For the proof in the countable case, let $a_s$ be the smallest element of $A$, and let $a_m$ be the biggest. Define $b_s$ and $b_m$ analogously. We will want our isomorphism to take $a_s$ to $b_s$, and $a_m$ to $b_m$. The rest of $A$ (and $B$) is a countable densely ordered set with no first or last element. I am making these obvious comments because you may have been given an isomorphism proof in that case.

Roughly speaking, we build the rest of the isomorphism gradually. List the non-endpoints of $A$ and $B$ as $a_1,a_2,\dots$ and $b_1, b_2,\dots$. Build the isomorphism $\phi$ by first letting $a'_1=a_1$ and $b'_1=b_1$, and putting $\phi(a_1')=b_1'$.

Suppose we have found objects $a'_1,\cdots,a'_n$ and $b'_1,\dots,b'_n$ for which the mapping that takes $a'_i$ to $b'_i$ ($i=1$ to $n$) respects order. If $n$ is odd, look at the smallest $w$ such that $b_w$ is not (yet) one of the $b'_i$. (Note, it is $b_m$, we are working with the arbitrary listing of the elements of $B$, not with the "real" ordering of $B$.)

Let $b'_{n+1}=b_w$. Find any $a\in A$ such that $a$ has the same order relationship to the $a'_i$ as $b_w$ has to the $b'_i$. (There is such an $a$, because our order is dense.) Let $a'_{n+1}=a$.

For $n$ even, do the same sort of thing, except that we use the smallest $w$ such that $a_w$ is not one of the $a'_i$, and let $a'_{n+1}=a_w$. Then we find a suitable $b$ to map $a'_{n+1}$ to.

Very sketchy! The Wikipedia article has more detail.


Hint: start by defining where the minima and maxima must go and then go "back and forth". I'll elaborate if you'd like.

  • $\begingroup$ so can I say that $$H(a_min) =b_min $$ and $$H(a_max) =b_max $$ and than use back and forth like @Nicolas showed? $\endgroup$ – Nahum Jun 9 '12 at 17:22
  • $\begingroup$ Yes, that's what you need to do. $\endgroup$ – Quinn Culver Jun 9 '12 at 17:24
  • $\begingroup$ thats horrible! would copy pasting the proof from en.wikipedia.org/wiki/Back-and-forth_method and adding the lines in my last comment will be correct answer? OK thats wrong, they count on the facttheres no maximum $\endgroup$ – Nahum Jun 9 '12 at 17:25
  • $\begingroup$ Yes, it would be correct, but you should try writing down the proof in your own words! $\endgroup$ – Alex Kruckman Jun 9 '12 at 17:29
  • $\begingroup$ they tought us nothing alike! at all. not even close :( $\endgroup$ – Nahum Jun 9 '12 at 17:30

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.