 Gödel's completeness theorem

Gödel's completeness theorem is a fundamental theorem in mathematical logic that establishes a correspondence between semantic truth and syntactic provability in firstorder logic. It was first proved by Kurt Gödel in 1929.
A firstorder formula is called logically valid if it is true in every structure for its language. The completeness theorem shows that if a formula is logically valid then there is a finite deduction (a formal proof) of the formula. The deduction is a finite object that can be verified by hand or computer. This relationship between truth and provability establishes a close link between model theory and proof theory in mathematical logic.
An important consequence of the completeness theorem is that it is possible to enumerate the logical consequences of any effective firstorder theory, by enumerating all the correct deductions using axioms from the theory.
Gödel's incompleteness theorem, referring to a different meaning of completeness, shows that if any sufficiently strong effective theory of arithmetic is consistent then there is a formula (depending on the theory) which can neither be proven nor disproven within the theory. Nevertheless the completeness theorem applies to these theories, showing that any logical consequence of such a theory is provable from the theory.
Contents
Background
There are numerous deductive systems for firstorder logic, including systems of natural deduction and Hilbertstyle systems. Common to all deductive systems is the notion of a formal deduction. This is a sequence (or, in some cases, a finite tree) of formulas with a speciallydesignated conclusion. The definition of a deduction is such that it is finite and that it is possible to verify algorithmically (by a computer, for example, or by hand) that a given collection of formulas is indeed a deduction.
A formula is logically valid if it is true in every structure for the language of the formula. To formally state, and then prove, the completeness theorem, it is necessary to also define a deductive system. A deductive system is called complete if every logically valid formula is the conclusion of some formal deduction, and the completeness theorem for a particular deductive system is the theorem that it is complete in this sense. Thus, in a sense, there is a different completeness theorem for each deductive system.
Statement and consequences
Gödel's completeness theorem says that a deductive system of firstorder predicate calculus is "complete" in the sense that no additional inference rules are required to prove all the logically valid formulas. A converse to completeness is soundness, the fact that only logically valid formulas are provable in the deductive system. Taken together, these theorems imply that a formula is logically valid if and only if it is the conclusion of a formal deduction.
A more general version of Gödel's completeness theorem holds. It says that for any firstorder theory T and any sentence S in the language of the theory, there is a formal deduction of S from T if and only if S is satisfied by every model of T. This more general theorem is used implicitly, for example, when a sentence is shown to be provable from the axioms of group theory by considering an arbitrary group and showing that the sentence is satisfied by that group.
The branch of mathematical logic that deals with what is true in different models is called model theory. The branch called proof theory studies what can be formally proved in particular formal systems. The completeness theorem establishes a fundamental connection between these two branches, giving a link between semantics and syntax. The completeness theorem should not, however, be misinterpreted as obliterating the difference between these two concepts; in fact Gödel's incompleteness theorem, another celebrated result, shows that there are inherent limitations in what can be achieved with formal proofs in mathematics. The name for the incompleteness theorem refers to another meaning of complete (see model theory  Using the compactness and completeness theorems). In particular, Gödel's completeness theorem deals with formulas that are logical consequences of a firstorder theory, while the incompleteness theorem constructs formulas that are not logical consequences of certain theories.
An important consequence of the completeness theorem is that the set of logical consequences of an effective firstorder theory is an enumerable set. The definition of logical consequence quantifies over all structures in a particular language, and thus does not give an immediate method for algorithmically testing whether a formula is logically valid. Moreover, a consequence of Gödel's incompleteness theorem is that the set of logically valid formulas is not decidable. But the completeness theorem implies that the set of consequences of an effective theory is enumerable; the algorithm is to first construct an enumeration of all formal deductions from the theory, and use this to produce an enumeration of their conclusions. The finitary, syntactic nature of formal deductions makes it possible to enumerate them.
Relationship to the compactness theorem
The completeness theorem and the compactness theorem are two cornerstones of firstorder logic. While neither of these theorems can be proven in a completely effective manner, each one can be effectively obtained from the other.
The compactness theorem says that if a formula φ is a logical consequence of a (possibly infinite) set of formulas Γ then it is a logical consequence of a finite subset of Γ. This is an immediate consequence of the completeness theorem, because only a finite number of axioms from Γ can be mentioned in a formal deduction of φ, and the soundness of the deduction system then implies φ is a logical consequence of this finite set. This proof of the compactness theorem is originally due to Gödel.
Conversely, for many deductive systems, it is possible to prove the completeness theorem as an effective consequence of the compactness theorem.
The ineffectiveness of the completeness theorem can be measured along the lines of reverse mathematics. When considered over a countable language, the completeness and compactness theorems are equivalent to each other and equivalent to a weak form of choice known as weak König's lemma, with the equivalence provable in RCA_{0} (a secondorder variant of Peano arithmetic restricted to induction over Σ^{0}_{1} formulas). Weak König's lemma is provable in ZF, the system of Zermelo–Fraenkel set theory, and thus the completeness and compactness theorems for countable languages are provable in ZF. However the situation is different when the language is of arbitrary large cardinality since then, though the completeness and compactness theorems remain provably equivalent to each other in ZF, they are also provably equivalent to a weak form of the axiom of choice known as the ultrafilter lemma. In particular, no theory extending ZF can prove either the completeness or compactness theorems over arbitrary (possibly uncountable) languages without also proving the ultrafilter lemma on a set of same cardinality, knowing that on countable sets, the ultrafilter lemma becomes equivalent to weak König's lemma. Also, although every consistent, countable firstorder theory has a finite or countable model (as a consequence of the completeness theorem and the LöwenheimSkolem theorem), it is known there are effective consistent firstorder theories that do not have computable models.
Completeness in other logics
The completeness theorem is a central property of firstorder logic that does not hold for all logics. Secondorder logic, for example, does not have a completeness theorem for its standard semantics (but does have the completeness property for Henkin semantics), and the same is true of all higherorder logics. It is possible to produce sound deductive systems for higherorder logics, but no such system can be complete. The set of logicallyvalid formulas in secondorder logic is not enumerable.
Lindström's theorem states that firstorder logic is the strongest (subject to certain constraints) logic satisfying both compactness and completeness.
A completeness theorem can be proved for modal logic or intuitionistic logic with respect to Kripke semantics.
Proofs
Gödel's original proof of the theorem proceeded by reducing the problem to a special case for formulas in a certain syntactic form, and then handling this form with an ad hoc argument.
In modern logic texts, Gödel's completeness theorem is usually proved with Henkin's proof, rather than with Gödel's original proof. Henkin's proof directly constructs a term model for any consistent firstorder theory. James Margetson (2004) developed a computerized formal proof using the Isabelle theorem prover. [1] Other proofs are also known.
See also
Further reading
 Gödel, K (1929). Über die Vollständigkeit des Logikkalküls. Doctoral dissertation. University Of Vienna.. The first proof of the completeness theorem.
 Gödel, K (1930). "Die Vollständigkeit der Axiome des logischen Funktionenkalküls" (in German). Monatshefte für Mathematik 37 (1): 349–360. doi:10.1007/BF01696781. JFM 56.0046.04. The same material as the dissertation, except with briefer proofs, more succinct explanations, and omitting the lengthy introduction.
