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

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

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

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

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

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

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

ФормулировкаПравить

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

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

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

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

• Теорема Гудстейна
• Теорема Канамори–Макалуна^[en]
• Теорема о дереве Краскала^[en]

ЛитератураПравить

• Paris J., Harrington L. A Mathematical Incompleteness in Peano Arithmetic // Handbook of Mathematical Logic. — Amsterdam: North-Holland, 1977. — ISBN 072042285X. (первая авторская публикация теоремы)
• Marker, David. Model Theory: An Introduction (англ.). — New York: Springer^[en], 2002. — ISBN 0-387-98760-6.

СсылкиПравить

• Кочетков Ю. Ю. Вычислимые функции. Глава 19. Теоремы, недоказуемые в аксиоматической арифметике  (неопр.). Дата обращения: 17 августа 2018.
• Bovykin, Andrey, Weisstein, Eric W. Paris-Harrington Theorem (англ.). Дата обращения: 17 августа 2018. на сайте MathWorld (англ.).
• Bovykin, Andrey. Brief introduction to unprovability (содержит доказательство теоремы).