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

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

Этот результат был описан некоторыми (например, редактором Handbook of Mathematical Logic в ссылках ниже) как первый «естественный» пример истинного утверждения о целых числах, которое могло быть сформулировано на языке арифметики, но не доказано в арифметике Пеано; существование таких утверждений было известно уже из первой теоремы Гёделя о неполноте .

Усиленная конечная теорема Рамсея — это утверждение о раскрасках и натуральных числах, в котором говорится, что:

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

Без условия, что число элементов Y равно по крайней мере наименьшему элементу Y , это является следствием конечной теоремы Рамсея в , где N задается формулой:${\displaystyle K_{{\mathcal {P}}_{n}(S)}}$

${\displaystyle {\binom {N}{n}}=|{\mathcal {P}}_{n}(S)|\geq R(\,\underbrace {m,m,\ldots ,m} _{k}\,).}$

Более того, усиленная конечная теорема Рамсея может быть выведена из бесконечной теоремы Рамсея почти точно таким же образом, как из нее может быть выведена конечная теорема Рамсея, используя аргумент компактности (подробнее см. статью о теореме Рамсея ). Это доказательство может быть выполнено в арифметике второго порядка .

Теорема Париса–Харрингтона утверждает, что усиленная конечная теорема Рамсея недоказуема в арифметике Пеано .

Грубо говоря, Джефф Пэрис и Лео Харрингтон (1977) показали, что усиленная конечная теорема Рамсея недоказуема в арифметике Пеано , показав в арифметике Пеано, что она подразумевает непротиворечивость самой арифметики Пеано. Предполагая, что арифметика Пеано действительно непротиворечива, поскольку арифметика Пеано не может доказать свою собственную непротиворечивость с помощью второй теоремы Гёделя о неполноте , это показывает, что арифметика Пеано не может доказать усиленную конечную теорему Рамсея.

Усиленная конечная теорема Рамсея может быть доказана, предполагая индукцию до для соответствующего класса формул. В качестве альтернативы, она может быть доказана, предполагая принцип отражения , для арифметической теории, для -предложений . Принцип отражения также подразумевает непротиворечивость арифметики Пеано. Она доказуема в арифметике второго порядка (или гораздо более сильной теории множеств Цермело–Френкеля ) и поэтому верна в стандартной модели.${\displaystyle \varepsilon _{0}}$${\displaystyle \Sigma _{1}^{0}}$

Наименьшее число N , удовлетворяющее усиленной конечной теореме Рамсея, является вычислимой функцией от n , m , k , но растет чрезвычайно быстро. В частности, оно не является примитивно рекурсивным , но оно также растет гораздо быстрее, чем стандартные примеры непримитивных рекурсивных функций, таких как функция Аккермана . Оно доминирует над каждой вычислимой функцией, доказуемо тотальной в арифметике Пеано ^[1] , которая включает такие функции, как функция Аккермана.

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

• Маркер, Дэвид (2002). Теория моделей: Введение . Нью-Йорк: Springer. ISBN 0-387-98760-6.
• запись в mathworld
• Париж, Джефф ; Харрингтон, Лео (1977). «Математическая неполнота в арифметике Пеано». В Barwise, Джон ; Кейслер, Х. Джером (ред.). Справочник по математической логике . Амстердам; Нью-Йорк: Северная Голландия. С.  1133–1142 . ISBN 978-0-7204-2285-6.

• Краткое введение в недоказуемость (содержит доказательство теоремы Париса–Харрингтона) Андрея Бовыкина