[PDF] [PDF] RELATIONS BINAIRES - Christophe Bertault

View - Download [PDF] RELATIONS BINAIRES - Christophe Bertault

Previous PDF

Next PDF

Christophe Bertault — Mathématiques en MPSI

RELATIONS BINAIRES

Dans tout ce chapitre,Eest un ensemble quelconque.

1 RELATIONS BINAIRES SUR UN ENSEMBLE

Les relations sont partout — et dans le monde mathématique, et dans la vraie vie. Nous passons notre temps à comparer

des objets, à les mettre en rapport les uns avec les autres selon tel ou tel aspect. Les phrases suivantes, pourtant diverses, sont

toutes l"affirmation d"un lien entre deux objets : " Minou et Matou ont la même couleur de poils », " 3?5 », " Truc

est amoureux de Bidule », " 4 divise 12 », " 1+i et 1-i ont le même module », etc.

De quelle manière pourrions-nous définir proprement la notion de relation en mathématiques? QuelOBJETla relation

1<3 et 2<3. Formellement, nous pourrions définir la relation (1,2),(1,3),(2,3) des couples

(x,y)??1,3?2pour lesquelsx ?1,3?serait quant à elle l"ensemble (1,1),(1,2),(1,3),(2,2),(2,3),(3,3) . Plus généralement :

Définition(Relation binaire sur un ensemble)On appellerelation binaire sur Etoute partie deE×E.

Si?est une telle relation, la proposition(x,y)? ?sera notée de préférencex?ypour tousx,y?E, et lue "xest

en relation avecypar?».

?Attention !Parce que le couple(x,y)n"est pas le couple(y,x), la relationx?ypeut être vraie sans que la relation

y?xle soit. Dieu que l"amour est cruel! ExempleVous connaissez depuis toujours certaines relations binaires :

— la relation d"égalité=surE, — les relations?et — la relation?sur??, définie pour toutes fonctionsf,g???par :f?g?? ?x??,f(x)?g(x), — la relation de divisibilité | sur?, définie pour tousm,n??par :m|n?? ?k??,n=km,

— pour toutα??, la relation≡[α]de congruence moduloαsur?, définie pour tousx,y??par :

x≡y[α]?? ?k??,x=y+kα. Définition(Propriétés des relations binaires)Soit?une relation binaire surE. •Réflexivité :On dit que?estréflexivesi :?x?E,x?x. •Transitivité :On dit que?esttransitivesi :?x,y,z?E, x?yety?z =?x?z. •Symétrie :On dit que?estsymétriquesi :?x,y?E,x?y=?y?x. •Antisymétrie :On dit que?estantisymétriquesi :?x,y?E, x?yety?x =?x=y.

Exemple

•La relation d"égalité=surEest réflexive, transitive, symétrique et antisymétrique.

•Les relations?sur?et??sontréflexives, transitives et antisymétriques. Elles nesontpas symétriques carparexemple

1?2 mais 2?1, et de même(x?-→1)?(x?-→2)mais(x?-→2)?(x?-→1).

•La relation

•La relation | de divisibilité sur?est réflexive et transitive, mais elle n"est pas antisymétrique car par exemple-2|2

et 2|-2 alors que-2?=2. •La relation d"inclusion?sur?(E)est réflexive, transitive et antisymétrique. •La relation " avoir le même signe » sur??est réflexive, transitive et symétrique. 1

Christophe Bertault — Mathématiques en MPSI

2 RELATIONS D"ÉQUIVALENCE

