10
$\begingroup$

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

$\endgroup$
3
  • 2
    $\begingroup$ 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). $\endgroup$ Aug 25, 2016 at 20:48
  • $\begingroup$ @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])$. $\endgroup$ Aug 31, 2016 at 2:57
  • $\begingroup$ Chris Laskowski and John Goodrick (among others) have investigated this behaviour in much detail, see for example math.umd.edu/~laskow/Pubs/SB2revise.pdf $\endgroup$ Aug 31, 2016 at 3:05

3 Answers 3

8
$\begingroup$

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.

$\endgroup$
1
  • $\begingroup$ Thanks, I figured out that every complete theory not satisfying the Schröder Bernstein property has such models but this is a nice example. $\endgroup$ Aug 25, 2016 at 16:06
14
$\begingroup$

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.

$\endgroup$
1
  • $\begingroup$ +1. Note that while this is much simpler than the other answers, it cannot be easily modified to produce an example involving countable structures. $\endgroup$ Aug 25, 2016 at 20:56
4
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.