[PDF] VIII Relations d’ordre et d’équivalence



Previous PDF Next PDF







VIII Relations d’ordre et d’équivalence

VIII-RELATIONSD’ORDREETD’ÉQUIVALENCE Définition2 0 8 Si R est une relation d’équivalence sur E, on appelleensemblequotientdeE parR l’ensemble desclassesd’équivalences,notéE/R



Relations binaires Relations d’équivalence et d’ordre

Remarque : Une relation d’équivalence est notée parfois ∼ Une relation d’équivalence permet de mettre en relation des éléments qui sont similaires pour une certaine propriété Exemples : • La relation ≡ [n]sur Z est une relation d’équivalence On vérifie facilement qu’elle est réflexive, symétrique et transitive



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éfinit 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éfinie sur R par



Feuille d’exercice n 08 : Relations d’ordre et d’équivalence

Feuille d’exercice n° 08 : Relations d’ordre et d’équivalence, et ensembles de nombres usuels Exercice 1 SoitEunensembleetAunepartiedeE OndéfinitlarelationRsurP(E) par :XRY siX∪A= Y∪A 1) MontrerqueRestunerelationd’équivalence 2) Décrirelaclassed’équivalencedeX∈P(E)



Relations binaires Relations d’équivalence et d’ordre

DERNIÈRE IMPRESSION LE 22 août 2017 à 10:06 Relations binaires Relations d’équivalence et d’ordre 1 Relations binaires EXERCICE 1 Soit E un ensemble et R une relation binaire sur E



CHAPITRE 3 : Relations d’équivalence et ensemble quotient

la définition dit Deux ensembles E et F sont équivalents si les élé-mentsdeEapparaissent(aumoinsunefois)dansFetréciproqe-ment 2 2 Représentant canonique et relation d’équivalence induite Dés qu’ils ont choisi une représentation des données A Les informaticiens



Ch 1 Relations

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 : xRy si x y est divisible par 2 Montrer que c’est une relation d’équivalence et déterminer ses classes d’équivalence



Partie IV : Relations binaires, applications

D Relations d’équivalence E Relations d’ordre, ensembles ordonnés Définitions Eléments remarquables Diagramme de Hasse d’une relation d’ordre A Les propositions B Le calcul propositionnel Premiers connecteurs logiques L’implication L’équivalence Vocabulaire Lois de Morgan et autres formules Formalisme logique et Théorie



1 Relations binaires - Mathématiques et Interactions à Nice

Définition Soit Rune relation d'équivalence sur E, et a un élément de E On appelle classe d'équivalence de a l'ensemble C(a) = fx 2E;xRag Propriété Si Rest une relation d'équivalence sur E et que a;b 2E véri ent aRb, alors a et b ont même classe d'équivalence Théorème Une relation d'équialencev Rsur un ensemble E dé nit une

[PDF] Relation d'ordre et relation d'équivalence 2

[PDF] Relation d'ordre et relation d'équivalence 3

[PDF] relation d’aide et validation

[PDF] relation d'aide définition

[PDF] relation d'aide définition larousse

[PDF] relation d'aide définition oms

[PDF] relation d'aide en soins infirmiers pdf

[PDF] relation d'aide pdf

[PDF] relation d'aide thérapeutique

[PDF] relation d'aide travail social

[PDF] relation d'équivalence

[PDF] relation d'ordre cours

[PDF] relation d'ordre et d'équivalence

[PDF] relation d'ordre exercices corrigés

[PDF] relation d'ordre pdf

X Relations d"ordre et d"équivalence.

30 août 2023

X - RELATIONS D"ORDRE ET D"ÉQUIVALENCE.

Dans tout ce chapitre,Eest un ensemble.

1. Relations binaires.Définition 1.0.1.On appellerelation binairetout tripletR=

(E,F,Γ)oùEetFsont des ensembles et oùΓest une partie deE×F. Au lieu de noter(x,y)?Γ, on notexRyce qui se lit :xest en relation avec y.

Remarque 1.0.2.

On considèrera uniquement des relations binaires sur un seul ensembleE,i.e.avecE=F.

Exemple 1.0.3.-

" Aimer » est une relation binaire : Brandon aime Sue Ellen mais Sue

Ellen n"aime pas Brandon. On voit sur cet

exemple qu"en généralxRyn"implique pas yRx.

