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

481 Views Asked by At

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.

1

There are 1 best solutions below

2
On 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.