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

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 essentiellment 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
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. 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

Voir aussi
 Théorème de Goodstein
 Théorème de Kruskal

Bibliographie
 
 
 

Théorème de logique mathématique