Arithmetic with addition alone is complete; add multiplication and Gödel's limits bite
In 1931 Kurt Gödel showed that any consistent, algorithmically listable set of axioms rich enough for ordinary arithmetic leaves some true statements unprovable, and cannot prove its own consistency. Strangely, strip out multiplication and keep only addition, and the resulting system escapes the trap entirely.
Gödel's two incompleteness theorems concern what formal axiom systems can prove. The first says that for any consistent system whose theorems a computer program could in principle list, and which can express basic arithmetic of the natural numbers, there are true arithmetical statements it cannot prove. The second says such a system cannot demonstrate its own consistency. Together they are widely read as ending David Hilbert's hope of finding a complete, consistent set of axioms for all of mathematics.
The conditions are all essential. A system can be complete, consistent and effectively axiomatised, but not all three if it handles enough arithmetic. True arithmetic, the collection of every true statement about the integers, is consistent and complete but has no algorithmically listable axioms. Taking every sentence as an axiom yields completeness at the cost of consistency, since an inconsistent system proves everything. Presburger arithmetic, with addition but no multiplication, is complete and consistent, as are the theory of algebraically closed fields and Tarski's version of Euclidean geometry, because none of them can encode full integer arithmetic.
Consistency proofs have to come from outside. Peano arithmetic, which appears consistent, can be proved consistent within the stronger Zermelo–Fraenkel set theory with choice, but not within itself. ZFC in turn can be proved consistent by adding an axiom asserting an inaccessible cardinal, and that enlarged system cannot prove its own consistency either. The continuum hypothesis shows ZFC is incomplete, with no obvious new axiom to settle it. Dan Willard has studied weak systems that avoid multiplication as a function and can verify their own consistency.
Gödel used a diagonal argument, and his results opened a series of related limits: Alfred Tarski's theorem that truth cannot be formally defined within such a system, Alonzo Church's proof that Hilbert's decision problem is unsolvable, and Alan Turing's proof that no algorithm can solve the halting problem. The theorems concern formal provability inside systems, not informal ideas of proof.
Source: Gödel's incompleteness theorems
