Goedel Incompleteness Theorem

11 Key excerpts on "Goedel Incompleteness Theorem"

• 

  eBook - ePub

  Changing Images in Mathematics

  From the French Revolution to the New Millennium

  • Umberto Bottazini, Amy Dahan Dalmedico(Authors)
  • 2013(Publication Date)
  • Routledge

    (Publisher)

  Chapter 10 DEFINABILITY AS A MATHEMATICAL CONCEPT BEFORE AND AFTER GÖDEL Gabriele Lolli    

  In the opinion of most commentators, either logicians or mathematicians, the importance and influence of Gödel's incompleteness results were nil. According to Kreisel [1988], Gödel's theorems have had absolutely no use, and properly so, since they were tailored to refute— or confirm, it does not matter—a specific thesis about the completeness of mathematical systems. Bourbaki [1960] dutifully recalled Gödel's two incompleteness theorems, but only in the historical notes of the section ‘Metamathematics’ and nowhere else in the treatise. The theorems were likewise seen as a negative answer to Hilbert's program. Bourbaki hinted at their proofs and the technique used, saying that it was based on a one-to-one correspondence between metamathematical sentences and certain propositions of formalized arithmetic.

  The most favorable appreciation is due to Myhill [1950], but he restricted himself to a philosophical point of view. He stressed the important conceptual distinction between the decidable and the semi-decidable which emerged from the combined effect of the completeness, incompleteness, and semidecidability theorems, and from the development of recursion theory. Semidecidability is a notion that could not even have been conceived of beforehand, and a fortiori no one could ever have imagined to give to it an abstract definition, nor that it could be exemplified by such important domains as logic itself.

  In philosophy, not even the Gödel-Tarski theorem on the undefin-ability of truth has had any influence, although it is easy to imagine that it could have. Ironically, the notion of truth itself still is often used in the sloppy characterization of the undecidable propositions as true but unprovable propositions.1

  In a sense the disparaging attitude towards Gödel's theorems is fair but in another sense, it is not. Mathematics has not changed because of (the awareness of) incompleteness. It would be possible to list names of people expecting and desiring completeness and decidability (from Leibniz to Peirce2

  Sign up to read

  Learn more about book
• 

  eBook - ePub

  Einstein, Tagore and the Nature of Reality

  • Partha Ghose(Author)
  • 2016(Publication Date)
  • Routledge

    (Publisher)

  A third point deserves to be emphasised in this context. That is connected with the notion of the truth of mathematical claims or propositions. According to the second incompleteness theorem, the consistency of mathematics implies that it (this consistency) cannot be proved in mathematics when considered as a formal theory. From our long familiarity with numbers, it is reasonable (here I follow Mehlberg) to assume that number theory is indeed consistent. So, by incompleteness theorem, its consistency is not provable. Thus, some mathematical ‘truths remain beyond mathematics’—a phenomenon making a sceptic naturally delighted. Gödel himself was far from scepticism in mathematics. He even ‘believed’ that someday, the continuum hypothesis would be established, though later years proved otherwise. But what Gödel proved in the second incompleteness theorem helps the sceptic in doubting truths obtained through mathematics, and as a consequence, truths in science. On the other hand, mathematicians earning their bread and butter on mathematics would say that the problem lies with the formal system; Gödel’s second incompleteness theorem shows only the limitation of formalisation, not of mathematics per se—too much dependency on formalism does not really pay. But, we know that formalism was a necessity of a particular era, at a particular stage of development of mathematics. Various problems arose out of general informal practices continuing over centuries. We know the story of non-Euclidean geometry. The informal arguments for centuries to prove the fifth postulate ended up with circularities several times. Concepts of calculus were extremely amorphous, so much so as to be ridiculed by Bishop Berkeley with the remark that infinitesimals of calculus are ‘ghosts of departed quantities’. This experience led mathematicians of the 20th century to take recourse to extreme caution while attempting to repair the damage caused by several paradoxes and antimonies, such as Russell’s paradox. In the ultimate analysis, what else can ‘caution’ mean other than ‘rigour’, and rigour means looking for some sort of formalism that can be used and inspected by the human brain mechanically, without any intuitive leap.

  Sign up to read

  Learn more about book
