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)$$