A B are totally-ordered sets and there exist two maps f and g such that f is a order-preserving injection from A to B and g is a order-preserving injection from B to A.


Q: Are A and B necessarily similar?



order-preserving question
In spite of not knowing whether similar means isomorphic or not, the answer seems to be no.


After an idea from Joel Hamkins, I transcribe some of the comments above.


I start the parade with: "No. Although all countable dense total orders without endpoints are isomorphic, there are countable total orders which are not dense and have one or two extrema. One example that is worth studying is the rationals x 2, which has countably many pairs (a,b) with no element c such that a < c < b. This can inject into the rationals, and the rest I leave to you as an exercise."


Part of what Stefan Geschke said: "To elaborate on Gerhard's example, any two countable linear orders that contain a copy of the rationals embed into each other. Except for containing a copy of $\mathbb Q$ they can be as dissimilar as you want."


User goldstern adds: "... whereas the embeddability and bi-embeddability structure on the countable linear orders that do not contain a copy of the rationals (so-called scattered orders) is complicated but well-investigated. (well-quasi-ordered, has exactly $\aleph\_1$ classes: Richard Laver, Fraisse conjecture, 1971) "


The original poster then observes: " take A=Q\{0} and B=Q\(-1, 1), and it is easy to get two injections. "


For extra flavor, Ali Enayat remarks: "Two points: (a) the intervals [0,1] and (0,1) provide the easiest counterexample; (b) with the added hypothesis that either A or B is a well-ordering, then A and B indeed have to be similar (by Cantor's so-called Trichotomy Theorem)."


In a closely related vein, Andreas Blass provides: "Another curious point: If $A$ is order-isomorphic to an initial segment of $B$ and $B$ is order-isomorphic to a final segment of $A$, then $A$ and $B$ are order-isomorphic. (It's essential that one of the segments be initial and the other final; if both are initial then $[0,1]$ and $[0,1)$ are a counterexample.)"


I'll let someone else turn this into a Wikipedia article.


EDIT: A late arrival, "The statement in the above note of Andreas Blass is due to A. Lindenbaum and it can be found in W. Sierpinski: Cardinal and ordinal numbers, 1965, Ch. XII 9, Theorem 2. It is also in my book with Totik: Problems and theorem in classical set theory, problem 13 in ch 6. – Péter Komjáth" END EDIT


Gerhard "Please To Call It Research" Paseman, 2011.07.09


