Past exam of the mathematics course of the University of Cambridge / 2002 / iii / Paper 23 / 3

A 1-embedding, or existential embedding, is a structure embedding $\alpha :A\to B$ satisfyingfor every quantifier-free $\theta$ and every parameter tuple $\mathbf{a}$ from $A$. The forward direction is automatic for an embedding; reflection of existential formulas is the extra property. For an inclusion this says that $A$ is simply closed in $B$. This is weaker than requiring an elementary embedding, which preserves all formulas.

Identify $A$ with its image under $\alpha$. In a language naming every element of $B$, use the same names for elements of $A$ in the two sets of sentencesThis union is consistent. To see finite satisfiability, conjoin the finitely many diagram facts about $B$ into a quantifier-free formula $\delta (\mathbf{a},\mathbf{b})$ and the finitely many elementary-diagram facts about $A$ into $\psi (\mathbf{a})$, where the elements in $\mathbf{b}$ have names outside $A$. Since $B\models \exists \mathbf{y}\delta (\mathbf{a},\mathbf{y})$, the 1-embedding property gives a witnessing tuple in $A$. Interpret the finitely many new names by that tuple. The resulting expansion of $A$ satisfies $\delta$ as well as $\psi$.

By compactness theorem, a model $C$ of this union exists. Its named copy of $B$ gives an embedding $\beta :B\to C$, while its named copy of $A$ is elementary. ConsequentlyThe naming ensures that the two maps agree on the original copy of $A$.

Here ${\forall }_2$ denotes universal-existential sentences, with quantifier-free matrix and possibly empty blocks. Add constants for $A$ and considerWe show that $\Sigma$ is consistent. Suppose a finite subset is inconsistent. Combine its diagram facts as $\delta (\mathbf{c})$ and its finitely many negative existential facts as $\neg \exists {\mathbf{y}}_j{\theta }_j(\mathbf{c},{\mathbf{y}}_j)$. Replacing the new constants by a variable tuple gives the consequenceThis is equivalent to a universal-existential sentence: move all the existential blocks to the front of the disjunction, using the usual nonempty-domain convention. If there are no negative existential facts, the consequence is simply $\forall \mathbf{x}\neg \delta$. By hypothesis $A$ satisfies the displayed consequence. Its named tuple satisfies $\delta$ but none of the existential alternatives, a contradiction.

A model $B$ of $\Sigma$ contains a diagram copy of $A$. Every existential formula false in $A$ is still false in $B$; every one true in $A$ is preserved by the embedding. ThusBoth preservation and reflection are required here; the atomic diagram alone would give only an ordinary embedding.

Let $S$ consist of all universal-existential sentences entailed by $T$, and take $A_0\models S$. By (c), there is an existential embedding of $A_0$ into $B_0\models T$. By (b), $B_0$ embeds in $A_1$ with $A_0\preccurlyeq A_1$. After replacing structures by isomorphic copies, arrange these maps as inclusions. Since $A_1\equiv A_0$, it also satisfies $S$ and the construction can be repeated. This producesThe two interleaved chains have the same union $D$. The elementary chain theorem gives $A_0\preccurlyeq D$. The $B_i$ are an ordinary chain of models of $T$, so the assumed closure under unions of chains gives $D\models T$. Therefore $A_0\models T$. This provesConversely, universal-existential axioms are preserved in such unions: a finite universal tuple occurs in one stage, which already supplies its existential witnesses. The quantifier-free matrix has the same truth value in that stage and in the union. This also explains the inductive first-order theory characterization.