• 

  eBook - ePub

  Foundations of Set Theory

  • A.A. Fraenkel, Y. Bar-Hillel, A. Levy(Authors)
  • 1973(Publication Date)
  • North Holland

    (Publisher)

  recursive arithmetic , i.e. in that part of arithmetic which contains general recursive functions, properties, and relations exclusively, that the system possesses all these desirable properties.

  § 7 The Limitative Theorems Of Gödel, Tarski, Church and Their Generalizations

  That the attempt to carry out the Hilbert program, as formulated in the preceding paragraph, would run into troubles was not too surprising: any logistic system strong enough to have all of classical mathematics developed in it would certainly contain all of classical number theory, hence presumably all of its own syntax and semantics. But does this not entail that the semantic antinomies, of the Liar and Richard types, could be reestablished within such a system?

  As already mentioned above, Gödel and Tarski asked themselves precisely this question. The partial answer at which Gödel arrived is

  GÖDEL’s (INCOMPLETENESS) THEOREM:1 ) Every logistic system rich enough to contain a formalization of recursive arithmetic is either ω-inconsistent or else contains an undecidable (though true) formula, i.e. a formula that can be neither proved nor refuted with the means of this system (though it can be shown to be true with the help of additional means outside of the system); in other words, any ω-consistent system of this kind is (syntactically and semantically) incomplete.

  Gödel established his theorem constructively ; for a given logistic system fulfilling the mentioned condition, the Gödelian undecidable sentence can actually, time and patience allowing, be written down in primitive notation. The truth of this undecidable sentence follows from the fact that, suitably interpreted, it states that this very sentence itself (more precisely, the sentence with a certain Gödel number – which then turns out to be the Gödel number of the sentence by which this statement is made) is not provable (in the given system)2

  Sign up to read

  Learn more about book
• 

  eBook - ePub

  What Is Mathematical Logic?

  • J. N. Crossley, C.J. Ash, C.J. Brickhill, J.C. Stillwell(Authors)
  • 2012(Publication Date)
  • Dover Publications

    (Publisher)

  5

  Gödel’s Incompleteness Theorems

  EARLIER this century the mathematician Hilbert posed the problem of finding a formal system which gave all the true mathematical statements, and only those. This was called ‘Hilbert’s programme’. However, the simple case of formal arithmetic disrupted this programme. By formal arithmetic I mean a formal system which will deal with the arithmetic of the natural numbers 0, 1, 2, ... and the usual basic functions such as addition and multiplication. In 1931, Gödel proved that if a formal system, let us call it F, included arithmetic, then (i) there is a statement of F (or indeed of arithmetic) which is true, but not provable and (ii) we need a system stronger than F if the consistency of F is to be proved.

  In this chapter I am going to describe a formal system of arithmetic which will be strong enough to treat all the usual things in arithmetic that one might want to deal with, including even such exotic things as Fermat’s Last Theorem. Also in this chapter I shall exhibit a formula which says ‘I am not provable’. This formula will be true, so clearly it will not be provable.

  In fact it is very easy to describe this formula. I shall go into the detail later. For the moment, consider a formula which I shall abbreviate as x Pf+ (x, b, c). This is to be true only when x is the Gödel number (and I shall say what this means later on) of a proof of the formula that one gets when one substitutes the numeral (I shall say what this means later on, too) for the free variable y, in the formula whose number is b. When this formula is interpreted in the ordinary integers, it says that there is an x such that x is the Gödel number of a proof of a certain formula when is substituted for its only free variable. The number of the formula is b before this substitution is performed.

  Now consider the formula x Pf+ (x, y, y). This formula itself will be given a Gödel number g, say. We shall investigate what happens when you put in the numeral of the number g in the formula for the y

  Sign up to read

  Learn more about book
• 

  eBook - ePub

  There's Something About Gödel

  The Complete Guide to the Incompleteness Theorem

  • Francesco Berto(Author)
  • 2011(Publication Date)
  • Wiley-Blackwell

    (Publisher)

  This concerns our incapacity to specify all of our mathematical abilities in terms of a formal system we can recognize as correct. The “Conclusion G” advanced on p. 76 of Shadows is: “Human mathematicians are not using a knowably sound algorithm in order to ascertain mathematical truth.” This seems to express Penrose’s usual thesis that human mind is not algorithmic. But instead of stressing the word “algorithm,” we could stress “knowably,” and say: “Human mind could not know the soundness” of such a formal system or algorithm. Now, this comes very close to something Gödel did claim – something that actually follows from the Incompleteness Theorem, and also reveals something important about us and our relation to mathematics. Let us have a look. On December 26, 1951, Gödel gave one of the prestigious Gibbs Lectures at the American Mathematical Society. In previous years, the Lectures had hosted great mathematicians and scientists such as Hardy, von Neumann, Weyl, and Einstein, but Gödel was the first logician to be invited. The title of his lecture was: “Some Basic Theorems on the Foundations of Mathematics and Their Philosophical Implications.” The “theorems” at issue were precisely the Incompleteness Theorems, and their “philosophical implications” concerned the nature of mathematics and the capacities of the human mind. Now, Gödel claimed that what the Theorems do entail (specifically, the Second Theorem) is that mathematics is inexhaustible : It is this theorem [i.e., the Second Theorem] which makes the incompletability of mathematics particularly evident. For, it makes it impossible that someone should set up a certain well-defined system of axioms and rules and consistently make the following assertion about it: All of these axioms and rules I perceive (with mathematical certitude) to be correct, and moreover I believe that they contain all of mathematics

  Sign up to read

  Learn more about book
