WikiDer > Вторая проблема Гильберта - Википедия

Hilberts second problem - Wikipedia

В математика, Вторая проблема Гильберта был поставлен Дэвид Гильберт в 1900 году как один из его 23 задачи. Он требует доказательства того, что арифметика последовательный - без внутренних противоречий. Гильберт заявил, что аксиомы, которые он рассматривал для арифметики, были теми, которые приведены в Гильберт (1900), которые включают аксиому полноты второго порядка.

В 1930-е гг. Курт Гёдель и Герхард Гентцен доказанные результаты, проливающие новый свет на проблему. Некоторые считают, что теоремы Гёделя дают отрицательное решение проблемы, в то время как другие рассматривают доказательство Гентцена как частичное положительное решение.

Проблема Гильберта и ее интерпретация

В одном английском переводе Гильберт спрашивает:

«Когда мы занимаемся исследованием основ науки, мы должны создать систему аксиом, которая содержит точное и полное описание отношений, существующих между элементарными идеями этой науки ... Но прежде всего я хочу обозначить следующие как наиболее важные среди многочисленных вопросов, которые могут быть заданы относительно аксиом: доказать, что они не противоречат друг другу, то есть что определенное количество логических шагов, основанных на них, никогда не может привести к противоречивым результатам. , доказательство совместимости аксиом может быть выполнено путем построения подходящего числового поля, такого, что аналогичные отношения между числами этого поля соответствуют геометрическим аксиомам. ... С другой стороны, нужен прямой метод для определения доказательство совместимости аксиом арифметики ».[1]

Утверждение Гильберта иногда понимают неправильно, потому что под «арифметическими аксиомами» он имел в виду не систему, эквивалентную арифметике Пеано, а более сильную систему с аксиомой полноты второго порядка. Система, которую Гильберт запросил для доказательства полноты, больше похожа на арифметика второго порядка чем арифметика Пеано первого порядка.

В качестве современной интерпретации положительное решение второго вопроса Гильберта, в частности, обеспечило бы доказательство того, что Арифметика Пеано согласуется.

Есть много известных доказательств непротиворечивости арифметики Пеано, которые могут быть выполнены в сильных системах, таких как Теория множеств Цермело – Френкеля. Однако они не дают ответа на второй вопрос Гильберта, потому что тот, кто сомневается в непротиворечивости арифметики Пеано, вряд ли примет аксиомы теории множеств (которая намного сильнее), чтобы доказать ее непротиворечивость. Таким образом, удовлетворительный ответ на проблему Гильберта должен быть дан с использованием принципов, приемлемых для того, кто еще не верит в непротиворечивость PA. Такие принципы часто называют финитистический потому что они полностью конструктивны и не предполагают завершенной бесконечности натуральных чисел. Вторая теорема Гёделя о неполноте (см. Теоремы Гёделя о неполноте) устанавливает строгий предел того, насколько слабой может быть финитистическая система, в то же время доказывая непротиворечивость арифметики Пеано.

Теорема Гёделя о неполноте

Основная статья: Теоремы Гёделя о неполноте

Гёделя вторая теорема о неполноте показывает, что никакое доказательство непротиворечивости арифметики Пеано невозможно провести внутри самой арифметики Пеано. Эта теорема показывает, что если единственными приемлемыми процедурами доказательства являются те, которые могут быть формализованы в рамках арифметики, то на призыв Гильберта к доказательству непротиворечивости нельзя ответить. Однако, как объясняют Нагель и Ньюман (1958: 96–99), все еще есть место для доказательства, которое нельзя формализовать с помощью арифметики:

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

Доказательство непротиворечивости Гентцена

Основная статья: Доказательство непротиворечивости Гентцена

В 1936 году Генцен опубликовал доказательство непротиворечивости арифметики Пеано. Результат Генцена показывает, что доказательство непротиворечивости может быть получено в системе, которая намного слабее теории множеств.

Доказательство Генцена проводится путем присвоения каждому доказательству в арифметике Пеано порядковый номер, исходя из структуры доказательства, каждый из этих порядковых номеров меньше ε0.[3] Затем он доказывает трансфинитная индукция на этих ординалах, что никакое доказательство не может привести к противоречию. Метод, использованный в этом доказательстве, также может быть использован для доказательства вырезать устранение результат для Арифметика Пеано в более сильной логике, чем логика первого порядка, но само доказательство непротиворечивости может быть выполнено в обычной логике первого порядка с использованием аксиом примитивная рекурсивная арифметика и принцип трансфинитной индукции. Tait (2005) дает теоретико-игровую интерпретацию метода Генцена.

Доказательство непротиворечивости Генцена положило начало программе порядковый анализ в теории доказательств. В этой программе формальные теории арифметики или теории множеств задаются порядковые номера которые измеряют постоянство прочности теорий. Теория не сможет доказать непротиворечивость другой теории с более высоким теоретическим порядковым номером доказательства.

