How Gödel’s Proof Works
Author: Natalie Wolchover
Publication date: July 14, 2020
Publisher:Quanta Magazine
The article explains the central idea behind Kurt Gödel’s incompleteness theorems, which overturned the hope that mathematics could be based on a single axiomatic system that was both completely consistent and capable of proving every mathematical truth. Gödel showed that any sufficiently expressive, consistent formal system capable of arithmetic must contain statements that are true but cannot be proved within that system. Moreover, such a system cannot establish its own consistency using only its internal rules.
The key technical device is Gödel numbering. Gödel assigns numbers to mathematical symbols and then encodes entire formulas as unique integers using prime factorization. For example, a sequence of symbols with codes $a_1,a_2,\ldots,a_n$ can essentially be represented by a number of the form
$2a13a25a3⋯pnan.2^{a_1}3^{a_2}5^{a_3}\cdots p_n^{a_n}$.
Because prime factorization is unique, the original mathematical expression can be reconstructed from its number. Gödel extended this idea to entire proofs, allowing statements about formulas and proofs—metamathematical statements—to be translated into ordinary statements about integers. Mathematics thereby acquires a way of talking about its own syntax and provability.
Gödel then uses a sophisticated self-reference construction to produce a sentence $G$ that effectively says “$G$ is not provable in this system.” If the system could prove $G$, then $G$ would be false, contradicting consistency. Therefore, assuming the system is consistent, $G$ cannot be proved; but that makes what $G$ says true. Thus there exists a true but unprovable statement, so the system is incomplete. Adding $G$ as a new axiom does not solve the problem permanently: the enlarged system allows another Gödel-type sentence to be constructed. This establishes a permanent gap between mathematical truth and formal provability.
Key takeaways
Central idea: Gödel did not show that mathematics is unreliable; he showed that formal axiomatic methods have intrinsic limits. There will always be mathematical truths lying beyond what any one sufficiently powerful consistent formal system can prove.
ARTICLE / ARTICLE [PDF]
Author: Natalie Wolchover
Publication date: July 14, 2020
Publisher:Quanta Magazine
The article explains the central idea behind Kurt Gödel’s incompleteness theorems, which overturned the hope that mathematics could be based on a single axiomatic system that was both completely consistent and capable of proving every mathematical truth. Gödel showed that any sufficiently expressive, consistent formal system capable of arithmetic must contain statements that are true but cannot be proved within that system. Moreover, such a system cannot establish its own consistency using only its internal rules.
The key technical device is Gödel numbering. Gödel assigns numbers to mathematical symbols and then encodes entire formulas as unique integers using prime factorization. For example, a sequence of symbols with codes $a_1,a_2,\ldots,a_n$ can essentially be represented by a number of the form
$2a13a25a3⋯pnan.2^{a_1}3^{a_2}5^{a_3}\cdots p_n^{a_n}$.
Because prime factorization is unique, the original mathematical expression can be reconstructed from its number. Gödel extended this idea to entire proofs, allowing statements about formulas and proofs—metamathematical statements—to be translated into ordinary statements about integers. Mathematics thereby acquires a way of talking about its own syntax and provability.
Gödel then uses a sophisticated self-reference construction to produce a sentence $G$ that effectively says “$G$ is not provable in this system.” If the system could prove $G$, then $G$ would be false, contradicting consistency. Therefore, assuming the system is consistent, $G$ cannot be proved; but that makes what $G$ says true. Thus there exists a true but unprovable statement, so the system is incomplete. Adding $G$ as a new axiom does not solve the problem permanently: the enlarged system allows another Gödel-type sentence to be constructed. This establishes a permanent gap between mathematical truth and formal provability.
Key takeaways
- Gödel numbering turns formulas and proofs into integers, letting arithmetic encode statements about mathematics itself.
- Gödel constructs a self-referential sentence $G$ asserting its own unprovability.
- A sufficiently powerful consistent axiomatic system therefore cannot be both consistent and complete.
- Gödel’s second incompleteness theorem shows that such a system cannot, in the relevant formal sense, prove its own consistency.
Central idea: Gödel did not show that mathematics is unreliable; he showed that formal axiomatic methods have intrinsic limits. There will always be mathematical truths lying beyond what any one sufficiently powerful consistent formal system can prove.
ARTICLE / ARTICLE [PDF]
┌────────────────────────────────┐
│ KONSTANTINOS MICHAILIDIS │
└────────────────────────────────┘
│ KONSTANTINOS MICHAILIDIS │
└────────────────────────────────┘