Вторая проблема Гильберта - Hilbert's second problem

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

• Гипотеза Такеути

Примечания

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

• Доусон, Джон В. (2006) «Расшатанные основы или революционная перестройка? Столетняя оценка влияния Курта Гёделя на логику, математику и информатику». 2006 21-й ежегодный симпозиум IEEE по логике в компьютерных науках , IEEE, стр. 339–341. ISBN   0-7695-2631-4 дои : 10,1109 / LICS.2006.47
• Майкл Детлефсен (1990). «О предполагаемом опровержении программы Гильберта с использованием первой теоремы Гёделя о неполноте». Журнал философской логики . Springer. 19 (4): 343–377. DOI : 10.1007 / BF00263316 .
• Торкель Франзен (2005), Теорема Гёделя: неполное руководство по ее использованию и злоупотреблениям , AK Peters, Wellesley MA. ISBN   1-56881-238-8
• Герхард Гентцен (1936). "Die Widerspruchsfreiheit der reinen Zahlentheorie". Mathematische Annalen , т. 112, стр. 493–565.
• Гёдель, Курт (1931). "Уверенные формальные принципы математики и правильной системы, I" . Monatshefte für Mathematik und Physik . 38 : 173–98. Архивировано из оригинала на 2006-07-05. Переведено Жаном ван Хейеноортом , 1967. От Фреге до Гёделя: Справочник по математической логике . Издательство Гарвардского университета: 596-616.
• Гильберт, Давид (1900), «Über den Zahlbegriff» , Jahresbericht der Deutschen Mathematiker-Vereinigung , 8 : 180–184
• Дэвид Гильберт [1900] (1901) "Mathematische Probleme". Archiv der Mathematik und Physik , v. 3 n. 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.) . Провиденс, Род-Айленд: амер. Математика. Soc. С. 93–130. ISBN   0-8218-1428-1 .
• Нагель, Эрнест и Ньюман, Джеймс Р., Доказательство Гёделя , издательство Нью-Йоркского университета, 1958.
• Стивен Г. Симпсон (1988). «Частичные реализации программы Гильберта». Журнал символической логики . 53 (2): 349–363. CiteSeerX   10.1.1.79.5808 . DOI : 10.2307 / 2274508 . ISSN   0022-4812 . JSTOR   2274508 . Доступно в Интернете по адресу http://www.math.psu.edu/simpson/papers/hilbert.pdf .
• Уильям В. Тейт (2005). «Переформулировка Геделем первого доказательства непротиворечивости арифметики Гентцена: интерпретация без контрпримера». Бюллетень символической логики v. 11 n. 2. С. 225–238.

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

• Оригинальный текст выступления Гильберта на немецком языке
• Английский перевод обращения Гильберта 1900 г.