Русская Википедия:Теорема Париса — Харрингтона
Теорема Па́риса — Ха́ррингтона (или Пэ́риса — Ха́ррингтона) — теорема в математической логике, ставшая первым в истории математики естественным и относительно несложным примером утверждения о натуральных числах, которое истинно, но недоказуемо в аксиоматике Пеано. Существование недоказуемых теорем арифметики прямо вытекает из первой теоремы Гёделя о неполноте (1930 год). Кроме того, вторая теорема Гёделя, (опубликованная вместе с первой), даёт конкретный пример такого утверждения: а именно утверждение о непротиворечивости арифметики. Однако долгое время не было известно «естественных» примеров таких утверждений, то есть таких утверждений, которые бы возникали не из утверждений о некоторой логике, а были бы естественными математическими утверждениями о числах.
Данная теорема и её доказательство были опубликованы в 1977 году Джеффри Парисом (Великобритания) и Лео Харрингтоном (США).
Усиленная теорема Рамсея
Результат Париса—Харрингтона опирается на несколько модифицированную комбинаторную теорему РамсеяШаблон:Sfn:
Шаблон:Рамка Для любых натуральных чисел <math>n,k,m</math> можно указать натуральное <math>N</math> со следующим свойством: если мы окрасим каждое из Шаблон:S подмножеств <math>S = \{1, 2, 3, \dots N\}</math> в один из <math>k</math> цветов, то в <math>S</math> существует подмножество <math>Y,</math> содержащее не менее <math>m</math> элементов таких, что все <math>n</math>-элементные подмножества <math>Y</math> имеют один и тот же цвет, а количество элементов <math>Y</math> не меньше, чем наименьший элемент <math>Y.</math> |}
Без условия «количество элементов <math>Y</math> не меньше, чем наименьший элемент <math>Y</math>» это утверждение вытекает из конечной теоремы Рамсея. Отметим, что усиленный вариант теоремы Рамсея может быть записан на языке логики первого порядкаШаблон:Sfn.
Формулировка
Теорема Париса-Харрингтона утверждает: Шаблон:Рамка Сформулированная выше усиленная теорема Рамсея не доказуема в аксиоматике Пеано. |}
В своей статье Парис и Харрингтон показали, что из этой теоремы вытекает непротиворечивость аксиоматики Пеано; однако, как показал Гёдель, арифметика Пеано не в состоянии доказать свою собственную непротиворечивость, поэтому теорема Париса-Харрингтона в ней недоказуема. С другой стороны, используя логику второго порядка или аксиоматику теории множеств ZF, несложно доказать, что усиленная теорема Рамсея истиннаШаблон:Sfn.
Другие примеры недоказуемых теорем арифметики
Примечания
Литература
- Шаблон:Книга (первая авторская публикация теоремы)
- Шаблон:Книга
Ссылки
- Шаблон:Cite web
- Шаблон:Cite web на сайте MathWorldШаблон:Ref-en.
- Bovykin, Andrey. Brief introduction to unprovability (содержит доказательство теоремы).
