[PDF] TD2 : Relations d’ordre et d’équivalence (avec corrigé)

View - Download TD2 : Relations d’ordre et d’équivalence (avec corrigé)

Previous PDF

Next PDF

28 septembreL1 FDV

TD2 : Relations d"ordre et d"équivalence (avec

corrigé)

Exercice 1:

(a) Prouvez que la relation surZ aRb?a-best un multiple de 5 est une relation d"équivalence.

Solution:On vérifie les 3 conditions :

— Réflexivité : Soitx?Z. On veut prouverxRx, c"est à direx-est un multiple de 5.On ax-x=0=5×0. Par conséquent,x-xest un multiple de 5, doncxRx. — Symétrie : Soitx,y?Z. On supposexRy(ie.x-yest un multiple de

5). On veut prouveryRx(ie.y-xest un multiple de 5 ). Ory-x=

-(x-y). Or, commex-yest un multiple de 5, il existek?Ztel que x-y=5k. Doncy-x=-5k. Doncy-xest un multiple de 5. Donc yRx. — Transitivité:Soitx,y,z?Z.OnsupposexRyetyRz.Onveutprouver xRz. On a par hypothèse x-y=5m y-z=5n Pour certainsmetn?Z. En sommant terme à terme, on trouve (x-y) + (y-z) =5m+5n ?x+ (-y+y)-z=5(m+n) ?x-z=5(m+n) ?xRz Les 3 conditions sont bien vérifiées, c"est une relation d"équivalence. (b) Soitx?Z. Déterminer cl(x).

Solution:On procède par double implication :

— Soity?Z. On supposexRy. Il existe doncktel que x-y=5k?y-x=-5k ?y=x-5k

Page 1

Donc toutyen relation avecxest de la formey=x-5kaveck?Z. — Réciproquement, soityde la formex-5kProuvons quexRy x-y=x-(x-5k) =x-x+5k =5k de la formex-5kest en relation avecx. de la formex-5kaveck?Z.

Exercice 2:

(a) Prouver que la relation surZ aRb?a+best pair est une relation d"équivalence.

Solution:

— Réflexivité : Soitx?Z. Prouvons quexRx. On ax+x=2xdonc x+xest pair. DoncxRx. — Symétrie : Soitx,y?Z. On supposexRy. On veut prouver queyRx. On ay+x=x+ypar conséquentx+yest pair puisquexRy. Donc y+xest pair. DoncyRx. — Transitivité:Soitx,y,z?Z.OnsupposexRyetyRz.Onveutprouver quexRz. On a par hypothèse x+y=2m y+z=2n

En sommant terme à terme, on a

(x+y) + (y+z) =2m+2n x+z+2y=2m+2n x+z=2(m+n-y)

Doncx+zest pair. DoncxRz.

DoncRest une relation d"équivalence.

(b) Soitx?Z. Déterminer cl(x).

Page 2

Solution:On distingue 2 cas :xest pair ouxest impair. —xest pair : Soity?Z. On supposexRy.x+yest pair. Doncyest pair. Réciproquement, siyest pair alorsx+yest pair aussi. Dans ce cas, cl (x)est l"ensemble des nombres pairs. —xest impair : Soity?Z. On supposexRy.x+yest pair. Doncyest impair. Réciproquement, siyest impair alorsx+yest pair. Dans ce cas, cl (x)est l"ensemble des nombres impairs.

Exercice 3:

(a) Prouver que la relation surR?×R? (a,b)R(c,d)?ad=cb est une relation d"équivalence.

Solution:

— Réflexivité : Soit(x,y)?R?×R?. Prouvons que(x,y)R(x,y). On a xy=yxdoncxRx. — Symétrie : Soit(a,b),(c,d)?R?×R?. On suppose(a,b)R(c,d). On veut prouver que(c,d)R(a,b). On aad=bcdonccb=da. Donc (c,d)R(a,b). — Transitivité:Soit(a,b),(c,d),(e,f)?R?×R?.Onsuppose(a,b)R(c,d) et(c,d)R(e,f). On veut prouver que(a,b)R(e,f). On a par hypothèse ad=bc?a b=cd cf=de?c d=ef

Partransitivitéde=.Onobtienta

b=ef.Doncaf=bedonc(a,b)R(e,f).

DoncRest une relation d"équivalence.

(b) Soit(a,b)?R?×R?. Déterminer cl?(a,b)?.

Solution:

— Soit(x,y)?R?×R?. On suppose(a,b)R(x,y). On a doncay=xb.

Doncy=xb

