TD3 Relations Correction

Télécharger le TD3 Relations Correction en pdf

Pages : 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42

Page 1 : Algebre-Premier semestre 2023CY TechTD AlgebreRelations.Algebre

Page 2 : Exercice 1Les relations suivantes sont-elles symetriques, reflexives, transitives ?1sur R, l’egalite.2sur R, l’ordre strict .3sur R, l’ordre .4sur R, la relation avoir le mˆeme carre .5sur R, la relation avoir le mˆeme sinus .6sur l’ensemble des droites du plan, le parallelisme.7sur l’ensemble des droites du plan, l’orthogonalite.Algebre

Page 3 : Exercice 1Les relations suivantes sont-elles symetriques, reflexives, transitives ?1Sur R, l’egalite.Solution : L’egalite est symetrique, reflexive et transitive.2Sur R, l’ordre strict .Solution : est seulement transitive.3Sur R, l’ordre .Solution : est seulement reflexive et transitive.4Sur R, la relation avoir le mˆeme carre .Solution : avoir le mˆeme carre est symetrique, reflexive ettransitive.5Sur R, la relation avoir le mˆeme sinus .Solution : avoir le mˆeme sinus est symetrique, reflexive et transitive.6Sur l’ensemble des droites du plan, le parallelisme.Solution : le parallelisme est symetrique, reflexive et transitive.7Sur l’ensemble des droites du plan, l’orthogonalite.Solution : l’orthogonalite est seulement symetrique.Algebre

Page 4 : Exercice 2Etudier les proprietes des relations suivantes. Dans le cas d’une relationd’equivalence, preciser les classes. Dans le cas d’une relation d’ordre,preciser si elle est totale et si l’ensemble admet un plus petit ou un plusgrand element.1Soit E un ensemble, on definit sur PE :ARB ⇐⇒A B.2Soit E un ensemble, on definit sur PE :ARB ⇐⇒A B = .3Sur Z on definit : aRb ⇐⇒a et b ont la mˆeme parite.4Sur Z on definit : aRb ⇐⇒n N, a b = 3n.5Sur Z on definit : aRb ⇐⇒a b est divisible par 3.6Sur R on definit :xRy ⇐⇒x2 y 2 = x y.Algebre

Page 5 : Exercice 2Soit E un ensemble, on definit sur PE :ARB ⇐⇒A B.Reflexive : Oui. En effet, pour tout partie A de E, nous avons A A.Donc ARA.Symetrique : Non. En effet, A B n’implique pas B A sauf siA = B.Antisymetrique : Oui. En effetA BetB A=⇒A = BTransitive : Oui. En effet, si A B et B C, alorsA B C=⇒A C.C’est donc une relation d’ordre.Algebre

Page 6 : Exercice 2La relationARB ⇐⇒A B.est une relation d’ordre partiel, sauf si E = ou E est un singleton i.e.E = a. En effet, si a E, b E avec a ̸= b, alorsaetbne sont pas comparables. Le plus petit element par rapport a l’inclusionest et le plus grand est E.Algebre

Page 7 : Exercice 2Soit E un ensemble, on definit sur PE :ARB ⇐⇒A B = .Reflexive : Non. En effet, pour tout partie non vide A de E, nous avonsA A = A ̸= .Donc A n’est pas en relation avec A.Symetrique : Oui. En effet, si ARB alors= A B = B A=⇒BRA.Antisymetrique : Non. En effet, on peut avoirA B = = B A,sans pour autant avoir A = B.Transitive : Non. En effet, A B = et B C = n’implique pasnecessairement que A C = .Algebre

Page 8 : Exercice 2Sur Z on definit :aRb ⇐⇒n N, a b = 3n.Reflexive : Oui. En effet, pour tout a R, nous avons a a = 0 = 3 · 0. DoncaRa.Symetrique : Non. En effet, si a b = 3n pour n N.Alorsb a = 3n = 3n.Puisque n /N, on conclut que b n’est pas en relation avec a.Antisymetrique : Oui. En effet, sia b = 3 ·nzNetb a = 3 · n′zN=⇒3n = 3n′=⇒nzN= n′zN= 0.Donc a = b.Transitive : Oui. En effet, si a b = 3n et b c = 3n′, alorsa c = a b + b c = 3n + n′=⇒aRc.Algebre