L"égalité est l"exemple le plus courant de

relation binaire.

Soitf:R→R. On peut définir pour tous

x,y?R,xRyssiy=f(x)(on a en fait défini ainsi une application via son graphe). -SurR,⩽et<(autre exemple oùxRyest vrai maisyRxest faux). -?est une relation binaire surP(E). les divisibilités sur NetZ.

Remarque 1.0.4.

Une relation binaire sur un ensembleEfini peut

être représentée au moyen d"un graphe dont les sommets sont les éléments deEet dont les arêtes sont orientées d"un sommet à l"autre : une flèche allant dexàysignifiexRy.

Exercice 1.0.5.

Déterminer le graphe de la relation⩽sur

{0,1,2,3}. Faire de même pour la relation|.Définition 1.0.6.

SoitRune relation binaire surE. On dit queR

est : (i)réflexivesi?x?E,xRx.(ii) transitivesi?x,y,z?E, (xRyetyRz)? xRz. (iii)symétriquesi?x,y?E,xRy?yRx. (iv) antisymétriquesi?x,y?E, (xRyetyRx) ?x=y.

Remarque 1.0.7.

Ces propriétés peuvent être décelées sur un graphe de la relation binaire, défini en 1.0.4.

Exemple 1.0.8.-

" Aimer » ne vérifie au- cune de ces propriétés. L"égalité est réflexive, symétrique, antisy- métrique et transitive.

Soitf:R→RetxRyssiy=f(x):

les propriétés de cette relation dépendent du choix defmais ne vérifie aucune de ces propriétés en général (considérer par exemplef:x?→x+ 1etf:x?→x). est réflexive, transitive et antisymétrique surR. -Démonstration.-

Montrons le résultat pour?:

SoientA,B,C?P(E).

•On a bien entenduA?A, donc?est réflexive.

On supposeA?BetB?C. AlorsA?Cet

donc?est transitive.

On supposeA?BetB?A. AlorsA=B, et?

est antisymétrique. Montrons le résultat pour la divisibilité surN: soientn,p,q?N.

•On an= 1×ndoncn|n.

Sin|petp|q, alors il existek,??Ntels quep=kn

etq=?p, doncq= (?k)net ainsin|q.

Sin|petp|n, alors il existek,??Ntels quep=kn

etn=?p, doncn= (?k)net ainsi?k= 1. Mais?et ksont deux entiers naturels et sont donc égaux à 1, doncn=p. Dans le cas de la divisibilité dansZ, on aurait pour ce pointk,??Z, et donc?k= 1serait aussi vérifié sik=?=-1, et en effet sin=-pon a bienn|p etp|n, maisn?=p! 2

X - RELATIONS D"ORDRE ET D"ÉQUIVALENCE.

2. Relations d"équivalence.

Définition 2.0.1.On appellerelation d"équivalencetoute relation binaire réflexive, transitive et symétrique.

Exemple 2.0.2.

L"égalité surEest l"exemple le plus classique de relation d"équivalence.

La relation de congruence modulonsurZen

est aussi une : on fixen?Znon nul, et on dit que deux entierspetqsontcongrus modulons"il existek?Ztel quep=q+kn, ce qui se note p=q[n]oup≡q[n].

Six?R, on définit surRla relation d"équiva-

lence moduloxpara≡b[x]s"il existek?Ztel quea-b=kx.

Attention, cette relation n"est pas compatible

avec la multiplication.

SurRn, on a la relation d"équivalence :MRN

si--→OMet--→ONsont colinéaires. C"est le point de départ de lagéométrie projective.

SurMn(K), deux matricesMetNsont dites

semblables si?P?GLn(K),M=P-1NP. Cela définit une relation d"équivalence.

SurMn(K), deux matricesMetNsont dites

équivalentes si?(P,Q)?GLn(K)2,M=Q-1NP.

Cela définit une relation d"équivalence.

Sur un intervalleI, et parmi les fonctions de

classeC1surI, on peut considérer la relation " fetgsont deux primitives d"une même fonction »,i.e.f?=g?. C"est une relation d"équivalence, qui donne son sens à la manipulation du symbole de primitivation générique? x.Définition 2.0.3.

SoitEun ensemble etRune relation d"équiva-

