Proof of contraposition theorem using logical (semantic) entailment definition

Question

I have been reading some older course material from Propositional Logic and I stumbled on a question, and I am unsure on how to start the proof. The question is:

Prove the following theorem (contraposition theorem), by using the definition of logical entailment |=.

W ∪ {ϕ} |= ¬ψ iff W ∪ {ψ} |= ¬ϕ

The definition of |= is:

Let W be a set of closed formulas. Then W entails ϕ, W |= ϕ, if and only if Mod(W ) ⊆ Mod(ϕ)

Where Mod(W) is the class of all models of W.

My first idea is to somehow use the Mod to show equivalence of both of the sides or to somehow work through all the possible cases of the left side formula and show that in every case, the left side entails the right side.

Answer 1

$\mathbf{1}$. Let $W \cup \{ \phi \} \vDash \neg \psi$ where $\phi, \psi$ are wffs and $W$ is a set of wffs. By definition of $\vDash$, we have

$$ \text{Mod}(W \cup \{ \phi \}) \subseteq \text{Mod}(\neg \psi) $$

and by definition of $\subseteq$, we have

$$ \forall x [x \in \text{Mod}(W \cup \{ \phi \}) \to x \in \text{Mod}(\neg \psi)] $$

In other words, for every interpretation $x$, if $x$ is a model of every formula in $W \cup \{ \phi \}$, then $x$ is a model of $\neg \psi$. Without loss of generality, let $x = a$ hereafter. So, by substitution, we have

$$ a \in \text{Mod}(W \cup \{ \phi \}) \to a \in \text{Mod}(\neg \psi) $$

$\mathbf{2}$. Now, assume $a \in \text{Mod}(W \cup \{\psi\})$. Of course, this implies $a \in \text{Mod}(W)$ and $a \in \text{Mod}(\psi)$.

$\mathbf{3}$. Furthermore, for purposes of proof by contradiction, assume $a \in \text{Mod}(\phi)$.

$\mathbf{4}$. Now, consider that if $a \in \text{Mod}(W)$ and $a \in \text{Mod}(\phi)$, then $a \in \text{Mod}(W \cup \{\phi\})$. Thus, by Modus Ponens with lines $2$ and $3$, we indeed have $a \in \text{Mod}(W \cup \{\phi\})$. However, according to line $1$, this implies that $a \in \text{Mod}(\neg \psi)$ and we have already stated on line $2$ that $a \in \text{Mod}(\psi)$. Hence, we have a contradiction, and if we keep all other assumptions in place, then our assumption on line $3$ must false. In other words, it must not be the case that $a \in \text{Mod}(\phi$), implying that $a \in \text{Mod}(\neg \phi)$.

$\mathbf{5}$. Thus, if $a \in \text{Mod}(W \cup \{\psi\})$ as stated on line $2$, then $a \in \text{Mod}(\neg \phi)$. Now, the choice of $a$ was arbitrary, so we know for every interpretation $x$, if $x \in \text{Mod}(W \cup \{\psi\})$, then $x \in \text{Mod}(\neg \phi)$. In other words,

$$ \forall x [x \in \text{Mod}(W \cup \{\psi\}) \to x \in \text{Mod}(\neg \phi)] $$

By definition of $\subseteq$, we have

$$ \text{Mod}(W \cup \{ \psi \}) \subseteq \text{Mod}(\neg \phi) $$

and by definition of $\vDash$, we have

$$ W \cup \{ \psi \} \vDash \neg \phi $$

$\mathbf{6}$. So, if $W \cup \{ \phi \} \vDash \neg \psi$ is the case on line $1$, then we have shown that $W \cup \{ \psi \} \vDash \neg \phi$ is the case on line $5$. Formally speaking,

$$ W \cup \{ \phi \} \vDash \neg \psi \Rightarrow W \cup \{ \psi \} \vDash \neg \phi $$

$\mathbf{7}$. Now, consider that the choice of $\phi$ and $\psi$ in the above formula is abitrary. In other words, we could easily exchange the symbols and repeat the above proof to show

$$ W \cup \{ \psi \} \vDash \neg \phi \Rightarrow W \cup \{ \phi \} \vDash \neg \psi $$

$\mathbf{8}$. Since both $ W \cup \{ \phi \} \vDash \neg \psi \Rightarrow W \cup \{ \psi \} \vDash \neg \phi $ and $ W \cup \{ \psi \} \vDash \neg \phi \Rightarrow W \cup \{ \phi \} \vDash \neg \psi $ hold true, we have

$$ W \cup \{ \phi \} \vDash \neg \psi \Leftrightarrow W \cup \{ \psi \} \vDash \neg \phi $$

by definition of the metalogical biconditional $\Leftrightarrow$. This completes the proof.

Answer 2

$W \cup \{\phi\} \models \neg \psi \iff W \cup \{\psi\} \models \neg \phi$ means: $\mathrm{Mod}(W \cup \{\phi\}) \subset \mathrm{Mod}(\neg \psi) \iff \mathrm{Mod}(W \cup \{\psi\}) \subset \mathrm{Mod}(\neg \phi)$.

($\implies$) Suppose $\mathcal{M} \in \mathrm{Mod}(W \cup \{\psi\})$. Suppose $\mathcal{M} \notin \mathrm{Mod}(\neg \phi)$. Then, $\mathcal{M} \in \mathrm{Mod}(\phi)$. But, as $\mathcal{M} \in \mathrm{Mod}(W \cup \{\psi\})$, $\mathcal{M} \in \mathrm{Mod}(W)$, hence $\mathcal{M} \in \mathrm{Mod}(W \cup \{\phi\})$, and $\mathcal{M} \in \mathrm{Mod}(\neg \psi)$, i.e., $\mathcal{M} \notin \mathrm{Mod}(\psi)$. But, as $\mathcal{M} \in \mathrm{Mod}(W \cup \{\psi\})$, $\mathcal{M} \in \mathrm{Mod}(\psi)$, hence we have a contradiction, and it must be that $\mathcal{M} \in \mathrm{Mod}(\neg \phi)$.

$(\impliedby)$ Exact analogue to the above proof.

$\square$