Elementary substructure

Remarks

Example: $(\Q, <) \preceq (\R, <)$. It follows from quantifier elimination for dense linear orders without endpoints: each formula is equivalent in these orders to a quantifier-free one. A quantifier-free formula has the same truth value in a structure and in its substructures.

Non-example: let $P = \set{1, 2, 3, \dots}$. Then $(P, <)$ is a substructure of $(\N, <)$, but not an elementary one. For $\varphi(x) = \exists y \, (y < x)$, $(P, <) \models \neg \varphi(1)$ and $(\N, <) \models \varphi(1)$.

Taking $n = 0$ in clause 2 shows that $\mathcal{M} \preceq \mathcal{N}$ implies $\mathcal{M} \equiv \mathcal{N}$. The non-example shows that the converse fails, since $(P, <)$ and $(\N, <)$ are isomorphic. The Tarski–Vaught test gives a practical criterion.