I'm trying to solve the following exercise in my lecture notes.
Let $T$ be a theory, $\phi(x)$ a formula. Show that the following
conditions are equivalent:
(1) $\phi$ is $T$-equivalent to a universal formula, i.e. there exists a universal
formula $\phi'$ such that $T \models (∀x)(\phi ↔ \phi')$.
(2) $\phi$ is preserved under passing to submodels of models of $T$, i.e. whenever
$A$, $B$ are models of $T$ with $A ≤ B$, $a ∈ A$, and $B \models \phi(a)$, we have
$A \models \phi(a)$.
I think I've made some good progress, but I'm unsure how to prove one step in the proof I've got.
Firstly, it's clear that if we can prove this for sentences $φ$ then the result will follow for arbitrary formulas, since the more general result will follow if we change the formula to a sentence by replacing the free variables with constants.
The (1) $\implies$ (2) is simple and follows easily by working with definitions.
This leaves me with the (2) $\implies$ (1) direction.
I've seen a reasonably similar proof to my attempt here in a related result, which I think I can adapt and make work here.
I let $\Sigma$ be the set of all universal sentences $\psi$ such that $T,\phi \models \psi$. If $T \cup \Sigma \models \phi$, then there's a finite subset $\Delta \subset \Sigma$ such that $T \cup \Delta \models \phi$. Clearly the conjunction of all $\psi \in \Delta$ will be equivalent to a universal formula, and this universal formula will be the one I'm looking for.
The only step I'm unsure about is proving that $T \cup \Sigma \models \phi$ (which I think is true). Presumably to do so I'd want to show $T \cup \Sigma \cup \lbrace\neg\phi\rbrace $ is unsatisfiable, but I can't see how I'd do that.
I'd appreciate any help anyone could offer – either, if my thinking is right, in showing that $T \cup \Sigma \models \phi$ or, if I'm mistaken and need to try another strategy, pointing me in the right direction.
Best Answer
You are very close indeed. You are right that the only gap is that $T \cup \Sigma \models \phi$, so I will fill that gap and then the rest of the argument goes through as you have written.
Let $M \models T \cup \Sigma$, we will show that $M \models \phi$. Consider $T' = T \cup \{\phi\} \cup \operatorname{Th_{qf}}(M)$, where $\operatorname{Th_{qf}}(M)$ is the set of all quantifier-free formulas in the language where we added constants for $M$. Suppose for a contradiction that $T'$ is inconsistent. Then there are $\psi_1, \ldots, \psi_n \in \operatorname{Th_{qf}}(M)$ such that $T \cup \{\phi\} \models \neg \psi_1 \vee \ldots \vee \neg \psi_n$. Since the constants from $M$ do not appear in $T \cup \{\phi\}$ we get that $\neg \psi_1 \vee \ldots \vee \neg \psi_n$ is equivalent to some universal sentence $\theta$ modulo $T \cup \{\phi\}$. So we have $\theta \in \Sigma$, but then $M \models \neg \psi_1 \vee \ldots \vee \neg \psi_n$, a contradiction. We conclude that $T'$ is consistent, so there is a model $N \models T'$. Then in particular $N \models T$ and $N \models \phi$, while also $M \leq N$. Now we can use (2) to conclude that $M \models \phi$, as required.