Une relation d’ordre sur E est, comme son nom l’indique, une relation qui met de l’ordre entre les éléments de E « Ordre » s’entend ici au sens de « hiérarchie » : il y a un haut et un bas, des plus petits et des plus grands
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 d’ordre Ce chapitre traite des relations d’ordre Apr`es des rappels de notions abord´ees l’an dernier, on s’int´eresse plus particuli`erement aux “ordres bien fond´es” qui permettent de g´en´eraliser le principe de r´ecurrence I 1 Ordre et ordre strict D´efinition (relation binaire) Soit E un ensemble
Relations d’ordre D enombrement Plus grand el ement Borne Sup erieure 1 Relations d’ordre 1 1 Relations d’ordre Ensembles ordonn es D e nition Soit E un ensemble muni d’une relation binaire R On dit que R est une relation d’ordre sur E ou que (E;R) est un ensemble ordonn e si et seulement si R poss ede les propri et es
3 2 Relation stricte associée à une relation d’ordre Définition 7 : Soit 4une relation d’ordre sur E La relation ≺ sur E définie par : ∀x,y ∈ E, x 4y et x 6=y est antisymétrique et transitive, est appelée la relation stricte associée à 4 PAUL MILAN 6 CPGE L1 - ALGÈBRE
Définition (Relation d’ordre) On appelle (relationd’) ordre sur E touterelation binaire sur E qui est à la fois réflexive, transitive et antisymétrique Les relations d’ordre sont généralement notées ¶ou ´ou ®ou Exemple Les relations ¶sur Ret RRsont des relations d’ordre, ainsi que la relation d’inclusion ⊂ sur P (E)
3 Relations d'ordre Définition Une relation binaire Rsur E est une relation d'ordre si et seulement si elle est ré exive, antisymétrique et transitive On dit alors que E est un ensemble ordonné (par R) Une relation d'ordre est souvent notée Exemples L'inégalité est une relation d'ordre sur N, Z ou R L'inclusion est une relation d
est une relation d’équivalence Préciser, pour x fixé dans R, le nombre d’éléments de la classe de x modulo R Indication H Correction H Vidéo [000212] 2 Relation d’ordre Exercice 3 Soit (E;6) un ensemble ordonné On définit sur P(E)nf0/gla relation ˚par X ˚Y ssi (X =Y ou 8x 2X 8y2Y x 6y): Vérifier que c’est une relation d
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 définissent une fonction canon : A -> A qui à chaque élément a:A associe sonreprésentant canonique 5
[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
DERNIÈRE IMPRESSION LE20 août 2017 à 15:44
Relations binaires. Relations
d"équivalence et d"ordre
Table des matières
1 Généralités2
1.1 Définition. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2
1.2 Compatibilité d"une relation avec une loi interne. . . . . . . . . . . 2
1.3 Qualité d"une relation binaire. . . . . . . . . . . . . . . . . . . . . . 3
1.4 Relation totale ou partielle. . . . . . . . . . . . . . . . . . . . . . . . 3
2 Relation d"équivalence4
2.1 Définition. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4
2.2 Classe d"équivalence. Ensemble quotient. . . . . . . . . . . . . . . 4
3 Relation d"ordre5
3.1 Définition. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5
3.2 Relation stricte associée à une relation d"ordre. . . . . . . . . . . . 6
4 Éléments fondamentaux d"un ensemble ordonné7
4.1 Majorant, minorant. . . . . . . . . . . . . . . . . . . . . . . . . . . . 7
4.2 Plus grand et plus petit élément. . . . . . . . . . . . . . . . . . . . . 7
4.3 Borne supérieure et borne inférieur. . . . . . . . . . . . . . . . . . . 8
PAUL MILAN1CPGE-L1 -ALGÈBRE
1. GÉNÉRALITÉS
1 Généralités
En mathématiques, on cherche souvent à comparer deux éléments d"un ensemble ou la propriété que deux éléments d"un ensemble sont susceptibles d"avoir.
1.1 Définition
Définition 1 :Une relation binaireRdéfinie sur un ensembleEest au choix : une propriété qui relie ou non deux élémentsxetydeE. On notexRypour dire que l"élémentxest en relation avecy
une partie deE×E. On notexRysi(x,y)?R
?Pour un couple(x,y)?= (y,x)donc on fera la différence entrexRyetyRx. Par exemple siRest la relation < surR: si l"on ax
», "?». La relation surZ" | » :a|bsi "adiviseb». La relation surZ"≡[n]» :a≡b[n]si queaest congru àbmodulon. La relation surP(E)"?» :A?Bsi queAest inclus dansB. La relation sur les droites du plan " //» :d//d?si la droitedest parallèle àd?. La relation sur les droites du plan "?» :d?d?si la droitedest perpendicu- laire àd?. Remarque :On peut représenter une relation binaire par un graphe ou un dia- gramme sagittal (du latinsagitta: flèche). Par exemple la relation?sur [[0,3]] 01 2 3 1.2 Compatibilité d"une relation avec une loi interne
Définition 2 :SoientRune relation binaire surE. La relationRest compatible avec la loi de composition interne?surEsi : (aRbetcRd)?(a?c)R(b?d) Exemples :
La loi?surRest compatible avec l"addition mais pas avec la multiplication. La loi≡[n]surZest compatible avec l"addition et la multiplication. PAUL MILAN2CPGE L1 -ALGÈBRE
1. GÉNÉRALITÉS
1.3 Qualité d"une relation binaire
Définition 3 :SoitRune relation binaire surE.
On dit queRest réflexive si :?x?E,xRx
On dit queRest symétrique si :?x,y?E,xRy?yRx On dit queRest antisymétrique si :?x,y?E,(xRyetyRx)?x=y On dit queRest transitive si :?x,y,z?E,(xRyetyRz)?xRz Exemples :
La relation d"égalité=surEest réflexive, symétrique, antisymétrique et tran- sitive. Les relations?et?surRsont réflexives, antisymétrique et transitives. Elles ne sont pas symétriques. Les relationsurRsont antisymétriques et transitives. Elles ne sont ni réflexives, ni symétriques. La relation de divisibilité|surZest réflexive et transitive. Elle n"est ni symé- trique, ni antisymétrique : (2|(-2)et-2|2 mais-2?=2) La relation≡[n]de congruence modulonsurZest réflexive, symétrique et transitive. Elle n"est pas antisymétrique. 1.4 Relation totale ou partielle
Définition 4 :SoitRune relation binaire surE.
On dit quexetydeEsont comparable parRsi :xRyouyRx. On dit que la relationRest totale si deux éléments quelconques deEsont comparable :?x,y?E,xRyouyRx On dit que la relationRest partielle dans le cas contraire. Exemple :
Les relations?et?surRsont totales maissont partielles car on ne peut comparer deux éléments identiques. La relation de divisibilité|surZ?est partielle : on ne peut comparer 3 et 5 car l"un des deux n"est pas un diviseur de l"autre. PAUL MILAN3CPGE L1 -ALGÈBRE
2. RELATION D"ÉQUIVALENCE
2 Relation d"équivalence
2.1 Définition
Définition 5 :SoitRune relation binaire surE.
On dit queRest une relation d"équivalence surEsiRest réflexive, symétrique et transitive. 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]surZest une relation d"équivalence. On vérifie facilement qu"elle est réflexive, symétrique et transitive. Soitα?R. Une autre relation≡[α]surRest une relation d"équivalence : x≡y[α]? ?k?Z,x=y+kα. - Réflexivité :a=a+0×αdonca≡a[α] - Symétrie :a≡b[α]?a=b+kα?b=a+ (-k)α?b≡a[α] - Transitivité : (a≡b[α]etb≡c[α])?(a=b+kαetb=c+k?α)? a=k?α+kα= (k?+k)α?a≡c[α] 2.2 Classe d"équivalence. Ensemble quotient
Théorème 1 :SoitRune loi d"équivalence surE. On appelle classe d"équivalence d"un élémentxdeE, l"ensembleC(x)des élé- ments deEen relation avecxparR: C(x) ={y?E,yRx}
L"ensemble des classes d"équivalence pourRforment une partition deE: leur réunion formeEet sont deux à deux disjointes. L"ensemble des classes d"équivalence deEpourRest appelé l"ensemble quo- tient deEparRnotéE/R Remarque :Toute classe d"équivalence peut être exprimée en français sous la forme "avoir le même [... ]». Par exemple "avoir le même reste dans la division parn» dansZ. Notation usuelle pour la classe d"équivalence dex: xoux Pour la relation≡[3]
Troisclassesd"équivalence:?
0 ,1 ,2?
correspondant aux trois restes dans la division par 3 Son ensemble quotient se note :Z/3Z0
reste 01 reste 1 2 reste 2
Z PAUL MILAN4CPGE L1 -ALGÈBRE
3. RELATION D"ORDRE
L"ensemble quotientE/Rest donc un ensemble d"ensembles inclus dansP(E) Démonstration :Montrons queE/Rforme une partition deE. Notons
xla classe d"équivalence dexpourR. ?x?E,x?xcar réflexivitéxRxon en déduit queE=? x?Ex. Montrons que six∩y?=∅alorsx=y.
z? x∩y??zRx zRy??Par symétrie et transitivité xRy?x=y Exemple :
Un bipoint (A,B) est un couple de
points du plan. On définit la relationR(équipollence)
telle que : (A,B)R(C,D) si les segments [AD] et [BC] ont même milieu. AB CD I Rest une relation d"équivalence car :
[AB] et [BA] ont même milieu donc (A,B)R(A,B). (A,B)R(C,D)?m[AD] =m[BC]?m[CB] =m[DA]?(C,D)R(A,B) ?(A,B)R(C,D) (C,D)R(E,F)??m[AD] =m[BC] m[CF] =m[DE]??ABDC et CDFEparallélogrammes? ?(AB)//(CD)//(EF) AB=CD=CF??ABFE parallélogramme
m[AF] =m[BE]?(A,B)R(E,F) La classe d"équivalence du bipoint (A,B) est le vecteur -→AB . C"est une façon de définir proprement un vecteur dans le plan. 3 Relation d"ordre
3.1 Définition
Définition 6 :SoitRune relation binaire surE.
On dit queRest une relation d"ordre siRest réflexive, antisymétrique et transitive. Remarque :On note généralement une relation d"ordre :?,?,?, ... La réflexivité est imposé dans la définition des relations d"ordre. On privilégie les relations d"ordre "large» du type "inférieur ou égal ». La transitivité et l"antisymétrie permettent de hiérarchiser les éléments d"un en- semble. PAUL MILAN5CPGE L1 -ALGÈBRE
3. RELATION D"ORDRE
Exemples :
Les relations?,?surRsont des relations d"ordre tandis que < et > ne le sont pas par manque de réflexivité. La relation de divisibilité|est une relation d"ordre surN?(mais pas surZ?) : -?n?N?,n|ndonc|est réflexive. k,k??N??k=k?=1?n=n?donc|est antisymétrique. donc|est transitive. Visualisation d"une relation d"ordre : idée d"orientation. Lorsque la relation d"ordre est totale comme?dansR. On peut représenterR sur une droite -∞-7-2.5301π203+∞| | | | | ||e|⎷17 Ce n"est plus le cas lorsque la relation d"ordre est partielle comme par exemple la relation de divisibilité|dans[[1,10]]. Dans ce graphe, on se préoccupe uni- quement de l"orientation des entiers de 1 à 10. 12 3 574 6 9 108
3.2 Relation stricte associée à une relation d"ordre
Définition 7 :Soit?une relation d"ordre surE.
La relation?surEdéfinie par :?x,y?E,x?yetx?=yest antisymétrique et transitive, est appelée la relation stricte associée à? PAUL MILAN6CPGE L1 -ALGÈBRE
4. ÉLÉMENTS FONDAMENTAUX D"UN ENSEMBLE ORDONNÉ
4 Éléments fondamentaux d"un ensemble ordonné
4.1 Majorant, minorant
Définition 8 :Soient?une relation d"ordre surEetFune partie deE. On dit queFest majorée pour?s"il existeM?Etel que : ?x?F,x?M On dit queMest un majorant deFou queFest majoré parM. On dit queFest minorée pour?s"il existem?Etel que : ?x?F,m?x On dit queMest un minorant deFou queFest minorée parm. SiFest minorée et majorée alorsFest bornée pour? Remarque :Il n"y a pas d"unicité pour le majorant et le minorant. Exemples :
F={2,10,12}est minoré par 2 et majorée par 120 pour la relation de divisibi- lité surE=N. P(E)est minoré par∅et majoré parEpour la relation?sur lui-même. 4.2 Plus grand et plus petit élément
Définition 9 :Soient?une relation d"ordre surEetFune partie deE. On appelle plus grand élément deFou maximum deFtout élément deFqui majoreF. S"il en existe un, cet élément est unique et appelé le plus grand élément deF. Il est noté maxF. On appelle plus petit élément deFou minimum deFtout élément deFqui minoreF. S"il en existe un, cet élément est unique et appelé le plus petit élément deF. Il est noté minF Exemples :Avec la relation de divisibilité|surE=N?. F={2,3,6}possède un plus grand élément 6 mais pas de plus petit élément. F=N?possède un plus petit élément 1 mais pas de plus grand élément. F=N?-{1}ne possède ni plus petit ni de plus grand élément. PAUL MILAN7CPGE L1 -ALGÈBRE
4. ÉLÉMENTS FONDAMENTAUX D"UN ENSEMBLE ORDONNÉ
4.3 Borne supérieure et borne inférieur
Définition 10 :Soient?une relation d"ordre surEetFune partie deE. Il existe une borne supérieure deF(unique) pour?s"il existe un plus petit majorant deF, notée supF. Il existe une borne inférieure deF(unique) pour?s"il existe un plus grand minorant deF, notée infF. Remarque :La borne inférieure et la borne supérieure deFn"appartiennent pas nécessairement àF. Exemple :F={6,8,10}admet une borne supérieure et une borne inférieure pour la relation de divisibilité|surE=N?et . supF=ppcm(6,8,10) =120??Fet infF=pgcd(6,8,10) =2??F Théorème 2 :Soient?une relation d"ordre surEetFune partie deE. SiFpossède un plus grand (resp. petit) élément pour?, alorsFadmet une borne supérieure (resp. inférieure) pour?et : supF=maxF(resp infF=minF) Exemple :P(E)admet un plus petit et un plus grand élément au sens de l"in- clusion?qui sont∅etE. Ils correspondent alors aux bornes deP(E) PAUL MILAN8CPGE L1 -ALGÈBRE
quotesdbs_dbs49.pdfusesText_49
c Christophe Bertault - MPSI Relations d’ordre