Page 9 : Exercice 2La relationaRb ⇐⇒n N, a b = 3n.est donc une relation d’ordre. Elle est une relation d’ordre partiel, parexemple 4 et 5 ne sont pas comparables. Puisquea R a + 3eta 3 R aon conclut que l’ensemble Z ne possede ni de minorants ni de majorantpar rapport a R. Il n’y a donc pas de plus petit ou plus grand element.Algebre

Page 10 : Exercice 2Sur Z on definit :aRb⇐⇒a b est divisible par 3.Notons quea b est divisible par 3⇐⇒k Z, a b = 3k.DoncaRb⇐⇒k Z, a b = 3k.Reflexive : Oui. En effet, pour tout a R, nous avonsa a = 3 · 0.Donc aRa.Symetrique : Oui. En effet, si a b = 3k pour k Z. Alorsb a = 3k = 3k.Donc bRa.Algebre

Page 11 : Exercice 2Antisymetrique : Non. Par exemple, 3 est divisible par 3 et 3 estdivisible par 3, mais 3 ̸= 3.Transitive : Oui. En effet, si a b = 3k et b c = 3k′, alorsa c = a b + b c = 3k + k′.Donc aRc.La relationaRb⇐⇒a b est divisible par 3.est donc une relation d’equivalence. Notons que d’apres la divisioneuclidienne, pour tout entier n Z on an = 3k + ravecr = 0 ou r = 1 ou r = 2.Par consequent, R possede trois classes d’equivalence :Les multiples de 3, qui s’ecrivent 3n.Les nombres qui s’ecrivent 3n + 1.Les nombres qui s’ecrivent 3n + 2.Algebre

Page 12 : Exercice 2On definit sur R la relationxRy⇐⇒x2 y 2 = x y.Tout d’abord, notons quexRy⇐⇒x2 y 2 = x y⇐⇒x2 x = y 2 y.Reflexive : Pour tout x R, nous avonsx2 x = x2 x=⇒xRx.Symetrique : Pour tout x, y R, nous avonsx2 x = y 2 y=⇒y 2 y = x2 x.DoncxRy=⇒yRx.Transitive :Pour tout x, y, z R, nous avonsx2 x = y 2 yety 2 y = z2 z=⇒x2 x = z2 z.DoncxRyetyRz=⇒xRz.Algebre

Page 13 : Exercice 2La relationxRy⇐⇒x2 y 2 = x y.est donc une relation d’equivalence. Determinons la classe d’equivalenced’un element x de R.Soit x R, alorsx=y R : xRy=y R :x2 x = y 2 y=y R :x2 y 2 x y = 0=y R :x yx + y x y = 0=y R :x yx + y 1 = 0=y R :y = xouy = 1 x.Ainsi, la classe de x est constituee de deux elements, sauf six = 1 x⇐⇒x = 12.Dans ce cas, la classe est donnee par 12.Algebre

Page 14 : Exercice 3 Produit cartesienSoit deux ensembles E et F et deux relations d’equivalences R sur E et S surF. On definit alors sur E × F la relation :x, y x′, y ′⇐⇒xRx′et yS y ′Verifier que est une relation d’equivalence.Reflexive : Soit x, y E × F. Montrons que x, y x, y. Puisque R etS sont des relations d’equivalence, nous avonsxRxetyS y.Donc x, y x, y.Symetrique : Soit x, y E × F et x′, y ′ E × F. Supposonsx, y x′, y ′, c’est-a-direxRx′etyS y ′.Puisque R et S sont symetriques, nous avonsxRx′=⇒x′RxyS y ′=⇒y ′S y.Donc x′, y ′ x, y.Algebre

Page 15 : Exercice 3 Produit cartesienTransitive : Soient x, y, x′, y ′ et x′′, y ′′ trois elements de E × F.Supposonsx, y x′, y ′etx′, y ′ x′′, y ′′.DoncxRx′etx′Rx′′yS y ′ety ′S y ′′.Puisque R et S sont transitives, nous avonsxRx′etx′Rx′′=⇒xRx′′yS y ′ety ′S y ′′=⇒yS y ′′Donc x, y x′′, y ′′.Algebre

