RAMSEY THÉORÈME DE

Ce sujet est traité dans les articles suivants :

1.  COMBINATOIRE ANALYSE

Écrit par : Dominique FOATA

Dans le chapitre "Théorèmes d'existence"  : … p. Le théorème de Ramsey peut être considéré comme une généralisation de ce principe. *Théorème de Ramsey. Soit X un ensemble de n éléments et supposons donnés d'abord trois entiers p, q, r satisfaisant à p ≥ r, q ≥ r et r ≥ 1, ensuite une partition… Lire la suite

2.  ERDÖS PAUL (1913-1996)

Écrit par : Jean-Louis NICOLAS

…  assuré par une seule des deux compagnies. Soit m et n deux nombres entiers. Le *théorème de Ramsey affirme l'existence d'un nombre r (m, n) tel que, si N ≥ r (m, n), alors ou bien il existe un sous-réseau de m aéroports entièrement reliés par la compagnie… Lire la suite

3.  MODÈLES THÉORIE DES

Écrit par : Daniel ANDLER, Daniel LASCAR, Gabriel SABBAGH

Dans le chapitre "Indiscernables"  : … de I, on a dans A : pour toute formule ϕ à n variables de L. Il résulte du théorème combinatoire de *Ramsey que, étant donné une théorie T et un ensemble ordonné infini I, il existe un modèle de T dans lequel I est indiscernable. On peut même obtenir des modèles qui sont engendrés (à l'aide des fonctions) par un ensemble ordonné… Lire la suite

4.  RÉCURSIVITÉ, logique mathématique

Écrit par : Kenneth Mc ALOON, Bernard JAULIN, Jean-Pierre RESSAYRE

Dans le chapitre "Complexité"  : … Paris et Harrington ont démontré qu'un certain énoncé combinatoire dérivé du théorème classique de *Ramsey est vrai mais n'est pas démontrable dans l'arithmétique de Peano. En effet, pour tout n, k, il existe p tel que, si q > p et si g est une application de l'ensemble [q]^k… Lire la suite