Is it possible to have two models $M$, $N$ and for each one an elementary embedding to the other one, but $M$, $N$ are not isomorphic?

Question

Is it possible to have two models $M$ and $N$ of a theory $T$, an elementary embedding $f$ from $M$ to $N$, and also an elementary embedding $g$ from $N$ to $M$, but such that $M$ and $N$ are not isomorphic?

I myself think the answer is no, but I don't have any good reasons. I'm looking for an example.

Answer 1

One simple source of examples is the theory of dense linear orders. This theory has quantifier elimination, so any embedding is elementary. So, for instance, $M=\mathbb{R}$ and $N=\mathbb{R}\setminus\{0\}$ each elementarily embed in the other (the embedding $N\to M$ is obvious and $M$ embeds in $N$ since $\mathbb{R}$ is order-isomorphic to any open interval in $\mathbb{R}$). However, they are not isomorphic, since $\mathbb{R}$ is Dedekind-complete and $\mathbb{R}\setminus\{0\}$ is not.

Answer 2

In a comment, bof has given a countable counterexample, and Eric's answer gives an example of size continuum. Here's an example which is "all about" cardinality: there is no interesting model-theoretic structure at all, a model is characterized entirely by a multiset of cardinals, and it all comes down to making a pair of sequences of cardinals which "dovetail."

Consider the language consisting of a single binary relation $E$. Let's look at two different models which consist of infinitely many $E$-equivalence classes.

• In $\mathcal{A}$, we have one $E$-class of cardinality $\aleph_{2n}$ for each $n\in\omega$.

• In $\mathcal{B}$, we have one $E$-class of cardinality $\aleph_{2n+1}$ for each $n\in\omega$.

The theory of these structures, as in Eric's example, has quantifier elimination, so all embeddings are elementary.

Answer 3

Here is an example with countable models, in fact, countable ordered sets. (By ordered set and order type I mean linearly ordered set and linear order type.)

Lemma 1. Let $\varphi,\psi$ be order types. If $(\omega^*+\omega)\varphi=(\omega^*+\omega)\psi,$ then $\varphi=\psi.$

Lemma 2. Let $M,N$ be ordered sets with order types $\operatorname{tp}M=(\omega^*+\omega)\varphi,\ \operatorname{tp}N=(\omega^*+\omega)\psi.$
If $\varphi\le\psi,$ then $M$ is elementarily embeddable in $N.$

Lemma 1 is more or less obvious. For Lemma 2, the method of Ehrenfeucht–Fraïssé games may be used to show that the natural embedding is elementary.

Now all we have to do is find countable order types $\varphi,\psi$ such that $\varphi\le\psi\le\varphi$ while $\varphi\ne\psi.$ For this we can take $\varphi=\eta$ and $\psi=1+\eta$ where $\eta$ is the order type of the rational numbers; or, if scattered orderings are preferred, $\varphi=\omega^*\omega$ and $\psi=1+\omega^*\omega$ will do.