Gödel's completeness theorem

Gödel's completeness theorem states that every first-order sentence true in all models is derivable in a standard proof system for first-order logic. Equivalently, semantic consequence in first-order logic coincides with syntactic derivability.

First-order logic: A formal system for reasoning about objects, relations, and quantifiers over a domain. The theorem establishes a correspondence between this logic's semantics and proof rules.
Kurt Gödel: An Austrian logician and mathematician known for foundational results in logic and mathematics. Gödel proved the completeness theorem in his 1929 doctoral dissertation.
First-order structure: A domain together with interpretations of the constants, functions, and predicates of a first-order language. Structures provide the models in which sentences are evaluated for truth.
Model theory: The mathematical study of structures that satisfy formal languages and theories. The theorem lets model-theoretic truth be analyzed through formal derivability.
Semantic entailment: A relation in which a set of sentences semantically entails a sentence when every model of the set satisfies it. Completeness says semantic entailment yields derivability in first-order logic.
Hilbert's program: David Hilbert's project to formalize mathematics and establish its consistency by finitary methods. The theorem answered a central question about the reach of formal proof systems.
Logical validity: A sentence is logically valid when it is true in every structure for its language. Validity is the special case of semantic truth that the theorem turns into provability.
Gödel's completeness theorem for predicate logic: The result that every semantically valid first-order formula is provable in a standard predicate-logic calculus. This formulation expresses the theorem directly as completeness of a logical calculus.
Formal proof: A finite sequence of formulas, each an axiom or derived from earlier formulas by inference rules. The theorem guarantees a formal proof for every sentence valid in all models.
Principia Mathematica: A work by Bertrand Russell and Alfred North Whitehead that sought to derive mathematics from logic. Its formalization efforts exemplified the foundational setting in which completeness mattered.

Linked from 21 pages