О формально неразрешимых предложениях Principia Mathematica и родственных систем. On Formally Undecidable Propositions of Principia Mathematica and Related Systems

Эта статья про газету. По поводу теорем, доказанных в этой статье, см. Теоремы Гёделя о неполноте .

« Über формальный unentscheidbare Sätze дер Principia Mathematica унд verwandter Systeme I » ( « О Формально Неразрешимые пропозиции Principia Mathematica и родственных систем I ») представляет собой документ , в математической логике на Курта Гёделя . Опубликовано 17 ноября 1930, она первоначально была опубликована на немецком языке в 1931 объем Monatshefte für Mathematik . Несколько английских переводов вышли в печати, и эта статья была включена в два сборника классических статей по математической логике. Статья содержит теоремы Гёделя о неполноте , которые теперь являются фундаментальными результатами в логике, которые имеют много значений для доказательств непротиворечивости в математике. Эта статья также известна введением новых методов, изобретенных Гёделем для доказательства теорем о неполноте.

Краткое описание и основные результаты

Основными установленными результатами являются первая и вторая теоремы Гёделя о неполноте , оказавшие огромное влияние на область математической логики . Они появляются в статье как теоремы 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),

К счастью, перевод Мельцера вскоре был заменен лучшим переводом, подготовленным Эллиоттом Мендельсоном для антологии Мартина Дэвиса « Неразрешимое» ; но он также не был доведен до сведения Гёделя почти до последней минуты, и новый перевод все еще не полностью ему нравился ... когда ему сообщили, что у него недостаточно времени, чтобы подумать о замене другого текста, он заявил, что перевод Мендельсона был « в целом очень хорошо »и согласился на его публикацию. 3 [ 3 Впоследствии он будет сожалеть о своем согласии, поскольку опубликованный том был испорчен неряшливой типографикой и многочисленными опечатками.]

Перевод Эллиотта Мендельсона появляется в сборнике «Неразрешимое» (Davis 1965: 5ff). Этот перевод также получил резкую рецензию Бауэра-Менгельберга (1966), который, помимо подробного списка типографских ошибок, также описал то, что он считал серьезными ошибками в переводе.

Перевод Жана ван Хейеноорта появляется в сборнике « От Фреге до Гёделя: справочник по математической логике» (van Heijenoort, 1967). В обзоре Алонзо Чёрча (1972) это описывается как «наиболее тщательный перевод из всех, что были сделаны», но в нем также содержится некоторая конкретная критика. Доусон (1997: 216) отмечает:

Гедель одобрил перевод, сделанный Жаном ван Хейенуртом ... В предисловии к тому ван Хейенорт отметил, что Гедель был одним из четырех авторов, которые лично читали и одобряли переводы его произведений.

Этот процесс утверждения был трудоемким. Гёдель внес изменения в свой текст 1931 года, и переговоры между людьми были «затянутыми»: «В частном порядке ван Хейенорт заявил, что Гёдель был самым упрямо привередливым человеком, которого он когда-либо знал». Между собой они «обменялись в общей сложности семьюдесятью письмами и дважды встречались в кабинете Гёделя, чтобы разрешить вопросы, касающиеся тонкостей значений и использования немецких и английских слов». (Доусон 1997: 216-217).

Хотя это и не является переводом оригинальной статьи, существует очень полезная 4-я версия, которая «покрывает основу, очень похожую на ту, что была охвачена оригинальной статьей Гёделя 1931 года о неразрешимости» (Davis 1952: 39), а также собственными расширениями Гёделя и комментарий по теме. Это выглядит как « О неразрешимых предложениях формальных математических систем» (Davis 1965: 39ff) и представляет собой лекции, записанные Стивеном Клини и Дж. Баркли Россером, в то время как Гедель читал их в Институте перспективных исследований в Принстоне, штат Нью-Джерси, в 1934 году. Две страницы исправленных ошибок. и дополнительные исправления Гёделя были добавлены Дэвисом к этой версии. Эта версия также примечательна тем, что в ней Гёдель сначала описывает предложение Эрбранда, которое привело к (общей, т. Е. Herbrand-Gödel) форме рекурсии .

Смотрите также

использованная литература

  • Стефан Бауэр-Менгельберг (1966). Обзор «Неразрешимых: основные статьи о неразрешимых предложениях, неразрешимых задачах и вычислимых функциях». Журнал символической логики , Vol. 31, No. 3. (сентябрь 1966 г.), стр. 484–494.
  • Церковь Алонсо (1972 г.). Рецензия на сборник материалов по математической логике 1879–1931 гг. Журнал символической логики , Vol. 37, No. 2 (июнь 1972 г.), стр. 405.
  • Мартин Дэвис , изд. (1965). Неразрешимое: основные статьи о неразрешимых предложениях, неразрешимых проблемах и вычислимых функциях , Рэйвен, Нью-Йорк. Перепечатка, Довер, 2004. ISBN  0-486-43228-9 .
  • Мартин Дэвис , (2000). Двигатели логики: математика и происхождение компьютера , W. w. Norton & Company, Нью-Йорк. ISBN  0-393-32229-7 pbk.
  • Курт Гёдель (1931), «Über form unentscheidbare Sätze der Principia Mathematica und Verwandter Systeme, I.» Monatshefte für Mathematik und Physik 38 : 173-198. DOI 10.1007 / BF01700692 Доступно онлайн через SpringerLink.
  • Курт Гёдель (1958). "Über eine bisher noch nicht benüzte Erweiterung des finiten Standpunktes". Dialectica v. 12, pp. 280–287. Перепечатано в английском переводе в Собрании сочинений Гёделя , том II, Соломан Феферман и др., Ред. Издательство Оксфордского университета, 1990.
  • Жан ван Хейеноорт , изд. (1967). От Фреге до Гёделя: Справочник по математической логике 1879–1931 . Издательство Гарвардского университета.
  • Бернард Мельцер (1962). О формально неразрешимых предложениях Principia Mathematica и родственных систем. Перевод немецкого оригинала Курта Гёделя, 1931. Basic Books, 1962. Перепечатано, Дувр, 1992. ISBN  0-486-66980-7 .
  • Раймонд Смуллян (1966). Обзор формально неразрешимых утверждений Principia Mathematica и родственных систем. Американский математический ежемесячник , Vol. 73, No. 3. (март, 1966), стр. 319–322.
  • Джон У. Доусон , (1997). Логические дилеммы: жизнь и творчество Курта Гёделя , А. К. Петерс, Уэлсли, Массачусетс. ISBN  1-56881-256-6 .

внешние ссылки