Современные взгляды на состояние проблемы

В то время как теоремы Гёделя и Гентцена теперь хорошо понимаются сообществом математической логики, не существует консенсуса относительно того, отвечают ли (и каким образом) эти теоремы второй проблеме Гильберта. Симпсон (1988: сек. 3) утверждает, что теорема Гёделя о неполноте показывает, что невозможно произвести конечные доказательства непротиворечивости сильных теорий. Kreisel (1976) утверждает, что хотя результаты Гёделя подразумевают невозможность получения конечного доказательства синтаксической непротиворечивости, семантические (в частности, второго порядка) аргументы могут быть использованы для получения убедительных доказательств непротиворечивости. Детлефсен (1990: стр. 65) утверждает, что теорема Гёделя не препятствует доказательству непротиворечивости, потому что ее гипотезы могут не применяться ко всем системам, в которых может быть проведено доказательство непротиворечивости. Доусон (2006: раздел 2) называет веру в то, что теорема Гёделя исключает возможность убедительного доказательства непротиворечивости, «ошибочным», ссылаясь на доказательство непротиворечивости, данное Гентценом, и более позднее доказательство, данное Гёделем в 1958 году.

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

Примечания

  1. ^ Из английского перевода М. Ньюсона, 1902 г., предоставленного http://aleph0.clarku.edu/~djoyce/hilbert/problems.html .
  2. ^ Подобная цитата с небольшими вариациями в формулировках появляется в издании 2001 г., стр.107-108, в редакции Дугласа Р. Хофстадтера, New York University Press, NY, ISBN 0-8147-5816-9.
  3. ^ Фактически, доказательство ставит каждому доказательству «обозначение» порядкового номера. Обозначение представляет собой конечную строку символов, которая интуитивно обозначает порядковый номер. Представляя порядковый номер конечным образом, доказательство Генцена не предполагает строгих аксиом относительно порядковых чисел.

Рекомендации

  • Доусон, Джон В. (2006) «Расшатанные основы или революционная перестройка? Столетняя оценка влияния Курта Гёделя на логику, математику и информатику». 2006 21-й ежегодный симпозиум IEEE по логике в компьютерных науках, IEEE, стр. 339–341. ISBN 0-7695-2631-4 Дои:10.1109 / LICS.2006.47
  • Майкл Детлефсен (1990). «О предполагаемом опровержении программы Гильберта с использованием первой теоремы Гёделя о неполноте». Журнал философской логики. Springer. 19 (4): 343–377. Дои:10.1007 / BF00263316.
  • Торкель Франзен (2005), Теорема Гёделя: неполное руководство по ее использованию и злоупотреблениям, А.К. Питерс, Уэлсли М.А. ISBN 1-56881-238-8
  • Герхард Гентцен (1936). "Die Widerspruchsfreiheit der reinen Zahlentheorie". Mathematische Annalen, т. 112, с. 493–565.
  • Гёдель, Курт (1931). "Uber form unentscheidbare Sätze der Principia Mathematica und Verwandter Systeme, I". Monatshefte für Mathematik und Physik. 38: 173–98. Архивировано из оригинал на 2006-07-05. Переведено на Жан ван Хейеноорт, 1967. От Фреге до Гёделя: Справочник по математической логике. Издательство Гарвардского университета: 596-616.
  • Гильберт, Дэвид (1900), "Убер ден Зальбегриф", Jahresbericht der Deutschen Mathematiker-Vereinigung, 8: 180–184
  • Дэвид Гильберт [1900] (1901) "Mathematische Probleme". Archiv der Mathematik und Physik, т. 3 п. 1. С. 44–63 и 213–237. Английский перевод, Маби Винтон, Бюллетень Американского математического общества 8 (1902), 437–479. Доступно на сайте http://aleph0.clarku.edu/~djoyce/hilbert/problems.html .
  • Джордж Крейзель (1976). «Что мы узнали из второй проблемы Гильберта?». Математические разработки, связанные с проблемами Гильберта (Proc. Sympos. Pure Math., Northern Illinois Univ., De Kalb, Ill.). Providence, R.I .: Amer. Математика. Soc. С. 93–130. ISBN 0-8218-1428-1.
  • Нагель, Эрнест и Ньюман, Джеймс Р., Доказательство Гёделя, Издательство Нью-Йоркского университета, 1958.
  • Стивен Г. Симпсон (1988). «Частичные реализации программы Гильберта». Журнал символической логики. 53 (2): 349–363. CiteSeerX 10.1.1.79.5808. Дои:10.2307/2274508. ISSN 0022-4812. JSTOR 2274508. Доступно на сайте http://www.math.psu.edu/simpson/papers/hilbert.pdf .
  • Уильям В. Тейт (2005). «Переформулировка Гёделем первого доказательства непротиворечивости арифметики Гентценом: интерпретация без контрпримера». Бюллетень символической логики т. 11 п. 2. С. 225–238.

внешняя ссылка