Soutenance mémoire
Application sur les suites monotones
La théorie de Ramsey infini
Le théorème de ramsey infini
Un résultat analogue, encore appelé théorème de Ramsey (ou théorème de Ramsey infini lorsque le contexte n’est pas clair), s’applique aux graphes infinis. Les représentations graphiques étant moins parlantes dans ce cas, les résultats de ce type sont généralement formulés dans le langage de la théorie des ensembles.Nous allons donc l’énoncer tout de suite, le prouver, voir comment la version fini peut se déduire du théorème de Ramsey infini, et en fin on va donner des applications de la version infini.Théorème : Soit X un ensemble infini dénombrable. Pour toute coloration finie de X (n) (l’ensemble des parties de X de taille n ), il existe un sousensemble infini M de X tel que M (n) (l’ensemble des parties de M de taille n) soit monochrome.
Preuve
Soit c le nombre de couleurs. On raisonne par récurrencesur n. Si n = 1, l’énoncé est vrai car dans toute partition finied’un ensemble infini,l’un des sous-ensembles est infini.
Supposons que le théorème soit vrai pour n = r, et montrons-le pour n = r + 1. Étant donnée une c-coloration P de X (r+1), soit a0 un élément de X et Y = X \ {a0}. P induit une c-coloration P 0 de Y (r) définiepar : la P 0-couleur d’une partie s de Y est la P -couleur de s ∪ a0.
Donc d’après l’hypothèse de récurrence, il existe un sous-ensemble infini Y1 de Y tel que Y1(r) soit monochrome. Il y a donc un élément a0 et un ensemble infini Y1 tels que tous les sous-ensembles à r + 1 éléments de X formés de a0 et de r éléments de Y1 ont la même couleur.
Le même argument montre qu’il y a un élément a1 de Y1 et un sousensemble infini Y2 de Y1 avec la même propriété, et donc, par récurrence, on obtient une suite infinie (a0 , a1, a2, …) telle que la couleur de n’importe quel sous-ensemble à r + 1 éléments de la forme (ai(1),ai(2),…, ai(r+1)) avec i(1) < i(2) < … < i(r + 1) dépend seulement de i(1). Il y a de plus un nombre infini de valeurs i(n) pour lesquelles cette couleur sera la même. L’ensemble de ces ai(n) est par construction un ensemble ayant la propriété cherchée.Ce théorème est à l’origine de la notion de cardinal de Ramsey (qu’on démontre être nécessairement un grand cardinal). Soit k un nombre cardinal infini, [k]<ω l’ensemble des sous-ensembles finis de k ; on dit que k est un cardinal de Ramsey (ou simplement que k est Ramsey) si, pour toute application f de [k]<ω dans l’ensemble {0, 1}, il existe un sous-ensemble A de k ayant le même cardinal que k qui est homogène pour f, c’est-à-dire que pour tout n, f est constante sur les sous-ensembles de A de cardinal n. Autrement dit, il s’agit d’un cardinal (non dénombrable) pour lequel le théorème de Ramsey (reformulé convenablement et un peu renforcé) est encore vrai.
Le cas infini implique le cas fini
On peut déduire le théorème fini de la version infinie en raisonnant par l’absurde, ou plutôt par contraposition. Supposons que le théorème fini soit faux. Il existe des entiers c, n, T tels que pour tout entier k, il existe une c-coloration de {1, 2, …, k}(n) sans ensemble monochromatique de cardinal T. Soit Ck l’ensemblede ces c-colorations.
Pour tout k, la restriction d’une coloration de Ck+1 à {1, 2, …, k}(n) obtenue en ignorant les ensembles contenant k + 1 est une coloration de Ck . Définissant C1 comme l’ensemble des colorations de Ck qui sont des restrictions de colorations dans Ck+1, on voit que C1 n’est pas vide, puisque Ck+1 ne l’est pas. De même, la restriction d’une coloration dans C1 est dans C1, ce qui permet de définir C2 comme l’ensemble non vide de ces restrictions; par récurrence, on peut donc définirCm pour tous les entiers m et k.On a donc pour tout k la suite décroissanteCk ⊇ C1 ⊇ C2 ⊇ …, et tous k k les ensembles de cette suite sont non vides. De plus, Ck est fini(de cardinal k! inférieur ou égal à cn!(k−n)!). Il en résulte que la suite est stationnaire, et que Dk = Ck ∩ C1 ∩ C2 ∩ . .. est non vide. Ainsi, toute coloration de Dk est k k la restriction d’une coloration dans D1 . Remontant alors en prolongeant une coloration de Dk à Dk+1, puis à Dk+2, et ainsi de suite, on construit une coloration de N(n) sans aucun ensemble monochromatique de cardinal T. Ceci est la contradiction cherchée avec le théorème de Ramsey infini ; par contraposition, ce dernier entraîne le cas fini.
|
Table des matières
1 Introducion
2 Le théorème de Ramsey fini
2.1 Cas particulier
2.2 Théoreme de Ramsey (cas de deux couleurs)
2.3 Théorème de Ramsey (cas de plusieurs couleurs)
2.4 le nombre de Ramsey
2.5 Application sur les suites monotones
3 la théorie de Ramsey infini
3.1 le théorème de ramsey infini
3.2 Le cas infiniimplique le cas fini
3.3 Application du théorème de Ramsey infini
3.3.1 Théorème de Ramsey infiniappliqué aux graphes
3.3.2 Application de Ramsey infinisur les suites
3.3.3 les mots infini
4 Conclusion
Télécharger le rapport complet
