https://www.quantamagazine.org/how-godels-proof-works-20200714/ We care about your data, and we'd like to use cookies to give you a smooth browsing experience. Please agree and read more about our privacy policy.Agree * Physics * Mathematics * Biology * Computer Science * Topics * Archive * * * * How Godel's Proof Works Read Later Share Copied! * Comments * Read Later Read Later Abstractions blog How Godel's Proof Works By Natalie Wolchover July 14, 2020 His incompleteness theorems destroyed the search for a mathematical theory of everything. Nearly a century later, we're still coming to grips with the consequences. Read Later Godel's incompleteness theorems. Every mathematical system will have some statements that can never be proved. Olena Shmahalo/Quanta Magazine Natalie Wolchover By Natalie Wolchover Senior Editor --------------------------------------------------------------------- July 14, 2020 --------------------------------------------------------------------- View PDF/Print Mode Abstractions blogcontinuum hypothesisexplainersfoundations of mathematicsmathematicsproofsset theoryAll topics Click to take Quanta's 10-minute reader survey.Click to take Quanta's 10-minute reader survey. Introduction In 1931, the Austrian logician Kurt Godel pulled off arguably one of the most stunning intellectual achievements in history. Mathematicians of the era sought a solid foundation for mathematics: a set of basic mathematical facts, or axioms, that was both consistent -- never leading to contradictions -- and complete, serving as the building blocks of all mathematical truths. But Godel's shocking incompleteness theorems, published when he was just 25, crushed that dream. He proved that any set of axioms you could posit as a possible foundation for math will inevitably be incomplete; there will always be true facts about numbers that cannot be proved by those axioms. He also showed that no candidate set of axioms can ever prove its own consistency. His incompleteness theorems meant there can be no mathematical theory of everything, no unification of what's provable and what's true. What mathematicians can prove depends on their starting assumptions, not on any fundamental ground truth from which all answers spring. In the 89 years since Godel's discovery, mathematicians have stumbled upon just the kinds of unanswerable questions his theorems foretold. For example, Godel himself helped establish that the continuum hypothesis, which concerns the sizes of infinity, is undecidable, as is the halting problem, which asks whether a computer program fed with a random input will run forever or eventually halt. Undecidable questions have even arisen in physics, suggesting that Godelian incompleteness afflicts not just math, but -- in some ill-understood way -- reality. Here's a simplified, informal rundown of how Godel proved his theorems. Godel Numbering Godel's main maneuver was to map statements about a system of axioms onto statements within the system -- that is, onto statements about numbers. This mapping allows a system of axioms to talk cogently about itself. The first step in this process is to map any possible mathematical statement, or series of statements, to a unique number called a Godel number. The slightly modified version of Godel's scheme presented by Ernest Nagel and James Newman in their 1958 book, Godel's Proof, begins with 12 elementary symbols that serve as the vocabulary for expressing a set of basic axioms. For example, the statement that something exists can be expressed by the symbol [?], while addition is expressed by +. Importantly, the symbol s, denoting "successor of," gives a way of specifying numbers; ss0, for example, refers to 2. These twelve symbols then get assigned the Godel numbers 1 through 12. Constant sign Godel number Usual Meaning ~ 1 not [?] 2 or [?] 3 if...then... [?] 4 there is an... = 5 equals 0 6 zero s 7 the successor of ( 8 punctuation mark ) 9 punctuation mark , 10 punctuation mark + 11 plus x 12 times Next, letters representing variables, starting with x, y and z, map onto prime numbers greater than 12 (that is, 13, 17, 19, ...). Then any combination of these symbols and variables -- that is, any arithmetical formula or sequence of formulas that can be constructed -- gets its own Godel number. For example, consider 0 = 0. The formula's three symbols correspond to Godel numbers 6, 5 and 6. Godel needs to change this three-number sequence into a single, unique number -- a number that no other sequence of symbols will generate. To do this, he takes the first three primes (2, 3 and 5), raises each to the Godel number of the symbol in the same position in the sequence, and multiplies them together. Thus 0 = 0 becomes 2^6 x 3^5 x 5^6, or 243,000,000. The mapping works because no two formulas will ever end up with the same Godel number. Godel numbers are integers, and integers only factor into primes in a single way. So the only prime factorization of 243,000,000 is 2^6 x 3^5 x 5^6, meaning there's only one possible way to decode the Godel number: the formula 0 = 0. Godel then went one step further. A mathematical proof consists of a sequence of formulas. So Godel gave every sequence of formulas a unique Godel number too. In this case, he starts with the list of prime numbers as before -- 2, 3, 5 and so on. He then raises each prime to the Godel number of the formula at the same position in the sequence (2^243,000,000 x ..., if 0 = 0 comes first, for example) and multiplies everything together. Arithmetizing Metamathematics The real boon is that even statements about arithmetic formulas, called metamathematical statements, can themselves be translated into formulas with Godel numbers of their own. First consider the formula ~(0 = 0), meaning "zero does not equal zero." This formula is clearly false. Nevertheless, it has a Godel number: 2 raised to the power of 1 (the Godel number of the symbol ~), multiplied by 3 raised to the power of 8 (the Godel number of the "open parenthesis" symbol), and so on, yielding 21 x 3^8 x 5^6 x 7^ 5 x 11^6 x 13^9. Because we can generate Godel numbers for all formulas, even false ones, we can talk sensibly about these formulas by talking about their Godel numbers. Consider the statement, "The first symbol of the formula ~(0 = 0) is a tilde." This (true) metamathematical statement about ~(0 = 0) translates into a statement about the formula's Godel number -- namely, that its first exponent is 1, the Godel number for a tilde. In other words, our statement says that 21 x 3^8 x 5^6 x 7^5 x 11^6 x 13^9 has only a single factor of 2. Had ~(0 = 0) begun with any symbol other than a tilde, its Godel number would have at least two factors of 2. So, more precisely, 2 is a factor of 21 x 3^8 x 5^6 x 7 ^5 x 11^6 x 13^9, but 2^2 is not a factor. We can convert the last sentence into a precise arithmetical formula that we can write down^* using elementary symbols. This formula of course has a Godel number, which we could calculate by mapping its symbols onto powers of primes. This example, Nagel and Newman wrote, "exemplifies a very general and deep insight that lies at the heart of Godel's discovery: typographical properties of long chains of symbols can be talked about in an indirect but perfectly accurate manner by instead talking about the properties of prime factorizations of large integers." Conversion into symbols is also possible for the metamathematical statement, "There exists some sequence of formulas with Godel number x that proves the formula with Godel number k" -- or, in short, "The formula with Godel number k can be proved." The ability to "arithmetize" this kind of statement set the stage for the coup. G Itself Godel's extra insight was that he could substitute a formula's own Godel number in the formula itself, leading to no end of trouble. To see how substitution works, consider the formula ([?]x)(x = sy). (It reads, "There exists some variable x that is the successor of y," or, in short, "y has a successor.") Like all formulas, it has a Godel number -- some large integer we'll just call m. Now let's introduce m into the formula in place of the symbol y. This forms a new formula, ([?]x)(x = sm), meaning, "m has a successor." What shall we call this formula's Godel number? There are three pieces of information to convey: We started with the formula that has Godel number m. In it, we substituted m for the symbol y. And according to the mapping scheme introduced earlier, the symbol y has the Godel number 17. So let's designate the new formula's Godel number sub(m, m , 17). Substitution forms the crux of Godel's proof. He considered a metamathematical statement along the lines of "The formula with Godel number sub(y, y, 17) cannot be proved." Recalling the notation we just learned, the formula with Godel number sub(y, y, 17) is the one obtained by taking the formula with Godel number y (some unknown variable) and substituting this variable y anywhere there's a symbol whose Godel number is 17 (that is, anywhere there's a y). Things are getting trippy, but nevertheless, our metamathematical statement -- "The formula with Godel number sub(y, y, 17) cannot be proved" -- is sure to translate into a formula with a unique Godel number. Let's call it n. Now, one last round of substitution: Godel creates a new formula by substituting the number n anywhere there's a y in the previous formula. His new formula reads, "The formula with Godel number sub(n, n, 17) cannot be proved." Let's call this new formula G. Naturally, G has a Godel number. What's its value? Lo and behold, it must be sub(n, n, 17). By definition, sub(n, n, 17) is the Godel number of the formula that results from taking the formula with Godel number n and substituting n anywhere there's a symbol with Godel number 17. And G is exactly this formula! Because of the uniqueness of prime factorization, we now see that the formula G is talking about is none other than G itself. G asserts of itself that it can't be proved. But can G be proved? If so, this would mean there's some sequence of formulas that proves the formula with Godel number sub(n, n, 17). But that's the opposite of G, which says no such proof exists. Opposite statements, G and ~G, can't both be true in a consistent axiomatic system. So the truth of G must be undecidable. However, although G is undecidable, it's clearly true. G says, "The formula with Godel number sub(n, n, 17) cannot be proved," and that's exactly what we've found to be the case! Since G is true yet undecidable within the axiomatic system used to construct it, that system is incomplete. You might think you could just posit some extra axiom, use it to prove G, and resolve the paradox. But you can't. Godel showed that the augmented axiomatic system will allow the construction of a new, true formula G' (according to a similar blueprint as before) that can't be proved within the new, augmented system. In striving for a complete mathematical system, you can never catch your own tail. No Proof of Consistency We've learned that if a set of axioms is consistent, then it is incomplete. That's Godel's first incompleteness theorem. The second -- that no set of axioms can prove its own consistency -- easily follows. What would it mean if a set of axioms could prove it will never yield a contradiction? It would mean that there exists a sequence of formulas built from these axioms that proves the formula that means, metamathematically, "This set of axioms is consistent." By the first theorem, this set of axioms would then necessarily be incomplete. But "The set of axioms is incomplete" is the same as saying, "There is a true formula that cannot be proved." This statement is equivalent to our formula G. And we know the axioms can't prove G. So Godel has created a proof by contradiction: If a set of axioms could prove its own consistency, then we would be able to prove G. But we can't. Therefore, no set of axioms can prove its own consistency. Godel's proof killed the search for a consistent, complete mathematical system. The meaning of incompleteness "has not been fully fathomed," Nagel and Newman wrote in 1958. It remains true today. --------------------------------------------------------------------- ^*For the curious, the statement reads: "There exists some integer x such that x multiplied by 2 is equal to 21 x 3^8 x 5^6 x 7^5 x 11^6 x 13^9, and there does not exist any integer x such that x multiplied by 4 is equal to 21 x 3^8 x 5^6 x 7^5 x 11^6 x 13^9." The corresponding formula is: ([?]x)(x x ss0 = sss ... sss0) [?] ~([?]x)(x x ssss0 = sss ... sss0) where sss ... sss0 stands for 21 x 3^8 x 5^6 x 7^5 x 11^6 x 13^9 copies of the successor symbol s. The symbol [?] means "and," and is shorthand for a longer expression in the fundamental vocabulary: p [?] q stands for ~(~p [?] ~q). [Back to article.] This article was reprinted on Wired.com. Share this article Copied! --------------------------------------------------------------------- Newsletter Get Quanta Magazine delivered to your inbox Subscribe now Recent newsletters Natalie Wolchover By Natalie Wolchover Senior Editor --------------------------------------------------------------------- July 14, 2020 --------------------------------------------------------------------- View PDF/Print Mode Abstractions blogcontinuum hypothesisexplainersfoundations of mathematicsmathematicsproofsset theoryAll topics Click to take Quanta's 10-minute reader survey.Click to take Quanta's 10-minute reader survey. Share this article Copied! --------------------------------------------------------------------- Newsletter Get Quanta Magazine delivered to your inbox Subscribe now Recent newsletters The Quanta Newsletter Get highlights of the most important news delivered to your email inbox Email[ ] Subscribe Recent newsletters Comment on this article Quanta Magazine moderates comments to facilitate an informed, substantive, civil conversation. Abusive, profane, self-promotional, misleading, incoherent or off-topic comments will be rejected. Moderators are staffed during regular business hours (New York time) and can only accept comments written in English. Show comments [Social-Dis] Next article The Math of Social Distancing Is a Lesson in Geometry * About Quanta * Archive * Contact Us * Terms & Conditions * Privacy Policy --------------------------------------------------------------------- All Rights Reserved (c) 2023 An editorially independent publication supported by the Simons Foundation.