Gödel's completeness theorem

Remarks

Together with soundness, the theorem gives that $\Gamma \vdash \varphi$ if and only if $\Gamma \models \varphi$. An equivalent form: every consistent set of sentences has a model. The usual proof is Henkin's. Extend a consistent $\Gamma$ to a maximal consistent set with witnesses: for each sentence $\exists x \, \chi$ in it, a constant $c$ with $\chi(c)$. The closed terms, modulo provable equality, then form a model. Since derivations are finite, the theorem implies the compactness theorem. For example, every sentence true in all groups is derivable from the group axioms. The theorem is about first-order logic; full second-order logic has no sound and complete proof system of this kind. Kurt Gödel proved the theorem in his doctoral thesis of 1929.

Going deeper

For a student

The completeness theorem links syntax with semantics. To show that something is unprovable, it is enough to build a model where the axioms hold and the statement fails. This is how independence results, such as those in set theory, are proved. It should not be confused with the incompleteness theorems: these say that some theories are incomplete, meaning that they neither prove nor refute some sentence. Both results hold at once, since such a sentence is true in some models of the theory and false in others.