• 

  eBook - ePub

  Naming, Necessity and More

  Explorations in the Philosophical Work of Saul Kripke

  • Jonathan Berg(Author)
  • 2014(Publication Date)
  • Palgrave Macmillan

    (Publisher)

  Part VLogic Passage contains an image

  11

  The Road to Gödel

  Saul A. Kripke

  What does this title mean?1 Gödel’s incompleteness theorem, as he originally presented it, seems to be an extraordinary and tricky magical construction. We can now, with modern recursion theory or computability theory,2 reduce the problem to the unsolvability of the halting problem, or the theorem that there is a recursively enumerable set that is not recursive (computably enumerable set that is not computable) – though that is not the way Gödel presented it himself. A friend of mine of the highest distinction in this very field of recursion (computability) theory once said to me in informal conversation that all of us know how the original Gödel statement was constructed, but no one really understands what it says. It is just an artificial product and has no intuitive content.

  Now, I want to do two things: first, to present the Gödel theorem as almost the inevitable result of a historic line of thought. I don’t mean that it did happen that way; I mean that it could have, and perhaps should have, but did not happen in that way. Second, I want to show that the Gödel statement, the one Gödel proves to be undecidable in the first incompleteness theorem, makes a fairly intelligible assertion that can actually be stated. Along the way I will do some things that are a little bit more technical, which are, not only as motivation but even as side theorems, unknown (as far as I know) even to specialists. They have to be separated out, because they involve more technicalities, though I will mention them and, to some extent, use them. I should also state at the outset that some of these issues are unnecessary to the main point about the interpretation of Gödel’s statement, and can be avoided if one wishes to do so.

  Let’s look first at Gödel’s own presentation, which has struck many readers as tricky and magical, by way of contrast with the present version. Gödel first says:

  Sign up to read

  Learn more about book
• 

  eBook - ePub

  The Universal Computer

  The Road from Leibniz to Turing, Third Edition

  • Martin Davis(Author)
  • 2018(Publication Date)
  • CRC Press

    (Publisher)

  At the end of a day’s work [von Neumann] would go to bed and very often awaken in the night with new insights. … In this case he was busily engaged in trying to develop a proof [of the consistency of arithmetic] and was unsuccessful! One night he dreamed how to overcome his difficulty and carried his proof much further along … The next morning he returned to the attack, again without success, and again that night retired to bed and dreamed. This time he saw his way through the difficulty, but when he arose … he saw there was still a gap …

  Things would have worked out differently, von Neumann quipped, if he had dreamed a third night!19

  The conference at which Gödel dropped his bombshell was but an adjunct to the major event taking place in Königsberg that week: a convention of the Society of German Scientists and Physicians. The opening address was delivered by David Hilbert the day following the round table. This was the occasion in which Hilbert articulated the slogan still on his tombstone in which he declared his faith that all mathematical questions must and will be answered: “wir müssen wissen; wir werden wissen,” [we must know; we shall know].

  Gödel’s incompleteness theorem shows that if mathematics is restricted to what can be encapsulated in specific formal systems like PM, then Hilbert’s faith was in vain. For any specific given formalism there are mathematical questions that will transcend it. On the other hand, in principle, each such question leads to a more powerful system which enables the resolution of that question. One envisions hierarchies of ever more powerful systems each making it possible to decide questions left undecidable by weaker systems.

  Although all of this is incontrovertible as a matter of theory, it is less clear to what extent it will ever become a matter of mathematical practice. Gödel has left as his legacy to mathematicians the task of learning to use these more powerful systems in settling intractable problems. Although some courageous researchers have been working along these lines, most mathematicians remain unaware of these issues, and some experts greet this work with extreme skepticism.20

  Sign up to read

  Learn more about book
