Théorème de Paris-Harrington

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_c), il existe un entier N tel que pour toute coloration en c couleurs du graphe complet K_N d'ordre N, il existe une couleur i et un sous-graphe complet de K_N d'ordre n_i qui soit monochromatique de couleur i ; le plus petit entier N ayant cette propriété est noté R(n₁, n₂, … , n_c).

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 $K_{{\mathcal {P}}_{n}(S)}$ , avec N donné par ${\binom {N}{n}}=|{\mathcal {P}}_{n}(S)|\geq R(\,\underbrace {m,m,\ldots ,m} _{k}\,).$

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[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

(en) Cet article est partiellement ou en totalité issu de l’article de Wikipédia en anglais intitulé « Paris–Harrington theorem » (voir la liste des auteurs).

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 $f_{\varepsilon _{0}}$ .

Voir aussi

Bibliographie

David Marker, Model Theory: An Introduction, New York, Springer, 2002 (ISBN 0-387-98760-6)
(en) Eric W. Weisstein, « Paris-Harrington Theorem », sur MathWorld
Jeff Paris et Leo Harrington, Handbook of Mathematical Logic, Amsterdam, Netherlands, North-Holland, 1977, « A Mathematical Incompleteness in Peano Arithmetic »
- Portail des mathématiques
- Portail de la logique

Cet article est issu de Wikipedia. Le texte est sous licence Creative Commons - Attribution - Partage dans les Mêmes. Des conditions supplémentaires peuvent s'appliquer aux fichiers multimédias.

[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 $f_{\varepsilon _{0}}$ .