Gödel's Incompleteness Theorems: What They Prove
Gödel's incompleteness theorems show that no consistent formal system for basic arithmetic can prove every truth about numbers, or prove its own consistency.
Gödel's incompleteness theorems are two results about formal systems of mathematics, published by the logician Kurt Gödel in 1931. The first says that any consistent set of axioms rich enough to express basic arithmetic contains a true statement that it cannot prove. The second says that such a system cannot prove its own consistency. Together they set a firm limit on what any fixed set of axioms can capture.
What is a formal system?
A formal system is a precise game with written rules. It has a set of symbols, rules that decide which strings of symbols count as well-formed statements, a list of axioms (statements accepted without proof), and rules of inference that turn accepted statements into new ones. A proof is a finite chain of statements in which each step is an axiom or follows from earlier steps by a rule, such as modus ponens.
Axioms can be changed. The parallel postulate of Euclid's geometry is one axiom, and replacing it produced non-Euclidean geometry.
Peano arithmetic is the standard example for this topic. Its axioms describe zero, the successor of a number and mathematical induction. They are enough to express facts such as the fundamental theorem of arithmetic.
A system is consistent if it never proves both a statement and its negation. It is complete if, for every statement it can express, it proves either the statement or its negation.
What does the first theorem say?
Gödel showed that a consistent formal system of this kind, whose axioms can be listed by a definite procedure, is incomplete. Some sentence in its language can be neither proved nor refuted.
The key sentence is often called the Gödel sentence. In plain words it says: "this statement cannot be proved in this system." If the system is consistent, the sentence is true but unprovable. Its negation is then unprovable too, so the system leaves the question open.
Gödel's 1931 paper needed a slightly stronger assumption than consistency. J. Barkley Rosser removed it in 1936, so plain consistency is enough today.
How did Gödel prove it?
Gödel gave every symbol, formula and proof a unique natural number, a method now called Gödel numbering. Statements about proofs then become statements about numbers, and arithmetic can express statements about numbers. The Gödel sentence is built with a diagonal argument, the same kind of construction Georg Cantor used to show that the real numbers cannot be listed.
The table summarises the three statements that matter.
| Statement | Provable, if the system is consistent? | What it shows |
|---|---|---|
| The Gödel sentence | No | It is true but cannot be proved |
| The negation of the Gödel sentence | No | The system leaves the sentence undecided |
| The statement that the system is consistent | No | Consistency needs assumptions from outside |
What does the second theorem add?
The second theorem applies the first to the system's own consistency. A consistent system strong enough for arithmetic cannot prove the arithmetical sentence that says it is consistent. To establish consistency, a mathematician must use a stronger system or different methods, and those raise the same question again.
This was a blow to David Hilbert's programme. Hilbert had hoped to prove that mathematics was consistent using simple, finite methods that everyone would accept. Gödel showed that arithmetic's consistency cannot be proved within arithmetic itself, so that goal could not be reached in the form Hilbert intended.
Do the theorems mean mathematics is unreliable?
No. They do not say that mathematics is broken or that most questions are unanswerable. The Gödel sentence is an artificial statement built for the proof, and working mathematicians prove theorems every day. The results also apply only to systems whose axioms form a definite, mechanically listable set.
Some writers have argued from the theorems that human minds cannot be machines. That argument is contested, and the theorems themselves do not establish it.
The same diagonal idea appears in Alan Turing's 1936 proof that no general algorithm can decide whether every program halts. It also lies behind questions about which problems computers can solve efficiently, covered in P vs NP.
Tags
axioms computation formal systems logic mathematics
Related articles
- Non-Euclidean Geometry
- What Is Linear Regression? How Least Squares Works
- The Fibonacci Sequence and the Golden Ratio Explained
- P vs NP
- Game Theory
- Quantum Computing