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?

Question

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

Answer 1

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.

Answer 2

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.

Answer 3

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.