[{"@context":"http:\/\/schema.org\/","@type":"BlogPosting","@id":"https:\/\/wiki.edu.vn\/en\/wiki7\/on-formally-undecidable-propositions-of-principia-mathematica-and-related-systems\/#BlogPosting","mainEntityOfPage":"https:\/\/wiki.edu.vn\/en\/wiki7\/on-formally-undecidable-propositions-of-principia-mathematica-and-related-systems\/","headline":"On Formally Undecidable Propositions of Principia Mathematica and Related Systems","name":"On Formally Undecidable Propositions of Principia Mathematica and Related Systems","description":"before-content-x4 1931 paper by Kurt G\u00f6del after-content-x4 “\u00dcber formal unentscheidbare S\u00e4tze der Principia Mathematica und verwandter Systeme I” (“On Formally","datePublished":"2016-09-03","dateModified":"2016-09-03","author":{"@type":"Person","@id":"https:\/\/wiki.edu.vn\/en\/wiki7\/author\/lordneo\/#Person","name":"lordneo","url":"https:\/\/wiki.edu.vn\/en\/wiki7\/author\/lordneo\/","image":{"@type":"ImageObject","@id":"https:\/\/secure.gravatar.com\/avatar\/c9645c498c9701c88b89b8537773dd7c?s=96&d=mm&r=g","url":"https:\/\/secure.gravatar.com\/avatar\/c9645c498c9701c88b89b8537773dd7c?s=96&d=mm&r=g","height":96,"width":96}},"publisher":{"@type":"Organization","name":"Enzyklop\u00e4die","logo":{"@type":"ImageObject","@id":"https:\/\/wiki.edu.vn\/wiki4\/wp-content\/uploads\/2023\/08\/download.jpg","url":"https:\/\/wiki.edu.vn\/wiki4\/wp-content\/uploads\/2023\/08\/download.jpg","width":600,"height":60}},"image":{"@type":"ImageObject","@id":"https:\/\/wiki.edu.vn\/wiki4\/wp-content\/uploads\/2023\/08\/download.jpg","url":"https:\/\/wiki.edu.vn\/wiki4\/wp-content\/uploads\/2023\/08\/download.jpg","width":100,"height":100},"url":"https:\/\/wiki.edu.vn\/en\/wiki7\/on-formally-undecidable-propositions-of-principia-mathematica-and-related-systems\/","wordCount":1729,"articleBody":"     (adsbygoogle = window.adsbygoogle || []).push({});before-content-x41931 paper by Kurt G\u00f6del       (adsbygoogle = window.adsbygoogle || []).push({});after-content-x4“\u00dcber formal unentscheidbare S\u00e4tze der Principia Mathematica und verwandter Systeme I” (“On Formally Undecidable Propositions of Principia Mathematica and Related Systems I“) is a paper in mathematical logic by Kurt G\u00f6del.  Submitted November 17, 1930, it was originally published in German in the 1931 volume of Monatshefte f\u00fcr Mathematik.  Several English translations have appeared in print, and the paper has been included in two collections of classic mathematical logic papers. The paper contains G\u00f6del’s incompleteness theorems, now fundamental results in logic that have many implications for consistency proofs in mathematics. The paper is also known for introducing new techniques that G\u00f6del invented to prove the incompleteness theorems.Table of Contents       (adsbygoogle = window.adsbygoogle || []).push({});after-content-x4Outline and key results[edit]Published English translations[edit]References[edit]External links[edit]Outline and key results[edit]The main results established are G\u00f6del’s first and second incompleteness theorems, which have had an enormous impact on the field of mathematical logic. These appear as theorems VI and XI, respectively, in the paper.In order to prove these results, G\u00f6del introduced a method now known as G\u00f6del numbering. In this method, each sentence and formal proof in first-order arithmetic is assigned a particular natural number. G\u00f6del shows that many properties of these proofs can be defined within any theory of arithmetic that is strong enough to define the primitive recursive functions. (The contemporary terminology for recursive functions and primitive recursive functions had not yet been established when the paper was published; G\u00f6del used the word rekursiv (“recursive”) for what are now known as primitive recursive functions.) The method of G\u00f6del numbering has since become common in mathematical logic.Because the method of G\u00f6del numbering was novel, and to avoid any ambiguity, G\u00f6del presented a list of 45 explicit formal definitions of primitive recursive functions and relations used to manipulate and test G\u00f6del numbers.  He used these to give an explicit definition of a formula Bew(x) that is true if and only if x is the G\u00f6del number of a sentence \u03c6 and there exists a natural number that is the G\u00f6del number of a proof of \u03c6. The name of this formula derives from Beweis, the German word for proof.A second new technique invented by G\u00f6del in this paper was the use of self-referential sentences. G\u00f6del showed that the classical paradoxes of self-reference, such as “This statement is false”, can be recast as self-referential formal sentences of arithmetic. Informally,the sentence employed to prove G\u00f6del’s first incompleteness theorem says “This statement is not provable.” The fact that such self-reference can be expressed within arithmetic was not known until G\u00f6del’s paper appeared; independent work of Alfred Tarski on his indefinability theorem was conducted around the same time but not published until 1936.       (adsbygoogle = window.adsbygoogle || []).push({});after-content-x4In footnote 48a, G\u00f6del stated that a planned second part of the paper would establish a link between consistency proofs and type theory (hence the “I” at the end of the paper’s title, denoting the first part), but G\u00f6del did not publish a second part of the paper before his death. His 1958 paper in Dialectica did, however, show how type theory can be used to give a consistency proof for arithmetic.Published English translations[edit]During his lifetime three English translations of G\u00f6del’s paper were printed, but the process was not without difficulty.  The first English translation was by Bernard Meltzer; it was published in 1963 as a standalone work by Basic Books and has since been reprinted by Dover and reprinted by Hawking (God Created the Integers, Running Press, 2005:1097ff). The Meltzer version\u2014described by Raymond Smullyan as a ‘nice translation’\u2014was adversely reviewed by Stefan Bauer-Mengelberg (1966).  According to Dawson’s biography of G\u00f6del (Dawson 1997:216),Fortunately, the Meltzer translation was soon supplanted by a better one prepared by Elliott Mendelson for Martin Davis’s anthology The Undecidable; but it too was not brought to G\u00f6del’s attention until almost the last minute, and the new translation was still not wholly to his liking … when informed that there was not time enough to consider substituting another text, he declared that Mendelson’s translation was ‘on the whole very good’ and agreed to its publication.3 [3\u00a0Afterward he would regret his compliance, for the published volume was marred throughout by sloppy typography and numerous misprints.]The translation by Elliott Mendelson appears in the collection The Undecidable (Davis 1965:5ff).  This translation also received a harsh review by Bauer-Mengelberg (1966), who in addition to giving a detailed list of the typographical errors also described what he believed to be serious errors in the translation.A translation by Jean van Heijenoort appears in the collection From Frege to G\u00f6del: A Source Book in Mathematical Logic (van Heijenoort 1967). A review by Alonzo Church (1972) described this as “the most careful translation that has been made” but also gave some specific criticisms of it. Dawson (1997:216) notes:The translation G\u00f6del favored was that by Jean van Heijenoort … In the preface to the volume van Heijenoort noted that G\u00f6del was one of four authors who had personally read and approved the translations of his works.This approval process was laborious. G\u00f6del introduced changes to his text of 1931, and negotiations between the men were “protracted”: “Privately van Heijenoort declared that G\u00f6del was the most doggedly fastidious individual he had ever known.” Between them they  “exchanged a total of seventy letters and met twice in G\u00f6del’s office in order to resolve questions concerning subtleties in the meanings and usage of German and English words.” (Dawson 1997:216-217).Although not a translation of the original paper, a very useful 4th version exists that “cover[s] ground quite similar to that covered by Godel’s original 1931 paper on undecidability” (Davis 1952:39), as well as G\u00f6del’s own extensions of and commentary on the topic. This appears as On Undecidable Propositions of Formal Mathematical Systems (Davis 1965:39ff) and represents the lectures as transcribed by Stephen Kleene and J. Barkley Rosser while G\u00f6del delivered them at the Institute for Advanced Study in Princeton, New Jersey in 1934. Two pages of errata and additional corrections by G\u00f6del were added by Davis to this version. This version is also notable because in it G\u00f6del first describes the Herbrand suggestion that gave rise to the (general, i.e. Herbrand-G\u00f6del) form of recursion.References[edit]Stefan Bauer-Mengelberg (1966). Review of The Undecidable: Basic Papers on Undecidable Propositions, Unsolvable problems and Computable Functions. The Journal of Symbolic Logic, Vol. 31, No. 3. (September 1966), pp.\u00a0484\u2013494.Alonzo Church (1972). Review of A Source Book in Mathematical Logic 1879\u20131931. The Journal of Symbolic Logic, Vol. 37, No. 2. (June 1972), p.\u00a0405.Martin Davis, ed. (1965).  The Undecidable: Basic Papers on Undecidable Propositions, Unsolvable Problems and Computable Functions, Raven, New York. Reprint, Dover, 2004. ISBN\u00a00-486-43228-9.Martin Davis, (2000). Engines of Logic: Mathematics and the Origin of the Computer, W. W. Norton & Company, New York. ISBN\u00a00-393-32229-7 pbk.Kurt G\u00f6del (1931), “\u00dcber formal unentscheidbare S\u00e4tze der Principia Mathematica und verwandter Systeme I”. Monatshefte f\u00fcr Mathematik und Physik 38: 173\u2013198.  doi:10.1007\/BF01700692. Available online via SpringerLink.Kurt G\u00f6del (1958). “\u00dcber eine bisher noch nicht ben\u00fczte Erweiterung des finiten Standpunktes”. Dialectica v. 12, pp.\u00a0280\u2013287.  Reprinted in English translation in G\u00f6del’s Collected Works, vol II, Soloman Feferman et al., eds. Oxford University Press, 1990.Jean van Heijenoort, ed. (1967). From Frege to G\u00f6del: A Source Book on Mathematical Logic 1879\u20131931. Harvard University Press.Bernard Meltzer (1962). On Formally Undecidable Propositions of Principia Mathematica and Related Systems. Translation of the German original by Kurt G\u00f6del, 1931. Basic Books, 1962. Reprinted, Dover, 1992. ISBN\u00a00-486-66980-7.Raymond Smullyan (1966). Review of On Formally Undecidable Propositions of Principia Mathematica and Related Systems. The American Mathematical Monthly, Vol. 73, No. 3. (March 1966), pp.\u00a0319\u2013322.John W. Dawson, (1997). Logical Dilemmas: The Life and Work of Kurt G\u00f6del, A. K. Peters, Wellesley, Massachusetts. ISBN\u00a01-56881-256-6.External links[edit]     (adsbygoogle = window.adsbygoogle || []).push({});after-content-x4"},{"@context":"http:\/\/schema.org\/","@type":"BreadcrumbList","itemListElement":[{"@type":"ListItem","position":1,"item":{"@id":"https:\/\/wiki.edu.vn\/en\/wiki7\/#breadcrumbitem","name":"Enzyklop\u00e4die"}},{"@type":"ListItem","position":2,"item":{"@id":"https:\/\/wiki.edu.vn\/en\/wiki7\/on-formally-undecidable-propositions-of-principia-mathematica-and-related-systems\/#breadcrumbitem","name":"On Formally Undecidable Propositions of Principia Mathematica and Related Systems"}}]}]