Teorema Paris-Harrington

Teorema Paris-Harrington (sau Paris-Harrington ) este o teoremă în logica matematică , care a devenit primul exemplu natural și relativ simplu de afirmație despre numerele naturale din istoria matematicii , ceea ce este adevărat, dar nedemonstrabil în axiomatica lui Peano . Existența teoremelor nedemonstrabile în aritmetică decurge direct din prima teoremă de incompletitudine a lui Gödel (1930). Mai mult, a doua teoremă a lui Gödel (publicată împreună cu prima), oferă un exemplu concret al unei astfel de afirmații: și anume, afirmația de consistență aritmetic. Cu toate acestea, pentru o lungă perioadă de timp nu au existat exemple „naturale” de astfel de afirmații, adică enunțuri care să nu decurgă din enunțuri despre o anumită logică, ci să fie enunțuri matematice naturale despre numere.

Această teoremă și demonstrația ei au fost publicate în 1977 de Geoffrey Paris (Marea Britanie) și Leo Harrington (SUA).

Teorema Ramsey puternică

Rezultatul lui Paris-Harrington se bazează pe o teoremă Ramsey combinatorie oarecum modificată [1] :

Pentru orice numere naturale, se poate specifica un număr natural cu următoarea proprietate: dacă colorăm fiecare dintre submulțimile -elementului într-una dintre culori, atunci există o submulțime care conține cel puțin elemente astfel încât toate subseturile -elementelor să aibă aceeași culoare , iar numărul de elemente nu este mai mic decât cel mai mic element $n,k,m$ $N$ $n$ $S=\{1,2,3,\dots N\}$ $k$ $S$ $Y,$ $m$ $n$ $Y$ $Y$ $Y.$

Fără condiția „ numărul de elemente nu este mai mic decât cel mai mic element $Y$ $Y$ ”, această afirmație decurge din teorema finită a lui Ramsey . Rețineți că o versiune consolidată a teoremei lui Ramsey poate fi scrisă în limbajul logicii de ordinul întâi [2] .

Formulare

Teorema Paris-Harrington spune:

Teorema Ramsey consolidată menționată mai sus nu este demonstrabilă în axiomatica lui Peano .

În lucrarea lor, Paris și Harrington au arătat că consistența axiomaticii lui Peano rezultă din această teoremă ; totuși, așa cum a arătat Gödel , aritmetica Peano nu reușește să-și demonstreze propria consistență, așa că teorema Paris-Harrington este nedemonstrabilă în ea. Pe de altă parte, folosind logica de ordinul doi sau axiomatica teoriei mulțimilor ZF , este ușor de demonstrat că teorema Ramsey puternică este adevărată [2] .

Alte exemple de teoreme nedemonstrabile în aritmetică

teorema lui Goodstein
Teorema Kanamori–Macaloon
Teorema arborelui Kruskal

Literatură

Paris J., Harrington L. A Mathematical Incompleteness in Peano Arithmetic // Handbook of Mathematical Logic. - Amsterdam: Olanda de Nord, 1977. - ISBN 072042285X . (publicarea primului autor a teoremei)
Marker, David. Teoria modelului: o introducere . - New York: Springer , 2002. - ISBN 0-387-98760-6 .

Link -uri

Kochetkov Yu. Yu. Funcții calculabile. Capitolul 19. Teoreme nedemonstrabile în aritmetica axiomatică . Preluat: 17 august 2018. (nedefinit)
Bovykin, Andrey, Weisstein, Eric W. Paris - Teorema Harrington . Recuperat la 17 august 2018. Disponibil de laMathWorld .
Bovykin, Andrei . Scurtă introducere în nedemonstrabilitatea (conține demonstrația teoremei).