lence surE. Alors, pour tout élémentxdeE, on appelleclasse d"équivalencedexl"ensemble {y?E|xRy}, que l"on note parfoisx.Exercice 2.0.4. Compléter le graphe suivant (voir figure 1) avec le moins de flèches possibles de manière à obtenir le graphe d"une relation d"équivalence. Identifier les classes d"équivalences.ab cde f Figure 1-À compléter (v oirexercice 2.0.4). Proposition 2.0.5.

SoitEun ensemble etRune relation d"équiva-

lence surE. Soit(x,y)?E2. Alors,

1.x?x.

2.xRy??x?y.

3.xRy??x=y.

Démonstration.

Le premier point découle de la réflexivité. Le second découle de la définition dey. Pour le troisième, il s"agit de montrer l"équivalence. Le sens direct se fait en montrant une double inclusion, qui découle de la transitivité. Le sens indirect découle du premier point et du second.Définition 2.0.6.

SoitEun ensemble,(Ai)i?Iune famille de parties

deEindexée par un ensembleI. On dit que (Ai)i?Iest unepartitiondeEsi les éléments de cette famille sont tous non vides, sont disjoints et si leur réunion vautE.Proposition 2.0.7.1.

SiRest une relation

d"équivalence surE, alors l"ensemble des classes d"équivalences deRforme une parti- tion deE. 3

X - RELATIONS D"ORDRE ET D"ÉQUIVALENCE.

2.Réciproquement, si(Ai)i?Iest une partition

deE, alors la relation binaire définie surE parxRysi?i?I,(x?Ai)?(y?Ai)est une relation d"équivalence.

Nous introduisons maintenant dans un but

culturel l"ensemble quotient (hors programme).Définition 2.0.8.

SiRest une relation d"équivalence surE, on

appelle ensemble quotient deEparRl"ensemble des classes d"équivalences, notéE/R.

Exemple 2.0.9.

Sif:E→Fest une application, la relation

binaire surEdéfinie parxRysif(x) =f(y) est une relation d"équivalence. Quelle est alors la partition qui lui est naturellement associée ? On pourra alors se poser la question suivante : y a- t-il un moyen naturel de construire une injection˜f:E/R→F?

Exemple 2.0.10.

On manipule naturellement certains ensembles

quotients : les vecteurs deRnet les fractions, par exemple.

3. Relations d"ordre.Définition 3.0.1.

On appellerelation d"ordretoute relation binaire

réflexive, transitive et antisymétrique.

Remarque 3.0.2.

L"usage est de noter≼, parfois⩽, les relations d"ordre.

Exemple 3.0.3.

Reprendre tous les exemples précédents et repérer les relations d"ordre.Définition 3.0.4.

Soit≼une relation d"ordre surE.1.

On dit quex,y?Esont deséléments com-

parablessix≼youy≼x. 2.

On dit que≼est unerelation d"ordre totale