• 

  eBook - ePub

  Logic from Russell to Church

  • Dov M. Gabbay, John Woods(Authors)
  • 2009(Publication Date)
  • North Holland

    (Publisher)

  a certain (decidable) formal structure and which in addition is true. Such a concept of demonstrability might have the required closure property, i.e., the following could be true: Any proof for a set-theoretic theorem in the next higher system above set theory (i.e., any proof involving the concept of truth which I just used) is replaceable by a proof from such an axiom of infinity. It is not impossible that for such a concept of demonstrability some completeness theorem would hold which would say that every proposition expressible from set theory is decidable from the present axioms plus some true assertion about the largeness of the universe of all sets. (emphasis ours)

  For a further analysis of Gödel’s views on extensions of the Zermelo-Fraenkel axioms, also in relation to the present developments in set theory, see [Kennedy and van Atten, 2004 ].

  1.4 Speed-up Theorems

  Gödel submitted an abstract in 1936 for what came to be known as the ‘speed-up’ theorem, entitled ‘On the length of proofs.’126 This result says that while some sentences of arithmetic are true but unprovable, there are other sentences which are provable but even the shortest proof is longer than any bound given in advance. More exactly:

  THEOREM 9 Given any recursive function f there are provable sentences of arithmetic such that the shortest proof is greater than f(˹ϕ˺) in length.

  The Speed-up Theorem is the result of contemplating and elaborating the proof of the incompleteness theorem. It applies the fixed-point technique to the concept of unprovability by a short proof, as opposed to the original idea of applying the fixed-point theorem to mere unprovability. The proof has very much the same flavor as the proof of the incompleteness theorem. Interestingly, it dates from the same year as the construction, due to Rosser, that eliminates the use of ω -consistency in the first Incompleteness Theorem; like the Speed-up Theorem of Gödel, Rosser’s construction exploits the issue of short and long proofs.

  Gödel never submitted a proof for the Speed-up Theorem. Over the years several related proofs were published, but the first full proof of Gödel’s original result was given only in 1994 by Sam Buss in his ‘On Gödel’s theorems on lengths of proofs I: Number of lines and speedups for arithmetic.’127

  Sign up to read

  Learn more about book
• 

  eBook - ePub

  The Loom of God

  Tapestries of Mathematics and Mysticism

  • Clifford A. Pickover(Author)
  • 2010(Publication Date)
  • Union Square & Co.

    (Publisher)

  You can’t disbelieve something if you don’t even know what it is you’re not believing in. Likewise, you can’t believe in something if you don’t even know what it is you’re believing in. This makes everyone an agnostic until or unless a definition is agreed upon.

  —Mark Hopkins

  I could not find significant information in the philosophical or mathematical literature regarding the interpretation of Goedel’s proof of God. Author Hao Wang expressed no opinion or help to the reader in interpreting the proof. In fact, he states enigmatically, “I am only including [the proof] for some measure of completeness, and shall, out of ignorance, make no comments on it.” I therefore consulted various mathematicians and philosophers on the Internet for their opinions. If you don’t understand all of their comments, don’t worry. At the least, they will give you the flavor of how current researchers in philosophy and mathematics express their thoughts on complex theomatic areas. I have not eliminated repetitious information so that you can get a feel for the overlap of current, common thinking among respondents.

  Ivan Ordonez Reinoso, a doctoral student in Computers and Information Sciences at the Ohio State University, comments:

  The proof has an obvious problem in that it only shows the existence of a mathematical object with the property “God-like” as defined in the proof. There is no relation to the real world; it is like proving that there is no last cardinal number. Furthermore, the proof does not exclude the possibility of the existence of an infinite number of disjoint objects all with the property “God-like.”

  Mike Miller from Western Illinois University comments:

  Here’s the easiest place at which the proof may be ripped apart. Now here is it shown that x has to exist, except by this definition. Thus, we must be shown why

  Sign up to read

  Learn more about book
