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

An $L$-embedding $\pi :A\to B$ is an injective map preserving the interpretations of all constants and functions and preserving and reflecting every relation. Explicitly $\pi (c^A)=c^B$, $\pi (f^A(\bar{a}))=f^B(\pi \bar{a})$, and $A\models R(\bar{a})$ if and only if $B\models R(\pi \bar{a})$. Injectivity handles logical equality. Equivalently it is an isomorphism onto an $L$-substructure of $B$, or a map preserving the truth of all quantifier-free formulas. Preserving relations in only one direction would instead give a weaker homomorphism notion, not an embedding.

The relation $A\subseteq B$ means that the domain of $A$ is a subset of the domain of $B$ and the inclusion map is an $L$-embedding. Thus it contains all named constants, is closed under every named function, and uses the restrictions of the ambient relations.

The stronger relation $A\preccurlyeq B$ means that for every first-order formula $\varphi (\bar{x})$ and tuple $\bar{a}$ from $A$,This includes formulas with quantifiers ranging over the respective domains. Elementary inclusion implies ordinary substructure inclusion, but the latter need only preserve quantifier-free truth. In particular an existential witness available in $B$ need not lie in an arbitrary substructure.

The Tarski-Vaught test says that a substructure $A\subseteq B$ is elementary exactly when for every formula $\varphi (x,\bar{y})$ and tuple $\bar{a}\in A$, if $B\models \exists x\varphi (x,\bar{a})$, some $b\in A$ satisfies $B\models \varphi (b,\bar{a})$. Thus every existential assertion with parameters from $A$ that has a witness in $B$ already has a witness in $A$. The matrix may contain quantifiers; restricting it to quantifier-free formulas would not state the full test.