[Math] Equivalence to a universal formula

logicmodel-theory

I am trying to prove the equivalence of the following assertions (Exercise 2.5.12 from Marker "Model Theory: An Introduction").

  1. There is a universal formula $\psi(\bar v)$ such that $T \models \forall \bar v (\phi(\bar v) \leftrightarrow \psi(\bar v))$.
  2. 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)$$

Best Answer

Here are a couple of hints:

(1) Prove this first for sentences $\chi$ instead of formulas.

(2) When working with sentences, do not explicitly construct the universal sentence $\chi^*$. Instead, consider the family $S_{\chi}$ of all universal sentences $\theta$ such that $T,\chi \vdash \theta$. Show that if $T \cup S_{\chi} \cup \{\neg \chi\}$ is inconsistent, then you can produce the universal sentence you need. The idea here is that you can recover $\chi$ from some of these universal sentences if $T \cup S_{\chi}$ is strong enough to prove $\chi$ in $T$. Since $S_{\chi}$ were all $T$-provable implications of $\chi$, you should be able to get equivalence in $T$.

(3) Now, actually prove that $T \cup S_{\chi} \cup \{\neg \chi\}$ is inconsistent. Try supposing there is a countable model $A$ of this theory, and show that it cannot exist.

(4) To pass to the case of formulas, expand the signature with new constants to represent the variables, and so change your formula into a sentence by replacing the variables with the constants. Repeat the argument above to obtain a universal sentence, and then justify the claim that replacing the constants with variables again will preserve the equivalence in $T$.

I apologize for not providing more details at the present moment. The proof I am thinking of is a little long. If you want me to flesh out the details please indicate so and I will do so later today.

Related Question