External links
 Stanford Encyclopedia of Philosophy: "Kurt Gödel"  by Juliette Kennedy.
 MacTutor biography: Kurt Gödel.
 Detlovs, Vilnis, and Podnieks, Karlis, "Introduction to mathematical logic."
Categories: Mathematical logic
 Theorems in the foundations of mathematics
 Metatheorems
 Model theory
 Proof theory
 Proofs
Wikimedia Foundation. 2010.
Look at other dictionaries:
Original proof of Gödel's completeness theorem — The proof of Gödel s completeness theorem given by Kurt Gödel in his doctoral dissertation of 1929 (and a rewritten version of the dissertation, published as an article in 1930) is not easy to read today; it uses concepts and formalism that are… … Wikipedia
Gödel's theorem — may refer to: *Gödel s incompleteness theorems *Gödel s completeness theorem … Wikipedia
Completeness — In general, an object is complete if nothing needs to be added to it. This notion is made more specific in various fields. Contents 1 Logical completeness 2 Mathematical completeness 3 Computing 4 … Wikipedia
Theorem — The Pythagorean theorem has at least 370 known proofs[1] In mathematics, a theorem is a statement that has been proven on the basis of previously established statements, such as other theorems, and previously accepted statements … Wikipedia
Gödel's incompleteness theorems — In mathematical logic, Gödel s incompleteness theorems, proved by Kurt Gödel in 1931, are two theorems stating inherent limitations of all but the most trivial formal systems for arithmetic of mathematical interest. The theorems are of… … Wikipedia
Gödel, Kurt — born April 28, 1906, Brünn, Austria Hungary died Jan. 14, 1978, Princeton, N.J., U.S. Austrian born U.S. mathematician and logician. He began his career on the faculty of the University of Vienna, where he produced his groundbreaking proof (see… … Universalium
Gödel's theorem(s) — Gödel s first incompleteness theorem states that for any consistent logical system S able to express arithmetic there must exist sentences that are true in the standard interpretation of S, but not provable. Moreover, if S is omega consistent… … Philosophy dictionary
Gödel number — In mathematical logic, a Gödel numbering is a function that assigns to each symbol and well formed formula of some formal language a unique natural number called its Gödel number. The concept was first used by Kurt Gödel for the proof of his… … Wikipedia
Gödel , Kurt — (1906–1978) Austrian–American mathematician Born in Brünn (now Brno in the Czech Republic), Gödel initially studied physics at the University of Vienna, but his interest soon turned to mathematics and mathematical logic. He obtained his PhD in… … Scientists
completeness — Intuitively, a logical system is complete if everything that we want can be derived in it. Thus a formalization of logic is complete if all logically valid forms of argument are derivable in the system; a system designed to codify mathematical… … Philosophy dictionary