order-preserving question

Question

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?

Answer 1

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

Answer 2

(Another try at a comprehensive answer, summarizing comments, omitting names of commenters, and adding a bit of context:)

On any class $C$ of structures there is a natural quasiorder: For two structures $A,B\in C$ we say $A \le B$ if there is a structure-preserving embedding of $A$ into $B$; this notion, as well as the related equivalence relation (bi-embeddability, $A\le B \ \wedge \ B\le A$) are ubiquitous in mathematics.

(By "embedding" I will always mean a structure-preserving 1-1 map; category theory offers an abstract variant of this notion, a "monic" or "left cancellative" morphism. There is a natural dual notion, which I will ignore here.)

While the existence of an isomorphism between $A$ and $B$ clearly implies bi-embeddability, the converse is rare. Most prominently, the converse does hold for "naked sets" "structureless structures"; the Cantor-Schroeder-Bernstein theorem says that the existence of injective maps from $A$ to $B$ and from $B$ to $A$ implies the existence of a bijection.

Other examples are:

• (trivially:) any class of finite structures

• (slightly less trivially:) any class of well-ordered structures (if we require the embeddings to respect order)

For linear orderings, even for countable linear orderings, bi-embeddability does not imply isomorphism. However, Lindenbaum proved the following curious fact (which is true in any cardinality): if a linear ordering $A$ is isomorphic to an initial segment (downwards closed set, ideal) of a linear ordering $B$, and $B$ is isomorphic to a final segment (upwards closed) of $A$, then $A$ and $B$ are isomorphic.

The rest of this answer will deal with countable structures only. (All the non-structure results mentioned will be "even more true" if uncountable structures are allowed. Structure theorems, such as Laver's theorem, either become more complicated or fail.)

CLO:= countable linear order.

For (countable) linear orders in general, bi-embeddability does not imply isomorphism. First, both the rational numbers as well as the closed rational unit interval are universal (contain an isomorphic copy of any linear countable order), and certainly any two universal CLOs are bi-embeddable.

Secondly, isomorphism preserves many properties of linear orders, such as the existence of a least element, the existence of an empty interval (p,q), the number of such intervals, etc. None of these is preserved under bi-embeddability.

Many classical theorems about linear orders can be found in Rosenstein's 1982 book "Linear Orderings", among them also Laver's theorem: The quasiorder of countable linear orders (under embeddability) is a well-quasi-order and even a "better quasi-order", and there are exactly $\aleph_1$ classes under bi-embeddability. (I find this theorem really remarkable, as I think this is one of the few cases where $\aleph_1$ rather than "continuum" or "a perfect set" appears as the answer to a question about cardinality, without any explicit reference to well-orders.)

Both Rosenstein's book and the wonderful book of "Problems and Theorems" by Komjath and Totik (which presents a nice short proof of Lindenbaum's theorem) are available legally from bookstores (and libraries) (Rosenstein, Komjath-Totik), and illegally from gigapedia.