# Show a formula is equivalent in a theory to a universal formula iff it is preserved under passing to submodels of models of the theory

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.

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.
• Thanks for your reply. It's really helpful, but I still have one question - why is $M \leq N$ - I'm sure it's probably quite simple but I can't immediately work it out so would appreciate a bit of advice. Commented Nov 8, 2020 at 2:48
• That is because $N$ is also a model of $\operatorname{Th_{qf}}(M)$ (this is also called the diagram of $M$). Commented Nov 8, 2020 at 8:02