Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

This question already has an answer here:

First of all the definition: A dense linear order is a $\{<\}$-structure in which the following formulas are valid:

enter image description here

Question: How can I prove that any two countable DLO's (dense linear order) are isomorph?

Hint (from my logic book): Let $M$ and $N$ be two countable DLOs. Now we should somehow be able to proof that every partial finite isomorphism $f:M\rightarrow N$ (what is the definition for a partial iso.?) can be continued to a finite partial isomorphism $f':M\rightarrow N$ which contains a given element from $M$ (or $N$) in the domain (range). Using this we can make enumerations from $M$ and $N$ and construct an isomorphism.

share|improve this question
    
I think by finite partial he means you only take a finite subset in the domain and map it to a finite subset of the codomain. Far from being sure though. –  xavierm02 Apr 16 '13 at 22:41
    
Your question has an obvious and immediate answer. We can't. $\Bbb R$ and $\Bbb Q$ are both DLO, but cannot be isomorphic because there is no bijection between the two sets. If you restrict your question to countable sets, then it is possible and I am almost certain that there is an answer on this site already. –  Asaf Karagila Apr 16 '13 at 22:47
    
I edited it, I meant countable DLOs. I found nothing on this site, I only found a proof in the book "Linear orderings" from Joseph Rosenstein, Theorem 2.8: "books.google.at/…; but I do not understand it in relation to my hint. The other problem is that unfortunately the notation in logic is not uniform –  Voyage Apr 16 '13 at 22:50
1  
You can find an answer here. And although it proves that DLO+endpoints are isomorphic I am certain that you will be able to figure out a way of deriving the wanted result for the case without endpoints. (I am still convinced that the answer appears somewhere on the site, though). –  Asaf Karagila Apr 16 '13 at 22:55
    
Thanks for the reference, still I would be really thankful if somebody could explain the proof using the hint I stated. –  Voyage Apr 16 '13 at 23:00
add comment

marked as duplicate by Asaf Karagila, Joe, Amzoti, vonbrand, Erick Wong Apr 17 '13 at 0:45

This question has been asked before and already has an answer. If those answers do not fully address your question, please ask a new question.

1 Answer

To understand the hint first recall that a partial isomorphism is a function from a subset of $M$ to a subset of $N$ which is an isomorphism of the induced substructres; i.e. bijective and order-isomorphism.

Now to show that you can always extend by one more step, suppose that $f$ was a partial isomorphism between two finite subsets, $x_1,\ldots,x_k\in M$ and $y_1\ldots y_k\in N$, such that $f(x_i)=y_i$. We may assume that $x_1<x_2<\ldots<x_k$.

Let $x\in M$ be a point distinct of all the $x_i$. If $x_k<x$ then we simply find $y\in N$ such that $y_k<y$ (since the orders are dense and without endpoints we can do that), and define $f'=f\cup\{\langle x,y\rangle\}$. Easily this is a partial isomorphism; and similarly if $x<x_1$ we find $y<y_1$ and do the same.

Otherwise there is some $i<k$ such that $x_i<x<x_{i+1}$. Since the order on $N$ is dense there is some $y\in N$ such that $y_i<y<x_{i+1}$. Simply extend $f$ to $f'$ as before, by setting $f'(x)=y$ and $f'(x_i)=y_i$.

In all cases it is easily checked that the result is a partial isomorphism. The proof of extending the function by a point from $N$ is the same by noting that $f^{-1}$ is a partial isomorphism in the other direction (so now we again extend the domain).


Now you fix some enumeration of the two DLOs and simply set $f_0(x_0)=y_0$; and then continue by induction each time carefully adding a point from the domain and then a point from the range.

share|improve this answer
    
Thank you, one questions. What do you mean with the notation $\{<(x,y)>\}$ ? –  Voyage Apr 16 '13 at 23:22
    
@Voyage: It means that I have to go to bed... :-) –  Asaf Karagila Apr 16 '13 at 23:22
add comment

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