a. Donc(x,y)est de la forme? x,xba? — Réciproquement soitx?R?. On veut prouver que? x,xb a?

R(a,b). En

effet, on axb=xb aa. Donc tout élément de la forme? x,xba? est en

Page 3

relation avec(a,b).

La classe d"équivalence de(a,b)est donc?

x,xb a? ?x?R??

Exercice 4:

(a) Prouver que la relation surR aRb?|a|=|b| est une relation d"équivalence.

Solution:

— Réflexivité : Soitx?R. Prouvons quexRx. On a|x|=|x|doncxRx. — Symétrie : Soitx,y?R. On supposexRy. On veut prouver queyRx. On a |x|=??y??donc??y??=|x|. DoncyRx. — Transitivité:Soitx,y,z?R.OnsupposexRyetyRz.Onveutprouver quexRz. On a par hypothèse|x|=??y??et??y??=|z|. Donc|x|=|z|.

DoncxRz.

DoncRest une relation d"équivalence.

(b) Soitx?R. Déterminer cl(x).

Solution:

— Soity?R. On supposexRy. On a donc|x|=??y??. Doncy=xou y=-x. — Réciproquement, on a évidemment,xRxetxR -x. La classe d"équivalence dexest donc{-x,x}. Attention. Quandx=0, la classe d"équivalence est alors {0}et dans ce cas uniquement, il n"y a qu"un seul élément.

Exercice 5:

(a) Prouver que la relation surN×N (a,b)R(c,d)?a?cetb?d est une relation d"ordre.

Solution:

— Réflexivité : Soit(x,y)?N. Prouvons que(x,y)R(x,y). On ax?xet y?y. Donc(x,y)R(x,y).

Page 4

— Antisymétrie : Soit(a,b),(c,d)?N×N. On suppose(a,b)R(c,d)et (c,d)R(a,b). On veut prouver que(a,b) = (c,d). On aa?c,c?a, b?detd?b. Donca=cetb=d. Donc(a,b) = (c,d). — Transitivité:Soit(a,b),(c,d),(e,f)?N×N.Onsuppose(a,b)R(c,d) et(c,d)R(e,f). On veut prouver que(a,b)R(e,f). On aa?cetc?e.

Donca?e. Parallèlement, on ab?detd?f. Doncb?f.

DoncRest une relation d"ordre.

(b) Prouver que cet ordre est bien fondé. Solution:Supposons qu"il existe((an,bn))n?Nune suite à valeur dansN telle que?n?N,(an+1,bn+1)R(an,bn)et(an+1,bn+1?= (an,bn)(une suite strictement décroissante). (an,bn)doncan+1+bn+1Exercice 6: (a) SoitEun ensemble fini. Prouver que la relation surP(E) xRy?x?y est une relation d"ordre.

Solution:

— Réflexivité : Soitxune partie deE. Prouvons quexRx. Tout ensemble est bien inclus dans lui même doncxRx. — Antisymétrie : Soitx,y? P(E). On supposexRyetyRx. On veut prouver quex=y. On ax?yety?x. Deux ensembles sont inclus l"un dans l"autre si et seulement s"ils sont égaux. Doncx=y. — Transitivité : Soitx,y,z? P(E). On supposexRyetyRz. On veut prouver quexRz. On sait quexest un sous ensemble deyetyest un sous ensemble dez. Doncxest un sous ensemble dez.

DoncRest une relation d"ordre.

(b) Prouver que cet ordre est bien fondé. Solution:Supposons qu"il existe(un)n?Nune suite strictement décroissante de parties deE. On a donc strictement moins d"éléments dans chaque terme

Page 5

que dans le précédent, donc la suite des cardinaux(|un|)n?Nest strictement décroissante, ce qui est impossible car c"est une suite d"entier naturels. Donc

Rest bien fondé.

Page 6

quotesdbs_dbs4.pdfusesText_7

[PDF] relation d'equivalence pdf

[PDF] montrer que r est une relation d'équivalence

[PDF] relation binaire exercices corrigés pdf

[PDF] relation d'équivalence et classe d'équivalence

[PDF] exo7 relation binaire

[PDF] liste des verbes d'action

[PDF] liste des verbes d'état cm2

[PDF] exercice sur les verbes d'état et d'action cm2

[PDF] les verbes d'action pdf

[PDF] film éthique et culture religieuse

[PDF] les verbes d'état pdf

[PDF] tous les verbes d'état

[PDF] liste des verbes attributifs

[PDF] surclassement pop corn c'est quoi

[PDF] upload file magazines gaumont 262 web