Page 16 : Exercice 41On definit une relation binaire sur R+ parx y⇐⇒n N,y = xn.Montrer que est une relation d’ordre. Cet ordre est-il total ?2Soit la relation definie sur E = x, y R2 : x y parx, y x′, y ′⇐⇒x, y = x′, y ′ouy x′.Montrer que est une relation d’ordre sur E.3Soit E un ensemble et f : E →R une application injective. Ondefinit sur E une relation binaire parx y⇐⇒f x f y.Montrer que est une relation d’ordre sur E.Algebre

Page 17 : Exercice 4On definit une relation binaire sur R+ parx y⇐⇒n N,y = xn.Montrer que est une relation d’ordre. Cet ordre est-il total ?Reflexive : Soit x R+, alorsx = x1.Donc x x.Antisymetrique : Soit x R+ et y R+. Supposons x y et y x,montrons x = y. Par hypothesen N,y = xnetm N,x = y m.D’ouy = xn = y mn = y mn.Si y = 1, on obtient x = 1m = 1, donc x = y. Si y ̸= 1 alorsy = y mn =⇒elny = elnymn =⇒lny = lny mn =⇒lny = mn lny.Comme y ̸= 1, on peut diviser par lny pour obtenir mn = 1. D’ou on conclutm = n = 1. Ainsi x = y 1 = y.Algebre

Page 18 : Exercice 4Transitive : Supposons x y et y z, montrons x z. Par hypothesen N,y = xnetm N,z = y m.D’ouz = y m = xnm = xmn.Donc x z.La relationx y⇐⇒n N,y = xn.est donc une relation d’ordre. Elle est une relation d’ordre partiel. Eneffet, 2 et 3 ne sont pas comparables. Si2n = 3m=⇒ln2n = ln3m=⇒n ln2 = m ln3.Ce qui implique queln2ln3 = mn=⇒ln2ln3 est rationnel.Contradiction ! Donc 2 et 3 ne sont pas comparables.Algebre

Page 19 : Exercice 4Soit la relation definie sur E = x, y R2 : x y parx, y x′, y ′⇐⇒x, y = x′, y ′ouy x′.Montrer que est une relation d’ordre sur E.Reflexive : Soit x, y E, alorsx, y = x, y=⇒x, y = x, youy x=⇒x, y x, y.Antisymetrique : Supposons x, y x′, y ′ et x′, y ′ x, y. Montronsx, y = x′, y ′. Par hypothesex, y = x′, y ′ ou y x′etx′, y ′ = x, youy ′ x.Ce qui est equivalent ax, y = x′, y ′ ouy x′ety ′ x.Maintenant, puisque x y et x′ y ′ car x, y E et x′, y ′ E on deduitx y x′ et x′ y ′ x=⇒x = x′y x′ y ′ et y ′ x y=⇒y = y ′Donc x, y = x′, y ′.Algebre

Page 20 : Exercice 4Transitive : Supposons x, y x′, y ′ et x′, y ′ x′′, y ′′. Montronsx, y x′′, y ′′. Par hypothesex, y = x′, y ′ ou y x′etx′, y ′ = x′′, y ′′ouy ′ x′′.Ce qui est equivalent ax, y = x′, y ′ et x′, y ′ = x′′, y ′′oux, y = x′, y ′ et y ′ x′′oux′, y ′ = x′′, y ′′ et y x′ouy x′ et y ′ x′′Maintenantx, y = x′, y ′ et x′, y ′ = x′′, y ′′=⇒x, y = x′′, y ′′x, y = x′, y ′ et y ′ x′′=⇒y = y ′ x′′x′, y ′ = x′′, y ′′ et y x′=⇒y x′ = x′′y x′ et y ′ x′′=⇒y x′ y ′ x′′.Ainsi on a x, y = x′′, y ′′ ou y x′′. Donc x, y x′′, y ′′. Il s’agit doncd’une relation d’ordre.Algebre