(ou que cet ordre est total) si tous les éléments deEsont comparables deux à deux. Sinon la relation est ditepartielle(ou l"ordre est dit partiel).

Exemple 3.0.5.-

On définit la relation

d"ordre usuelle surN, notée⩽par :a⩽bsi ?k?N,b=a+k. C"est une relation d"ordre totale.

La relation d"ordre usuelle⩽surRest totale

: quand on choisit deux réels, il y en a toujours un des deux qui est inférieur ou

égal à l"autre.

La relation d"ordre?surP(E)est partielle

(siCardE⩾2) : en effet, quand on choisit deux parties deE, il n"y a aucune raison pour que l"une soit incluse dans l"autre.

La relation de divisibilité surNest une re-

lation d"ordre partielle : quand on choisit deux entiers positifs, l"un n"est pas forcé- ment multiple ou diviseur de l"autre.

Exercice 3.0.6.

Compléter le graphe suivant (voir figure 2) avec le moins de flèches possibles de manière à ob- tenir le graphe d"une relation d"ordre?sur

E={a,b,c,d,e,f,g}: la flèchex←ysignifie

x?y. Continuer ensuite avec l"exercice 4.3.3.ab cd ef g

Figure 2-À compléter (v oirexercice 3.0.6).

4

X - RELATIONS D"ORDRE ET D"ÉQUIVALENCE.

4. Majorants, minorants et

compagnie.Dans toute cette section,≼est une relation d"ordre surEetAest une partie deE.

4.1. Majorants, minorants.Définition 4.1.1.(i)

On dit queAestmajorée

(resp.minorée) pour≼s"il existe un élément

M?Etel que pour touta?A,a≼M

(resp.M≼a) ; on dit alors queMestUN majorant(resp.minorant) deAou queM majore (resp. minore)A. (ii) on dit queAestbornéesi elle est à la fois majorée et minorée.

En général, une partie majorée a

plusieurs majorants, et peut même en avoir une infinité !

Exemple 4.1.2.

•[1,2]dansRest majoré par tout réelxtel que

2⩽x, et minoré par tout réelytel quey⩽1.

•]- ∞,2[est majoré mais non minoré.

Pour la relation?,P(E)est minorée par∅et

majorée parE.

Exercice 4.1.3.

On considère dansP(Z)muni de?la partie

A={J0,nK|n?N}.

Déterminer l"ensemble des minorants et celui

des majorants deA.

4.2. Plus grand et plus petit éléments.Définition 4.2.1.

On dit quex?Eest unplus grand élémentou

maximum(resp.plus petit élémentouminimum) deAsixest un majorant (resp. minorant deA)

ETx?A.Exemple 4.2.2.

•I = [-1,2[a un plus petit élément, mais pas de plus grand élément. En effet,-1est un minorant deIet-1?I. Mais supposons par l"absurde queIait un plus grand élémentM. AlorsM?I, doncM <2. Ainsi il existea?]M,2[, donca?I etM < a, ce qui est en contradiction avec le fait queMmajoreI. •R n"est ni majoré ni minoré, donc n"a ni plus grand ni plus petit élément.Théorème 4.2.3. SiAa un plus grand élément, ce dernier est unique. Il en est de même pour un petit élément, s"il existe. Dans le cas d"existence, le plus grand élément de Aest alors noté maxA, et le plus petit élément deAest noté minA.

Démonstration.

On suppose queAa deux maxima : ils sont alors récipro- quement plus grand l"un que l"autre, et par antisymétrie ils sont égaux.Exemple 4.2.4.

DansNmuni de la relation d"ordre|: 0 est le

plus grand élément et 1 est le plus petit. En effet tout entier divise 0, et 1 divise tout entier.

Exercice 4.2.5.

En reprenant les notations de l"exercice 4.1.3, dé- terminer siApossède un maximum, ainsi qu"un minimum.

4.3. Bornes supérieure et inférieure.Définition 4.3.1.(i)S"il existe

, le plus petit

élément de l"ensemble des majorants deA

est appelé la borne supérieure deAet noté supA. (ii)S"il existe , le plus grand élément de l"en- semble des minorants deAest appelé la borne inférieure deAet noté infA.

Il y a une grosse différence entre max

et sup : le premier doit appartenir àA, pas le 5

X - RELATIONS D"ORDRE ET D"ÉQUIVALENCE.

deuxième.

Exemple 4.3.2.

I= [-1,2[a une borne inférieure et une borne

supérieure : l"ensemble des minorants deIest ]- ∞,-1], qui admet-1comme maximum, et donc-1est la borne inférieure deI. De même [2,+∞[est l"ensemble des majorants deI, et il admet2comme minimum, donc2est la borne supérieure deI.

Exercice 4.3.3.

On reprend l"exercice 3.0.6. Répondre aux ques- tions suivantes. 1.

Cet ordre est-il total ? Si ce n"est pas le cas,

donner deux éléments non comparables. 2.E est-il majoré ? Possède-t-il un plus grand

élément ? Une borne supérieure ?

3.

Même question a vec{c,d}.

4.

Même question a vec{d,e}.

5.

Même question a vec{b,d,e}.

6.

Même question a vec{a,c,f}.

Exercice 4.3.4.

En reprenant les notations de l"exercice 4.1.3, dé- terminer siApossède une borne supérieure, ainsi qu"une borne inférieure.

Exercice 4.3.5.

On considère la relation d"ordre|surN. Déter- miner les ensembles des minorants et majorants des parties suivantes, puis dire si ces parties sont majorées, minorées, admettent un maximum, un minimum, une borne supérieure ou inférieure (que l"on déterminera le cas échéant).

1.A={1}

2.B={2,3}

3.C={2p+ 1|p?N}

4.D={2p|p?N}Proposition 4.3.6.

SoitA?EetM?E.1.

SiAadmet une borne supérieure, alors

supA≼M? ?x?A x≼M. 2. (M=supA) si et seulement siMvérifie deux points : (i)MmajoreA (ii) six?Eetx?M, alors il existea?A tel quex?a≼M.

Remarque 4.3.7.

L"idée est la suivante : si on peut " caser » un élément deEentreMetA, ce qui revient en fait

à trouver un majorant deAplus petit queM,

alorsMn"est pas la borne supérieure deA: la borne supérieure " colle » àA.

Démonstration.1.?

: car supAest un majorant de A. ?: car supAest le plus petit majorant deA. 2.

Remarquons qu"ici, x?ysignifiex≼yetx?=y.

Par définition d"une borne supérieure, il suffit pour montrer cette équivalence de démontrer que le point (ii) équivaut à :Mest le plus petit majorant deA.

Supposons que nous avons (ii). Soit alorsNun ma-

jorant deA, tel queN?M. Alors avec (ii), il existe a?Atel queN?a. Ceci est absurde carNmajore A, doncM≼N:Mest bien inférieur à tout majo- rant deA.

Suposons réciproquement queMest le plus petit

majorant deA. Soitx?Etel quex?M. Alors,x étant plus petit queM,xn"est pas un majorant de A. En prenant la négation de la phrase "xmajore

A», nous obtenons : il existea?Atel quex?a.

Mais si de plusMmajoreA, alorsa≼Met nous

avons fini. Ce dernier raisonnement sera très souvent utilisé dans les exercices.Théorème 4.3.8.

SiApossède un maximum (resp. minimum), alors

Aa une borne supérieure (resp. inférieure) et cette borne est justement le maximum (resp. le minimum) deA:supA=maxA(resp.infA= minA).

Démonstration.

On ne donne la démonstration que pour la borne supérieure (c"est la même pour la borne inférieure) : soitEl"ensemble des majorants deA. Il faut montrer queEa un plus petit 6

X - RELATIONS D"ORDRE ET D"ÉQUIVALENCE.élément. Par définitionmaxAest un majorant deA, donc

maxA?E. SoitM?E.Mest plus grand que tout élément deA, ormaxAappartient àAdoncA≼M, et ce pour toutMdeE:maxAest donc un minorant de

E. De ces deux points on tiremaxA=minE, et donc

maxA= supA.4.4. Application aux fonctions réelles.

Définition 4.4.1.

SoientAune partie deRetf:A→R.

(i)

On dit quefestmajorée(resp.minorée)

surAsif(A)l"est pour la relation naturelle surR, i.e. :?M?R?x?A f(x)⩽M (resp.M⩽f(x)). Dans ce cas on dit queM est unmajorant(resp.minorant) def, ou queMmajore(resp.minore)f. (ii)

On dit quefestbornéesi elle est majorée

et minorée. Ceci est équivalent à :|f|est majorée.

Un majorant ou minorant ne doit pas

dépendre de la variable de la fonction ! Ainsi sur

R+,x?→xn"est pas un majorant desin, bien

que?x?R+,sinx⩽x. Un majorant est une

CONSTANTE.Définition 4.4.2.

Si l"ensemblef(A)a un maximum (resp. un

minimum), alors ce dernier est appelé lemaxi- mum(resp.minimum)defsurA, et notémaxAf oumaxx?Af(x)(resp.minAfouminx?Af(x)). Ainsi maxf(A) =maxAf. Un maximum ou minimum d"une fonction est donc un majorant ou minorant

ATTEINT.

On appelleextremumdeftout minimum ou

maximum def.

Les extrema sont uniques mais peuvent

être atteints plusieurs fois. Considérer pas exemple les fonctions continues périodiques comme sin ou cos.

Exemple 4.4.3.

•x?→x2

admet un minimum mais pas de majo- rant surR. Arctan est majorée et minorée surR, mais n"ad- met ni minimum ni maximum.Définition 4.4.4.

Si l"ensemblef(A)admet une borne supérieure

(resp. une borne inférieure), alors cette dernière est appelée laborne supérieure(resp.inférieure)de fsurA. On la notesup

Afousup

x?Af(x)(resp.infAfquotesdbs_dbs49.pdfusesText_49