A topic in the Open Knowledge Graph — a free, open map of 15,290 topics and the order to learn them in.
Gödel's First Incompleteness Theorem (1931) states that any consistent formal system T extending Peano Arithmetic is incomplete: there exists a sentence G that is true (in the standard model) but neither provable nor disprovable in T. The proof uses Gödel numbering to encode the statement 'this sentence is not provable in T' as an arithmetic formula. The Second Incompleteness Theorem states that such a system T cannot prove its own consistency — Con(T) is unprovable in T. These results shattered Hilbert's program of finding a complete, consistent, decidable foundation for all mathematics.
Understand the diagonal lemma (fixed-point lemma) first: every formula φ(x) has a sentence G such that T proves G ↔ φ(⌜G⌝). Then apply it with φ(x) = 'x is not provable in T'. Separate the philosophical implications from the precise mathematical statement.
Gödel's incompleteness theorems are among the most profound results in mathematics, and among the most frequently misunderstood. Stated loosely, they say that no sufficiently powerful formal system can be both complete (proves all truths) and consistent (proves no contradictions). But the precise mathematical content is more specific — and requires the machinery of formal arithmetic, representability, and Gödel numbering that you have already studied.
The proof of the First Incompleteness Theorem turns on what is now called the *diagonal lemma* (or fixed-point lemma): for any formula φ(x) in the language of arithmetic, there exists a sentence G such that T proves G ↔ φ(⌜G⌝), where ⌜G⌝ is the Gödel number of G. In other words, G is a sentence that talks about itself via its own code. Apply this with φ(x) = "x is not provable in T" — a formula that is expressible in arithmetic because provability is a primitive recursive relation. You obtain a sentence G that says, in effect, "I am not provable in T." If T proves G, then G is false (it said it was unprovable), making T inconsistent. If T proves ¬G, then T asserts that G is provable, but then G would actually be provable — another contradiction. So in any consistent T, G is undecidable.
The sentence G is actually *true* in the standard model of arithmetic. The standard natural numbers contain no nonstandard proofs; G is either provable or not, and since T cannot prove it, G is simply true but beyond T's reach. This is the gap between semantic truth (true in the intended model) and syntactic provability (derivable from the axioms). Incompleteness is exactly this gap: there are sentences that are true but not provable.
The Second Incompleteness Theorem extends this. The sentence Con(T) — "T does not derive a contradiction" — can be expressed in arithmetic. A careful formalization shows that T itself proves the conditional "if Con(T), then G is not provable in T." Since T cannot prove G (first theorem), it follows that T cannot prove Con(T) either. Any proof of T's own consistency inside T would thus be circular in a deep sense — the theorem says no such proof can exist. This result devastated Hilbert's program, which aimed to secure all of mathematics by proving consistency from within the formal system itself.
What the theorems do NOT say is equally important. They do not say mathematics is inconsistent or that truth is unknowable. The Gödel sentence is a logically artificial construction; the overwhelming majority of mathematical questions are decidable in standard theories. Very weak systems, like Presburger arithmetic (addition but no multiplication), escape incompleteness entirely — they are complete and decidable. The theorems bite precisely when a system is strong enough to represent primitive recursive functions, which is the minimum needed to encode its own provability predicate.