Encyclopedia > Goedels completeness theorem

  Article Content

Gödel's completeness theorem

Redirected from Goedels completeness theorem

Gödel's completeness theorem is a fundamental theorem in Mathematical logic proved by Kurt Gödel in 1929. It states, in its most familiar form, that in first-order predicate calculus every universally valid formula can be proved.

A logical formula is called universally valid if it is true in every possible domain and with every possible interpretation, inside that domain, of non-constant symbols used in the formula. To say that it can be proved means that there exists a formal proof of that formula which uses only the logical axioms and rules of inference adopted in some particular formalisation of first-order predicate calculus.

The theorem can be seen as a justification of the logical axioms and inference rules of first-order logic. The rules are "complete" in the sense that they are strong enough to prove every universally valid statement. It was already known earlier that only universally valid statements can be proven in first-order logic.

To cleanly state Gödel's completeness theorem, one has to refer to an underlying set theory in order to clarify what the word "domain" in the definition of "universally valid" means.

The branch of mathematical logic that deals with what is true in different domains and under different interpretations is Model theory; the branch that deals with what can be formally proved is Proof theory. The completeness theorem, therefore, establishes a fundamental connection between what can be proved and what is (universally) true; between model theory and proof theory; between semantics and syntax in mathematical logic. It should not, however, be misinterpreted as obliterating the difference between these two concepts; in fact, another celebrated result by the same author, Gödel's incompleteness theorem, shows that there are inherent limitations in what can be achieved with formal proofs in mathematics.

For an explanation of Gödel's original proof of the theorem, see original proof.

Further Reading

  • Kurt Gödel, "Über die Vollständigkeit des Logikkalküls", doctoral dissertation, University Of Vienna, 1929. This dissertation is the original source of the proof of the completeness theorem.
  • Kurt Gödel, "Die Vollständigkeit der Axiome des logischen Funktionen-kalküls", Monatshefte für Mathematik und Physik 37 (1930), 349-360. This article contains the same material as the doctoral dissertation, in a rewritten and shortened form. The proofs are more brief, the explanations more succinct, and the lengthy introduction has been omitted.

External Link

All Wikipedia text is available under the terms of the GNU Free Documentation License

  Search Encyclopedia

Search over one million articles, find something about almost anything!
  Featured Article
French resistance

... own agents to France in cooperation with SOE. In June 1943 SOE sent Edward Yeo-Thomas for the first time to liaise between Gaullist BCRA and SOE activities in Paris. In ...

This page was created in 37.5 ms