I am trying to prove the equivalence of the following assertions (Exercise 2.5.12 from Marker "Model Theory: An Introduction").
- There is a universal formula $\psi(\bar v)$ such that $T \models \forall \bar v (\phi(\bar v) \leftrightarrow \psi(\bar v))$.
- If $\cal M$ and $\cal N$ are models of $T$ with $\cal M \subset N$, $\bar a \in M$ and ${\cal N} \models \phi(\bar a)$, then ${\cal M} \models \phi(\bar a)$.
It is straightforward to show that 1 implies 2. For the converse I tried to work out some examples. Let $\begin{array} {rl} T = \{ & \forall x (\exists y R(x, y) \leftrightarrow P(x)) \lor \forall x (\exists y R(x, y) \leftrightarrow \lnot P(x)), \\ & \exists x, y R(x, y)\} \end {array}$ and $\phi$ be $\exists y R(x, y)$. Assume that $\cal M$ and $\cal N$ are models of $T$ with $\cal M \subset N$. Then ${\cal M} \models \forall x(\exists y R(x, y) \leftrightarrow P(x)) \lor \forall x (\exists y R(x, y) \leftrightarrow \lnot P(x)).$ Without lose of generality assume that ${\cal M} \models \forall x(\exists y R(x, y) \leftrightarrow P(x)).$ For some $b, c \in M$ we must also have ${\cal M} \models R(b, c)$ and hence ${\cal M} \models P(b)$. It follows that ${\cal N} \models \exists y R(b, y) \land P(b)$. Hence ${\cal N} \not \models \forall x (\exists y R(x, y) \leftrightarrow \lnot P(x))$. And so ${\cal N} \models \forall x (\exists y R(x, y) \leftrightarrow P(x)).$ But now if ${\cal N} \models \exists y R(a, y)$ for some $a \in M$, then ${\cal N} \models P(a)$ hence ${\cal M} \models P(a)$ and hence ${\cal M} \models \exists y R(a, y)$. Thus the second property holds and so $T \models \forall x(\exists y R(x, y) \leftrightarrow \psi(x))$ for some universal formula $\psi$. But I can't find such a formula. Is there such a $\psi$ or have I an error in my deductions?
Edit
I have found the universal formula. $T \models \forall x \Bigg(\exists y R(x, y) \leftrightarrow \forall u, v \bigg(\Big(\big(R(u,v) \to p(u)\big) \land p(x) \Big) \lor \Big(\big(R(u,v) \to \lnot p(u) \big) \land \lnot p(x)\Big)\bigg)\Bigg)$