6

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.

Metta World Peace
  • 6,403

2 Answers2

12

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).

Alex Kocurek
  • 2,991
  • 1
    Hi, I am a little confused by the step: $\Gamma \nvDash \neg \phi$ implying $\Gamma \cup { \phi }$ has a model. I'm wondering if you could elaborate on this? How would this mean there is an L-structure such that all sentences of $\Gamma \cup { \phi }$ are true? – CowNorris Mar 05 '19 at 22:33
3

To prove the second from the first, set $\phi$ to be a contradiction and take the contrapositive. To prove the first from the second, consider the consistency of $\Gamma \cup \{ \neg \phi \}$ and take the contrapositive.

Qiaochu Yuan
  • 419,620