[PDF] Relations dordre relation d'ordre strict) quand

View - Download Relations dordre

Previous PDF

Next PDF

Chapter 1

Relations d"ordre

Ce chapitre traite des relations d"ordre. Apr`es des rappels de notions abord´ees l"an dernier, on s"int´eresse plus particuli`erement aux "ordres bien fond´es" qui permettent de g´en´eraliser le principe de r´ecurrence.

1.1 Ordre et ordre strict

D´efinition (relation binaire).SoitEun ensemble. Unerelation binaire RsurEest un sous-ensemble deE×E. On notexRypour signifier que (x,y)? RetxR/ ypour signifier que (x,y)/? R. D´efinition (classification).SoitRune relation binaire surE. On dit que

Rest•r´eflexivequand?x?E,xRx;•irr´eflexivequand?x?E,xR/ x;•sym´etriquequand?x,y?E,xRy?yRx;•antisym´etriquequand?x,y?E,xRyetyRx?x=y;•transitivequand?x,y,z?E,xRyetyRz?xRz.

D´efinition (ordre).Une relation binaire est unordre(ou unerelation d"ordre) quand elle est r´eflexive, antisym´etrique et transitive. D´efinition (ensemble ordonn´e).SoitEun ensemble et?une relation d"ordre surE. On dit que (E,?) est unensemble ordonn´e. Remarque: Attention, les d´efinitions ci-dessus correspondent `a l"ordre large mais pas `a l"ordre strict : (IR,<) o`u2CHAPTER 1. RELATIONS D"ORDRED´efinition (ordre strict)Une relation binaire est unordre strict(ou une relation d"ordre strict) quand elle est irr´eflexive et transitive. D´efinition (ensemble strictement ordonn´e)SoitEun ensemble et? une relation d"ordre strict surE. On dit que (E,?) est unensemble stricte- ment ordonn´e.Th´eor`eme 1.1Un ordre strict est toujours antisym´etrique. D´efinition (´el´ements incomparables)Soit (E,?) un ensemble ordonn´e. Deux ´el´ementxetydeEsont ditsincomparablesquand on a nix?y, ni y?x. D´efinition (ordre total)Un ordre?surEest dittotalsi deux ´el´ements sont toujours comparables :?x,y?E, x?youy?x. Un ordre qui n"est pas total est ditpartiel. D´efinition (ordre strict total)Un ordre strict?surEest ditstrict total si deux ´el´ements diff´erents sont toujours comparables :?x,y?E, x?=y? x?youy?x. Remarque: Sans surprise, on peut toujours passer d"un ordre `a un ordre strict et r´eciproquement. Si (E,?) est un ensemble ordonn´e, la relation? d´efinie parx?yssi (x?=yetx?y) est un ordre strict. R´eciproquement, si (E,?) est un ensemble strictement ordonn´e, la relation?d´efinie parx?y ssi (x=youx?y) est une relation d"ordre.

1.2 Minorants, majorants, minimaux et maximaux

D´efinition (minorant, plus petit ´el´ement)Soit (E,?) un ensemble ordonn´e etFune partie (c"est-`a-dire un sous-ensemble) non vide deE. On dit quex?Eest unminorantdeFsi tout ´el´ement deFest plus grand que xpour?:?y?F,x?y. Si le minorant deFest un ´el´ement deFon dit que c"estle plus petit ´el´ementdeF. D´efinition (majorant, plus grand ´el´ement).Soit (E,?) un ensemble ordonn´e etFune partie non vide deE. On dit quex?Eest unmajorant deFsi tout ´el´ement deFest plus petit quexpour?:?y?F,y?x. Si le majorant deFest un ´el´ement deFon dit que c"estle plus grand ´el´ement deF. Remarque: Il n"y a pas toujours un minorant ou un majorant : si l"ensemble c"estZet la partiePl"ensemble des entiers relatifs divisibles par 2, il n"y a ni minorant ni majorant.Th´eor`eme 1.2Soit(E,?)un ensemble ordonn´e etFune partie non vide deE.Fa au plus un plus petit ´el´ement et au plus un plus grand ´el´ement.

1.3. PRODUIT D"ORDRES3D´efinition (´el´ement minimal).Soit (E,?) un ensemble ordonn´e etF

une partie non vide deE. Un ´el´ementx?Fest un´el´ement minimalde Fquand aucun ´el´ement deFn"est strictement plus petit, pour?, quex: ?y?F,y?x?y=x. D´efinition (´el´ement maximal).Soit (E,?) un ensemble ordonn´e etF une partie non vide deE. Un ´el´ementx?Fest un´el´ement maximalde Fquand aucun ´el´ement deFn"est strictement plus grand, pour?, quex: ?y?F,x?y?y=x.

1.3 Produit d"ordres

D´efinition (ordre produit simple).Soit (E,?E) et (F,?F) deux en- sembles ordonn´es. On d´efinit l"ordre produit simple?prodsurE×Fpar D´efinition (ordre produit lexicographique).Soit (E,?E) et (F,?F) deux ensembles ordonn´es. On d´efinit l"ordre produit lexicographique?lexsur E×Fpar, on notant?Eet?Fles ordres stricts associ´es `a?Eet?F, ?x?Ex? ou x=x?ety?Fy?. Remarque: Si?Eet?Fsont des ordres totaux,?lexest aussi un ordre total; ce n"est pas vrai pour?prod.

1.4 Ordre bien fond´e

D´efinition (ordre bien fond´e)Soit (E,?) un ensemble ordonn´e. On dit que?estbien fond´equand il n"existe pas de suite infinie strictement d´ecroissante d"´el´ements deE. Remarque: L"ordre usuel surNest bien fond´e, mais pas celui surZ, ni celui sur IR +.Th´eor`eme 1.3(caract´erisation des ordres bien fond´es)Soit(E,?) un ensemble ordonn´e. L"ordre?est bien fond´e si et seulement si tout partie

non videFdeEadmet au moins un ´el´ement minimal.Th´eor`eme 1.4Le produit lexicographique de deux ordres bien fond´es est

bien fond´e.

4CHAPTER 1. RELATIONS D"ORDRE1.5 Application `a la terminaison de programmes

Si on consid`ere le programme suivant, o`u les entiersmetnsont strictements positifs avant de commencer, on montre facilement qu"ils restent tout le temps strictement positifs.while (m != n) { if (m > n) m = m - n; else n = n - m; La question est: est-ce que cette boucle s"arrˆete toujours, pour n"importe quel choix demetndansN?? la r´eponse et oui et on peut le montrer grˆace `a l"ordre lexicographique: si on consid`ere l"ordre lexicographique naturel sur N ?×N?, on s"aper¸coit qu"`a chaque it´eration le couple (m,n) est strictement inf´erieur `a celui d"avant. Comme l"ordre lexicographique surN?×N?est bien fond´e (d"apr`es le th´eor`eme pr´ec´edent), on ne peut effectuer qu"un nombre fini d"it´erations dans le programme. Le proc´ed´e se g´en´eralise aux fonctions r´ecursives, quand on veut prouver qu"elle termine. Il suffit de trouver un ordre bien fond´e sur les entr´ees, et de montrer que lors d"un appel `a la fonction, on ne lance des appels r´ecursif que sur des donn´ees plus petites pour l"ordre consid´er´e. Voir le TD pour un exemple.

1.6 Diagramme de Hasse d"un ensemble ordonn´e

fini Quand (E,?) est un ensemble fini ordonn´e, on peut le repr´esenter graphique- ment par sondiagramme de Hasse, qui est un graphe non-orient´e avec les

contraintes suivantes :•les sommets sont les ´el´ements deE;•six?yon placexplus bas queysur le diagramme;•six?yet qu"il n"y a pas dez?Etel quex?z?y, on met une

arˆete entrexety. Exemple: Le diagramme de Hasse pour l"ordre?surE={1,2,3}est :

1.7. ORDRES SUR LES MOTS5{1,2,3}{2,3}{1,3}{1,2}{3}{2}{1}∅

Th´eor`eme 1.5Soit(E,?)un ensemble fini ordonn´e. L"ordre?est bien fond´e surE.

1.7 Ordres sur les mots

On se donne un ordre strict?sur l"alphabet. Dans cette partie on rappelle juste les deux ordres sur les mots vus l"an dernier. D´efinition (ordre lexicographique sur les mots).SoitAun alphabet ?uest pr´efixe dev ou ?w,s,t?A?,?a,b?A,a?betu=wasetv=wbt D´efinition (ordre militaire sur les mots).SoitAun alphabet fini. On ?|u|<|v| ou l"ordre lexicographique. ATTENTION :ne pas confondre l"ordre lexicographique produit et l"ordre lexicographique sur les mots.quotesdbs_dbs47.pdfusesText_47

[PDF] montrer verbe

[PDF] Montres que le lycée est un lieu régit par le Droit

[PDF] montrez

[PDF] montrez comment la structure de l'adn explique sa fonction de support de l'information génétique

[PDF] montrez comment le progrès technique stimule la croissance économique

[PDF] Montrez comment un pouvoir est politique et comment une question devient politique

[PDF] Montrez en citant des indices, que Les Confessions appartiennent au genre autobiographique

[PDF] montrez en quoi la croissance est un phénomène cumulatif

[PDF] Montrez l'importance des ressources alimentairess sur la reproduction des anchois

[PDF] montrez les différentes facettes du défi alimentaire auquel l'Inde est confrontée

[PDF] montrez que la 2 nd guerre mondiale fut une guerre d'aneantissement

[PDF] montrez que la détermination du salaire peut dépendre de l'intervention de l'état.

[PDF] montrez que la fiscalité peut contribuer ? la justice sociale.

[PDF] Montrez que la fonction f a pour expression

[PDF] montrez que le facteur capital est source de croissance économique.