Soundness

Theorem 3.1 (Soundness of Propositional Calculus)   Let $\Phi$ be a set of formulas of the propositional calculus, and let $\phi$ be one such formula. Then

$$\mbox{If } \Phi \vdash \phi \mbox{ then } \Phi \models \phi.$$

We give the proof for a Fitch-style system of deduction. A number of lemmas are required; the first needed is the following one.

Lemma 3.1   If $\Gamma'$ is a superset of $\Gamma$, and $\Gamma \models \phi$, then $\Gamma' \models \phi$ as well.

Proof. Suppose that $\Gamma \models \phi$ and that $\Gamma' \supseteq \Gamma$. Then for every t.v.a. $\cal V$, if $\cal V$ $\models \Gamma$, $\cal V$ $\models \phi$. Now suppose for contradiction that $\Gamma' \not\models \phi$. Then there exists a $\cal V$' such that $\cal V$ $' \models \Gamma'$ but $\cal V$ $\not\models \phi$. Of course, if $\cal V$ $' \models \Gamma'$, then $\cal V$ $' \models \Gamma$. Hence $\cal V$ $' \models \phi$ -- contradiction. QED

Now let $\Phi_i$ be the set of undischarged assumptions at line i in a proof, and let $\phi_i$ be the formula at line i. The theorem is established if we can show

$$\mbox{If } \Phi_k \vdash \phi_k\mbox{ then } \Phi_k \models \phi_k.$$ (3.1)

The proof is by mathematical induction. For the basis clause, set k = 1. Then we need to show

$$\mbox{If } \Phi_1 \vdash \phi_1\mbox{ then } \Phi_1 \models \phi_1.$$ (3.2)

Suppose that $\Phi_1 \vdash \phi_1$. Clearly, {$\phi_1$} $\models \phi_1.$ Now, assume the inductive hypothesis, that is, for every $h \le k$,

$$\mbox{If } \Phi_h \vdash \phi_h\mbox{ then } \Phi_h \models \phi_h$$ (3.3)

To prove the theorem for k+1 it is necessary to consider the 10 different inferences allowed in a standard Fitch-style system of natural deduction. We consider two such cases; the rest are left to our readers.

The first case we consider is $\wedge$ Elimination. Assume that $\phi_{k+1}$ has been derived by this rule at line k+1. Then the following situation sums things up.

$$\begin{array}{r\vert ll} \vdots & \vdots & \vdots\\ l & \ph... ...s\\ k+1 & \phi_{k+1} & l \: \wedge \mbox{ Elim}\\ \end{array}$$

Assume now that $\Phi_{k+1} \vdash \phi_{k+1}$. We know that $\Phi_l \vdash \phi_{k+1} \wedge \psi$, from which it follows by the inductive hypothesis that $\Phi_l \models \phi_{k+1} \wedge \psi$. It follows now by Lemma 3.1 that $\Phi_{k+1} \models \phi_{k+1} \wedge \psi$. Now assume that for all $\cal V$, $\cal V$ $\models \phi_{k+1} \wedge \psi$. By the truth-table definition of conjunction it follows that for all $\cal V$, $\cal V$ $\models \phi_{k+1}$.

Now let's do the case of $\rightarrow$ Intro. For this case we need another lemma, namely:

Lemma 3.2   If $\Gamma \cup \{\phi\} \models \psi$, then $\Gamma \models \phi \rightarrow \psi$.

Proof. Suppose that $\Gamma \cup \{\phi\} \models \psi$. Suppose as well, for contradiction, that $\Gamma \not\models \phi \rightarrow \psi$. Then there is a t.v.a. $\cal V$ such that $\cal V$ $\models \Gamma$ but $\cal V$ $\not\models \phi \rightarrow \psi$. Then by the truth-table for the conditional $\cal V$$\models \phi$ but $\cal V$ $\not\models \psi$. But since $\cal V$ models $\Gamma$ and $\phi$, it follows by our first assumption that $\cal V$$\models \psi$, and we have our desired contradiction. QED

Now, the supposition that $\Phi_{k+1} \vdash \phi_{k+1}$ yields:

$$\begin{array}{r\vert lll} \vdots & & \!\!\!\!\!\! \vdots &\\... ...rrow \psi_j & & i-j \: \rightarrow \mbox{ Intro}\\ \end{array}$$

From this we know $\Phi_i \vdash \psi_i$ and $\Phi_j \vdash \psi_j$, and by the inductive hypothesis we therefore know $\Phi_i \models \psi_i$ and $\Phi_j \models \psi_j$. Since $\Phi_{k+1} \cup \{\psi_i\}$ is a superset of of $\Phi_j$, by Lemma 3.1 it follows that

$$\Phi_{k+1} \cup \{\psi_i\} \models \psi_j.$$

And by Lemma 3.2 it follows from this that

$$\Phi_{k+1} \models \psi_i \rightarrow \psi_j.$$

QED