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

Page 1 : Algebre-Premier semestre 2024 - 2025CY 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 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 17 : 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 18 : 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 19 : 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 20 : 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 21 : 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 22 : 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 23 : 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 24 : 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 25 : 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 26 : 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 27 : 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 28 : 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 29 : 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 30 : 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 31 : 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 32 : 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 33 : 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 34 : 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 35 : 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 36 : 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