О формально неразрешимых предложениях 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-я версия, которая «охватывает основы, весьма схожие с тем, которые были раскрыты в оригинальной статье Геделя о неразрешимости 1931 года» (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» на веб-странице Вильгельма К. Эсслера (профессора логики, Университет Гете, Франкфурт-на-Майне)