# If $\mathcal{A} \equiv \mathcal{B}$ and $\mathcal{A} \not \cong \mathcal{B}$, is it possible that $\mathcal{A}$ and $\mathcal{B}$ are bi-embeddable?

Are there structures $\mathcal{A}$ and $\mathcal{B}$ such that $\mathcal{A}$ and $\mathcal{B}$ are elementary equivalent, not isomorphic but bi-embeddable?

• Yet another example, which I don't think is worth another answer but is valuable to keep in mind: the usual example of a complete theory with three countable models gives an example (consider the two models where $\{c_i\}$ is bounded). – Noah Schweber Aug 25 '16 at 20:48
• @NoahSchweber: or just $Th(\mathbb{Z}, <)$: compare $\mathcal{A} = \mathbb{Z} \times \mathbb{Q}$, and $\mathcal{B} = \mathbb{Z} \times (\mathbb{Q} \cap [0, 1])$. – Douglas Ulrich Aug 31 '16 at 2:57
• Chris Laskowski and John Goodrick (among others) have investigated this behaviour in much detail, see for example math.umd.edu/~laskow/Pubs/SB2revise.pdf – Douglas Ulrich Aug 31 '16 at 3:05

Take the free groups $F_n$ and $F_m$ where $m\neq n$ and both are bigger than 1. This paper: http://www.math.mcgill.ca/olga/p3new.PDF proves that they both have the same elementary theory. The groups are not isomorphic, but each one can be embedded in the other.

• Thanks, I figured out that every complete theory not satisfying the Schröder Bernstein property has such models but this is a nice example. – Dino Rossegger Aug 25 '16 at 16:06

Let $\mathcal{A}=(\mathbb{R},<)$ and $\mathcal{B}=(\mathbb{R}\setminus\{0\},<)$. They are elementarily equivalent being both dense linear orders without end-points, clearly each one can be embedded in the other, but $\mathcal{A}$ is a complete order while $\mathcal{B}$ is not.

• +1. Note that while this is much simpler than the other answers, it cannot be easily modified to produce an example involving countable structures. – Noah Schweber Aug 25 '16 at 20:56

Here's another example, with a computability-theoretic motivation and a set-theoretic proof: for a countable linear order $\alpha$, let $H(\alpha)$ be the linear order $\alpha+\alpha\cdot\eta$, where $\eta$ is the order type of the rationals. So, $H(\alpha)$ looks like a copy of $\alpha$ followed by a dense family of copies of $\alpha$.

The "$H$" stands for "Harrison," who investigated the case where $\alpha=\omega_1^{CK}$ is the first non-computable ordinal. That linear order has a number of interesting computability-theoretic properties.

Now, since $\eta$ embeds into $H(\alpha)$ for all $\alpha$, we have that $H(\alpha)$ and $H(\beta)$ are bi-embeddable for any countable linear orders $\alpha$ and $\beta$ (this is just Cantor's theorem that any countable linear order embeds into the rationals). On the other hand, $H(\alpha)\cong H(\beta)\iff \alpha\cong\beta$ is easily checked if $\alpha$ and $\beta$ are ordinals (that is, linear orders with no infinite descending chain). So we just need to find two non-isomorphic ordinals whose $H$-versions are elementarily equivalent.

Note that a counting argument does not immediately do the job: there are continuum-many nonisomorphic linear orders, but there are also continuum-many different complete first-order theories in the language $\{<\}$. In fact, if we restrict attention to ordinals, there may be fewer countable ordinals (up to isomorphism, there are $\aleph_1$) than there are complete theories (there are always $2^{\aleph_0}$-many of those, and assuming that the Continuum Hypothesis fails that's more than $\aleph_1$). So we need to be a bit clever.

There are many ways to do this, but here's one that I like. It's not hard to show that for each sentence $\varphi$ in the language of linear order, the set $$S_\varphi=\{\alpha: \alpha\mbox{ is a countable ordinal and }H(\alpha)\models\varphi\}$$ is $\Pi^1_1$ (or rather, the set of codes for elements of $S_\varphi$ is a $\Pi^1_1$ set of reals). Now, it's a nice fact that any such set either contains or is disjoint from a club ( = closed unbounded set of countable ordinals). So for each of the countably-many sentences $\varphi_i$ in the language of linear order, we may find a club $C_i$ of countable ordinals such that for all $\alpha,\beta\in C_i$, $H(\alpha)$ and $H(\beta)$ agree on whether $\varphi_i$ is true. Now, the intersection of countably many clubs is a club, so we get a club $C$ of ordinals such that for every sentence $\varphi$ in the language of linear order, and every $\alpha,\beta\in C$, either $H(\alpha)$ and $H(\beta)$ both satisfy $\varphi$ or they both satisfy $\neg\varphi$; that is, $H(\alpha)\equiv H(\beta)$ for all $\alpha,\beta\in C$.

Now just use the fact that a club has more than one element.

EDIT: Note that this in fact provides an uncountable family of countable structures which are pairwise elementary equivalent and nonisomorphic, any one of which can be embedded into any other. With a bit more work, we can turn this into such a family of size continuum, which is of course the best possible, by consider the notion of a club of countable linear orders and performing basically the same analysis.

NOTE 1: We could have made do with a much simpler construction - let $I(\alpha)=\alpha+\eta$. This would be enough. However, the $H(\alpha)$s are a natural class of structures, so that seemed worth the extra complexity.

NOTE 2: large cardinal axioms imply that more complicated sets of countable ordinals contain or are disjoint from a club; that is, that the club filter is "closer to being an ultrafilter." So in cases where we have a construction more complicated than $\alpha\mapsto H(\alpha)$, we can still get away with the same argument . . . if we have the right set-theoretic hypotheses.