Теорема Пэрис – Харрингтона - Paris–Harrington theorem

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

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

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

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

Без условия, что количество элементов Y является по крайней мере наименьшим элементом Y , это является следствием конечной теоремы Рамсея в , где N определяется как:

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

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

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

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

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

Смотрите также

использованная литература

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

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