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