[PDF] relation d'ordre et d'équivalence
[PDF] relation d'ordre exercices corrigés
[PDF] relation d'ordre pdf
[PDF] relation d'ordre total et partiel exercice corrigé
[PDF] relation dali picasso
[PDF] Relation de Chales
[PDF] relation de chargaff
[PDF] Relation de Chasles
[PDF] Relation de Chasles
[PDF] Relation de Chasles - 1ère S
[PDF] relation de chasles 1ere s cours
[PDF] relation de chasles 1ere s exercices
[PDF] relation de chasles angles orientés
[PDF] relation de chasles cours 1ère s
[PDF] relation de chasles exercices corrigés
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 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?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.
quotesdbs_dbs49.pdfusesText_49
c Christophe Bertault - MPSI Relations d’ordre