David Marker, Model Theory: An Introduction, Exercise 2.5.12

A preservation criterion for formulas equivalent to universal formulas modulo a theory.

Exercise 2.5.12. Let \(\phi(v)\) be an \(\mathcal{L}\)-formula. Show that the following are equivalent.

1. There is a universal formula \(\psi(v)\) such that \(T \vDash \forall v\,(\phi(v) \leftrightarrow \psi(v))\).
2. If \(\mathcal{M}\) and \(\mathcal{N}\) are models of \(T\) with \(\mathcal{M} \subseteq \mathcal{N}\), \(a \in M\), and \(\mathcal{N} \vDash \phi(a)\), then \(\mathcal{M} \vDash \phi(a)\).

Proof. \((1 \Rightarrow 2)\) Let \(\psi(v)\) be a universal formula such that \(T \vDash \forall v\,(\phi(v) \leftrightarrow \psi(v))\). Let \(\mathcal{M}\) and \(\mathcal{N}\) be models of \(T\) with \(\mathcal{M} \subseteq \mathcal{N}\), \(a \in M\), and \(\mathcal{N} \vDash \phi(a)\). We have

\[ \begin{aligned} \mathcal{N} &\vDash \phi(a), \\ \mathcal{N} &\vDash \psi(a), \\ \mathcal{M} &\vDash \psi(a), \\ \mathcal{M} &\vDash \phi(a). \end{aligned} \]

\((2 \Rightarrow 1)\) Consider the following collection:

\[ \Gamma := \{\psi(v) : \psi(v) \text{ is universal and } T \cup \{\phi(v)\} \vDash \psi(v)\}. \]

By compactness and because \(\Gamma\) is closed under conjunctions, \(T \cup \Gamma \vDash \phi(v)\) implies that \(T \cup \{\psi(v)\} \vDash \phi(v)\), and hence \(T \vDash \forall v\,(\phi(v) \leftrightarrow \psi(v))\) for some \(\psi(v) \in \Gamma\).

To that end, let \(\mathcal{M} \vDash T \cup \Gamma\). We will show that \(\mathcal{M} \vDash \phi(v)\). Consider the theory \(T' := T \cup \diag \mathcal{M} \cup \{\phi(v)\}\). For a contradiction, assume \(T' \vDash \bot\). By compactness, there exist \(a \in M\) and \(\chi(a,v) \in \diag \mathcal{M}\) such that \(T \cup \{\phi(v), \chi(a,v)\} \vDash \bot\). This means \(T \cup \{\phi(v)\} \vDash \forall x \, \neg \chi(x,v)\), showing \(\forall x \, \neg \chi(x,v) \in \Gamma\). Thus \(\mathcal{M} \vDash \forall x \, \neg \chi(x,v)\) but \(\mathcal{M} \vDash \chi(a,v)\), a contradiction.

Therefore \(T'\) is satisfiable. Let \(\mathcal{N} \vDash T'\). Then, by (2), \(\mathcal{M} \vDash \phi(v)\). \(\square\)