[PDF] [PDF] Pour remettre un peu dordre dans R 1 Relation dordre sur R 2

[PDF] Chapitre 3 :Relations dordre

Dans tout ce qui suit, E désigne un ensemble quelconque I Généralités A) Relations binaires Une relation binaire définie sur E est une propriété que chaque 

[PDF] RELATION BINAIRE - Licence de mathématiques Lyon 1

Montrer que est une relation d'ordre partiel sur On considère dans la suite de l' exercice que l'ensemble est ordonné par la relation 2 Soit { } Déterminer 

[PDF] Relation - Université de Toulouse

Une relation binaire ≼ sur un ensemble E est une relation d'ordre si elle sur X Pour montrer que pour tout x ∈ X la propriété P(x) est vraie, il suffit de montrer 

[PDF] 1 Relations binaires 2 Relations déquivalence 3 Relations dordre

relations sur l'ensemble des droites du plan ou de l'espace L'inclusion ⊂ est une relation sur P(X), où X est un ensemble quelconque Définitions Soit R 

[PDF] Ch 1 Relations - LACIM

relation d'équivalence Montrer aussi que R détermine une relation d'ordre sur l' ensemble des classes d'équivalence de ~ 2 On définit une relation R sur Z par 

[PDF] Relation déquivalence Relation dordre - PAGE WEB DANDRE

Montrer que R est une relation d'équivalence 2 Déterminer la classe d' équivalence de z ∈ C Exercice 4 Soit R une relation binaire sur un ensemble E  

[PDF] RELATIONS BINAIRES - Christophe Bertault

symétrie des rôles de x et y, il nous suffit de montrer que : cl(x) ⊂ cl(y) Exemple La relation de divisibilité n'est pas une relation d'ordre sur , mais c'en est 

[PDF] Relations binaires Relations déquivalence et dordre

20 août 2017 · Exemples : Les relations que l'on utilise couramment en mathématiques • La relation d'égalité sur un ensemble E «=» • Les relations sur R « < » 

[PDF] Pour remettre un peu dordre dans R 1 Relation dordre sur R 2