Définition(Relation d"équivalence)On appellerelation d"équivalence sur Etoute relation binaire surEà la fois

réflexive, transitive et symétrique. Les relations d"équivalence sont généralement notées≂ou?ou≈ou≡...

ExempleLa relation d"égalité=surEet la relation " avoir le même signe » sur??sont des relations d"équivalence.

ExemplePour toutα??, la relation≡[α]de congruence moduloαsur?est une relation d"équivalence.

De manière analogue, pour toutn??, la relation≡[n]de congruence modulonsur?est une relation d"équivalence.

Démonstration

•Réflexivité :Pour touta??:a=a+0×αet 0??, donca≡a[α].

•Transitivité :Soienta,b,c??. Sia≡b[α]etb≡c[α]:a=b+kαetb=c+lαpour certains

k,l??, donc :a=b+kα= (c+lα)+kα=c+(k+l)αaveck+l??, donca≡c[α]. •Symétrie :Soienta,b??. Sia≡b[α]:a=b+kαpour un certaink??, doncb=a+(-k)αavec -k??, doncb≡a[α].

Théorème(Classes d"équivalence d"une relation d"équivalence, ensemble quotient)Soit≂une relation d"équi-

valence surE.

•Classes d"équivalence :Pour toutx?E, l"ensembley?E|x≂yest appelé laclasse d"équivalence de x

(pour≂). Ces classes d"équivalence forment une partition deE.

•Ensemble quotient :L"ensemble des classes d"équivalences deEpour≂est appelé l"ensemble quotient de E par

≂et souvent notéE≂. E

Une classe

d"équivalence

Une classe

d"équivalence

Une classe d"équivalence

La notion d"ensemble quotient est hors programme mais il n"est pas inutile de l"avoir quelque part en tête. Vous noterez bien que le quotientE≂est unENSEMBLE D"ENSEMBLES, en l"occurrence un ensemble de parties deE.

Ce que ce théorème raconte, c"est que la relation d"équivalence≂peut être représentée

comme une carte au sens géographique. Chaque classe d"équivalence est comme un pays à

l"intérieur deEdont les éléments sont caractérisés par une nationalité. LemondeEse trouve

ainsi partitionné en pays.

On peut dire les choses autrement. Toute relation d"équivalence peut être exprimée en français sous la forme " Avoir le

même (...) » : " avoir le même signe », " avoir le même reste de division euclidienne parn», etc.

DémonstrationPour toutx?E, notons cl(x)la classe d"équivalence dexpour≂.

•Pour toutx?E:x≂xpar réflexivité, doncx?cl(x), donc cl(x)est non vide. Rappelons à cette

occasion que cette condition différencie les partitions des recouvrements disjoints.

•Clairement :E=?

x?Ecl(x)carx?cl(x)pour toutx?E.

•Soientx,y?E. Pour montrer que cl(x)et cl(y)sont égales ou disjointes, supposons-lesNONdisjointes et

montrons qu"elles sont égales. Par hypothèse, nous pouvonsnous donner un élémentzcommun à cl(x)et

cl(y). Par symétrie des rôles dexety, il nous suffit de montrer que cl(x)?cl(y). Soitt?cl(x). D"abordz?cl(y), doncy≂z. Ensuitez?cl(x), doncx≂z, puisz≂x. Enfint?cl(x), doncx≂t. Conclusion :y≂tpar transitivité.

ExempleLa relation " avoir le même signe » sur??possède deux classes d"équivalence, la classe??+et la classe??-.

L"ensemble quotient associé est donc l"ensemble d"ensembles??+,??-.

ExempleSoitα >0. Les classes d"équivalences de?pour la relation de congruence moduloαsont exactement les en-

semblesα?+x,xdécrivant[0,α[, sans répétition. L"ensemble quotient associé est donc l"ensemble

α?+x|x?[0,α[

DémonstrationLe théorème d"existence et d"unicité de la partie entière peut être formulé ainsi :

?x??,?!(k,?)??×[0,1[,x=k+?, d"où en particulier :?x??,?!(k,?)??×[0,1[,x

α=k+?,

et finalement, après multiplication parα:?x??,?!??[0,α[,x≡?[α]. Cette proposition signifie

que tout réel appartient à la classe d"équivalence pour≡[α]d"un et un seul élément de[0,α[.

2

Christophe Bertault — Mathématiques en MPSI

ExempleSoitn???. Nous établirons au prochain chapitre " Arithmétique des entiers relatifs » lethéorème de la division

euclidiennesuivant :?a??,?!r??0,n-1?,a≡r[n], selon lequel tout entier relatif appartient à la classe

d"équivalence pour≡[n]d"un et un seul élément de?0,n-1?, donc que les classes d"équivalence de?pour cette relation

sont exactementn?,n?+1, ...,n?+n-1. On note traditionnellement? n?l"ensemble quotient n?,n?+1,...,n?+n-1

3 RELATIONS D"ORDRE

Définition(Relation d"ordre, relation d"ordre totale)

•Relation d"ordre :On appelle (relation d")ordre sur Etoute relation binaire surEà la fois réflexive, transitive

et antisymétrique. Les relations d"ordre sont généralement notées?ou?ou?ou?... •Relation d"ordre totale :Soit?une relation d"ordre surE. On dit que?esttotalesi : ?x,y?E,x?youy?x.

Dans le cas contraire, on dit que?estpartielle.

Quand?est une relation d"ordre, la relationx?yest généralement lue "xest plus petit quey», mais rien ne s"oppose

à ce qu"on la lise "xest plus grand quey», c"est pure affaire de convention et il convient seulementd"être cohérent. Être

plus grand en vieillesse, c"est être plus petit en jeunesse.

Une relation d"ordre hiérarchise les éléments qu"elle compare, mais qu"attendons-nous intuitivement des notions de clas-

sement, hiérarchie, ordre, préférence?

— Essentiellement la transitivité, c"est ce qui compte le plus. SiAest plus grand queBetBplus grand queC, alorsAest

plus grand queC. Toute entorse à la transitivité contredit l"idée d"une hiérarchie.

— La réflexivité est imposée dans la définition des relations d"ordre mais aurait pu ne pas l"être. L"exiger revient simple-

ment à privilégier les relations " inférieurOU ÉGAL» aux relations d"infériorité stricte.

— L"antisymétrie est un autre choix conventionnel. La relation " être plus âgé (ou du même âge) que » est transitive et

réflexive sur l"ensemble des êtres humains, mais pas antisymétrique car deux individus peuvent être nés au même

instant. Bien que non antisymétrique, cette relation a pournous la saveur d"une relation hiérarchique.

En résumé, les relations d"ordre sont des exemples importants de hiérarchies, mais ne formalisent pas toutes les hiérar-

chies concevables.

Exemple

•La relation?est une relation d"ordre totale sur?. En particulier, les réels sont tous comparables à 0 — positifs ou

négatifs — et c"est pour cela qu"on a pu définir la valeur absolue|x|d"un réelxen distinguant les casx?0 etx<0.

•La relation?est une relation partielle d"ordre sur??. Les fonctions cosinus et sinus, par exemple, ne sont pas

comparables : sin?cos et cos?sin.

•La relation d"inclusion?est une relation d"ordre sur?(E), partielle dès queEcontient au moins deux éléments. En

effet, pour tousaetbélémentsDISTINCTSdeE:a??betb??a.

ExempleLa relation de divisibilité | n"est pas une relation d"ordresur?, mais c"en est une sur?, partielle car 2 et 3 ne

sont comparables : 2? |3 et 3? |2.

DémonstrationNous avons déjà vu que la relation | sur?n"est pas antisymétrique. Travaillons donc sur?.

•Réflexivité :Pour toutn??:n|ncarn=1×n.

•Transitivité :Soientn,n?,n????des entiers pour lesquelsn|n?etn?|n??. Aussitôtn?=knetn??=k?n?

pour certainsk,k???, donc :n??=k?n?=kk?naveckk???, doncn|n??. •Antisymétrie :Soientn,n???des entiers pour lesquelsn|n?etn?|n. Aussitôtn?=knetn=k?n?pour certainsk,k???, doncn=k?n?=kk?n.

— Sin=0 :n?=kn=0, doncn=n?.

— Sin?=0 :kk?=1, orketk?sont desENTIERS NATURELS,donck=k?=1, doncn=k?n?=n?. 3

Christophe Bertault — Mathématiques en MPSI

Remarque importante. Les relations d"ordre excluent les boucles. Une boucle de la formex1?x2?x3?...?xn?x1

entre des éléments distinctsavecn?2estinconcevable carla transitivité et l"antisymétrie forcent l"égalitéx1=x2=...=xn.

Sans boucles, les relations d"ordre ont comme une orientation naturelle. De même que les fleuves et les rivières coulent

en direction de la mer sans jamais boucler, on va toujours de l"avant quand on parcourt une relation d"ordre, on ne tourne

jamais en rond et c"est ça qui nous fait dire que certains éléments sont plus petits/grands que d"autres.

?-101?2eLa relation d"ordre?sur?estTOTALEet c"est pour cela que nous nous représentons?commeuneligneunique etnonpascommeunréseau fluvial compliqué doté d"une foule d"affluents.

Ona représenté ci-dessous àgauchela relation?sur l"ensemble des parties de1,2,3et àdroite la relation dedivisibilité

| sur?1,20?. Le fait que ces relations ne sont pas totales se visualise bien, il ne suffit pas d"UNEfibre pour représenter ces

relations, il en faut plusieurs. 1 2 3 1,2 1,3 2,3 1,2,3 1 2

3 57111317 194

691014158

1218 2016

Définition(Relation stricte associée à une relation d"ordre)Soit?une relation d"ordre surE. La relation?sur

Edéfinie pour tousx,y?Epar :x?y??x?yetx?=yest transitive et antisymétrique, appelée la relation stricte associée à?.

Démonstration

•Transitivité :Soientx,y,z?E. On supposex?yety?z. En particulierx?yety?z, doncx?z

par transitivité de?. L"égalitéx=zest-elle possible? Le cas échéantx?yety?x, doncx=ypar

antisymétrie de?— contradiction. Bref :x?zetx?=z, i.e.x?z. •Antisymétrie :Soientx,y?E. Six?yety?x, alorsx?yety?x, doncx=ypar antisymétrie de ExempleNaturellement, la relation usuelleLa fin du chapitre généralise rapidement certaines notions du chapitre " Compléments sur les réels ».

Définition(Majorant/minorant)Soient?une relation d"ordre surEetAune partie deE. •Partie majorée/minorée :On dit queAestmajorée(pour?) si :?M?E,?a?A,a?M. Un telMest appeléUNmajorant de A. On dit aussi queAestmajorée par Mou encore queM majore A. On définit de même les notions de partieminoréeet deminorant.

•Partie bornée :On dit queAestbornée(pour?) si elle est à la fois majorée et minorée.

Exemple

•L"ensemble8,10,12est minoré par 2 et majoré par 120 pour la relation de divisibilité | sur?.

• ?(E)est minoré par∅et majoré parEpour la relation d"inclusion?.

Définition(Plus grand/petit élément, maximum/minimum)Soient?une relation d"ordre surEetAune partie

deE. On appelleplus grand élément de Aoumaximum de Atout élément deAqui majoreA.

S"IL EN EXISTE UN, un tel plus grand élément est unique et donc appeléLEplus grand élément deA, noté maxA.

On définit de même la notion deplus petit élémentouminimum. 4

Christophe Bertault — Mathématiques en MPSI

DémonstrationPour l"unicité, même preuve qu"au chapitre " Compléments sur les réels ».

ExempleOn travaille avec la relation d"inclusion?sur?(E)et on suppose queEcontient au moins deux éléments.

L"ensemble des singletons deEne possède alors pas de plus grand élément. DémonstrationParl"absurde, sil"ensemble dessingletons deEpossèdeunplusgrand élémente:x?e pour toutx?E, i.e.x=e, doncE=e— contradiction carEpossède au moins deux éléments. ExempleOn travaille dans cette série d"exemples avec la relation dedivisibilité | sur?.

(i) L"ensemble2,3,6possède un plus grand élément — c"est 6 — mais pas de plus petitélément.

(ii) 0 est le plus grand élément de?— eh oui! — et 1 est son plus petit élément. (iii) L"ensemble?\0,1ne possède ni plus petit élément ni plus grand élément.

Démonstration

(ii) L"entier 0 est élément de?et plus grand que tout le monde car tout le monde le divise, donc c"est le plus

quotesdbs_dbs43.pdfusesText_43

[PDF] ensemble quotient exercice corrigé

[PDF] relation d'equivalence exercice corrigé pdf

[PDF] exercice relation d'equivalence

[PDF] chargaff adn

[PDF] ordre de grandeur de la voie lactée

[PDF] a+t / g+c

[PDF] niveaux d'organisation du vivant svt

[PDF] les différents niveaux d'organisation du vivant

[PDF] niveau d'organisation du vivant exercices

[PDF] les différents niveaux d'organisation des êtres vivants

[PDF] niveau d'organisation biologique

[PDF] décomposition d'un vecteur dans une base 1ere s

[PDF] diamètre du noyau d'un atome

[PDF] ordre de grandeur electron

[PDF] ordre de grandeur d'un noyau atomique