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

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

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

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

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

Шаблон:Рамка Для любых натуральных чисел $n,k,m$ можно указать натуральное $N$ со следующим свойством: если мы окрасим каждое из Шаблон:S подмножеств $S=\{1,2,3,\dots N\}$ в один из $k$ цветов, то в $S$ существует подмножество $Y,$ содержащее не менее $m$ элементов таких, что все $n$-элементные подмножества $Y$ имеют один и тот же цвет, а количество элементов $Y$ не меньше, чем наименьший элемент $Y.$ |}

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

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

Теорема Париса-Харрингтона утверждает: Шаблон:Рамка Сформулированная выше усиленная теорема Рамсея не доказуема в аксиоматике Пеано. |}

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

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

• Теорема Гудстейна
• Шаблон:Нп5
• Шаблон:Нп5

Литература

• Шаблон:Книга (первая авторская публикация теоремы)
• Шаблон:Книга

Ссылки

• Шаблон:Cite web
• Шаблон:Cite web на сайте MathWorldШаблон:Ref-en.
• Bovykin, Andrey. Brief introduction to unprovability (содержит доказательство теоремы).