Relations d’ordre

˛ une relation d’ordre, a isomorphisme pr es Dans la suite, on travaillera, sans le repr eciser a chaque fois, dans un ensemble Ad’ensembles bien ordonn es, de sorte que, restreinte a A, 4 soit une ˝ vraie ˛ relation d’ordre (3) Montrer que 4 est un ordre total (4) Montrer que 4 est un bon ordre 4

Relation binaire, relation dordre, treillis

Relation d’ordre Deﬁnition:´ Une relation sur X ∼ qui est reﬂexive´ , antisymetrique et´ transitive est appelee une relation d’ordre ´ On dit alors que X est partiellement ordonnee´ et on note ≤ a` la place de ∼ Si (x,y) ∈ X2, x et y seront comparables si x ≤ y ou y ≤ x

1 Relations d’´equivalence et d’ordre

La relation R est-elle r´eﬂexive, sym´etrique, transitive ? Exercice 6 Dans N∗, on d´eﬁnit une relation

SUITESRECURRENTESLINEAIRES D’ORDRE2

2 ∆ = 0 L’équation caractéristique possède une solution double notée r Dans ce cas u appartientàU sietseulements’ilexiste(λ,µ) ∈R2 telque: ∀n∈N,u n = (λn+ µ)rn 3 ∆

RELATION BINAIRE - Claude Bernard University Lyon 1

1 Montrer que est une relation d’ordre 2 On admettra qu’il s’agit d’une relation d’ordre totale Classer par ordre croissant les dix premiers couples de muni de la relation d’ordre Allez à : Correction exercice 18 : Exercice 19 : Soient une relation définie sur par : ( ) ( ) 1 Montrer que est une relation d’équivalence 2

TD 2 : Relations d’ordre et d’ equivalence

Montrer que jest une relation d’ordre sur N Est-ce un ordre total? 2 Montrer que N muni de cet ordre admet un plus petit el ement et un plus grand el ement Comparer ces r esultats a ce que l’on a dans N muni de l’ordre naturel Exercice 6 : Pour tout x 2R et tout y 2R, on pose xRy ()x2 y2 = x y: 1 Montrer que Rest une relation d

Relation d’équivalence, relation d’ordre 1 Relation d’équivalence

Relation d’équivalence, relation d’ordre 1 Relation d’équivalence Exercice 1 Dans C on déﬁnit la relation R par : zRz0,jzj=jz0j: 1 Montrer que R est une relation d’équivalence 2 Déterminer la classe d’équivalence de chaque z2C Indication H Correction H Vidéo [000209] Exercice 2 Montrer que la relation R déﬁnie sur R par

Relations binaires Relations d’équivalence et d’ordre

a) Montrer que 4o est une relation d’ordre b) Montrer que si E possède au moins deux éléments, 4 o n’est pas totale 2) On déﬁnit un relation 4 ∗ sur E × E par :

Induction, relations et ordres bien fondés

Montrer qu’une relation qui a la propriété du diamant est conﬂuente Donner un exemple de relation conﬂuente qui n’a pas la propriété du diamant Exercice 8 Prouver qu’un relation fortement conﬂuente est conﬂuente Exercice 9 Deux relations R;S A A commutent si: a S / R b R c S /d Soient R;S A A Prouver que R S S est

[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

[PDF] Relations d’ordre