# Prove that there exists separator between two sets of sentences FO.

Let $\Delta$ and $\Gamma$ be such sets of formulas that for every $M$ either $M \models \Delta$ or $M \models \Gamma$. Prove that there exists a such $\phi$ that $\Delta \models \phi \text{ and } \Gamma \cup \{\phi\}$ is inconsistent.

My solution:

Let assume that there is no such $\phi$.

Let's take a such $\psi$ that $\Delta \models \psi$. ( We can consider that there exists such sentence because if it doesn't that means what $\Delta$ must be empty and it simpleto show contradiction.

So, for every $\psi \in \Delta$ ( $\Delta \models \psi$) $\Gamma \cup \psi$ is consistent. So, $\Delta \cup \Gamma$ is consistent. So there is a such model $M$ that $M \models \Delta, M \models \Gamma$ . Contradiction.

Where am I wrong? I've seen solution using compactness theorem but I cannot recall myself it. So, I suppose that I am wrong but I cannot see why. Please explain :).

• How exactly are you getting that $\Delta\cup\Gamma$ is consistent? Also, presumably there is a typo in the problem statement and it should say "either $M\not\models\Delta$ or $M\not\models\Gamma$"? – Eric Wofsey Dec 8 '16 at 4:26

## 1 Answer

As pointed in the comments, the key to this problem is realizing that $\Delta\cup\Gamma$ is consistent if we suppose there is no such $\phi$.

This is because of compactness. If either $Delta$ or $Gamma$ is inconsistent, then trivially there is such a $\phi$. Otherwise, if $S$ is a finite subset of $\Delta\cup\Gamma$ then either $S\subset \Delta$ or $S\subset \Gamma$, in which case $S$ is consistent by virtue of $\Delta$ and $\Gamma$ being consistent themselves.

At last, it might be that $S$ has a mixture of sentences of $\Delta$ and of $\Gamma$. Let $S_\Delta = S\cap\Delta$ and $S_\Gamma = S\cap \Gamma$. If such an $S$ is inconsistent, then we have that $\wedge S_\Delta \implies \neg \wedge S_\Gamma$. As $S_\Delta \subset \Delta$, then $\Delta \implies \neg \wedge S_\Gamma$, while $\Gamma \implies \wedge S_\Gamma$. That contradicts the hypothesis, so $S$ must be consistent.

Therefore, we have just shown that every finite subset of $\Delta\cup\Gamma$ is consistent, and therefore due to compactness the whole set of sentences is consistent. $\square$