Gödel's incompleteness theorems

E71396

mathematical theorem metamathematical theorem result in mathematical logic

Gödel's incompleteness theorems are two fundamental results in mathematical logic showing that any sufficiently powerful, consistent formal system cannot prove all true statements about arithmetic, and cannot prove its own consistency.

Aliases (6)

Statements (49)

Predicate	Object
instanceOf	mathematical theorem → metamathematical theorem → result in mathematical logic →
appliesTo	Peano arithmetic → Zermelo–Fraenkel set theory with Choice → effectively axiomatized theories → formal axiomatic systems → recursively axiomatizable theories → sufficiently strong theories of arithmetic →
assumes	ω-consistency in Gödel's original proof of the first theorem →
author	Kurt Gödel →
concerns	provability in formal systems → truth in arithmetic →
field	foundations of mathematics → mathematical logic → metamathematics → proof theory →
firstTheoremStates	any consistent, effectively axiomatized theory capable of expressing elementary arithmetic is incomplete →
hasPart	Gödel's first incompleteness theorem → Gödel's second incompleteness theorem →
implies	a sufficiently strong consistent theory cannot prove its own consistency → existence of true but unprovable statements → limitations of Hilbert's program → no complete and consistent extension of Peano arithmetic is recursively axiomatizable →
influenced	philosophy of logic → philosophy of mathematics → proof theory → theory of computation →
laterGeneralizedBy	results using only simple consistency instead of ω-consistency →
namedAfter	Kurt Gödel →
originalLanguage	German →
publishedIn	Monatshefte für Mathematik →
relatedTo	Church–Turing thesis → Gödel numbering → Hilbert's program → Löb's theorem → Peano arithmetic → Tarski's undefinability theorem →
requires	ability to represent basic arithmetic → consistency of the formal system → effective axiomatization →
secondTheoremStates	no consistent, effectively axiomatized theory capable of expressing elementary arithmetic can prove its own consistency →
showsLimitationOf	axiomatic method for arithmetic → formalism in mathematics →
status	proven →
usesMethod	arithmetization of syntax → diagonalization → self-referential sentences →
yearProved	1931 →

Referenced by (14)

Subject (surface form when different)	Predicate
Berry paradox ("Gödel’s incompleteness theorems") → Church–Turing thesis ("Gödel’s incompleteness theorems") → Epimenides paradox ("Gödel incompleteness theorems") → On Computable Numbers, with an Application to the Entscheidungsproblem ("Gödel’s incompleteness theorems") → Tarski's undefinability theorem → liar paradox →	relatedTo
Gödel's incompleteness theorems ("Gödel's first incompleteness theorem") → Gödel's incompleteness theorems ("Gödel's second incompleteness theorem") →	hasPart
Kurt Gödel → Raymond Smullyan ("Gödel’s Incompleteness Theorems") →	notableWork
Hilbert’s program ("Gödel’s incompleteness theorems") →	challengedBy
ZF ("Gödel incompleteness theorems") →	isIncompletenessSubjectTo
Kurt Gödel ("incompleteness theorems") →	knownFor
Gödel, Escher, Bach →	subject