[Math] Why are the two versions of Gödel Completeness theorem equivalent

logic

There're two versions of Gödel Completeness theorem:

  • If $\Gamma \vDash \phi$, then $\Gamma \vdash \phi$.
  • Any consistent set of fomulas is satisfiable.

I've seen a proof of the second version which is extending a consistent set of fomulas to a maximal set of consistent fomulas with the help of Henkin constants. But I can't see how they're equivalent.

Best Answer

Suppose any consistent set of formulae is satisfiable. Suppose $\Gamma \not\vdash \phi$. Then by definition, $\Gamma \cup \{\neg\phi\}$ is consistent. By assumption, $\Gamma \cup \{\neg\phi\}$ has a model, so not every model of $\Gamma$ is a model of $\phi$, i.e. $\Gamma \not\vDash \phi$.

Suppose instead that $\Gamma \vDash \phi$ implies $\Gamma \vdash \phi$. Take any (non-empty) consistent set of sentences, say $\Sigma = \Gamma \cup \{\phi\}$. Since $\Gamma \cup \{\phi\}$ is consistent, $\Gamma \not\vdash \neg\phi$. By assumption, $\Gamma \not\vDash \neg\phi$, i.e. $\Gamma \cup \{\phi\}$ has a model. (Note, we can always write a non-empty consistent set this way, even if $\Gamma$ here is empty).

Related Question