Original proof of Gödel's completeness theorem

1925 kurt gödel (cropped)

Gödel's completeness theorem is a fundamental theorem in mathematical logic that was proven by Kurt Gödel in 1930. The theorem is significant in the field of logic and philosophy of mathematics, as it addresses the capability of formal systems to adequately capture all truths about a mathematical structure. Gödel's completeness theorem specifically pertains to first-order logic, a system of logic that includes quantifiers and variables that can stand for objects in a domain.

Statement of the Theorem

The theorem can be stated as follows: For any given set of axioms in first-order logic, if a statement is true in every model that satisfies the axioms, then there exists a proof of the statement from the axioms. In simpler terms, the theorem asserts that if a statement is logically entailed by the axioms (i.e., it holds under all interpretations that make the axioms true), then it can be proven from those axioms using the rules of first-order logic.

Historical Context

Kurt Gödel announced his completeness theorem in 1930, fundamentally altering the understanding of the scope and limits of formal systems. This theorem, along with his later Gödel's incompleteness theorems, which demonstrate inherent limitations in formal systems, constitutes some of the most important work in 20th-century logic.

Proof Overview

Gödel's original proof of the completeness theorem introduced several innovative techniques and concepts. One key idea is the construction of a canonical model or a term model, built directly from the syntactic objects of the theory itself. Gödel showed that if a statement cannot be proven from a set of axioms, then it is possible to construct a model of the axioms in which the statement is false. This construction involves extending the language of the theory to include constants for each class of equivalent terms and then showing that this extended language can be interpreted in such a way that all the axioms are satisfied but the statement in question is not.

Significance

The completeness theorem has profound implications for the philosophy of mathematics and the foundations of logic. It ensures that first-order logic is a powerful enough system to capture all logical truths about mathematical structures defined by axioms within its scope. However, Gödel's later incompleteness theorems show that for any sufficiently rich formal system that can encode a certain amount of arithmetic, there are true statements about the natural numbers that cannot be proven within that system.

See Also

• First-order logic
• Gödel's incompleteness theorems
• Model theory
• Proof theory