# Example of two structures

This is probably a very trivial question, still I don't seem to find an answer.

I'd like to see an example (in some language) of two countable structures $\mathcal{M}_1$ and $\mathcal{M}_2$ with $$\mathcal{M}_1 \equiv\mathcal{M}_2$$ and the property that there is no elementary embedding from either one to the other.

Maybe also another one: the same setting as above, but with existing embeddings, just no elementary embeddings. Are there such examples?

-
I'd like to thank everyone for the very helpful responses! (I won't accept a single answer since they're all good answers) – ftonti Dec 9 '11 at 16:20

Take two mutually transcendental real numbers $s$ and $t$ and consider the ordered fields $\mathbb{Q}[r]$ and $\mathbb{Q}[s]$. These are elementarily equivalent but there is no embedding from one to the other because the type defined by either $r$ or $s$ defines a Dedekind cut in the rationals that can be filled in one field but not the other.

-
An even easier version of this example is to take ${\mathbb Q}[r]$ and ${\mathbb Q}[s]$ as ordered additive groups. Now it is clear that they are elementarily equivalent since they are nontrivial divisible ordered abelian groups, but no embedding exist for the same reasons. – Dave Marker Nov 29 '11 at 13:51

Yet another one: For any discrete linear order $L$ without endpoints, let $\sim$ be the natural equivalence relation "distance is finite". Now take two orders $L_1$, $L_2$ such that $L_1/{\sim}$ has, for example, order type $\omega$, and $L_2/{\sim}$ has the converse order type.

(If you equip discrete linear orders with successor and predecessor functions, then the theory has elimination of quantifiers, which shows that the theory is complete.)

-

There are many examples.

For example, in the case of uncountable models, let the language have one unary predicate $U$, and let the predicate be satisfied in ${\cal M}_1$ on a countable set with an uncountable complement, but vice versa in ${\cal M}_2$, with the predicate holding on an uncountable set with a countable complement. These are both models of the theory of an infinite co-infinite predicate, which is complete because all countable models are isomorphic, and so they are elementarily equivalent. But there is no elementary embedding in either direction, since this would involve mapping an uncountable set into a countable set.

But you said you wanted a countable example. Let us modify it by adding infinitely many constant symbols $c_n$ for $n\in\mathbb{N}$. Let us have $U(c_{2n})$ and $\neg U(c_{2n+1})$ in both models, as well as $c_n\neq c_m$, and furthermore each model has a unique $x$ that is not the interpretation of any constant symbol $c_n$. In ${\cal M}_1$, we have $U(x)$, but in ${\cal M}_2$, we have $\neg U(x)$ for this object $x$. The models are elementarily equivalent, since the corresponding theory in any finite restriction of the language is $\omega$-categorical, but there is no elementary embedding in either direction, since there is no place to send the additional object $x$.

-
of course, that's an example without additional conditions (and solves the question by set-theoretic reasoning). But I'd like $\mathcal{M}_1$ and $\mathcal{M}_2$ to be $\textbf{countable}$! – ftonti Nov 29 '11 at 12:12
And why is there no elementary embedding in one direction in your example? Don't we need two relation symbols? – ftonti Nov 29 '11 at 12:18
I have now edited to give a countable example of a similar nature. The point of the unary predicate is that any elementary embedding must take the extension of $U$ in one model to the extension of $U$ in the other, and the complement to the complement. – Joel David Hamkins Nov 29 '11 at 13:36

For each $n \geq 1$, let $F_{n}$ be the free group on $n$ generators and let $\mathbb{Q}^{n}$ be the direct product of $n$ copies of the additive group of the rationals. Since $\mathbb{Q}^{2} \equiv \mathbb{Q}$ and $F_{2} \equiv F_{3}$, it follows that $F_{2} \times \mathbb{Q}^{2} \equiv F_{3} \times \mathbb{Q}$. Clearly $F_{3} \times \mathbb{Q}$ embeds into $F_{2} \times \mathbb{Q}^{2}$ and it is easily seen that $F_{2} \times \mathbb{Q}^{2}$ does not embed into $F_{3} \times \mathbb{Q}$. On the other hand, using the proof that elementary subgroups of free groups are free factors, it follows that $F_{3} \times \mathbb{Q}$ cannot be elementarily embedded into $F_{2} \times \mathbb{Q}^{2}$.

Just for fun, I will also show that there exists an uncountable family of pairwise non-embeddable elementarily equivalent finitely generated simple amenable groups ... but fail to provide a single explicit example of a pair of such groups. Let $\mathcal{G}$ be the Polish space of f.g. groups. Using recent work of Grigorchuk-Medynets, there exists a Borel reduction $\varphi: 2^{\mathbb{N}} \to \mathcal{G}$ from $E_{0}$ to $\cong$; say, $x \mapsto G_{x}$. Let $L$ be the language of group theory and let $\psi: \mathcal{G} \to \mathcal{P}(L)$ be the Borel map $G \mapsto Th(G)$. Then there exists a fixed complete theory and a comeagre $X \subseteq 2^{\mathbb{N}}$ such that $Th(G_{x}) = T$ for all $x \in X$. Consider the Borel subset $Z = \varphi(X) \subseteq \mathcal{G}$. Define a Borel coloring $\theta: [Z]^{2} \to 2$ by $\theta(G,H) = 0$ iff $G$, $H$ are incomparable with respect to embeddability. Then there exists a Cantor set $C \subseteq Z$ such that $\theta$ is constant on $[C]^{2}$. Since each f.g. group has only countably many f.g. subgroups, it follows easily that $C$ is an uncountable family of pairwise non-embeddable elementarily equivalent finitely generated simple amenable groups.

-
Simon, regarding your family of pairwise non-embeddable but elementarily equivalent models, perhaps there is a general model theoretic argument asserting that any theory admitting a perfect set of types has such a family? After all, all we would need is a bunch of models of the theory realizing types, such that no two of them are comparable by inclusion. What is the exact requirement on the theory? – Joel David Hamkins Nov 30 '11 at 19:07
There is a classical theorem (I believe of Shelah) which gives, for any complete unstable theory $T$, $2^\kappa$ pairwise non-embeddable models of $T$ of cardinality $\kappa$, for any $\kappa>|T|$. – Richard Rast Dec 5 '11 at 20:55
But what makes you think that my groups are unstable? – Simon Thomas Dec 6 '11 at 2:15