Example of two structures - MathOverflow

Example of two structures

2011-11-29T10:34:13Z

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?

Answer by Joel David Hamkins for Example of two structures

2011-11-29T12:02:21Z

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$.

Answer by Juris Steprans for Example of two structures

2011-11-29T12:29:55Z

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.

Answer by Goldstern for Example of two structures

2011-11-29T16:30:07Z

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.)

Answer by Simon Thomas for Example of two structures

2011-11-29T19:15:25Z

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.