Proving the Completeness Theorem

679 Views Asked by At

In my lecture notes for logic, the Completeness Theorem for First Order Predicate Calculus has been introduced. In the lectures, it was stated that in order to show the Completeness Theorem holds (i.e. that if $\Gamma \vDash \phi$ then $\Gamma \vdash \phi$), it is enough to show that any consistent set of sentences has a model.

Can someone please explain why this is the case?

1

There are 1 best solutions below

3
On

If $\Gamma$ doesn't prove $\phi$, then $\Gamma\cup\{\lnot\phi\}$ is consistent. Therefore it has a model, and therefore $\Gamma\not\models\phi$.

(Note that if $\Gamma\cup\{\lnot\phi\}$ is inconsistent, then $\Gamma\vdash\lnot\phi\rightarrow\bot$, meaning that $\Gamma\vdash\top\rightarrow\phi$, so $\Gamma\vdash\phi$. Therefore, if $\Gamma$ doesn't prove $\phi$, it has to be the case that $\Gamma\cup\{\lnot\phi\}$ is consistent.)