Gödel's incompleteness theorems: The proof that broke mathematics | Joel David Hamkins

Quick Overview

Gödel's incompleteness theorems decisively refute Hilbert's program by proving that no computably axiomatized theory strong enough to encompass elementary arithmetic can be both complete (answering all questions) and consistent, and furthermore, no such theory can prove its own consistency.

Key Points: Gödel's first incompleteness theorem states that one cannot write down a computably axiomatized theory that answers all the questions, meaning every such theory strong enough to include arithmetic will be incomplete if consistent. The second incompleteness theorem states that no such theory can ever prove its own consistency, which is a decisive takedown of Hilbert's goal to prove the safety of strong set theory using finitary means. Hilbert's program aimed to secure all of classical mathematics on a finitary foundation, intending to use a weak, purely finitary theory to prove the consistency of a strong, infinitary theory (like set theory) that could answer all mathematical questions. The speaker contrasts mathematical truth, defined by Tarski's disquotational theory (truth is the content of the sentence being the case), with proof, which is a syntactic sequence of assertions conforming to logical rules like modus ponent. The undecidability of the halting problem, proven via a diagonal argument, is used as the simplest proof of Gödel's theorem: if a complete theory of elementary mathematics existed, it could solve the halting problem, which is impossible. The speaker notes that before Gödel, people were often sloppy conflating truth and proof, but the theorems reveal that provability is equivalent to logical consequence (due to earlier completeness theorems), and the general provability problem is undecidable, equivalent to the halting problem.

Context: The discussion centers on explaining Gödel's incompleteness theorems in the context of Hilbert's program, an early 20th-century project to establish a completely secure finitary foundation for all of classical mathematics, addressing paradoxes like Russell's paradox that arose in set theory. Hilbert sought a strong theory capable of answering all questions, which he wished to prove consistent using only purely finitary, formalist reasoning about finite sequences of symbols.