Why $models(\Sigma_1) \cap models(\varphi) = \emptyset \equiv models(\Sigma_1) \subseteq models(\lnot \varphi)$ in the first order logic?

20 Views Asked by At

Here is what my textbook says: enter image description here

I can not see how $models(\Sigma_1) \cap models(\varphi) = \emptyset \equiv models(\Sigma_1) \subseteq models(\lnot \varphi)$. Is this because of the law of excluded middle, i.e. no model satisfies $\Sigma_1 \cup \{ \varphi \}$ and therefore all of them must satisfy $\Sigma_1 \cup \{ \lnot \varphi \}$; otherwise there exists some model $m$ such that neither is satisfied and that definitely breaks the law of excluded middle?

1

There are 1 best solutions below

0
On BEST ANSWER

$\DeclareMathOperator{mod}{models}$Suppose $\mod(\Sigma_1) \cap \mod(\phi) = \emptyset$. Suppose $x \in \mod(\Sigma_1)$. Then $x \notin \mod(\phi)$. Since $x$ is not a model of $\phi$, it is, by definition, a model of $\neg \phi$. So $x \in \mod(\neg \phi)$. Thus, we see that $\mod(\Sigma_1) \subseteq \mod(\neg \phi)$.

Conversely, suppose $\mod(\Sigma_1) \subseteq \mod(\neg \phi)$. Suppose $x \in \mod(\Sigma_1) \cap \mod(\phi)$. Since $x \in \mod(\Sigma_1)$, we see that $x \in \mod(\phi)$. Since $x \in \mod(\Sigma_1)$, we see that $x \in \mod(\neg \phi)$. Then $x \notin \mod(\phi)$. Contradiction. So we see that $\mod(\Sigma_1) \cap \mod(\phi) = \emptyset$.

Note that the law of excluded middle doesn't come into the picture. It's the law of noncontradiction which is relevant. The law of excluded middle is only necessary in the larger proof because it's required for a proof by contrapositive.