Теорема Париса — Харрингтона — Википедия. Что такое Теорема Париса — Харрингтона
Wiki.sc

Теорема Париса — Харрингтона

Материал из Википедии — свободной энциклопедии

Теорема Па́риса — Ха́ррингтона (или Пэ́риса — Ха́ррингтона) — теорема в математической логике, ставшая первым в истории математики естественным и относительно несложным примером утверждения о натуральных числах, которое истинно, но недоказуемо в аксиоматике Пеано. Существование недоказуемых теорем арифметики прямо вытекает из первой теоремы Геделя о неполноте (1930 год). Кроме того, вторая теорема Гёделя, (опубликованная вместе с первой), дает конкретный пример такого утверждения: а именно утверждение о непротиворечивости арифметики. Однако долгое время не было известно «естественных» примеров таких утверждений, то есть таких утверждений, которые бы возникали не из утверждений о некоторой логике, а были бы естественными математическими утверждениями о числах.

Данная теорема и её доказательство были опубликованы в 1977 году Джеффри Парисом (Великобритания) и Лео Харрингтоном (США).

Усиленная теорема Рамсея

Результат Париса—Харрингтона опирается на несколько модифицированную комбинаторную теорему Рамсея[1]:

Для любых натуральных чисел можно указать натуральное со следующим свойством: если мы окрасим каждое из -элементных подмножеств в один из цветов, то в существует подмножество содержащее не менее элементов таких, что все -элементные подмножества имеют один и тот же цвет, а количество элементов не меньше, чем наименьший элемент

Без условия «количество элементов не меньше, чем наименьший элемент » это утверждение вытекает из конечной теоремы Рамсея. Отметим, что усиленный вариант теоремы Рамсея может быть записан на языке логики первого порядка[2].

Формулировка

Теорема Париса-Харрингтона утверждает:

Сформулированная выше усиленная теорема Рамсея не доказуема в аксиоматике Пеано.

В своей статье Парис и Харрингтон показали, что из этой теоремы вытекает непротиворечивость аксиоматики Пеано; однако, как показал Гёдель, арифметика Пеано не в состоянии доказать свою собственную непротиворечивость, поэтому теорема Париса-Харрингтона в ней недоказуема. С другой стороны, используя логику второго порядка или аксиоматику теории множеств ZF, несложно доказать, что усиленная теорема Рамсея истинна[2].

Другие примеры недоказуемых теорем арифметики

Примечания

Литература

Ссылки

Что такое Wiki.sc Вики является главным информационным ресурсом в интернете. Она открыта для любого пользователя. Вики это библиотека, которая является общественной и многоязычной.

Основа этой страницы находится в Википедии. Текст доступен по лицензии CC BY-SA 3.0 Unported License.

Wikipedia® — зарегистрированный товарный знак организации Wikimedia Foundation, Inc. WIKI.SC является независимой компанией и не аффилирована с Фондом Викимедиа (Wikimedia Foundation).

E-mail: admin@wiki.sc