« Über формальный unentscheidbare Sätze дер Principia Mathematica унд verwandter Systeme I » ( « О Формально Неразрешимые пропозиции Principia Mathematica и родственных систем I ») представляет собой документ , в математической логике на Курта Гёделя . Датированный 17 ноября 1930 года, он был первоначально опубликован на немецком языке в сборнике Monatshefte für Mathematik 1931 года . Несколько английских переводов вышли в печати, и эта статья была включена в два сборника классических статей по математической логике. Статья содержит теоремы Гёделя о неполноте , которые теперь являются фундаментальными результатами в логике, которые имеют большое значение для доказательств непротиворечивости.по математике. Эта статья также известна введением новых методов, изобретенных Гёделем для доказательства теорем о неполноте.
Краткое описание и основные результаты
Основными установленными результатами являются первая и вторая теоремы Гёделя о неполноте , оказавшие огромное влияние на область математической логики . Они появляются в статье как теоремы VI и XI соответственно.
Чтобы доказать эти результаты, Гёдель ввел метод, теперь известный как нумерация Гёделя . В этом методе каждому предложению и формальному доказательству в арифметике первого порядка присваивается конкретное натуральное число. Гёдель показывает, что многие свойства этих доказательств могут быть определены в рамках любой теории арифметики, которая достаточно сильна для определения примитивных рекурсивных функций . (Современная терминология для рекурсивных функций и примитивных рекурсивных функций еще не была установлена, когда статья была опубликована; Гёдель использовал слово rekursiv («рекурсивный») для того, что теперь известно как примитивно-рекурсивные функции.) Метод нумерации Гёделя с тех пор существует. стали обычным явлением в математической логике.
Поскольку метод нумерации Гёделя был новым и во избежание какой-либо двусмысленности, Гёдель представил список из 45 явных формальных определений примитивных рекурсивных функций и отношений, используемых для манипулирования числами Гёделя и их проверки. Он использовал их, чтобы дать явное определение формулы Bew ( x ), которая истинна тогда и только тогда, когда x является гёделевским числом предложения φ и существует натуральное число, которое является числом Гёделя доказательства φ. Название этой формулы происходит от немецкого слова Beweis , обозначающего доказательство.
Второй новой техникой, изобретенной Геделем в этой статье, было использование самореференциальных предложений. Гёдель показал, что классические парадоксы самоотнесения, такие как « Это утверждение ложно », могут быть преобразованы в формальные арифметические предложения, ссылающиеся на самих себя. Неформально предложение, использованное для доказательства первой теоремы Гёделя о неполноте, гласит: «Это утверждение не доказуемо». Тот факт, что такая ссылка на себя может быть выражена в рамках арифметики, не был известен до появления статьи Гёделя; Независимая работа Альфреда Тарского по его теореме о неопределимости проводилась примерно в то же время, но публиковалась только в 1936 году.
В сноске 48a Гёдель заявил, что запланированная вторая часть статьи установит связь между доказательствами непротиворечивости и теорией типов, но Гёдель не опубликовал вторую часть статьи до своей смерти. Однако его статья 1958 года в « Диалектике» показала, как можно использовать теорию типов для доказательства непротиворечивости арифметики.
Опубликованные английские переводы
При его жизни было напечатано три английских перевода статьи Гёделя, но процесс не прошел без труда. Первый английский перевод был сделан Бернардом Мельцером; он был опубликован в 1963 году как отдельный труд издательством Basic Books, с тех пор переиздан Dover и перепечатан Хокингом ( God Created the Integer , Running Press, 2005: 1097ff). Версия Мельтцера, которую Раймонд Смуллян назвал «хорошим переводом», была подвергнута отрицательной оценке Стефаном Бауэр-Менгельбергом (1966). Согласно биографии Гёделя Доусоном (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ödel'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 Afterward 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ödel: 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ödel favored was that by Jean van Heijenoort ... In the preface to the volume van Heijenoort noted that Gödel was one of four authors who had personally read and approved the translations of his works.
This approval process was laborious. Gödel introduced changes to his text of 1931, and negotiations between the men were "protracted": "Privately van Heijenoort declared that Gödel was the most doggedly fastidious individual he had ever known." Between them they "exchanged a total of seventy letters and met twice in Gödel'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ödel'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ödel delivered them at the Institute for Advanced Study in Princeton N.J. in 1934. Two pages of errata and additional corrections by Gödel were added by Davis to this version. This version is also notable because in it Gödel first describes the Herbrand suggestion that gave rise to the (general, i.e. Herbrand-Gödel) form of recursion.
Смотрите также
Рекомендации
- 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. (Sep., 1966), pp. 484–494.
- Alonzo Church (1972). Review of A Source Book in Mathematical Logic 1879–1931. The Journal of Symbolic Logic, Vol. 37, No. 2. (Jun., 1972), p. 405.
- Martin Davis, ed. (1965). The Undecidable: Basic Papers on Undecidable Propositions, Unsolvable Problems and Computable Functions, Raven, New York. Reprint, Dover, 2004. ISBN 0-486-43228-9.
- Martin Davis, (2000). Engines of Logic: Mathematics and the Origin of the Computer, W. w. Norton & Company, New York. ISBN 0-393-32229-7 pbk.
- Kurt Gödel (1931), "Über formal unentscheidbare Sätze der Principia Mathematica und verwandter Systeme, I." Monatshefte für Mathematik und Physik 38: 173-198. DOI 10.1007/BF01700692 Available online via SpringerLink.
- Kurt Gödel (1958). "Über eine bisher noch nicht benüzte Erweiterung des finiten Standpunktes." Dialectica v. 12, pp. 280–287. Reprinted in English translation in Gödel's Collected Works, vol II, Soloman Feferman et al., eds. Oxford University Press, 1990.
- Jean van Heijenoort, ed. (1967). From Frege to Gödel: A Source Book on Mathematical Logic 1879–1931. Harvard University Press.
- Bernard Meltzer (1962). On Formally Undecidable Propositions of Principia Mathematica and Related Systems. Translation of the German original by Kurt Gödel, 1931. Basic Books, 1962. Reprinted, Dover, 1992. ISBN 0-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. (Mar., 1966), pp. 319–322.
- John W. Dawson, (1997). Logical Dilemmas: The Life and Work of Kurt Gödel, A. K. Peters, Wellesley, MA. ISBN 1-56881-256-6.
Внешние ссылки
- "On formally undecidable propositions of Principia Mathematica and related systems I." Translated by Martin Hirzel, November 27, 2000.
- "Über formal unentscheidbare Sätze der Principia Mathematica und verwandter Systeme I" on Wilhelm K. Essler's (Prof. em. of Logic, Goethe-Universität Frankfurt am Main) webpage