Теорема Канамори–Макалуна

В математической логике теорема Канамори –Макалуна , выдвинутая Канамори и МакАлуном (1987), дает пример неполноты в арифметике Пеано , аналогичный теореме Париса –Харрингтона . Они показали, что определенная финитная теорема в теории Рамсея не доказуема в арифметике Пеано (PA).

Заявление

Для данного набора неотрицательных целых чисел обозначим минимальный элемент . Пусть обозначим множество всех n -элементных подмножеств . ${\displaystyle s\subseteq \mathbb {N} }$ ${\displaystyle \min(s)}$ ${\displaystyle s}$ ${\displaystyle [X]^{n}}$ ${\displaystyle X}$

Функция , где называется регрессивной, если для всех не содержащих 0. ${\displaystyle f:[X]^{n}\rightarrow \mathbb {N} }$ ${\displaystyle X\subseteq \mathbb {N} }$ ${\displaystyle f(s)<\min(s)}$ ${\displaystyle s}$

Теорема Канамори–Макалуна утверждает, что следующее утверждение, обозначенное в исходной ссылке как , недоказуемо в PA: ${\displaystyle (*)}$

Для каждого существует такое , что для всех регрессивных существует множество такое, что для всех с , имеем . ${\displaystyle n,k\in \mathbb {N} }$ ${\displaystyle m\in \mathbb {N} }$ ${\displaystyle f:[\{0,1,\ldots ,m-1\}]^{n}\rightarrow \mathbb {N} }$ ${\displaystyle H\in [\{0,1,\ldots ,m-1\}]^{k}}$ ${\displaystyle s,t\in [H]^{n}}$ ${\displaystyle \min(s)=\min(t)}$ ${\displaystyle f(s)=f(t)}$

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

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

Ссылки

• Канамори, Акихиро ; МакАлун, Кеннет (1987), «О неполноте Гёделя и конечной комбинаторике», Annals of Pure and Applied Logic , 33 (1): 23–41, doi : 10.1016/0168-0072(87)90074-1 , ISSN  0168-0072, MR  0870685