Montrer que B est bornée puis comparer sup A, sup B, inf A et inf B Exercice 5 Soient A et B deux parties non vides et bornées de R On pose −A = {−x, x ∈ 

[PDF] montrer verbe

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

[PDF] montrez

[PDF] montrez ? l'aide d'un exemple comment le progrès technique peut contribuer ? la croissance

[PDF] Montrez Comment la société médiévale s'organise progréssivement entre le XI et XIII siècle

[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 certaines caractéristiques des plantes sont en rapport avec la vie fixé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.

Relations d'ordre

Club ParisMaths - groupe avance

Noe de Rancourt

22 fevrier 2013

1. Generalites

SoitXun ensemble. UnerelationRsurXest une partie deX2; etant donnesxetydeux elements deX, on noteraxRyplut^ot que (x; y)2 R. Unerelation d'ordresurXest une relation6satisfaisant les trois proprietes suivantes : (Re exivite)8x2X; x6x; (Transitivite)8x; y; z2X;(x6yety6z))x6z; (Antisymetrie)8x; y2X;(x6yety6x))x=y. On dit que la relation6est totale si elle verie de plus la propriete suivante :

8x; y2X; x6youy6x.

A une relation d'ordre6, on associe la relation d'ordre stricteExercice 1 Donnez des exemples de relations d'ordre que vous connaissez (cherchez bien, on ne vous les a peut-^etre pas toutes presentees comme telles!) Lesquelles sont totales? SoitXun ensemble ordonne etx2X. On dit quexest unelement minimals'il n'existe pas dey2Xtel quey < x. On dit quexest unplus petit element(ou unminimum) si pour tout y2X, on ax6y. On dit que l'ordre6estbien fondesi toute partie non-vide deXadmet un element minimal, et que c'est unbon ordresi toute partie non-vide deXadmet un plus petit element.

Exercice 2

(1)Quelle est la dierence entre un plus petit element et un element minimal? Dans quel cas ces notions concident-elles? Donner un exemple d'element minimal qui n'est pas un plus petit element. 1 (2)Montrer que si un plus petit element existe, alors il est unique. Est-ce le cas pour les elements minimaux?

Exercice 3

(1)Donner un exemple de bon ordre. (2)Quels sont les elements minimaux de (N;j)? De (Nn f1g;j)? Et ses elements maximaux? (N;j) est-il bien fonde?

Exercice 4

(1)Montrer qu'un ordre est bon si et seulement s'il est total et bien fonde. (2)Montrer que (X;6) est bien fonde si et seulement s'il n'existe pas de suite strictement decroissante d'elements deX.

Exercice 5

Trouver une condition necessaire et susante sur l'ensembleXpour que l'ordre (P(X);) soit bien fonde.

Exercice 6

Soit (X;6) un ensemble totalement ordonne. Montrer qu'on a equivalence entre : (1)Xest ni; (2)Toute partie non-vide deXadmet un plus petit et un plus grand element.

2. Operations sur les ordres

Dans cette partie, on considerenensembles ordonnesX1; :::; Xn, dont les relations d'ordre seront toutes notees6.

Exercice 7

On supposeX1; :::; Xndeux-a-deux disjoints. Construire une relation d'ordre surX1[:::[Xn qui correspond a l'idee de mettre bout a boutles ensemblesX1; :::; Xndans cet ordre. Montrer

qu'elle est totale (resp. bien fondee, bonne) lorsque les relations d'ordre surX1; :::; Xnsont toutes

totales (resp. bien fondees, bonnes). Sur le produitX1:::Xnon denit deux relations d'ordre : {L'ordre produit, note6prod, et deni par (x1; :::; xn)6prod(y1; :::; yn) si et seulement si x i6yipour tout indicei; {L'ordre lexicographique, note6lex, dont l'ordre strictExercice 8 (1)Montrer que l'ordre produit est une relation d'ordre. (2)Supposons queX1; :::; Xnsoient totalement ordonnes. L'ordre produit est-il total? (Faire un dessin) (3)Montrer que si les ordres surX1; :::; Xnsont bien fondes, alors l'ordre produit aussi. Cela reste-t-il vrai en remplacant bien fondeparbon?

Exercice 9

(1)Vous avez deja rencontre et utilise l'ordre lexicographique. Dans quel contexte? (2)Montrer que l'ordre lexicographique est une relation d'ordre. (3)Montrer que si les ordres deX1; :::; Xnsont totaux (resp. bien fondes, bon) alors l'ordre lexicographique est total (resp. bien fonde, bon).

3. Applications croissantes, isomorphismes

SoientXetYdeux ensembles ordonnes, etf:X!Yune application. On dit quefest croissantesi8x1; x22X; x16x2)f(x1)6f(x2). On dit qu'elle eststrictement croissante si8x1; x22X; x1< x2)f(x1)< f(x2). Unisomorphismeest une bijection croissante de reciproque croissante. On dit queXetYsontisomorphess'il existe un isomorphisme entre les deux; intuitivement, cela signie queXetYsont identiques en tant qu'ensembles ordonnes, lorsqu'on fait abstraction de la nature de leurs elements. En particuliers, ils auront exactement les m^emes proprietes dependant de l'ordre.

Exercice 10

Une bijection croissante est-elle forcement un isomorphisme?

Exercice 11

SoitAune partie innie deN. On munitAetNde l'ordre usuel. Montrer queAetNsont isomorphes.

Exercice 12

Montrer que deux ensembles nis totalement ordonnes de m^eme cardinal sont isomorphes.

Exercice 13

SoitN(N), l'ensemble des suites innies d'entiers naturels qui sont nulles a partir d'un certain rang. On le munit de l'ordre produit, deni par (xn)6prod(yn) si et seulement si pour tout n2N,xn6yn(c'est exactement la m^eme denition que dans le cas des produits nis, et on montre de la m^eme facon que c'est une relation d'ordre). Montrer que (N;j) et (N(N);6prod) sont isomorphes. Un ensemble ordonne est ditdensesi8x; y2X; x < y) 9z2X; x < z < y; il estsans extremitessi8x2X;9y; z2X; y < x < z. 3

Exercice 14

(1)Donner des exemples d'ordres denses sans extremites. (2)Montrer que deux ordres denses sans extremites denombrables sont isomorphes.

4. Bons ordres

Dans toute cette partie, sauf mention contraire,XetYdesignent des ensembles bien ordonnes.

Exercice 15

SoitP(x) une propriete dependant d'un elementxdeX. On suppose que pour toutx2X, si pour touty < x,P(y) est vraie, alorsP(x) est vraie.

Montrer queP(x) est vraie pour toutx2X.

(C'est leprincipe de recurrence transnie, une generalisation de la recurrence forte surN. Rappelons a toutes ns utiles que8x2?;P(x) est toujours vrai; c'est pour cette raison qu'il n'y a pas besoin d'initialisation.)

Exercice 16

Soitf:X!Xune application strictement croissante. Montrer que pour toutx2X, f(x)>x. Unsegment initialdeXest une partieAdeXveriant8x2A;8y2XnA; x < y. Pour touta2X, on noteSa=fx2Xjx < ag.

Exercice 17

(1)Montrer queXet lesSasont des segments initiaux deX. (2)Montrer que tout segment initial deXest de l'une des formes precedentes. Cela reste-t-il vrai si l'on ne suppose plus queXest bien ordonne? (3)Soient S et T deux segments initiaux deXetf:S!Tun isomorphisme. Montrer que

S=Tet quefest l'identite.

On noteraX4YsiXest isomorphe a un segment initial deY.

Exercice 18

(1)Montrer que la relation4est re exive et transitive. (2)Montrer que siX4YetY4X, alorsXetYsont isomorphes.

4est doncpresqueune relation d'ordre, a isomorphisme pres. Dans la suite, on travaillera,

sans le repreciser a chaque fois, dans un ensembleAd'ensembles bien ordonnes, de sorte que, restreinte aA,4soit unevraierelation d'ordre. (3)Montrer que4est un ordre total. (4)Montrer que4est un bon ordre. 4quotesdbs_dbs47.pdfusesText_47