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

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

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

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

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

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

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

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

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

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

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

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

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

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

См. также

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

Ссылки

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

Внешние ссылки

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