[<] Image directe, image réciproque d'une partie [>] Relations d'ordre

 
Exercice 1  4477  

On définit une relation11 1 C’est la relation de commensurabilité: deux longueurs sont commensurables lorsqu’elles sont multiples d’une longueur commune. binaire sur l’ensemble + en posant

xy(k,)(*)2,kx=y.
  • (a)

    Montrer que définit une relation d’équivalence.

  • (b)

    Soit x+. Décrire la classe d’équivalence de x.

 
Exercice 2  2643  Correction  

Soit une relation binaire sur un ensemble E à la fois réflexive et transitive.
On définit les nouvelles relations 𝒮 et 𝒯 par:

x𝒮y(xy et yx) et x𝒯y(xy ou yx).

Les relations 𝒮 et 𝒯 sont-elles des relations d’équivalences?

Solution

Les relations 𝒮 et 𝒯 sont clairement réflexives et symétriques.
Soient x,y,zE.
Supposons x𝒮y et y𝒮z.
On a alors xy et yz donc xz et aussi yx et zy donc zx puis x𝒮z.
Le raisonnement n’est plus valable avec 𝒯 et l’on peut présumer que 𝒯 ne sera pas une relation d’équivalence.
Prenons pour la relation divise définie sur *. On a 26 et 36 donc 2𝒯6 et 6𝒯3 or 23.
Ici la relation 𝒯 n’est pas transitive.

 
Exercice 3  2983  Correction  

On considère sur (E,E) la relation binaire définie par:

fgφ𝒮(E),fφ=φg.
  • (a)

    Montrer que est une relation d’équivalence.

  • (b)

    Décrire la classe d’équivalence d’une fonction donnée f(E,E).

Solution

  • (a)

    fIdE=IdEf donc ff.

    Si fg alors il existe φ𝒮(E) telle que fφ=φg mais alors gφ-1=φ-1f donc gf.

    Si fg et gh alors il existe φ,ψ𝒮(E) telles que fφ=φg et gψ=ψh donc fθ=θh avec θ=φψ𝒮(E). Ainsi, fh.

    Finalement, est une relation d’équivalence.

  • (b)

    Pour g(E,E),

    gCl(f)φ𝒮(E),g=φ-1fφ.

    Finalement,

    Cl(f)={φ-1fφ|φ𝒮(E)}.
 
Exercice 4  4488   

Soit f:EF une application. On définit une relation binaire sur E par:

xyf(x)=f(y).
  • (a)

    Montrer que définit une relation d’équivalence sur E.

  • (b)

    Exprimer la classe d’équivalence d’un élément x quelconque de E.

 
Exercice 5  2357     CENTRALE (MP)Correction  

Soient E un ensemble de cardinal n, une relation d’équivalence sur E ayant k classes d’équivalence et G={(x,y)E2|xy} le graphe de supposé de cardinal p.

Montrer que n2kp.

Solution

Notons n1,,nk les cardinaux respectifs des k classes d’équivalence de . D’une part,

n=n1++nk,

et d’autre part,

p=n12++nk2.

Par l’inégalité de Cauchy-Schwarz,

(n1++nk)2k(n12++nk2).
 
Exercice 6  2644   Correction  

Soient E un ensemble et A une partie de E.

On définit une relation sur (E) par:

XYXA=YA.
  • (a)

    Montrer que est une relation d’équivalence

  • (b)

    Décrire la classe d’équivalence de X(E)

Solution

  • (a)

    La relation étudiée est évidemment réflexive, symétrique et transitive.

  • (b)

    Pour Y(E),

    YCl(X)YA=XA.

    Soit YCl(X). On a YA=XA. Pour tout xYA, on a xYA=XA et xA donc xXA. Ainsi, YAXA et inversement XAYA donc XA=YA.

    Puisque Y=(YA)(YA), on a Y=(XA)B avec B(A).

    Inversement, soit Y=(XA)B avec B(A). On a

    YA=(XA)(BA)=(XA¯)A=XA.

    Finalement,

    Cl(X)={(XA)B|B(A)}.
 
Exercice 7  2984   Correction  

Soit une relation binaire réflexive et transitive sur un ensemble E. On définit une relation 𝒮 sur E par

x𝒮yxy et yx.

Montrer que 𝒮 est une relation d’équivalence et que permet de définir une relation d’ordre sur les classes d’équivalences de 𝒮.

Solution

𝒮 est réflexive, symétrique et transitive sans difficultés.

On définit

Cl(x)Cl(y)xy.

La relation est bien définie, réflexive transitive.

Si Cl(x)Cl(y) et Cl(y)Cl(x) alors x𝒮y donc Cl(x)=Cl(y).

 
Exercice 8  2985   Correction  

Soient (G,×) un groupe et H un-sous groupe de (G,×).

On définit une relation binaire sur G par:

xyxy-1H.

Montrer que est une relation d’équivalence et en décrire les classes d’équivalence.

Solution

Soit xG. On a xx car xx-1=1H.

Soient x,yG. Si xy alors xy-1H et donc yx-1H d’où yx.

Soient x,y,zG. Si xy et yz alors xy-1H et yz-1H donc xz-1H d’où xz.

Finalement, est une relation d’équivalence.

Pour aG,

xCl(a) xa
xa-1H

On en déduit

Cl(a)=Ha={ha|hH}.
 
Exercice 9  3243      X (MP)Correction  

Soit G un groupe multiplicatif de cardinal pα avec p premier et α*.
Montrer que

Z(G){1}.

Solution

Considérons la relation binaire sur G définie par

y1y2xG,xy1=y2x.

Il est immédiat de vérifier que est une relation d’équivalence sur G. Les classes d’équivalence de forment donc une partition de G ce qui permet d’affirmer que le cardinal de G est la somme des cardinaux des classes d’équivalence de .
Une classe d’équivalence d’un élément y est réduite à un singleton si, et seulement si,

xG,xy=yx.

c’est-à-dire

yZ(G).

En dénombrant G en fonction des classes d’équivalence de et en isolant parmi celles-ci celles qui sont réduites à un singleton on a

Card(G)=Card(Z(G))+N

avec N la somme des cardinaux des classes d’équivalence de qui ne sont pas réduites à un singleton.
Pour poursuivre, montrons maintenant que le cardinal d’une classe d’équivalence de la relation divise le cardinal de G.
Considérons une classe d’équivalence {y1,,yn} pour la relation et notons

Hi={xG|xy1=yix}.

Pour i{1,,n}, puisque y1yi, il existe xiG tel que

xiy1=yixi.

Considérons alors l’application φ:H1Hi définie par

φ(x)=xix.

On vérifie que cette application est bien définie et qu’elle est bijective.
On en déduit

Card(H1)==Card(Hn)=m

et puisque G est la réunion disjointes des H1,,Hn

Card(G)=mn=pα.

Ainsi, toutes les classes d’équivalences qui ne sont pas réduites à un élément ont un cardinal multiple de p et donc pN.
Puisque p divise Card(G)=Card(Z(G))+N, on a

pCard(Z(G)).

Sachant Z(G) (car 1Z(G)) on peut affirmer

Card(Z(G))p.

[<] Image directe, image réciproque d'une partie [>] Relations d'ordre



Édité le 08-11-2019

Bootstrap Bootstrap 3 - LaTeXML [LOGO] - Powered by MathJax Powered by MathJax