In the page for elementary equivalence on wikipedia, in the introduction, they say:
"If N is a substructure of M, one often needs a stronger condition. In this case N is called an elementary substructure of M if every first-order σ-formula φ(a1, …, an) with parameters a1, …, an from N is true in N if and only if it is true in M."
Is it really true that it is a stronger condition? That is, are there structures N and M where Theory(N) = Theory(M) but there is no elementary mapping of N into M?
Perhaps a clarification: The wikipedia page mentions two distinct definitions of elementary equivalence(every sentence is true in both structures or false in both vs. There is a mapping of one into the other that is preserved under all formulas). What I am curious about is a counterexample to the equivalence of these two versions.
A link from one of the comments that answers my question: https://mathoverflow.net/questions/82157/example-of-two-structures
There are counterexamples. Consider the language with signature $\{P_n\mid n\in {\bf N}\}$, where $P_n$ are unary predicates.
Now, consider the model $M=(2^{\bf N},P_n)_{n\in {\bf N}}$ where $P_n$ have the obvious interpretations ($x\in P_n^M$ if $x(n)=1$), and two submodels: $M_1$ which consists of those elements of $M$ which are eventually $0$, so that $$ \forall x\in M_1\,\exists n_0\in {\bf N}\,\forall n>n_0\,(\neg P_n(x))$$ and its dual, $M_2$, which consists of those elements of $M$ which are eventually $1$. Then $M_1$ and $M_2$ are elementarily equivalent (they are models of the theory of infinitely many independent sets), but not only is there no elementary embedding from one into the other, there isn't even any nontrivial partial homomorphism.