Page 21 : Exercice 4Soit E un ensemble et f : E →R une application injective. On definit sur Eune relation binaire parx y⇐⇒f x f y.Montrer que est une relation d’ordre sur E.Reflexive : Soit x E, alorsf x f x.Donc x x.Antisymetrique : Supposons x y et y x, montrons x = y. Par hypothesef x f yetf y f x=⇒f x = f y.Puisque f est injective on conclut x = y.Transitive : Supposons x y et y z, montrons x z. Par hypothesef x f yetf y f z=⇒f x f y f z.Donc x z.Il s’agit d’une relation d’ordre.Algebre

Page 22 : Exercice 5On definit sur R2 la relation :x, y x′, y ′ ⇐⇒x x′ y ′ y.1Verifier que c’est une relation d’ordre.2Dessiner les ensembles des majorants et des minorants d’un couplea, b.3L’ordre est-il total ?Solution :Reflexive : Soit x, y R2. Nous avonsx x = 0 0 = y y.Donc x, y x, y.Algebre

Page 23 : Exercice 5Antisymetrique : Supposons x, y x′, y ′ et x′; y ′ x, y, montronsx, y = x′, y ′. Par hypothese0 x x′ y ′ yet0 x′ x y y ′=⇒0 = y ′ y.Donc y = y ′. Ce qui implique que x = x′. Par consequent x, y = x′, y ′.Transitive : Supposons x, y x′, y ′ et x′, y ′ x′′, y ′′, montronsx, y x′′, y ′′. Par hypothesex x′ y ′ yetx′ x′′ y ′′ y ′Maintenantx x′′ = x x′ + x′ x′′.Gˆrace a l’inegalite triangulaire nous pouvons donc ecrirex x′′ = x x′ + x′ x′′x x′ + x′ x′′y ′ y + y ′′ y ′=y ′′ y.Donc, x, y x′′, y ′′.Algebre

Page 24 : Exercice 5La relationx, y x′, y ′ ⇐⇒x x′ y ′ y.est donc une relation d’ordre.Soit a, b R2. Donnons une representation graphique de l’ensembledes majorants et des minorants de a, b. Pour cela, soit x, y unmajorant de a, b. Alorsa, b x, y=⇒0 x a y b,d’oub y x a y b.Cela est equivalent ay x + b aety x + a + b.De mˆemex, y a, b⇐⇒y x + b aety a + b x.Algebre

Page 25 : Exercice 5Ce qui nous donne le suivant diagrammeSur le diagramme, on remarque que si deux points ont la mˆemeordonnee, ils ne pourront pas ˆetre compare. Par exemple, 2, 1 et 5, 1ne sont pas comparable car2 5 = 5 2 = 3 1 1 = 0.L’ordre n’est donc pas total.Algebre

Page 26 : Exercice 6Soit n 0 un entier et n la relation binaire definie sur Z par :a n b⇐⇒n divise a b.On parle d’egalite modulo n, aussi notee a b mod n ou a b n.1Montrer que n est une relation d’equivalence.2Combien existe-t-il de classes d’equivalence ? Donner un systeme derepresentants.3Montrer que n est compatible avec l’addition et la multiplicationde Z.Algebre

Page 27 : Exercice 6Sur Z on definit :a n b⇐⇒ndivisea b.Notons quendivisea b⇐⇒k Z, a b = nk.Donca n b⇐⇒k Z, a b = nk.Reflexive : Oui. En effet, pour tout a Z, nous avonsa a = n · 0.Donc a n a.Symetrique : Oui. En effet, si a b = nk pour k Z. Alorsb a = nk = nk.Donc b n a.Algebre

Page 28 : Exercice 6Transitive : Oui. En effet, si a b = nk et b c = nk′, alorsa c = a b + b c = nk + k′.Donc a n c.La relationa n b⇐⇒a b est divisible par n.est donc une relation d’equivalence.Algebre

