Takeaway

Any sufficiently strong, consistent formal system cannot prove all true statements about arithmetic (first theorem) and cannot prove its own consistency (second theorem).

The problem (before → after)

  • Before: Hilbert’s program sought complete, consistent, finitely checkable foundations for all mathematics.
  • After: Gödel shows inherent limits: truth outstrips provability; consistency cannot be proven from within.

Mental model first

It’s a legal code that cannot fully adjudicate all cases about numbers because you can construct a case that says, “This statement has no legal proof.” If the code is consistent, that case is true but unprovable.

Just-in-time concepts

  • Arithmetization of syntax: Encode statements and proofs as numbers (Gödel numbering).
  • Diagonalization: Construct self-referential sentences via fixed-point (the “this sentence is unprovable” trick).
  • Ω-consistency vs consistency: Technical conditions ensuring no contradictions.

First-pass solution

Build a sentence G that asserts its own unprovability. If the system proves G, it proves a falsehood (inconsistency). If it proves ¬G, it proves that G has a proof, contradicting consistency. Hence, if consistent, the system proves neither: it’s incomplete.

Iterative refinement

  1. Rosser’s improvement weakens assumptions to plain consistency.
  2. Second theorem: Formalize “the system is consistent” and show it unprovable if the system is consistent.
  3. Scope: Applies to any system interpreting a fragment of arithmetic (e.g., PA).

Principles, not prescriptions

  • Self-reference via arithmetic encoding exposes system limits.
  • Completeness in logic (Gödel’s completeness theorem) does not imply completeness in arithmetic truth.

Common pitfalls

  • Confusing semantic truth with syntactic provability.
  • Overextending to everyday reasoning without care.

Connections and contrasts

  • See also: [/blog/halting-problem-undecidability], [/blog/p-vs-np-problem], [/blog/cantors-diagonal-argument].

Quick checks

  1. Why “sufficiently strong”? — Needs to express basic arithmetic.
  2. Does this refute all formal systems? — No, but any that capture arithmetic face incompleteness.
  3. Can a stronger system prove consistency of a weaker one? — Yes (relative consistency).

Further reading

  • Gödel’s original paper; Nagel & Newman, “Gödel’s Proof”