Past exam of the model theory and Gödel's incompleteness theorems course of the University of Oxford / 2009 / B / 4 / c / ii

If a model $B$ of $T$ contains $A$ as a substructure, every existential sentence true in $A$ remains true in $B$: use the same witness tuple and preservation of quantifier-free truth. Hence $B$ satisfies the required joint theory.

For the existential-theory embedding criterion, conversely suppose that joint theory has a model. Expand the language by a constant $c_a$ for each $a\in A$, and add the atomic and negated atomic diagram $D(A)$ to $T$. Any finite collection of its literals is a quantifier-free conjunction $\theta (\bar{c})$ true of the corresponding tuple in $A$. Replacing those named constants by variables and existentially closing gives a sentence in ${\mathrm{Th}}_{\exists }(A)$. A model of the assumed joint theory can supply its witnesses, and hence an expansion satisfying those finitely many diagram requirements and any finite subset of $T$.

Compactness therefore gives a model of $T+D(A)$. Its named Elements define an embedding of $A$ into its $L$-reduct: inequalities ensure injectivity, and all function and relation literals ensure preservation and reflection. Replace the ambient model by an isomorphic copy identifying this image with $A$ itself. Thus a model of $T$ containing $A$ exists. The diagram step explains how parameter-free existential information nevertheless yields an embedding of the whole structure.

If $B\models T$ and $B\subseteq A^{\ast }\equiv A$, every universal sentence of $A$ holds in $A^{\ast }$ and is preserved by passage to the substructure $B$. Thus $B$ witnesses satisfiability of the joint theory.

For universal theory and substructures of elementarily equivalent models, conversely let $B$ satisfy $T$ together with the universal theory of $A$. Every existential sentence true in $B$ must be true in $A$: if an existential $\sigma$ were false in $A$, its universal negation would belong to ${\mathrm{Th}}_{\forall }(A)$ and hold in $B$, a contradiction. Hence ${\mathrm{Th}}_{\exists }(B)\subseteq \mathrm{Th}(A)$. In particular $\mathrm{Th}(A)\cup {\mathrm{Th}}_{\exists }(B)$ is satisfiable, with model $A$. Apply the preceding embedding result to the theory $\mathrm{Th}(A)$ and structure $B$. It supplies a structure $A^{\ast }\models \mathrm{Th}(A)$ containing $B$. Therefore $A^{\ast }\equiv A$ and $B\subseteq A^{\ast }$, as required. Elementary equivalence here does not assert that $A$ itself contains a copy of $B$.