Вторая проблема Гильберта

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Хотя теоремы Гёделя и Генцена теперь хорошо поняты сообществом математической логики, не сформировалось единого мнения относительно того, отвечают ли (и каким образом) эти теоремы на вторую проблему Гильберта. Симпсон (1988) утверждает, что теорема Гёделя о неполноте показывает, что невозможно получить финитистские доказательства непротиворечивости сильных теорий. ^{[ 5 ]} Крайзель (1976) утверждает, что, хотя результаты Гёделя подразумевают, что финитистское доказательство синтаксической непротиворечивости невозможно получить, семантические аргументы (в частности, второго порядка ) могут использоваться для получения убедительных доказательств непротиворечивости. Детлефсен (1990) утверждает, что теорема Гёделя не препятствует доказательству непротиворечивости, поскольку ее гипотезы могут не применяться ко всем системам, в которых может быть проведено доказательство непротиворечивости. ^{[ 6 ]} Доусон (2006) называет веру в то, что теорема Гёделя исключает возможность убедительного доказательства непротиворечивости, «ошибочной», ссылаясь на доказательство непротиворечивости, данное Генценом, а также более позднее, данное Гёделем в 1958 году . ^{[ 7 ]}

См. также

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

Примечания

^ Американское математическое общество (1902) , перевод М. Ньюсона. Оригинальную версию см. в Hilbert (1901) .
^ Нагель и Ньюман (1958) , с. 96–99.
^ Похожая цитата с небольшими изменениями в формулировках содержится в Nagel & Newman (2001) , стр. 107–108, в редакции Дугласа Р. Хофштадтера .
^ Фактически, доказательство присваивает каждому доказательству «обозначение» порядкового номера. Обозначение представляет собой конечную строку символов, которая интуитивно обозначает порядковый номер. Представляя порядковый номер конечным образом, доказательство Генцена не предполагает строгих аксиом относительно порядковых чисел.
^ Симпсон (1988) , сек. 3.
^ Детлефсен (1990) , с. 65.
^ Доусон (2006) , сек. 2.

Ссылки

Доусон, Джон В. (2006). «Потрясенные основы или революционная перестройка? Столетняя оценка влияния Курта Гёделя на логику, математику и информатику». 2006 21-й ежегодный симпозиум IEEE по логике в информатике . IEEE. стр. 339–341. дои : 10.1109/LICS.2006.47 . ISBN 0-7695-2631-4 .
Детлефсен, Майкл (1990). «О предполагаемом опровержении программы Гильберта с помощью первой теоремы Гёделя о неполноте». Журнал философской логики . 19 (4). Спрингер: 343–377. дои : 10.1007/BF00263316 . S2CID 44736805 .
Франзен, Торкель (2005). Теорема Гёделя: неполное руководство по ее использованию и злоупотреблениям . Уэлсли М.А .: А.К. Питерс . ISBN 1-56881-238-8 .
Генцен, Герхард (1936). «Непротиворечивость чистой теории чисел». Математические летописи . 112 . Спрингер: 493-565. дои : 10.1007/BF01565428 .
Гёдель, Курт (1931). «О формально неразрешимых теоремах Principia Mathematica и родственных систем I» . Ежемесячные журналы по математике и физике . 38 : 173–98. дои : 10.1007/BF01700692 . S2CID 197663120 . Архивировано из оригинала 5 июля 2006 г.
Гильберт, Дэвид (1900). «О понятии числа» . Годовой отчет Немецкой ассоциации математиков . 8 : 180-184.
——— (1901) [1900]. «Математические задачи». Архив математики и физики . 3 (1): 44–63, 213–237.
Крейзель, Джордж (1976). «Чему мы научились из второй проблемы Гильберта?». Математические разработки, возникающие из задач Гильберта (Proc. Sympos. Pure Math., Northern Illinois Univ., De Kalb, Ill.) . Провиденс, Род-Айленд: Амер. Математика. Соц. стр. 93–130. ISBN 0-8218-1428-1 .
«Математические задачи» (PDF) . Бюллетень Американского математического общества . 8 . Американское математическое общество : 437–479. 1902.
Нагель, Эрнест ; Ньюман, Джеймс Р. (1958). Доказательство Геделя . Издательство Нью-Йоркского университета.
———; ——— (2001). Хофштадтер, Дуглас Р. (ред.). Доказательство Геделя . Издательство Нью-Йоркского университета. ISBN 9780814758014 .
Симпсон, Стивен Г. (1988). «Частичные реализации программы Гильберта». Журнал символической логики . 53 (2): 349–363. CiteSeerX 10.1.1.79.5808 . дои : 10.2307/2274508 . ISSN 0022-4812 . JSTOR 2274508 .
Тейт, Уильям В. (2005). «Переформулировка Гёделя первого доказательства непротиворечивости арифметики Генцена: интерпретация без контрпримеров». Бюллетень символической логики . 11 (2): 225–238. JSTOR 1556751 .
ван Хейеноорт, Жан (1967). От Фреге до Гёделя: Справочник по математической логике . Издательство Гарвардского университета. стр. 596–616. .

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

[1] Американское математическое общество (1902) , перевод М. Ньюсона. Оригинальную версию см. в Hilbert (1901) .

[FOOTNOTENagelNewman195896&ndash;99-2] Нагель и Ньюман (1958) , с. 96–99.

[3] Похожая цитата с небольшими изменениями в формулировках содержится в Nagel & Newman (2001) , стр. 107–108, в редакции Дугласа Р. Хофштадтера .

[4] Фактически, доказательство присваивает каждому доказательству «обозначение» порядкового номера. Обозначение представляет собой конечную строку символов, которая интуитивно обозначает порядковый номер. Представляя порядковый номер конечным образом, доказательство Генцена не предполагает строгих аксиом относительно порядковых чисел.

[FOOTNOTESimpson1988sec._3-5] Симпсон (1988) , сек. 3.

[FOOTNOTEDetlefsen199065-6] Детлефсен (1990) , с. 65.

[FOOTNOTEDawson2006sec._2-7] Доусон (2006) , сек. 2.

[ 1 ]

[ 2 ]

[ 3 ]

[ 4 ]

[ 5 ]

[ 6 ]

[ 7 ]