https://billwadge.com/2024/03/11/the-complete-story-of-godel-incompleteness/ Bill Wadge's Blog Just another WordPress.com site [cropped-sail41] Skip to content * Home * A short academic biography [6100 views] * About * Contact * Lucid Language [440 views] * Wadge Degrees [160 views] - To Infinity ... Streams in PyFL [< 100 views] The complete story of Godel incompleteness. [410 views] Posted on March 11, 2024 by Bill Wadge The famous mathematician Kurt Godel proved two "incompleteness" theorems. This is their story. By the 1930s logicians, especially Tarski, had figured out the semantics of predicate logic. Tarski described what exactly was an 'interpretation' and what it meant for a formula to be true in an interpretation. Briefly, an interpretation is a nonempty set (the "universe of discourse") together with, for each n-ary relation symbol, an n-ary relation over the universe, and for each n-ary operation symbol, an n-ary operation over the universe. Before this, logic had been strictly syntactical and proof theoretic. With the emergence of semantics the question arose about the relation between syntax and semantics. In particular, logicians asked if every tautology (formula true in all interpretations) is provable. The young Kurt Godel, in his PhD thesis, answered this affirmatively: he showed that every tautology has a proof. This is his "completeness" theorem. We won't get into it here. True arithmetic Truth in all interpretations is important but for practical purposes we are also interested in what is true in individual interpretations. In particular, we'd like to know what is true in arithmetic - in the interpretation where the universe of discourse is the integers and we have equality, the less than relation and the operations successor, addition and multiplication. Godel's colleagues were searching for what, in modern terminology, we'd call a decision procedure for the set of true first order formulas of arithmetic. In other words, a mechanical procedure to decide whether or not a first order formula in the language of arithmetic is true in the standard interpretation. Remember that the twin primes conjecture, for example, is one such formula. Godel at first tried to find such a procedure but eventually came to suspect that there wasn't one, and he set out to prove it. Suppose the set of true arithmetic formulas (this set is now called True Arithmetic) has a mechanical test for membership. We can start listing all formulas and rejecting the false ones. Those left over, the true ones, we can take as axioms for True Arithmetic. These axioms are complete: every formula is either one of these, or its complement is. Godel's strategy was to show that True Arithmetic has no complete axiomatization. Given a proposed set A of axioms, he constructs a statement U[A] that is true but unprovable from A. He used the same trick as the liar paradox: U[A] says it itself is not provable from A. It follow easily that U[A] is true (it's not provable) but - not provable. Recursive and recursively enumerable An important concept that arises is that of (recursive) enumerability . A set is recursively enumerable (re) if there is a machine which, running possibly indefinitely, eventually outputs any particular element of the set, and only elements of the set. A very simple example of an re set is the natural numbers, They are enumerated by a counter that starts at 0. Every finite set is re. A set is recursive iff there is a mechanical decision procedure for testing membership. In other words, Godel's colleagues were trying to show that the set of all true first-order formulas of arithmetic is recursive. It's not hard to show that every recursive set is re - to enumerate its elements you feed the natural numbers through a filter that eliminates non elements. On the other hand, if both a set S and its complement -S are re, S must be recursive. To decide if a number n is in S, you simultaneously enumerate S and its complement -S until n shows up in one of these. If it shows up in the enumeration of S, n is in S, otherwise n is in -S. Godel coding We need to establish that various sets of formulas are re or recursive, but strictly speaking we can't because only sets of natural numbers have these properties. The solution Godel came up with was to devise a coding scheme for formulas so that every formula has a unique code and vice versa. There are various ways to do this and the details don't matter. For example we can factor a number into a product of powers of exponentials. Then we can consider the number as the code for the sequence of powers. Once we can code arbitrarily long sequences we can code nested sequences and arbitrary hierarchical structures. This gives us logical formulas, proof trees, sets of formulas and the like. It's not hard to show that the sets of formulas and proof trees (in particular) are recursive and thus re. Enumerability of consequences Then from the enumeration of the proof trees we can filter out those that have no assumptions and extract their conclusions. This shows that the set of (codes for) tautologies is re. The tautologies are the consequences of the empty set of axioms. We can easily use a similar argument to show that the set of consequences of any finite set of axioms is re. With a little more effort we can establish the same for any enumerable set of axioms. We take our enumeration of the axioms and produce an enumeration of the initial segments, and for each enumerate the consequences. We merge these enumerations for the desired result. (The principal here is that an re union of re sets is re). Decision procedure What this means is that if we have a set of axioms for arithmetic that is complete, we have our decision procedure A set of axioms is complete iff it settles the status of every formula ps: either ps or !ps is a consequence. If we had a complete (re) set of axioms for arithmetic then to decide if ps is true in arithmetic, we enumerate the consequences of the axioms and wait for either ps or !ps to show up. If ps shows up it's true, otherwise false. Since the axioms are complete one of ps and !ps will eventually show up, and we won't wait forever. On the other hand, if there is decision procedure, we can easily find an enumerable complete set of axioms. We run the set of formulas through our decision procedure and filter out the false ones, leaving the set of true formulas of arithmetic. This set is clearly re (given our assumption of a decision procedure) and so clearly constitutes a complete axiomatization of arithmetic truth. To summarize, arithmetic truth is recursive iff it has a complete (re) axiomatization. Axioms for arithmetic The question then is, which axioms? There is really only one candidate, namely Peano arithmetic. There are different presentations. The simplest are the recurrence equations for + and * plus an axiom schema for proving formulas true by induction. It is now known that Peano arithmetic is strong enough (using coding) for almost all of finite mathematics (it doesn't handle real arithmetic) but of course is incomplete. We know it's incomplete because of Godel's result but obviously he didn't have this information. I haven't been able to find out if Peano arithmetic was known already to be incomplete. If Peano arithmetic is incomplete, what do you add? You can already prove, e.g. the distributive law by induction. Godel initially believed arithmetic was axiomatizable, but at some point he began to have second thoughts and started working on a proof that it was not. His strategy was to come up with a sentence whose provability would produce a contradiction. The sentence should therefore assert the unprovability of something that is nevertheless true. The Liar Sentence The answer is to produce a sentence that asserts its own unprovability. If you can prove it, it's false and you have your contradiction. But if you can't prove it, it's true, and you have incompleteness. With the coding you can talk about provability but the trick is to get the sentence to refer to itself. Let P[A] be provability in A. Enumerate the one-place formulas so that ph[n] is the nth such formula. Now consider the one-place formula !P[A](ph[i](i))), call it d(i). It must have an index d in the above enumeration, so that d(d) [?] !P[A](ph [d](d)). But d's index is d, so d(d) is ph[d](d), Putting our equivalences together, we get ph[d](d) [?] !P[A](ph[d](d)) which is ph[d] (d) asserting its own unprovability. So now we reason carefully. If ph[d](d) were provable, we'd get a contradiction, impossible if A is consistent. So con(A) implies ph[d] (d) not provable, i.e. con(A) -> ph[d](d) . But suppose we were able to prove the consistency of A; then we could prove ph[d](d), impossible (if A is actually consistent). The end result is that if A is consistent, we can't prove it's consistent. This is the second incompleteness theorem. So given a powerful consistent system A, not only is it incomplete but in particular its own consistency is unprovable. This put paid to the dream of a complete, final axiomatization of arithmetic, of a decision procedure for true arithmetic, and a provably consistent set of axioms. In fact true arithmetic is a very complicated set - a new level of complexity for every number of quantifier alterations. Very far from the decidable set the researchers before Godel hoped it would be. Relying on Experience We can't prove Peano arithmetic consistent so where does that leave us? (We can prove consistency using stronger systems whose own consistency is questionable.) It leaves us with more than a century of experience with the Peano axioms. In all that time no contradiction has been uncovered. This is strong experimental evidence for the consistency of Peano arithmetic. Also, in all that time the Peano system has proved perfectly adequate for 'practical' mathematics. This is strong experimental evidence for completeness in a practical sense: everything true that we're interested in is provable. In fact it wasn't till 1977 that Paris and Harrington discovered a 'natural' example of incompleteness. They found a powerful form of Ramsey's theorem that implies the consistency of Peano arithmetic and therefore can't be proved. So consistency and completeness have proved to be not a problem in any practical sense. The situation is grim only if we restrict ourselves to formal reasoning. If we allow experimental evidence, like any other science, we're in good shape. This is the real meaning of the incompleteness theorems. Share this: * Facebook * X * Like Loading... Related [b8e5755] About Bill Wadge I am a retired Professor in Computer Science at UVic. View all posts by Bill Wadge - This entry was posted in Uncategorized. Bookmark the permalink. - To Infinity ... Streams in PyFL [< 100 views] Leave a comment Cancel reply [ ] [ ] [ ] [ ] [ ] [ ] [ ] D[ ] This site uses Akismet to reduce spam. Learn how your comment data is processed. * Search for: [ ] [Search] * Email Subscription Enter your email address to subscribe to this blog and receive notifications of new posts by email. Email Address: [ ] Sign me up! Join 81 other subscribers * Recent Posts + The complete story of Godel incompleteness. [410 views] + To Infinity ... Streams in PyFL [< 100 views] + The Rise and Fall of GOFAI [2700 views] + Algebraic Pattern Matching [< 100 views] + The Autocomplete Myth [< 100 views] * Archives + March 2024 + February 2024 + April 2023 + March 2023 + February 2023 + December 2022 + November 2022 + July 2022 + June 2022 + May 2022 + March 2022 + February 2022 + January 2022 + December 2021 + August 2021 + July 2021 + June 2021 + May 2021 + March 2021 + February 2021 + January 2021 + September 2020 + August 2020 + July 2020 + June 2020 + April 2020 + March 2020 + February 2020 + January 2020 + December 2019 + October 2019 + June 2019 + April 2019 + March 2019 + October 2018 + September 2018 + November 2017 + June 2017 + May 2017 + April 2017 + March 2017 + March 2016 + January 2016 + December 2015 + November 2015 + October 2015 + September 2015 + July 2012 + April 2012 + March 2012 + December 2011 + May 2011 + April 2011 + March 2011 + February 2011 + July 2010 * Meta + Register + Log in + Entries feed + Comments feed + WordPress.com Bill Wadge's Blog Blog at WordPress.com. * Comment * Reblog * Subscribe Subscribed + [wpcom-] Bill Wadge's Blog Join 81 other subscribers [ ] Sign me up + Already have a WordPress.com account? Log in now. * + [wpcom-] Bill Wadge's Blog + Customize + Subscribe Subscribed + Sign up + Log in + Copy shortlink + Report this content + View post in Reader + Manage subscriptions + Collapse this bar %d [b]