В математической логике , то Париж-Harrington теорема утверждает , что некий комбинаторный принцип в теории Рамсея , а именно усиленной теоремы конечной Рэмси, это верно, но не доказуемо в арифметике Пеано . Некоторые (например, редактор Справочника по математической логике в приведенных ниже ссылках) описали это как первый «естественный» пример истинного утверждения о целых числах, которое может быть сформулировано на языке арифметики, но не доказано в Арифметика Пеано; уже было известно, что такие утверждения существовали по первой теореме Гёделя о неполноте .
Усиленная конечная теорема Рамсея
Усиленная конечная теорема Рамсея является утверждением о раскрасках и натуральных числах и утверждает, что:
- Для любых натуральных чисел n , k , m можно найти N со следующим свойством: если мы раскрасим каждое из n -элементных подмножеств S = {1, 2, 3, ..., N } в один из k цветов, то можно найти подмножество Y из S , по меньшей мере м элементов, таким образом, что все п -элементные подмножества Y имеют одинаковый цвет, и количество элементов Y , по меньшей мере наименьший элемент Y .
Без условии , что число элементов Y , по меньшей мере , наименьший элемент Y , это является следствием из конечной Рэмси теорема в, где N определяется выражением:
Более того, усиленная конечная теорема Рамсея может быть выведена из бесконечной теоремы Рамсея почти точно так же, как конечная теорема Рамсея может быть получена из нее, используя аргумент компактности (подробности см. В статье о теореме Рамсея ). Это доказательство можно провести в арифметике второго порядка .
Теорема Пэрис – Харрингтона утверждает, что усиленная конечная теорема Рамсея не доказуема в арифметике Пеано .
Теорема Пэрис – Харрингтона
Грубо говоря, Джефф Пэрис и Лео Харрингтон (1977) показали, что усиленная конечная теорема Рамсея недоказуема в арифметике Пеано, показав, что в арифметике Пеано она подразумевает непротиворечивость самой арифметики Пеано. Поскольку арифметика Пеано не может доказать свою непротиворечивость по второй теореме Гёделя о неполноте , это показывает, что арифметика Пеано не может доказать усиленную конечную теорему Рамсея.
Наименьшее число N , удовлетворяющее усиленной конечной теореме Рамсея, является вычислимой функцией от n , m , k , но растет чрезвычайно быстро. В частности, он не является примитивно рекурсивным , но он также намного больше стандартных примеров непримитивно рекурсивных функций, таких как функция Аккермана . Ее рост настолько велик, что арифметика Пеано не может доказать, что она определена всюду, хотя арифметика Пеано легко доказывает, что функция Аккермана определена правильно.
Смотрите также
Рекомендации
- Маркер, Дэвид (2002). Теория моделей: Введение . Нью-Йорк: Спрингер. ISBN 0-387-98760-6.
- запись в mathworld
- Paris, J .; Харрингтон, Л. (1977). «Математическая неполнота в арифметике Пеано». В Барвайз, Дж. (Ред.). Справочник по математической логике . Амстердам, Нидерланды: Северная Голландия.
Внешние ссылки
- Краткое введение в недоказуемость (содержит доказательство теоремы Пэрис – Харрингтона) Андрея Бовыкина