Gödel proved two incompleteness theorems in 1931 that set hard limits on what formal systems can establish about themselves. They are among the most important results in mathematical logic, and are frequently misapplied — particularly the claim that they apply to propositional logic or Boolean arithmetic.
The Two Theorems
First incompleteness theorem: Any consistent formal system capable of expressing basic arithmetic contains statements that are true but unprovable within the system. It cannot be both complete and consistent.
Second incompleteness theorem: Such a system cannot prove its own consistency. Any proof of consistency would require a strictly more powerful meta-system — which itself cannot prove its consistency, generating infinite regress.
What “Capable of Expressing Basic Arithmetic” Requires
This is the precise condition the theorems turn on. The minimum bar is Robinson arithmetic (Q) — a weak system that requires:
- An infinite domain: the natural numbers 0, 1, 2, 3, …
- A successor function generating each next number
- Addition and multiplication defined over that infinite domain
Why this matters: Gödel’s proof works by Gödel numbering — encoding statements about the formal system itself as natural numbers, then constructing a self-referential sentence (“this statement is unprovable”) within the system. This encoding requires an infinite domain to work. Without natural number arithmetic, there is nowhere to put the encoding.
What the Theorems Do Not Apply To
Propositional logic / Boolean arithmetic is the most common misapplication.
Boolean arithmetic operates on {0, 1} — two elements. Any formula can be evaluated by exhaustive truth-table enumeration. This makes it:
- Decidable — a mechanical procedure settles every formula
- Complete — every tautology is provable (Gödel proved this, in his 1929 completeness theorem, a year before the incompleteness theorems)
The attempt to rescue the claim via “Boolean arithmetic is still arithmetic” fails. Boolean algebra has a finite model. You cannot Gödel-number anything into a two-element set. The diagonal construction that generates the unprovable sentence requires quantification over an infinite domain. Boolean arithmetic simply does not have this.
Related Limits That Do Apply to Propositional Logic
These are distinct from incompleteness but worth knowing alongside it:
Computational complexity: SAT (Boolean satisfiability) is NP-complete — no known polynomial-time algorithm, though always decidable. Hardness is not incompleteness.
Proof complexity: Some propositional tautologies (e.g. the pigeonhole principle) require exponentially long proofs in restricted systems such as resolution. The proof always exists — it is just very long. This is a hardness result within a complete system, not an incompleteness result.
The Theorems That Do Apply Beyond Arithmetic
The incompleteness results generalise to any formal system that can interpret Robinson arithmetic — meaning any system expressive enough to simulate it. This includes:
- Peano arithmetic (PA)
- ZFC set theory
- Any sufficiently expressive type theory
It does not include propositional logic, Boolean algebra, Presburger arithmetic (addition without multiplication — which is decidable and complete), or the theory of real closed fields (also decidable).
Why This Matters
Gödel’s theorems are often invoked to argue that “logic has limits” or “truth exceeds proof” in a general sense. The argument is correct but needs to be stated precisely: the limits apply to systems powerful enough to encode self-reference via arithmetic. Systems below that threshold are complete and decidable. The incompleteness is not a property of formal reasoning as such — it is a property of sufficient expressive power.