Page 29 : Exercice 6Combien existe-t-il de classes d’equivalence ? Donner un systeme derepresentants.Solution : Notons que d’apres la division euclidienne, pour tout entier m Zon a m = nk + r avec 0 r n 1. Autrement ditm = nk + ravecr = 0 ou r = 1 ou r = 2 · · ·ou r = n 1.Ceci implique que pour tout m Z, on am n 0 ou m n 1 ou m n 2 ou· · ·ou m n n 1.Par consequent, n possede n classes d’equivalence :Les multiples de n, qui s’ecrivent nk. Pour representant de cette classe onpeut choisir 0.Les nombres qui s’ecrivent nk + 1. Pour representant de cette classe onpeut choisir 1.Les nombres qui s’ecrivent nk + 2. Pour representant de cette classe onpeut choisir 2....Les nombres qui s’ecrivent nk + n 1. Pour representant de cette classeon peut choisir n 1.Algebre

Page 30 : Exercice 6Un systeme de representants pour les classes d’equivalence de n estdonne donc par0 , 1 , 2 , · · · , n 1.L’ensemble des classes d’equivalences est note :Z/nZ = 0 , 1 , 2 , · · · , n 1Algebre

Page 31 : Pour aller plus loin - Exercice 6Montrer que n est compatible avec l’addition et la multiplication de Z.Solution :Addition : Soit a n b et c n d. On doit montrer quea + c n b + dPar definition, il existe k et k′ tels quea = nk + betc = nk′ + d.Ainsi,a + c = nk + k′ + b + d=⇒a + c n b + d.La relation n est donc compatible avec l’addition, c’est-a-dire quel’addition ne depend pas du representant choisit pour la classe.Algebre

Page 32 : Pour aller plus loin - Exercice 6Multiplication : Soit a n b et c n d. On doit montrer quea · c n b · dPar definition, il existe k et k′ tels quea = nk + betc = nk′ + d.Ainsi,a · c = nnkk′ + kd + k′b + bd=⇒a · c n b · d.La relation n est donc compatible avec la multiplication, c’est-a-dire que la multiplication ne depend pas du representant choisitpour la classe.Algebre

Page 33 : Exercice 7Soit X un ensemble et R une relation d’equivalence sur X. Pour x X,on note x sa classe d’equivalence. Montrer que :1x X, x x.2x, y X 2 on ax y ⇐⇒y x ⇐⇒x = y ⇐⇒x y ̸= .Solution :1Soit x X, montrons x x. Comme R est une relationd’equivalence, elle est reflexive. Donc xRx, d’oux x.2Soit x, y X 2, montronsx y ⇐⇒y x ⇐⇒x = y ⇐⇒x y ̸= .Pour cela il suffit de montrerx y =⇒y x =⇒x = y =⇒x y ̸= =⇒x y.Algebre

Page 34 : Exercice 7Commen¸cons par montrer l’implicationx y =⇒y xOn ax y ⇐⇒yRx=⇒xRypar symetrie de R=⇒y x.Montrons maintenanty x =⇒x = ySoit z x, alors xRz. Or y x, d’ou xRy. Par symetrie et transitivite deR nous avonsxRyetxRz=⇒yRxetxRz=⇒yRz.D’ou z y et x y. De mˆeme, si z y, alors yRz. Or y x, d’ouxRy. Par transitivite de R nous avonsxRyetyRz=⇒xRz.D’ou z x et y x. Donc x = y.Algebre

Page 35 : Exercice 7Pour montrer l’implicationx = y =⇒x y ̸= il suffit de noter que, comme x = y on deduitx y = x.Maintenant, puisque R est reflexive, on a xRx. Doncx x = x y=⇒x y ̸= .Montrons finalement l’implicationx y ̸= =⇒x y.Soit z x y. Alors z x et z y. D’ouyRzetxRz=⇒zpar symetrie de RyRzetzRx=⇒zpar transitivite de RyRx.Donc x y.Algebre

