Введение
Теорема о том, что определенный принцип в теории Рамзи верен, но не доказуем в арифметике Пеано. В математической логике теорема Пари-Харрингтона утверждает, что определенный комбинаторный принцип в теории Рамзи, а именно усиленная конечная теорема Рамзи, который может быть выражен в арифметике Пеано, не доказуем в этой системе. Однако этот комбинаторный принцип доказуем в немного более сильных системах. Некоторые (например, редактор «Справочника по математической логике», указанный в ссылках ниже) описали этот результат как первый «естественный» пример истинного утверждения о целых числах, которое можно сформулировать на языке арифметики, но не доказать в арифметике Пеано; существование таких утверждений уже было известно благодаря первой теореме о неполноте Гёделя.
In mathematical logic, the Paris–Harrington theorem states that a certain combinatorial principle in Ramsey theory, namely the strengthened finite Ramsey theorem, which is expressible in Peano arithmetic, is not provable in this system. The combinatorial principle is, however, provable in slightly stronger systems. This result has been described by some (such as the editor of the Handbook of Mathematical Logic in the references below) as the first "natural" example of a true statement about the integers that could be stated in the language of arithmetic, but not proved in Peano arithmetic; it was already known that such statements existed by Gödel's first incompleteness theorem.
Теорема Парижа и Харрингтона
Грубо говоря, Джефф Париж и Лео Харрингтон (1977) показали, что усиленная конечная теорема Рамзи недоказуема в арифметике Пеано, продемонстрировав в арифметике Пеано, что она влечет за собой непротиворечивость самой арифметики Пеано. Поскольку арифметика Пеано не может доказать свою собственную непротиворечивость согласно второй теореме о неполноте Гёделя, это показывает, что арифметика Пеано не может доказать усиленную конечную теорему Рамзи. Комбинаторный принцип может быть доказан, предполагая индукцию вплоть до для релевантных классов формул. Альтернативно, его можно доказать, предполагая принцип отражения для арифметической теории для -предложений. Принцип отражения также влечет за собой непротиворечивость арифметики Пеано. Он доказуем в арифметике второго порядка (или в гораздо более сильной теории множеств Цермело — Френкеля) и, следовательно, истинен в стандартной модели. Наименьшее число N, удовлетворяющее усиленной конечной теореме Рамзи, является вычислимой функцией от n, m, k, но растет чрезвычайно быстро. В частности, это не примитивно рекурсивная функция, но она также растет гораздо быстрее, чем стандартные примеры не примитивно рекурсивных функций, такие как функция Аккермана. Она доминирует над любой вычислимой функцией, доказуемо полной в арифметике Пеано, которая включает в себя такие функции, как функция Аккермана.