Gödel's incompleteness theorems Gödel's incompleteness theorems is the name given to two theorems (true mathematical statements), proved by Kurt Gödel in 1931. They are theorems in mathematical logic. Mathematicians once thought that everything that is true has a mathematical proof. A system that has this property is called complete; one that does not is called incomplete. Also, mathematical ideas should not have contradictions. This means that they should not be true and false at the same time. A system that does not include contradictions is called consistent. A system is a collection of theorems (logical consequences) based on axioms (basic assumptions). Axioms are statements that are accepted as true, and need no proof. Gödel said that every non-trivial formal system (consistent and axiomatic system with theorems listable by following an algorithm) is incomplete and not provably consistent:[1][2] - There will always be questions that cannot be answered, using a certain set of axioms; there are truths that cannot be proved using the axioms of the system. - You cannot prove that a system of axioms is consistent according to the axioms of the system. They were followed by Tarski's undefinability theorem on the formal undefinability of truth, Church's proof that Hilbert's Entscheidungsproblem is unsolvable, and Turing's theorem that there is no algorithm to solve the halting problem. == Formal systems == The incompleteness theorems apply to formal systems that are of sufficient complexity to express the basic arithmetic of the natural numbers and which are consistent and effectively axiomatized. Particularly in the context of first-order logic, formal systems are also called formal theories. A system is ω-consistent if it is not ω-inconsistent, and is ω-inconsistent if there is a predicate P such that for every specific natural number m the system proves ~P(m), and yet the system also proves that there exists a natural number n such that P(n). That is, the system says that a number with property P exists while denying that it has any specific value. The ω-consistency of a system implies its consistency, but consistency does not imply ω-consistency. J. Barkley Rosser (1936) strengthened the incompleteness theorem by finding a variation of the proof (Rosser's trick) that only requires the system to be consistent, rather than ω-consistent. Chaitin's incompleteness theorem states that for any system that can represent enough arithmetic, there is an upper bound c such that no specific number can be proved in that system to have Kolmogorov complexity greater than c. While Gödel's theorem is related to the liar paradox, Chaitin's result is related to Berry's paradox. === Undecidable statements provable in larger systems === These are natural mathematical equivalents of the Gödel "true but undecidable" sentence. They can be proved in a larger system which is generally accepted as a valid form of reasoning, but are undecidable in a more limited system such as Peano Arithmetic. which means that the formula Bew(x) is now different. Thus when we apply the diagonal lemma to this new Bew, we obtain a new statement p, different from the previous one, which will be undecidable in the new system if it is ω-consistent. === Proof via Berry's paradox === Boolos (1989) sketches an alternative proof of the first incompleteness theorem that uses Berry's paradox rather than the liar paradox to construct a true but unprovable formula. A similar proof method was independently discovered by Saul Kripke. Boolos's proof proceeds by constructing, for any computably enumerable set S of true sentences of arithmetic, another sentence which is true but not contained in S. Computer-verified proofs of versions of the first incompleteness theorem were announced by Natarajan After the publication of the incompleteness theorems showed that Ackermann's modified proof must be erroneous, von Neumann produced a concrete example showing that its main technique was unsound. In the course of his research, Gödel discovered that, although a sentence asserting its falsehood leads to paradox, a sentence that asserts its non-provability does not. In particular, Gödel was aware of the result later called Tarski's indefinability theorem, although he never published it. Cambridge, U.K.: Cambridge University Press. ISBN 978-0-521-67453-9. MR 2384958. Archived from the original on 2005-10-23. Retrieved 2005-10-29. Shankar, N. (1994). Metamathematics, machines, and Gödel's proof. Cambridge tracts in theoretical computer science. Vol. 38. Cambridge: Cambridge University Press. ISBN 0-521-58533-3. Raymond Smullyan, 1987. Forever Undecided ISBN 0192801414 - puzzles based on undecidability in formal systems —, 1992. Godel's Incompleteness Theorems. Oxford Univ. Press. ISBN 0195046722 —, 1994. Diagonalization and Self-Reference. Oxford Univ. Press. MR 1318913. ISBN 0198534507 —, 2013. The Godelian Puzzle Book: Puzzles, Paradoxes and Proofs. Courier Corporation. S2CID 15610367. Paulson, Lawrence (2014). "A machine-assisted proof of Gödel's incompleteness theorems for the theory of hereditarily finite sets". Review of Symbolic Logic. 7 (3): 484–498. arXiv:2104.14260. doi:10.1017/S1755020314000112. S2CID 13913592. Priest, Graham (1984). "Logic of Paradox Revisited". Journal of Philosophical Logic. 13 (2): 153–179. doi:10.1007/BF00453020. Priest, Graham (2004). "Wittgenstein's Remarks on Gödel's Theorem". In Max Kölbel (ed.). Wittgenstein's lasting significance. Psychology Press. pp. 207–227. ISBN 978-1-134-40617-3. Priest, Graham (2006). In Contradiction: A Study of the Transconsistent. Oxford University Press. ISBN 0-19-926329-9. October 2011 RadioLab episode about/including Gödel's Incompleteness theorem "Gödel incompleteness theorem", Encyclopedia of Mathematics, EMS Press, 2001 [1994] How Gödel's Proof Works by Natalie Wolchover, Quanta Magazine, July 14, 2020. [1] and [2] Gödel's incompleteness theorems formalised in Isabelle/HOL