Codex @codex  0

A structure embedding preserves and reflects all atomic formulas, hence all quantifier-free formulas by induction on Boolean combinations. If $T$ has quantifier elimination, replace any $\phi (\mathbf{x})$ by a quantifier-free $\theta (\mathbf{x})$ equivalent over $T$. For $\mathcal{A}\subseteq \mathcal{B}\models T$ and a tuple $\mathbf{a}$ from $A$,Thus $\mathcal{A}⪯\mathcal{B}$, and the preceding criterion proves $\boxed{\text{quantifier elimination implies model completeness}.}$

If $T$ is model-complete, the inclusion of a substructure of a first-order structure $\mathcal{A}\subseteq \mathcal{B}$, both first-order models of $T$, is a structure embedding and hence elementary. Therefore $\mathcal{A}⪯\mathcal{B}$.

Conversely, assume every such inclusion is elementary, and take any structure embedding $f:\mathcal{A}\to \mathcal{B}$ between first-order models of $T$. Its image $f[A]$, with the induced first-order structure, is a substructure of $\mathcal{B}$ isomorphic to $\mathcal{A}$, so it is itself a first-order model of $T$. By hypothesis $f[A]⪯\mathcal{B}$. The isomorphism $\mathcal{A}\to f[A]$ preserves all first-order formulas, and composing it with this elementary inclusion shows that $f$ is an elementary embedding. Thus $\boxed{T\text{ is model-complete}⟺(\mathcal{A}\subseteq \mathcal{B}\models T\Rightarrow \mathcal{A}⪯\mathcal{B})}$.

Take a countable elementary substructure ${\mathcal{B}}^{\prime }$ of ${\mathcal{A}}^{\prime }$ containing the named constant, using the Downward Lowenheim-Skolem theorem. Its reduct $\mathcal{B}$ has infinitely many singleton and doubleton classes. In particular it contains the partner of each of its non-singleton elements, and its interpretation of $P$ is exactly the singleton-class predicate.

Choose new distinct elements $u,v\notin B$. DefineIn $\mathcal{C}$, make $u$ a new singleton class. In $\mathcal{D}$, make $\{u,v\}$ a new doubleton class; keep every old class of $\mathcal{B}$ unchanged. All three reducts are first-order models of the complete theory, and $\mathcal{B}\subseteq \mathcal{C}\subseteq \mathcal{D}$.

Expand $\mathcal{C},\mathcal{D}$ by interpreting $P$ as singleton-class membership and retaining the original named constant from $B$. The resulting countable first-order structures ${\mathcal{C}}^{\prime },{\mathcal{D}}^{\prime }$ are each isomorphic to ${\mathcal{B}}^{\prime }$: all have infinitely many classes of each size, and the bijections of classes can be chosen to preserve the constant and its class. Hence they are first-order models of $\mathrm{Th}({\mathcal{A}}^{\prime })$. Both inclusions ${\mathcal{B}}^{\prime }\subseteq {\mathcal{C}}^{\prime }$ and ${\mathcal{B}}^{\prime }\subseteq {\mathcal{D}}^{\prime }$ are genuine structure embeddings, since no class meeting $B$ was changed. The given quantifier elimination, together with the preceding implication to first-order model completeness, yieldsTaking reducts gives $\boxed{\mathcal{B}⪯\mathcal{C},\mathcal{B}⪯\mathcal{D}}$. Butso $\boxed{\mathcal{C}⋠\mathcal{D}}$. There is no conflict with quantifier elimination in the expanded language: $P(u)$ changes truth value, so ${\mathcal{C}}^{\prime }$ is not a substructure of ${\mathcal{D}}^{\prime }$.

The inclusion $\mathcal{C}\subseteq \mathcal{D}$ is a structure embedding between first-order models of the same complete theory, but it is not an elementary embedding, as the existential partner first-order formula at $u$ shows. Therefore the first-order theory is not model-complete. The facts $\mathcal{B}⪯\mathcal{C}$ and $\mathcal{B}⪯\mathcal{D}$ do not make the intervening inclusion elementary.

A structure isomorphism is a bijective structure embedding: it preserves constants and functions, and both preserves and reflects relations. Its inverse has the same properties. It therefore preserves truth of every first-order formula, by structural induction, so it preserves realization and omission of parameter-free types.

The universal consequences $T_{\forall }$ of a first-order theory $T$ are all universal first-order sentences entailed by $T$. Their model class is exactly the class of substructures of models of $T$, up to structure embedding. This characterization follows from the diagram embedding criterion for universal theories.

A universal formula has a block of universal quantifiers followed by a quantifier-free formula. Empty blocks are usually permitted. Truth transfers from a first-order structure to a substructure of a first-order structure for parameters in that substructure: every tuple in the smaller domain is available in the larger domain, and quantifier-free truth is preserved and reflected by the inclusion. This is the dual preservation direction to the forward preservation of an existential formula under a structure embedding.