incompleteness theorem
Godel's results showing that any sufficiently powerful consistent formal system contains true statements it cannot prove, and cannot prove its own consistency.
As defined in 282 | Joel David Hamkins on Puzzles of Reality and Infinity
Where it comes up · 4
- Joel David Hamkins3 claims
- 282 | Joel David Hamkins on Puzzles of Reality and Infinity3 claims
- Janna Levin2 claims
- Conversations with Tyler - Terence Tao1 claim
Most important claims · 9 of 9Search all claims for “incompleteness theorem” →
- By Godel's second incompleteness theorem no theory can prove its own consistency, so if Peano arithmetic is consistent then the theory PA plus the axiom asserting PA is inconsistent (PA + ¬Con(PA)) is itself a consistent theory — even though it appears incoherent in asserting a theory while also asserting that theory's inconsistency.282 | Joel David Hamkins on Puzzles of Reality and Infinity
- Gödel's incompleteness theorem showed that no fixed set of rules of mathematics can settle every statement, so Hilbert's dream of solving all open problems can never be finished, though the undecidable statements Gödel built are rarely ones that arise in practice.Conversations with Tyler - Terence Tao
- Gödel's two incompleteness theorems decisively refute Hilbert's program: the first shows no computably axiomatizable theory containing enough arithmetic can answer all questions (every such consistent theory is incomplete), and the second shows no such theory can prove its own consistency.Joel David Hamkins
- A theory proving its own consistency gives no real reason to believe it is consistent, because even an inconsistent theory would prove its own consistency—like a used car salesman telling you he is trustworthy, the statement provides no logical grounds for trust.Joel David Hamkins
- Gödel's incompleteness theorem follows immediately from the undecidability of the halting problem without needing the Gödel sentence: a complete computable axiomatization of elementary mathematics would let a theorem-enumeration machine solve the halting problem by waiting for either the halt or non-halt statement, which is impossible.Joel David Hamkins
- A simplified version of Godel's incompleteness theorem states that there is no computably axiomatizable theory of arithmetic that is true and proves all and only the true statements of arithmetic; this follows from the undecidability of the halting problem, because such a complete true theory would let us decide halting by searching for proofs that a program halts or not, contradicting Turing's 1936 result.282 | Joel David Hamkins on Puzzles of Reality and Infinity
- Godel's incompleteness result overturned the universal belief (held by Hilbert and the great mathematicians) that any mathematical truth could in principle be proven, by demonstrating that there exist facts even among the numbers that are true yet can never be proven to be true — essentially showing there is no theory of everything for mathematics.Janna Levin
- Godel refuted Hilbert's picture by showing not only that the finitary theory cannot prove the consistency of the strong infinitary theory, but that it cannot even prove the consistency of itself.282 | Joel David Hamkins on Puzzles of Reality and Infinity
- Levin tied Turing and Godel together because, beyond their connected work, there is a fundamental impossibility of fully understanding or proving things about their lives — even a factual biography leaves something that eludes you — structurally mirroring the mathematical themes of incompleteness, undecidability, and uncomputability they discovered, about what we can believe to be true but can never really know.Janna Levin