Newtonpedia ES
Home › Mathematics › Gödel's completeness theorem
Mathematics · 1929

Gödel's completeness theorem

A theorem of first-order logic stating that every formula true in all possible models can be proved by a formal deduction, linking semantic truth with syntactic provability.

Year
1929
Section
Mathematics

History

Gödel's completeness theorem is a central result of mathematical logic that relates two ways of understanding when a statement is true. On one side is semantic truth: a formula is logically valid if it holds in every structure, that is, for every assignment of values to its variables. On the other is syntactic provability: a formula is provable if there is a formal deduction, a finite list of steps in which each step is either an axiom or follows from earlier steps by an inference rule, and whose correctness can be checked mechanically. The theorem states that, for first-order logic, these two notions coincide: every logically valid formula has a formal proof.

Before Gödel, formal logic had advanced considerably thanks to the work of Frege, Russell, Hilbert and Ackermann, who had defined precise deductive systems for predicate calculus. What remained open was whether such systems were strong enough, that is, whether their rules could prove everything that is logically true. In 1929, in his doctoral work at Vienna, Kurt Gödel showed that for first-order logic the answer was yes. His original proof, published in 1930, reduced the problem to a special case of formulas with a particular syntactic form and handled that case with an ad hoc argument. He worked within the Hilbert–Ackermann system, and his argument relied on the deduction theorem and on rules such as modus ponens.

The original proof was regarded as technically intricate. In 1947 Leon Henkin, in his PhD thesis, noticed that the hard part could be presented as a model existence theorem, which he published in 1949. Gisbert Hasenjaeger further simplified Henkin's argument in 1953. Today textbooks usually present Henkin's proof, although Herbrand's approach is sometimes used as well. The modern method enriches the theory with new constants for existential statements, extends it to a complete consistent theory, and builds from it a model out of terms.

The result had lasting consequences. It yields the compactness theorem: if a formula follows logically from an infinite set of premises, it also follows from some finite subset. Gödel himself used the completeness theorem to obtain this compactness, which gave first-order logic a firm foundation. The theorem also means that provability depends only on the chosen axioms rather than on a particular proof system, and that the consequences of a theory can be listed mechanically, though not always decided.

The theorem does not conflict with Gödel's incompleteness theorems, which concern another sense of complete, namely whether a theory settles every statement. Those results show that some true statements about natural numbers cannot be proved in certain theories, and the completeness theorem implies that there are non-standard models in which such statements are false. Today first-order logic underpins much of mathematics, theoretical computer science, program verification and proof assistants. Margetson verified a formal proof of the theorem in Isabelle in 2004.

Timeline

  • 1929Kurt Gödel proves the completeness theorem for first-order logic in his doctoral thesis.
  • 1930Gödel's original proof is published, reducing the problem to a special case of formulas.
  • 1947Leon Henkin observes in his PhD thesis that the hard part of the proof can be presented as a model existence theorem.
  • 1949Henkin's model existence theorem is published.
  • 1953Gisbert Hasenjaeger simplifies Henkin's proof.
  • 2004James Margetson develops a computer-verified formal proof of the theorem using the Isabelle prover.

Trivia and anecdotes

Compactness as a consequence

Gödel used the completeness theorem to prove the compactness theorem, which says that a logical consequence of infinitely many premises is also a consequence of finitely many of them.

Non-standard models

Because it does not contradict incompleteness, the theorem implies there are models of arithmetic where an unprovable statement is false, and these models contain non-standard numbers.

Other milestones in Mathematics