Теорема Па́риса — Ха́ррингтона (или Пэ́риса — Ха́ррингтона) — теорема в математической логике, ставшая первым в истории математики естественным и относительно несложным примером утверждения о натуральных числах, которое истинно, но недоказуемо в аксиоматике Пеано. Существование недоказуемых теорем арифметики прямо вытекает из первой теоремы Гёделя о неполноте (1930 год). Кроме того, вторая теорема Гёделя, (опубликованная вместе с первой), даёт конкретный пример такого утверждения: а именно утверждение о непротиворечивости арифметики. Однако долгое время не было известно «естественных» примеров таких утверждений, то есть таких утверждений, которые бы возникали не из утверждений о некоторой логике, а были бы естественными математическими утверждениями о числах.
Данная теорема и её доказательство были опубликованы в 1977 году Джеффри Парисом (Великобритания) и Лео Харрингтоном (США).
Усиленная теорема Рамсея Результат Париса — Харрингтона опирается на несколько модифицированную комбинаторную теорему Рамсея:
Для любых натуральных чисел можно указать натуральное со следующим свойством: если мы окрасим каждое из подмножеств в один из цветов, то в существует подмножество содержащее не менее элементов таких, что все -элементные подмножества имеют один и тот же цвет, а количество элементов не меньше, чем наименьший элемент
Без условия «количество элементов не меньше, чем наименьший элемент » это утверждение вытекает из конечной теоремы Рамсея. Отметим, что усиленный вариант теоремы Рамсея может быть записан на языке логики первого порядка.
Формулировка Теорема Париса — Харрингтона утверждает:
Сформулированная выше усиленная теорема Рамсея не доказуема в аксиоматике Пеано.
В своей статье Парис и Харрингтон показали, что из этой теоремы вытекает непротиворечивость аксиоматики Пеано; однако, как показал Гёдель, арифметика Пеано не в состоянии доказать свою собственную непротиворечивость, поэтому теорема Париса — Харрингтона в ней недоказуема. С другой стороны, используя логику второго порядка или аксиоматику теории множеств ZF, несложно доказать, что усиленная теорема Рамсея истинна.
Другие примеры недоказуемых теорем арифметики Теорема Гудстейна
Примечания
Литература (первая авторская публикация теоремы)
Ссылки
на сайте MathWorld. Bovykin, Andrey. Brief introduction to unprovability (содержит доказательство теоремы).
Категория:Основания математики Категория:Теоремы математической логики