Gödel's Incompleteness

Self-reference plus arithmetization yields a true sentence that proves nothing.

The idea

Theorem (Gödel's first incompleteness theorem).

Let $S$ be a consistent formal system whose axioms can be listed by an algorithm and which proves enough elementary arithmetic. Then $S$ is incomplete: there is a sentence of arithmetic that $S$ can neither prove nor refute, and it is true.

The theorem separates provability from truth. Provability is syntactic: a sentence is provable in $S$ when some finite list of formulas, each an axiom or derived from earlier ones by a rule, ends in it. Truth is semantic: a sentence of arithmetic is true when the natural numbers satisfy it. For any system meeting the hypotheses, the provable sentences cannot be exactly the true ones. The figure shows this as regions: the provable sentences sit strictly inside the true ones, and the Gödel sentence $G$ built below lies in the gap.

Ways to work on it

• Walkthrough. The construction of the self-referential sentence and what it implies, with a concept check at each turn.
• Practice. Multiple-choice questions on truth versus provability and the two incompleteness theorems.
• Hardest. Reconstruct Gödel's incompleteness argument step by step.

Not sure where to start? Take the ten-question placement test.