Gödel's completeness theorem is a theorem in
model theory proved by
Kurt Gödel in
1929. It states that in
first-order predicate calculus every universally valid statement can be proven.
A statement is called
universally valid if it is true in every domain in which the axioms hold. To cleanly state Gödel's completeness theorem, one therefore has to refer to an underlying
set theory in order to clarify what the word "domain" in the previous sentence means.
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.
References:
- 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 succint, and the lengthy introduction has been omitted.
- Vilnis Detlovs and Karlis Podnieks, "Introduction to mathematical logic", http://www.ltn.lv/~podnieks/