• 

  eBook - ePub

  Engaging Putnam

  • James Conant, Sanjit Chakraborty(Authors)
  • 2022(Publication Date)
  • De Gruyter

    (Publisher)

  Fulfillability, Instability, and Incompleteness

  Roy T. Cook

  Abstract

  The purpose of this essay is to publicize, and to a more limited extent, further develop, an alternate proof of Gödel’s incompleteness theorem due to Saul Kripke, based on a notion called fulfillability. Kripke’s work has been publicized in talks, but at the time of writing this essay the only published discussion of the material appears in Putnam (2000). Here, a more detailed and more accessible overview of the approach is given, centered on a novel generalization – the Instability Theorem. After setting up the technical machinery and demonstrating the Instability Theorem, we prove both the first incompleteness theorem and Lob’s theorem. We conclude with some observations regarding potential directions for future research along these lines.

  I  Two Incompleteness Proofs

  As is well known, Kurt Gödel provided the first proof of the incompleteness of Peano arithmetic (and consistent extensions of the same).1 His tools were primarily syntactic/proof-theoretic. In the 1980s, Saul Kripke formulated an alternative proof of the (first) incompleteness theorem. His tools were primarily semantic/model-theoretic.

  Kripke’s proof is far less well known, however, and the reason is simple: Kripke has never published the proof.2 Hilary Putnam, however, published a version of Kripke’s proof in a paper titled “Non-standard models and Kripke’s Proof of the Gödel theorem”.3 His reasons for publishing a paper devoted to someone else’s result are not hard to decipher: He notes in a footnote that:

  This paper is developed from a lecture to the Department of Computer Science at Peking University, June 1984. I have decided to publish this lecture at this time because Kripke’s proof is still unpublished.4

  Sadly, despite Putnam’s efforts, the proof is still not well known beyond the small group of specialists working on completeness proofs and/or non-standard models of arithmetic. In fact, I am aware of only three other logicians that have investigated the main tool used in the proof – the notion of fulfillability – in any depth: Joseph Quinsey, Alex Wilkie, and Stella Moon.5 Of these, only the first directly investigates the use of fulfillability in proving incompleteness (although Moon’s thesis does contain a brief overview of Putnam’s paper), and only the second is “officially” published (the other two are final theses for graduate degrees). This is unfortunate, since the methods mobilized in the proof are not only beautiful and astonishingly simple in and of themselves, but they also promise to provide powerful new methods for proving all sorts of metatheoretic results regarding arithmetic and related systems.6 With this in mind, I will here attempt to complete the task begun by Putnam: to draw more attention to Kripke’s proof of Gödel’s (first) incompleteness theorem and, perhaps more importantly, to the novel method he uses in the proof. I will not merely re-present the extremely simple and clear version of the incompleteness proof already given by Putnam, however. Instead, I will attempt a more general introduction to the methods by proving a very general theorem regarding fulfillability – what I will call the Instability Theorem

  Sign up to read

  Learn more about book
• 

  eBook - ePub

  From Frege to Gödel

  A Source Book in Mathematical Logic, 1879-1931

  • Jean van Heijenoort(Author)
  • 2002(Publication Date)
  • Harvard University Press

    (Publisher)

  Some metamathematical results on completeness andconsistency,On formally undecidable propositions of Principia mathematica and related systems I ,and On completeness and consistency

  KURT GÖDEL

  (1930b, 1931 , and 1931a )

  The main paper below (1931 ), which was to have such an impact on modern logic, was received for publication on 17 November 1930 and published early in 1931. An abstract (1930b ) had been presented on 23 October 1930 to the Vienna Academy of Sciences by Hans Hahn.

  Gödel’s results are now accessible in many publications, but his original paper has not lost any of its value as a guide. It is clearly written and does not assume any previous result for its main line of argument. It is, moreover, rich in interesting details. We now give some indications of its contents and structure.

  Section 1 is an informal presentation of the main argument and can be read by the nonmathematician; it shows how the argument, by dealing with the proposition that states of itself “I am not provable”, instead of the proposition that states of itself “I am not true”, skirts the Liar paradox, without falling into it. Gödel also brings to light the relation that his argument bears to Cantor’s diagonal procedure and Richard’s paradox (Herbrand, on pages 626–628 below, and Weyl (1949 , pp. 219–235) particularly stress this aspect of Gödel’s argument; see also above, p. 439).

  Section 2, the longest, is the proof of Theorem VI. The theorem states that in a formal system satisfying certain precise conditions there is an undecidable proposition, that is, a proposition such that neither the proposition itself nor its negation is provable in the system. Before coming to the core of the argument, Gödel takes a number of preparatory steps:

  (1) A precise description of the system P with which he is going to work. The variables are distinguished as to their types and they range over the natural numbers (type 1), classes of natural numbers (type 2), classes of classes of natural numbers (type 3), and so forth. The logical axioms are equivalent to the logic of Principia mathematica without the ramified theory of types. The arithmetic axioms are Peano’s, properly transcribed. The identification of the individuals with the natural numbers and the adjunction of Peano’s axioms (instead of their derivation, as in Principia

  Sign up to read

  Learn more about book