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

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

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

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

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

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

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

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

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

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

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

• Теорема Гудстейна

Примечания

Литература

• Paris J., Harrington L. // Handbook of Mathematical Logic. — Amsterdam: North-Holland, 1977. — ISBN 072042285X . (первая авторская публикация теоремы)
• Marker, David. (англ.) . — New York: , 2002. — ISBN 0-387-98760-6 .

Ссылки

• Кочетков Ю. Ю. (неопр.) . Дата обращения: 17 августа 2018.
• Bovykin, Andrey, Weisstein, Eric W. (англ.) . Дата обращения: 17 августа 2018. на сайте MathWorld (англ.) .
• Bovykin, Andrey . (содержит доказательство теоремы).