Page 36 : A faire chez soi - Exercice 8Etudier la relation R definie sur l’ensemble des applications de R dans R parf Rg⇐⇒A 0, x R, x A =⇒f x = gxNotons que la fonction f est en relation avec g si et seulement si les deuxfonctions sont egales a partir d’un certain rang a partir de un certain moment.Solution : Etudions les proprietes de la relation :Reflexive : Soit f une application de R dans R. Puisque pour tout x R on af x = f x,on conclut que f Rf . En effet, il suffit de prendre n’importe quel reel A 0pour avoir f x = f x.Symetrique : Soient f et g deux applications de R dans R. Supposons quef Rg et montrons que gRf . Puisque f Rg, il existe A 0 tel que pour toutx R avec x A on af x = gx=⇒gx = f x.Ce qui implique que pour tout x R avec x A on a gx = f x. DoncgRf .Algebre

Page 37 : A faire chez soi - Exercice 8Antisymetrie : Soient f et g deux applications de de R dans R. Supposons quef Rg et gRf . C’est-a-dire, il existe A 0, tel quef x = gxx R, x A.Est-il vrai que f = g ? Non, car mˆeme si f = g pour tout x R avec x A,on n’a pas forcement f = g sur R. Pour voir cela il suffit de prendre, parexemple, deux fonctions qui co¨ıncident sur Rmais qui sont differentes en 0.Transitive : Soient f , g et h trois applications de R dans R. Supposons f Rg etgRh. Alors il existe A1 0 et A2 0 tels quepour toutx A1on af x = gxpour toutx A2on agx = hx.Par consequent, en prennant A = maxA1, A2 on conclutpour toutx Aon af x=zxA1gx=zxA2hx.Donc f Rh.Finalement, comme R est reflexive, symetrique et transitive on en deduit quela relation est une relation d’equivalence.Algebre

Page 38 : A faire chez soi - Exercice 9Soit E un ensemble et R une relation binaire sur E, reflexive ettransitive. On definit la relation :xS y⇐⇒xRyetyRxLa relation S est elle une relation d’equivalence ?Solution :Reflexive : Soit x E, montrons xS x. Puisque R est reflexive nousavonsxRxetxRxDonc xS x.Symetrique : Soient x et y deux elements dans E. Supposons xS y etmontrons yS x. Puisque xS y, nous avonsxRyetyRx=⇒yRxetxRy.D’ou yS x.Algebre

Page 39 : A faire chez soi - Exercice 9Transitive : Soient x, y et z trois elements dans E. Supposons xS y etyS z, montrons xS z. Par hypothesexRyetyRxetyRzetzRy⇐⇒xRyetyRzetzRyetyRxPar transitivite de R, nous pouvons donc ecrirexRyetyRz=⇒xRzzRyetyRx=⇒zRx.d’ouxRzetzRx=⇒xS z.Par consequent, S est une relation d’equivalence.Algebre

Page 40 : A faire chez soi - Exercice 10Soit R une relation symetrique et reflexive sur un ensemble X. On definitune relation S sur X par :xS y⇐⇒n N, z0, · · · , zn X, z0 = x, zn = y, 0 i n 1, ziRzi+1Montrer que S est une relation d’equivalence.Reflexive : Oui. En effet, pour tout x X il suffit de choisirn = 1, z0 = x, z1 = x.Alors comme R est reflexive on obtientx = z0Rz1 = x.Donc xS x.Algebre

Page 41 : A faire chez soi - Exercice 10Symetrique : Oui. En effet, si xS y alorsn N, z0, · · · , zn X, z0 = x, zn = y, 0 i n 1, ziRzi+1Puisque S est symetrique, nous avons0 i n 1, ziRzi+1=⇒zi+1RziPar consequent, en definissantz′0 = y, z′1 = zn1, · · · , z′n = xon conclutz′0 = y, z′n = x, 0 i n 1, z′i Rz′i+1Donc yS x.Algebre

Page 42 : A faire chez soi - Exercice 10Transitive : Oui. En effet, si xS y et yS walorsn N, z0, · · · , zn X, z0 = x, zn = y, 0 i n 1, ziRzi+1etm N, t0, · · · , tm X, t0 = y, tm = w, 0 i m1, tiRyi+1.Donc en posantz′0 = x, z′1 = z1, · · · , z′n = y = t0, z′n+1 = t1, · · · , z′n+m = won a bienz′0 = x, z′n = w, 0 i n 1, z′i Rz′i+1Donc xS w.Algebre

Pages : 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42