Predicate Logic - Main Theorem

TheoremGödel's Completeness Theorem (1929)

Let $\Gamma$ be a set of first-order sentences and $\phi$ be a first-order sentence. Then $\Gamma$ semantically entails $\phi$ (written $\Gamma \models \phi$ ) if and only if $\Gamma$ syntactically proves $\phi$ (written $\Gamma \vdash \phi$ ) in first-order logic.

Equivalently: $\Gamma \vdash \phi$ if and only if $\Gamma \models \phi$ .

Moreover, a set $\Gamma$ of sentences has a model if and only if $\Gamma$ is consistent (does not prove a contradiction).

This theorem, proved by Kurt Gödel in his doctoral dissertation, is one of the most important results in mathematical logic. It establishes that:

Soundness: Every provable formula is semantically valid
Completeness: Every semantically valid formula is provable

The completeness theorem has several equivalent formulations:

Model Existence: A set of sentences $\Gamma$ has a model if and only if $\Gamma$ is syntactically consistent (cannot derive a contradiction).

Refutation Completeness: If $\Gamma$ is unsatisfiable, then $\Gamma$ proves a contradiction.

ExampleApplication to Algebra

Consider the axioms of group theory in first-order logic. The completeness theorem guarantees:

If a statement is true in all groups, it can be proved from the group axioms
If the group axioms plus some additional axioms (e.g., commutativity) are consistent, then there exists a model (an actual group) satisfying all these axioms

For instance, the axioms of abelian groups are consistent (because such groups exist), so by completeness, no contradiction can be derived from them.

Remark

Gödel's completeness theorem applies to semantic consequence, answering the question "Does $\phi$ follow from $\Gamma$ ?" His later incompleteness theorems (1931) address a different question about provability of truth in a fixed structure (like arithmetic). The completeness theorem says the proof system is powerful enough to prove all semantic consequences. The incompleteness theorem says that for arithmetic, there are true statements that cannot be proved.

These are not contradictory: completeness concerns the general notion of logical consequence across all models, while incompleteness concerns truth in a specific intended model.

Proof Sketch: The proof proceeds by constructing a model from a consistent set of sentences.

If $\Gamma \nvdash \phi$ , then $\Gamma \cup \{\neg \phi\}$ is consistent
Extend $\Gamma \cup \{\neg \phi\}$ to a maximal consistent set $\Gamma^*$ (using Zorn's Lemma)
Use the Henkin construction: add witnesses for existential statements
Build a model $\mathcal{M}$ from the Herbrand universe where terms are equivalence classes
Prove that $\mathcal{M} \models \Gamma^*$ , hence $\mathcal{M} \models \Gamma$ and $\mathcal{M} \not\models \phi$
Therefore $\Gamma \not\models \phi$ , proving the contrapositive of completeness

Remark

The completeness theorem has profound implications for mathematics. It justifies formal proof systems as complete tools for establishing logical truth. Combined with the compactness theorem (a corollary), it enables non-standard analysis, model-theoretic constructions, and much of modern mathematical logic.