# If two structures are elementarily equivalent, is there a zigzag of elementary embeddings between them?

Fix a first-order signature $\Sigma$. There is an equivalence relation $\sim$ on the class $\Sigma\mathrm{-Str}$ of all $\Sigma$-structures given by $M \sim N$ iff $M$ and $N$ are elementarily equivalent. Define a relation $\to$ on the class of all $\Sigma$-structures by $M\to N$ if there exists an elementary embedding from $M$ to $N$. Consider the equivalence relation $\stackrel{\sim}{\to}$ generated by $\to$. Does $\stackrel \sim \to$ coincide with $\sim$? If the answer is no in general, then are there natural conditions we can impose on $M,N$ to make the answer come out "yes"?

Unpacking things, $M\stackrel \sim \to N$ iff there are $M_1, \dots, M_{n-1}$ and a zigzag of elementary embeddings $M \leftarrow M_1 \to M_2 \leftarrow \dots \to M_{n-1} \leftarrow N$ of length $n$ (some of these embeddings might be identities). So the question is: if $M$ and $N$ are elementarily equivalent, does such a zigzag of elementary embeddings exist?

It's natural to ask for examples of two $\Sigma$-structures which are elementarily equivalent but have no elementary embedding between them -- i.e. $\Sigma$-structures where there is no zigzag of length 1. And it's easy to give such examples: for example if $\Sigma$ consists of a single unary relation $P$, then a $\Sigma$-structure is a set equipped with a subset, and two such structures are elementarily equivalent if the subsets and their complements are both infinite. But there won't generally be an elementary embedding either way for cardinality reasons. But in this case, a countable subset with a countable complement embeds elementarily into any structure in this elementary equivalence class, so there is a zigzag of length 2 between any two elementarily equivalent $\Sigma$-structures in this case.

There is a (motivating) analogy with homotopy theory: elementary equivalence is like weak homotopy equivalence, while elementary embeddings are like actual homotopy equivalences. In homotopy theory we need to restrict to CW complexes in order for these notions to coincide (this is Whitehead's theorem). The question can be beefed up to ask: if we consider the category of $\Sigma$-structures and homomorphisms, and localize at the elementary embeddings, do two structures become isomorphic in the localized category if they are elementarily equivalent?

• My homotopy theory analogy might be misleading: the affirmative answer to this question shows that if you localize $\Sigma$-structures and homomorphisms at the elementary embeddings, then structures become isomorphic exactly if they are elementarily equivalent. But elementary embeddings are not saturated among homomorphisms! It might be interesting to determine their saturation. – Tim Campion May 15 '15 at 19:26

The Keisler–Shelah theorem implies that the following are equivalent:

• $M$ and $N$ are elementarily equivalent.
• For some set $X$ and some ultrafilter $U$ on $X$, $M^X / U$ and $N^X / U$ are isomorphic.

Thus, recalling Łoś's theorem, any two elementarily equivalent structures in $\Sigma\textbf{-Str}$ are connected by a cospan.

As Emil Jeřábek points out, the use of the Keisler–Shelah theorem is overkill. In fact, the conclusion is just a special case of the elementary amalgamation theorem, which is proved by using the compactness theorem.

• The Keisler–Shelah theorem, which involves a delicate construction of an ultrafilter, is an overkill. The fact that any two elementarily equivalent structures are elementarily embedded in one structure can be proved by a very simple compactness argument. – Emil Jeřábek May 15 '15 at 15:24
• Yes. And the argument is this: let $T'$ be a finite subset of $T_2$, and $\phi(a_1,\dots,a_n)$ its conjunction, with the $M_2$-constants explicitly indicated. Since $M_1$ and $M_2$ are elementarily equivalent, the sentence $\exists x_1\dots\exists x_n\,\phi(x_1,\dots,x_n)$, which holds in $M_2$, must also hold in $M_1$, so you can choose $a'_1,\dots,a'_n\in M_1$ such that $M_1\models\phi(a'_1,\dots,a'_n)$. Then $M_1$, expanded with its own constants, and with $a'_i$ for $M_2$'s constants, is a model of $T_1\cup T'$. – Emil Jeřábek May 15 '15 at 16:12
• @TimCampion: In the statement of Theorem 5.3.1, take $\bar a$ and $\bar c$ to be the empty sequences. The picture is somewhat misleading, as the two mappings depicted in the lower part are not really elementary. – Emil Jeřábek May 15 '15 at 16:18
• What's wrong with overkills? If you are not careful, and you only underkill something, it will come back to haunt you. Haven't you watched '80s horror films to learn that? :-) – Asaf Karagila May 15 '15 at 16:22
• @Asaf: You can hang the theorem at your belt and pat it in a suggestive way in case they wanted to try more tricks, but it’s no good trying to examine the body when all what’s left is a smoking crater in the ground. Meanwhile, given your professional interests, you might appreciate that sometimes you just don’t have the Choice. Can you prove the Keisler–Shelah theorem (and Łoś’s theorem) in ZF + BPIT? It works for elementary amalgamation. – Emil Jeřábek May 15 '15 at 16:46