First Steps

We now prove the completeness of our Fitch-style system of natural deduction for first-order languages, i.e.,

Theorem 4.1 (Completeness of Natural Deduction for First-Order Languages)   Let $\Phi$ be a set of first-order formulas, and let $\phi$ be one such formula. Then

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

To establish this theorem it suffices to show that

$$\mbox{Every consistent set $\Gamma$\space of first-order formulas is satisfiable.}$$ (4.1)

Here's why: First, we need to prove that

$$\mbox{If } \Phi \not\vdash \phi, \mbox{ then } \Phi \cup \{\neg\phi\} \mbox{ is consistent}.$$ (4.2)

In order to do so, suppose that $\Phi \not\vdash \phi$; and suppose for contradiction that $\Phi \cup \{\neg\phi\}$ is inconsistent. Then there is some finite $\Gamma = \{\psi_1, \psi2, \ldots, \psi_n\} \subseteq \Phi \cup \{\neg\phi\}$ such that $\Gamma \cup \{\neg\phi\}$ can be used to derive $\phi$. We also know that we can prove $\psi \vee \neg\psi$ at any point in a derivation without leaving any suppositions standing. And of course $\Gamma \cup \{\phi\}$ are together sufficient to derive $\phi$. All of this allows us to construct the following derivation, which establishes $\Phi \vdash \phi$, giving us our desired contradiction; so 4.2 can be taken as a given from this point on.

$$\begin{array}{rlll} 1 & \!\!\!\vline \hspace{.05in} \phi_1 &... ...!\vline \hspace{.05in} \phi & &\vee \mbox{ Elim}\\ \end{array}$$

Now here's how to obtain the completeness theorem from 4.1: Assume 4.1, fix an arbitrary set $\Phi$ and formula $\phi$, and suppose that $\Phi \models \phi$, but -- aiming for a contradiction -- that $\Phi \not\vdash \phi$. From $\Phi \not\vdash \phi$ it follows by way of 4.2 that $\Phi \cup \{\neg\phi\}$ is consistent, and this, conjoined with 4.1, implies that $\Phi \cup \{\neg\phi\}$ is satisfiable. But we know that every $\cal I$ that satisfies $\Phi$ must satisfy $\phi$ as well, so there is some $\cal I$$^\ast$ which both satisfies both $\Phi \cup \{\neg\phi\}$ and $\phi$, i.e., an $\cal I$$^\ast$ that both satisfies $\phi$ and fails to satisfy $\phi$. QED