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 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 SueEllen 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. -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! 2X - 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. 3X - 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 injectionf: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?surE={a,b,c,d,e,f,g}: la flèchex←ysignifie
x?y. Continuer ensuite avec l"exercice 4.3.3.ab cd ef gFigure 2-À compléter (v oirexercice 3.0.6).
4X - 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émentM?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 que2⩽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 5X - 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 "xmajoreA», 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 6X - 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