О формально неразрешимых предложениях Principia Mathematica и родственных системах

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

План и ключевые результаты

Гёделя Основными установленными результатами являются первая и вторая теоремы о неполноте , оказавшие огромное влияние на область математической логики . В статье они фигурируют как теоремы VI и XI соответственно.

Чтобы доказать эти результаты, Гёдель ввел метод, ныне известный как нумерация Гёделя . В этом методе каждому предложению и формальному доказательству в арифметике первого порядка присваивается определенное натуральное число. Гёдель показывает, что многие свойства этих доказательств могут быть определены в рамках любой теории арифметики, достаточно сильной для определения примитивно-рекурсивных функций . (Современная терминология для рекурсивных функций и примитивно-рекурсивных функций еще не была установлена на момент публикации статьи; Гёдель использовал слово rekursiv («рекурсивный») для обозначения того, что теперь известно как примитивно-рекурсивные функции.) С тех пор метод нумерации Гёделя появился. стали обычным явлением в математической логике.

Поскольку метод нумерации Гёделя был новым и во избежание какой-либо двусмысленности, Гёдель представил список из 45 явных формальных определений примитивно-рекурсивных функций и отношений, используемых для манипулирования и проверки чисел Гёделя. Он использовал их, чтобы дать явное определение формулы $Bew(x)$ , которая верна тогда и только тогда, когда $x$ является числом Гёделя предложения $φ$ и существует натуральное число, которое является числом Гёделя доказательства $φ$ . Название этой формулы происходит от Beweis , немецкого слова, обозначающего доказательство.

Второй новый метод, изобретенный Гёделем в этой статье, заключался в использовании самореферентных предложений. Гёдель показал, что классические парадоксы самореференции, такие как « Это утверждение ложно », можно преобразовать в самореферентные формальные арифметические предложения. Неофициально,В предложении, использованном для доказательства первой теоремы Гёделя о неполноте, говорится: «Это утверждение недоказуемо». Тот факт, что такая ссылка на себя может быть выражена в арифметике, не был известен до появления статьи Гёделя; независимая работа Альфреда Тарского над его теоремой неопределимости была проведена примерно в то же время, но опубликована только в 1936 году.

В сноске 48a Гёдель заявил, что запланированная вторая часть статьи установит связь между доказательствами непротиворечивости и теорией типов (отсюда и буква «I» в конце названия статьи, обозначающая первую часть), но Гёдель не опубликовал вторую часть статьи перед смертью. Однако его статья 1958 года в журнале «Диалектика» показала, как теорию типов можно использовать для доказательства непротиворечивости арифметики.

Опубликованные английские переводы

При его жизни было напечатано три английских перевода статьи Гёделя, но этот процесс оказался непростым. Первый английский перевод был сделан Бернардом Мельцером ; он был опубликован в 1963 году как отдельная работа издательством Basic Books и с тех пор был переиздан Дувром и переиздан Хокингом ( God Created the Integers , Running Press, 2005:1097ff). Версия Мельцера, которую Рэймонд Смалльян назвал «хорошим переводом», получила негативную оценку со стороны Стефана Бауэра-Менгельберга (1966). Согласно Доусона биографии Гёделя (Dawson 1997:216),

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

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

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

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

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

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

Ссылки

Стефан Бауэр-Менгельберг (1966). Обзор книги «Неразрешимое: основные статьи о неразрешимых предложениях, неразрешимых проблемах и вычислимых функциях». Журнал символической логики , Vol. 31, № 3. (сентябрь 1966 г.), стр. 484–494.
Церковь Алонсо (1972 г.). Обзор справочника по математической логике 1879–1931 гг. Журнал символической логики , Vol. 37, № 2. (июнь 1972 г.), с. 405.
Мартин Дэвис , изд. (1965). Неразрешимое: основные статьи о неразрешимых предложениях, неразрешимых проблемах и вычислимых функциях , Рэйвен, Нью-Йорк. Перепечатка, Дувр, 2004 г. ISBN 0-486-43228-9 .
Мартин Дэвис , (2000). Логические машины: математика и происхождение компьютера , WW Norton & Company, Нью-Йорк. ISBN 0-393-32229-7 пбк.
Курт Гёдель (1931), «О формально неразрешимых теоремах Principia Mathematica и родственных систем I». Ежемесячные выпуски по математике и физике 38 : 173–198. дои : 10.1007/BF01700692 . Доступно онлайн через SpringerLink.
Курт Гёдель (1958). «О неиспользованном до сих пор расширении конечной точки зрения». Диалектика в. 12, стр. 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, № 3. (март 1966 г.), стр. 319–322.
Джон В. Доусон (1997). Логические дилеммы: жизнь и творчество Курта Гёделя , А. К. Питерса, Уэлсли, Массачусетс. ISBN 1-56881-256-6 .

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

«О формально неразрешимых положениях Principia Mathematica и родственных им систем I» . Перевод Мартина Хирзеля, 27 ноября 2000 г.
«О формально неразрешимых теоремах Principia Mathematica и связанных с ними систем I» на веб-странице Вильгельма К. Эсслера (профессора логики, Университет Гете, Франкфурт-на-Майне)