{"id":132149,"date":"2022-04-12T20:59:28","date_gmt":"2022-04-12T18:59:28","guid":{"rendered":"https:\/\/www.pauljorion.com\/blog\/?p=132149"},"modified":"2023-06-03T17:29:39","modified_gmt":"2023-06-03T15:29:39","slug":"unilog-2022-godels-incompleteness-theorem-revisited-par-yu-li","status":"publish","type":"post","link":"https:\/\/www.pauljorion.com\/blog\/2022\/04\/12\/unilog-2022-godels-incompleteness-theorem-revisited-par-yu-li\/","title":{"rendered":"UNILOG 2022 – G\u00f6del\u2019s Incompleteness Theorem revisited<\/b>, par Yu Li"},"content":{"rendered":"
\"\"\r\n\r\nTexte de l\u2019article qu’a pr\u00e9sent\u00e9 samedi ma coll\u00e8gue Yu Li de l\u2019Universit\u00e9 de Picardie, au congr\u00e8s Unilog 2022 qui se tenait \u00e0 Chania en Cr\u00e8te.<\/blockquote>\r\n\r\n

G\u00f6del\u2019s Incompleteness Theorem revisited<\/strong><\/p>\r\n\r\n\r\n\r\n

– What is the undecidable problem<\/em>?<\/strong><\/p>\r\n\r\n\r\n\r\n

\u00a0I would rather have questions that can’t be answered than answers that can’t be questioned.<\/em> – Richard P. Feynman<\/p>\r\n\r\n\r\n\r\n

Yu Li *\r\n* Laboratoire MIS, Universit\u00e9 de Picardie Jules Verne, 33 rue Saint-Leu, 80090 Amiens, France\u00a0<\/p>\r\n\r\n\r\n\r\n\r\n\r\n

    \r\n
  1. Introduction<\/strong><\/li>\r\n<\/ol>\r\n\r\n\r\n\r\n

    In a famous article written in 1931 : \u00ab\u00a0 On Formally Undecidable Propositions of Principia Mathematica<\/em> and Related Systems I \u00bb\u00a0 <\/em>[1], Kurt G\u00f6del claimed to have proved the incompleteness of the system reported in Principia Mathematica <\/em>(i.e. Peano arithmetic), and by that answered negatively the Entscheidungsproblem<\/em> (the \u00ab\u00a0decision problem\u00a0\u00bb), a challenge put forward by David Hilbert and Wilhelm Ackermann in 1928.\u00a0<\/p>\r\n\r\n\r\n\r\n

    The Entscheidungsproblem was originally expressed as \u00ab Determination of the solvability of a diophantine equation\u00a0\u00bb, i.e., the 10th of the 23 problems proposed by Hilbert in his lecture at the International Congress of Mathematicians in Paris in 1900 [2].\u00a0 Church formulated the Entscheidungsproblem as : \u00ab\u00a0By the Entscheidungsproblem of a system of symbolic logic is here understood the problem to find an effective method by which, given any expression Q in the notation of the system, it can be determined whether or not Q is provable in the system<\/em>\u00a0\u00bb [3] (Copeland 2004: 45).\u00a0 If it is not possible to find such a method, some propositions would be regarded as \u00ab\u00a0undecidable\u00a0\u00bb. Such a realisation would then establish the incompleteness of Principia Mathematica (PM).<\/em><\/p>\r\n\r\n\r\n\r\n

    G\u00f6del claimed that the PM system is incomplete, as it is possible to show at least one such undecidable proposition. As a proof, G\u00f6del gave a paradox similar in nature to the Liar<\/em>\u2019<\/em>s paradox<\/em>: a proposition Q<\/em> asserting about itself that it is unprovable.It is nowadays a commonly accepted view that G\u00f6del proved the incompleteness of the PA system, thus revealing that truth is simply bigger than proof <\/em>[4].<\/p>\r\n\r\n\r\n\r\n

    However, G\u00f6del’s proof of the incompleteness theorem has been continuously challenged since its publication. Let us note that as early as 1936 the logician Cha\u00efm Perelman had drawn the attention to the fact that there wasn’t anything more to G\u00f6del’s demonstration than the generation of a paradox [5]; and the logician Wittgenstein held a similar view [6]. Paul Jorion, a former pupil of Perelman, has claimed in a different context [7] that G\u00f6del’s proof is marred by several other errors, due to his disdain towards the tight or lax persuasive quality of the various steps in his demonstration. Ernst Zermelo stated in a letter to G\u00f6del in 1931 that G\u00f6del’s proof of the existence of undecidable propositions exhibits an \u00ab\u00a0essential gap\u00a0\u00bb <\/em>[8]. Alan Turing alluded to the errors made by G\u00f6del without mentioning his name and ventured to fix them in his article in 1936, entitled \u00ab\u00a0On Computable Numbers, with an Application to the Entscheidungsproblem\u00a0\u00bb <\/em>[9].<\/em><\/p>\r\n\r\n\r\n\r\n

    G\u00f6del’s thesis consists of three chapters: Chapter 1 outlines the main idea of the proof; Chapters 2 and 3 formalise the idea of Chapter 1. In this paper, I focus on Chapter 1, where I examine G\u00f6del’s proof from the perspective of a dynamic process<\/em> by considering the generation of hypotheses and the reasoning from hypotheses to conclusion as an organic whole, and analyze how G\u00f6del constructed the paradoxical proposition Q.\u00a0<\/p>\r\n\r\n\r\n\r\n

    I try to point out that by confusing the proof of formula<\/em>\u00a0with the formula<\/em>, G\u00f6del’s proof becomes an infinite regress<\/em> that would have made it impossible to construct any meaningful proposition. Unfortunately, G\u00f6del did not realize this, but introduced improper presuppositions<\/em> which allow to construct the paradoxical proposition Q. Moreover, he considered Q as an undecidable proposition that exists in PM.<\/p>\r\n\r\n\r\n\r\n

    II. The crux of G\u00f6del’s proof<\/strong><\/p>\r\n\r\n\r\n\r\n

    G\u00f6del’s proof is framed by a proof by contradiction [1] (p. 17-19), which assumes that PM is complete, according to him it means that all formulas in PM or their negations are provable; in addition, all formulas in PM can be divided into classes of<\/em>formulas<\/em> (class sign<\/em>) and be enumerated. G\u00f6del then resorts to Cantor\u2019s diagonal argument to construct a paradox similar in nature to the Liar\u2019s paradox: a proposition Q<\/em> asserting about itself that it is unprovable.<\/p>\r\n\r\n\r\n\r\n

    G\u00f6del enumerates accordingly all classes of formulas in PM :<\/p>\r\n\r\n\r\n\r\n

    R(1) : [R(1), 1] [R(1), 2] [R(1), 3]\u2026 [R(1), n] \u2026<\/p>\r\n\r\n\r\n\r\n

    R(2) : [R(2), 1] [R(2), 2] [R(2), 3]\u2026 [R(2), n] \u2026<\/p>\r\n\r\n\r\n\r\n

    R(3) : [R(3), 1] [R(3), 2] [R(3), 3]\u2026 [R(3), n] \u2026<\/p>\r\n\r\n\r\n\r\n

    R(4) : [R(4), 1] [R(4), 2] [R(4), 3]\u2026 [R(4), n] \u2026<\/p>\r\n\r\n\r\n\r\n

    \u2026<\/p>\r\n\r\n\r\n\r\n

    R(q) : [R(q), 1] [R(q), 2] [R(q), 3]\u2026 [R(q), q] \u2026 [R(q), n] \u2026<\/p>\r\n\r\n\r\n\r\n

    \u2026<\/p>\r\n\r\n\r\n\r\n

    R(n) denotes a class of formulas and [R(n), j] denotes the jth formula of R(n). G\u00f6del takes the formulas on the diagonal: [R(1), 1] [R(2), 2] [R(3), 3] [R(4), 4]… [R(n), n], … derives the negations of them, and defines the formula class K, K = {n|Bew\u00ac[R(n); n]}, while Bew x<\/em> means that the formula x is provable. K is actually the set of the negations of [R(n), n], K = {\u00ac[R(1), 1],\u00ac[R(2), 2],\u00ac[R(3), 3],\u00ac[R(4), 4]\u2026 \u00ac[R(q), q]\uff0c\u2026 }.<\/p>\r\n\r\n\r\n\r\n

    G\u00f6del considers that the formula class K falls within the sequence of enumerated formula classes, say corresponding to R(q). Thus, on the one hand, [R(q); q] is the formula A on the diagonal, and on the other hand, it is the formula \u00acQ in K. There is a paradox: Q = \u00acQ, that is, the proposition Q says about itself that it is unprovable<\/em>!<\/p>\r\n\r\n\r\n\r\n

    The gist of our argument below, is that there exist improper presuppositions <\/em>inG\u00f6del’s proof.<\/p>\r\n\r\n\r\n\r\n

    III. An analysis of the proof of G\u00f6del’s Incompleteness Theorem<\/strong><\/p>\r\n\r\n\r\n\r\n

    At the beginning of the proof, G\u00f6del unconsciously took proof of formula<\/em> as formula<\/em>, which led to an infinite regress<\/em>; unfortunately, G\u00f6del was not aware of this and introduced an improper presupposition<\/em>, provable formulas,<\/em> which led to the paradoxial proposition Q.<\/p>\r\n\r\n\r\n\r\n

      \r\n
    1. P<\/em><\/strong>roof of a formula<\/em> and formula<\/em>: confusion of meta-language with object language<\/strong><\/li>\r\n<\/ol>\r\n\r\n\r\n\r\n

      We consider a familiar instance :<\/p>\r\n\r\n\r\n\r\n

      Illustration<\/strong> 1.<\/strong> Proposition P: \u221a2 is a rational number; its negation \u00acP: \u221a2 is not a rational number.<\/p>\r\n\r\n\r\n\r\n

      \u00ab\u00a0 \u221a2 is not a rational number\u00a0\u00bb\u00a0 (\u00acP) cannot be proved directly, but there exists the familiar proof by contradiction <\/em>to prove that \u00ab\u00a0 \u221a2 is a rational number\u00a0\u00bb\u00a0 (P), thus \u00acP is proved to be true indirectly.<\/p>\r\n\r\n\r\n\r\n

      Proof<\/strong> :<\/p>\r\n\r\n\r\n\r\n

      Assume that \u00ab\u00a0 \u221a2 is a rational number\u00a0\u00bb , then \u221a2 = p\/q, where p and q are both positive integers and mutually prime;<\/p>\r\n\r\n\r\n\r\n

      p = \u221a2 \u00d7 q,\u00a0<\/p>\r\n\r\n\r\n\r\n

      p^2 = 2 \u00d7 q^2,<\/p>\r\n\r\n\r\n\r\n

      p^2 is thus even and so is p, since only the even square of an even number is even.<\/p>\r\n\r\n\r\n\r\n

      Since p is even, we can regard p as being the double of s : p = 2 x s<\/p>\r\n\r\n\r\n\r\n

      Let\u2019s substitute 2s to p in p^2 = 2 \u00d7 q^2,<\/p>\r\n\r\n\r\n\r\n

      (2 x s)^2 =\u00a0 2 \u00d7 q^2<\/p>\r\n\r\n\r\n\r\n

      4 x s^2 = 2 \u00d7 q^2<\/p>\r\n\r\n\r\n\r\n

      2 x s^2 = q^2<\/p>\r\n\r\n\r\n\r\n

      q^2 is thus even and so is q<\/p>\r\n\r\n\r\n\r\n

      p and q are even numbers, thus not mutually prime, contradicting the assumption that p and q are mutually prime;<\/p>\r\n\r\n\r\n\r\n

      Therefore, the assumption \u00ab\u00a0 \u221a2 is a rational number\u00a0\u00bb is invalid, and \u00ab\u00a0 \u221a2 is not a rational number\u00a0\u00bb has been proven.<\/p>\r\n\r\n\r\n\r\n

      P and \u00acP are the formulas about the numbers themselves; while the proof by contradiction is about the provability of P and \u00acP.<\/p>\r\n\r\n\r\n\r\n

      The relation between the formula\u00a0 and the proof of formula is generally expressed as the relation between the object language and the meta-language. What is about mathematical objects and what is about the provability of formulas are two concepts completely different in nature but intrinsically related.<\/p>\r\n\r\n\r\n\r\n

      However, G\u00f6del made such a claim with surprising imprudence: \u00ab\u00a0Similarly, proofs, from a formal point of view, are nothing but finite sequences of formulae (with certain specifiable properties)\u00bb<\/em>. In this way, the formula and the proof of formula are confused.<\/p>\r\n\r\n\r\n\r\n

      2. A provable formula<\/em> : infinite regress and improper presumption<\/strong><\/p>\r\n\r\n\r\n\r\n

      As G\u00f6del shows in the end of chapter 1, the provable formula <\/em>is the key concept in his proof :<\/p>\r\n\r\n\r\n\r\n

      \u00ab\u00a0The method of proof just explained can clearly be applied to any formal system that, first, when interpreted as representing a system of notions and propositions, has at its disposal sufficient means of expression to define the notions occurring in the argument above (in particular, the notion \u2018provable formula\u2019) and in which, second, every demonstrable formula is true in the interpretation considered. \u00bb [1] (p. 19).<\/p>\r\n\r\n\r\n\r\n

      What is the meaning of a \u00ab\u00a0provable formula\u00a0\u00bb <\/em>in PM?\u00a0<\/p>\r\n\r\n\r\n\r\n

      From common sense, a provable formula means that there exists a valid proof of this formula, that is, the provable formula concerns the existence of the proof.<\/p>\r\n\r\n\r\n\r\n

      In illustration 1, the proposition \u00ab \u221a2 is not a rational number \u00bb is a provable formula<\/em> since there is a valid proof by contradiction for proving that \u221a2 is not a rational number.<\/p>\r\n\r\n\r\n\r\n

      Since G\u00f6del treats the proof of formula as the formula, the provable formula in PM<\/em> means that the proof is provable in PM<\/em>, that is, the validity of proof can be verified in PM<\/em>, which leads to an infinite regress<\/em>. Lewis Carroll\u2019s fable \u00ab\u00a0What the Tortoise Said to Achilles\u00a0<\/em>\u00bb provides an illustration of infinite regress [10].<\/p>\r\n\r\n\r\n\r\n

      Suppose that \u00ab\u00a0P0 is provable<\/em>\u00a0\u00bb, that implies that there exists\u00a0 P1,\u00a0the proof of P0, and since P1 is treated as a formula, \u00ab\u00a0P1 is provable<\/em>\u00a0\u00bb. Similarly, \u00ab\u00a0P1 is provable<\/em>\u00a0\u00bb\u00a0 implies that there exists P2, the proof of formula P1, and \u00ab\u00a0 P2 is provable<\/em>\u00a0\u00bb, \u2026 and so on, resulting in an infinite regress (Figure 1).\u00a0<\/p>\r\n\r\n\r\n\r\n

      A proof of infinite regress\u00a0cannot establish any conclusion, so the verification of the validity of proof\u00a0in PM becomes problematic, then the existence of proof\u00a0in PM becomes problematic, and the existence of provable formulas in PM\u00a0becomes also problematic.<\/p>\r\n\r\n\r\n\r\n

      Consequently, G\u00f6del cannot talk about the enumeration of classes of formulas, nor about the use of diagonal method to construct the paradoxical proposition Q in PM. In other words, the paradoxical proposition Q cannot be constructed in G\u00f6del\u2019s proof.<\/p>\r\n\r\n\r\n\r\n

      But G\u00f6del constructed the paradoxical proposition Q after all, because he presupposed the verification of the validity of proof\u00a0in PM<\/em>, which made the provable formula<\/em> an improper presupposition<\/em>.<\/p>\r\n\r\n\r\n\r\n

      Russell gave a simple example of an improper presupposition in \u00ab\u00a0On Denoting<\/em>\u00a0\u00bb : \u00ab\u00a0the present king of France is bald.<\/em>\u00a0\u00bb [11] Whether this proposition is judged to be true or false, it presupposes the existence of the present King of France, who, however, does not exist.<\/p>\r\n\r\n\r\n\r\n

      I<\/strong>V. Conclusion<\/strong><\/p>\r\n\r\n\r\n\r\n

      The brief analysis in this paper shows that there are improper presuppositions in G\u00f6del’s proof that enable G\u00f6del to construct the paradoxical proposition Q as evidence for the existence of undecidability problems of PM, and thus to conclude that PM is incomplete.<\/p>\r\n\r\n\r\n\r\n

      Therefore, taken as a whole, the actual formulation of G\u00f6del’s incompleteness theorem is :<\/p>\r\n\r\n\r\n\r\n

      – PM is incomplete, because there are undecidable problems similar to the liar’s paradox in PM.<\/strong><\/p>\r\n\r\n\r\n\r\n

      Let\u2019s remember what Bertrand Russell once wrote in a letter to Leon Henkin: \u00ab\u00a0I realised, of course, that G\u00f6del\u2019s work is of fundamental importance, but I was puzzled by it. [\u2026] If a given set of axioms leads to a contradiction, it is clear that at least one of the axioms must be false<\/em>\u00a0\u00bb [1] (p. 90)<\/p>\r\n\r\n\r\n\r\n

      I hope to initiate a debate :<\/p>\r\n\r\n\r\n\r\n

        \r\n
      1. Is the paradoxical proposition Q similar to the liar’s paradox an undecidable proposition in PM?\u00a0<\/li>\r\n
      2. Is G\u00f6del’s proof valid? If not, what is a valid proof for the incompleteness of PM?<\/li>\r\n
      3. By revisiting G\u00f6del’s incompleteness theorem today, what would be the insights for us from the perspective of epistemology? What would be the insights for solving the \u00ab\u00a0P vs NP\u00a0\u00bb problem, as well as some underlying theoretical problems of artificial intelligence, from the perspective of algorithm theory?<\/li>\r\n<\/ol>\r\n\r\n\r\n\r\n

        Reference :<\/strong><\/p>\r\n\r\n\r\n\r\n

        [1] S.G. Shanker (ed.), G\u00f6del\u2019s Theorem in Focus, Croom Helm 1988, https:\/\/pdfslide.net\/documents\/godels-theorem-in-focus-philosophers-in-focus.html<\/a><\/p>\r\n\r\n\r\n\r\n

        [2] David Hilbert, Mathematical Problems, http:\/\/aleph0.clarku.edu\/~djoyce\/hilbert\/problems.html<\/a><\/p>\r\n\r\n\r\n\r\n

        [3] Brian Jack Copeland, The EssentialTuring, http:\/\/www.cse.chalmers.se\/~aikmitr\/papers\/Turing.pdf<\/a><\/p>\r\n\r\n\r\n\r\n

        [4] Casti, John L. & Werner DePauli, G\u00f6del. A Life of Logic<\/em>, Cambridge (Mass.) Perseus: 2000<\/p>\r\n\r\n\r\n\r\n

        [5] Jean Ladri\u00e8re, Les limitations internes des formalismes. Etude sur la signification du th\u00e9or\u00e8me de G\u00f6del et des th\u00e9or\u00e8mes apparent\u00e9s dans la th\u00e9orie des fondements des math\u00e9matiques, ed. Nauwelaerts-Gauthier-Villars, Leuven-Paris, 1957, pages 140 \u00e0 142<\/p>\r\n\r\n\r\n\r\n

        \u00a0[6] Kreisel, G. (1958). \u00ab\u00a0Wittgenstein’s Remarks on the Foundations of Mathematics\u00a0\u00bb.\u00a0The British Journal for the Philosophy of Science.\u00a0IX\u00a0(34): 135\u201358.\u00a0doi<\/a>:10.1093\/bjps\/IX.34.135<\/a><\/p>\r\n\r\n\r\n\r\n

        [7] Paul Jorion, Comment la v\u00e9rit\u00e9 et la r\u00e9alit\u00e9 furent invent\u00e9es<\/em> (Gallimard 2009)<\/p>\r\n\r\n\r\n\r\n

        [8] NOTE Completing the Godel-Zermelo Correspondence, https:\/\/www.sciencedirect.com\/science\/article\/pii\/0315086085900709<\/a><\/p>\r\n\r\n\r\n\r\n

        [9] Turing, A.M. On Computable Numbers, with an Application to the Entscheidungsproblem. Proceedings of the London Mathematical Society<\/em>, 2 (published 1937), 42<\/p>\r\n\r\n\r\n\r\n

        [10] https:\/\/en.wikisource.org\/wiki\/What_the_Tortoise_Said_to_Achilles<\/a><\/p>\r\n\r\n\r\n\r\n

        [11] https:\/\/en.wikipedia.org\/wiki\/On_Denoting<\/a><\/p>\r\n","protected":false},"excerpt":{"rendered":"

        \n

        \"\"<\/p>\n

        Texte de l\u2019article qu’a pr\u00e9sent\u00e9 samedi ma coll\u00e8gue Yu Li de l\u2019Universit\u00e9 de Picardie, au congr\u00e8s Unilog 2022 qui se tenait \u00e0 Chania en Cr\u00e8te.<\/p>\n<\/blockquote>\n

        G\u00f6del\u2019s Incompleteness Theorem revisited<\/strong><\/p>\n

        – What is the undecidable problem<\/em>?<\/strong><\/p>\n

        \u00a0I would rather have questions that can’t be […]<\/em><\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"closed","sticky":false,"template":"","format":"standard","meta":{"_crdt_document":"","footnotes":""},"categories":[8601,16],"tags":[5335],"class_list":["post-132149","post","type-post","status-publish","format-standard","hentry","category-fondement-des-mathematiques","category-mathematiques","tag-kurt-godel"],"_links":{"self":[{"href":"https:\/\/www.pauljorion.com\/blog\/wp-json\/wp\/v2\/posts\/132149","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/www.pauljorion.com\/blog\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/www.pauljorion.com\/blog\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/www.pauljorion.com\/blog\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/www.pauljorion.com\/blog\/wp-json\/wp\/v2\/comments?post=132149"}],"version-history":[{"count":7,"href":"https:\/\/www.pauljorion.com\/blog\/wp-json\/wp\/v2\/posts\/132149\/revisions"}],"predecessor-version":[{"id":136366,"href":"https:\/\/www.pauljorion.com\/blog\/wp-json\/wp\/v2\/posts\/132149\/revisions\/136366"}],"wp:attachment":[{"href":"https:\/\/www.pauljorion.com\/blog\/wp-json\/wp\/v2\/media?parent=132149"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/www.pauljorion.com\/blog\/wp-json\/wp\/v2\/categories?post=132149"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/www.pauljorion.com\/blog\/wp-json\/wp\/v2\/tags?post=132149"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}