How does completeness differ from Goedel's incompleteness theorems?

Completeness is about logical consequence: every sentence true in all models of a theory is provable. Incompleteness is about a specific theory: a sufficiently strong consistent theory has sentences true in its intended model that it cannot prove. The two concern different notions and are not in conflict.

Why is first-order logic the standard choice?

It is expressive enough to formalize most of mathematics yet enjoys completeness and compactness, which fail for stronger logics such as second-order logic. This balance of expressiveness and good metatheoretic properties makes it the default logical framework.

First-Order Logic and Completeness

First-order logic is the formal language of quantified statements about objects and relations, and Goedel's completeness theorem shows that its proof system captures exactly the sentences true in all interpretations.

Definition

First-order logic extends propositional logic with quantifiers ranging over a domain of objects together with relation, function, and constant symbols; the completeness theorem states that a sentence is derivable in its proof system precisely when it is a logical consequence of the assumed axioms.

Scope

This topic covers the syntax of first-order languages, terms, formulas, and sentences, the semantics of structures and satisfaction, the notions of validity and logical consequence, a deductive system for first-order logic, and the soundness and completeness theorems relating provability to truth.

Core questions

What is the precise syntax and semantics of first-order logic?
What does it mean for a sentence to be a logical consequence of a theory?
Why is every valid sentence formally provable?
How does completeness connect the proof system to the class of all models?

Key theories

Soundness theorem: Every sentence derivable in the proof system is true in every model of the premises, so the deductive system never proves false consequences.
Goedel completeness theorem: Conversely, every sentence that holds in all models of a theory is derivable from it, so provability and logical consequence coincide for first-order logic.
Henkin construction: Completeness is proved by building a model directly from a maximal consistent set of sentences with witnesses for existential statements, giving a syntactic recipe for constructing models.

Clinical relevance

First-order logic is the standard framework for formalizing mathematical theories, and completeness guarantees that any semantic truth common to all models can in principle be proved, underpinning automated theorem proving and the foundational adequacy of axiomatic systems.

History

First-order logic emerged from Frege's Begriffsschrift and was isolated as a distinct system by Hilbert and Ackermann. Goedel proved completeness in his 1929 doctoral dissertation, and Henkin's 1949 construction gave the streamlined proof using maximal consistent sets that is standard today.

Key figures

Gottlob Frege
Kurt Goedel
Leon Henkin
Alfred Tarski

Seminal works

enderton2001
marker2002
shoenfield1967

Frequently asked questions

How does completeness differ from Goedel's incompleteness theorems?: Completeness is about logical consequence: every sentence true in all models of a theory is provable. Incompleteness is about a specific theory: a sufficiently strong consistent theory has sentences true in its intended model that it cannot prove. The two concern different notions and are not in conflict.
Why is first-order logic the standard choice?: It is expressive enough to formalize most of mathematics yet enjoys completeness and compactness, which fail for stronger logics such as second-order logic. This balance of expressiveness and good metatheoretic properties makes it the default logical framework.