Théorème de Paris-Harrington

Un article de Wikipédia, l'encyclopédie libre.

En logique mathématique, le théorème de Paris–Harrington, obtenu en 1977 par Jeff Paris et Leo Harrington, affirme qu'un certain résultat combinatoire, le théorème de Ramsey fini renforcé, est vrai mais non démontrable dans l'arithmétique de Peano. Ce théorème est souvent décrit comme le premier exemple d'énoncé « naturel » d'indécidabilité connu, par contraste avec les exemples construits par Gödel utilisant un codage « peu naturel ».

Théorème de Ramsey renforcé[modifier | modifier le code]

Le théorème de Ramsey fini affirme que pour tout entier c et toute suite d'entiers (n1, n2, … , nc), il existe un entier N tel que pour toute coloration en c couleurs du graphe complet KN d'ordre N, il existe une couleur i et un sous-graphe complet de KN d'ordre ni qui soit monochromatique de couleur i ; le plus petit entier N ayant cette propriété est noté R(n1, n2, … , nc).

La forme renforcée utilisée par Paris et Harrington est un énoncé analogue sur les colorations d'ensembles d'entiers, affirmant que :

Pour tous entiers n, k, m tels que m ≥ n, il existe N tel que si on colorie tous les sous-ensembles à n éléments de S = {1, 2, 3,..., N} avec une couleur choisie parmi k, on peut trouver un sous-ensembleY de S ayant au moins m éléments, tel que tous les sous-ensembles à n éléments de Y ont la même couleur, et que le nombre d'éléments de Y est au moins égal au plus petit entier de Y.

Sans cette dernière condition sur Y, ce résultat serait un corollaire du théorème de Ramsey fini sur le graphe , avec N donné par

Le théorème renforcé est une conséquence du théorème de Ramsey infini, obtenue par essentiellement le même argument de compacité que celui permettant d'en déduire le théorème fini ; la démonstration peut également être menée dans l'arithmétique du second ordre ; le résultat de Paris–Harrington est qu'il ne peut en revanche être démontré dans l'arithmétique de Peano.

Théorème de Paris–Harrington[modifier | modifier le code]

La démonstration de Paris et Harrington revient essentiellement à montrer que dans l'arithmétique de Peano, le théorème de Ramsey implique la consistance de l'arithmétique de Peano elle-même. Comme le second théorème d'incomplétude de Gödel affirme qu'aucune théorie de ce genre ne peut démontrer sa propre consistance, il en résulte que l'arithmétique de Peano ne peut démontrer le théorème de Ramsey fini renforcé.

Le plus petit entier N satisfaisant le théorème est une fonction calculable de n, m et k, mais elle croît extrêmement vite[1]. En particulier elle n'est pas récursive primitive, et elle croît même beaucoup plus vite que la fonction d'Ackermann, une des fonctions non récursives primitives les plus connues. C'est cette croissance rapide qui fait que l'arithmétique de Peano ne peut démontrer qu'elle est partout définie, ce qui implique le résultat d'indécidabilité du théorème.

Notes et références[modifier | modifier le code]

  1. L'impossibilité de montrer qu'elle est partout définie implique qu'elle croît au moins aussi vite que la fonction de la hiérarchie de croissance rapide .

Voir aussi[modifier | modifier le code]

Bibliographie[modifier | modifier le code]