Théorème de Paris-Harrington - Paris–Harrington theorem

En logique mathématique , le théorème de Paris-Harrington déclare qu'un certain principe combinatoire de la théorie de Ramsey , à savoir le théorème de Ramsey fini renforcé, est vrai, mais non prouvable en arithmétique de Peano . Cela a été décrit par certains (comme l'éditeur du Handbook of Mathematical Logic dans les références ci-dessous) comme le premier exemple "naturel" d'une déclaration vraie sur les nombres entiers qui pourraient être énoncés dans la langue de l'arithmétique, mais pas prouvés dans arithmétique de Peano; on savait déjà que de telles déclarations existaient par le premier théorème d'incomplétude de Gödel .

Théorème de Ramsey fini renforcé

Le théorème de Ramsey fini renforcé est une déclaration sur les colorations et les nombres naturels et déclare que :

Pour tout entier positif n , k , m , tel que m n , on peut trouver N avec la propriété suivante : si on colore chacun des n sous-ensembles d'éléments de S = {1, 2, 3,..., N } avec l'une des k couleurs, alors nous pouvons trouver un sous-ensemble Y de S avec au moins m éléments, tel que tous les sous-ensembles de n éléments de Y ont la même couleur, et le nombre d'éléments de Y est au moins le plus petit élément de Y .

Sans la condition que le nombre d'éléments de Y soit au moins le plus petit élément de Y , c'est un corollaire du théorème fini de Ramsey dans , avec N donné par :

De plus, le théorème de Ramsey fini renforcé peut être déduit du théorème de Ramsey infini presque exactement de la même manière que le théorème de Ramsey fini peut en être déduit, en utilisant un argument de compacité (voir l'article sur le théorème de Ramsey pour plus de détails). Cette preuve peut être effectuée en arithmétique du second ordre .

Le théorème de Paris-Harrington déclare que le théorème de Ramsey fini renforcé n'est pas prouvable en arithmétique de Peano .

Théorème de Paris-Harrington

En gros, Jeff Paris et Leo Harrington (1977) ont montré que le théorème de Ramsey fini renforcé est indémontrable en arithmétique de Peano en montrant qu'en arithmétique de Peano il implique la cohérence de l'arithmétique de Peano elle-même. Puisque l'arithmétique de Peano ne peut pas prouver sa propre cohérence par le deuxième théorème d'incomplétude de Gödel , cela montre que l'arithmétique de Peano ne peut pas prouver le théorème de Ramsey fini renforcé.

Le plus petit nombre N qui satisfait le théorème de Ramsey fini renforcé est une fonction calculable de n , m , k , mais croît extrêmement vite. En particulier, il n'est pas récursif primitif , mais il est également beaucoup plus grand que les exemples standard de fonctions récursives non primitives telles que la fonction d'Ackermann . Sa croissance est si grande que l'arithmétique de Peano ne peut pas prouver qu'elle est définie partout, bien que l'arithmétique de Peano prouve facilement que la fonction d'Ackermann est bien définie.

Voir également

Les références

  • Marqueur, David (2002). Théorie des modèles : une introduction . New York : Springer. ISBN 0-387-98760-6.
  • entrée mathworld
  • Paris, J. ; Harrington, L. (1977). « Une incomplétude mathématique dans l'arithmétique de Peano ». Dans Barwise, J. (éd.). Manuel de logique mathématique . Amsterdam, Pays-Bas : Hollande du Nord.

Liens externes