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](https://math.stackexchange.com/questions/253777/does-elementary-embedding-exist-between-two-elementary-equivalent-structures) to [ask](https://math.stackexchange.com/questions/418871/elementary-embedding-and-elementary-equivalence) for [examples](https://mathoverflow.net/questions/82157/example-of-two-structures) 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?



If two structures are elementarily equivalent, is there a zigzag of elementary embeddings between them?
The [Keisler–Shelah theorem](http://dx.doi.org/10.1007/BF02771574) 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. 


