[<] Relations d'équivalence

 
Exercice 1  1518  Correction  

On définit une relation binaire sur +* par:

xyn,y=xn.

Montrer que est une relation d’ordre. Cet ordre est-il total?

Solution

Soit x>0, on a x=xn pour n=1 donc xx. La relation est réflexive.
Soient x,y>0, si xy et yx alors il existe n,m tels que y=xn et x=ym.
On a alors x=xnm donc ln(x)=nmln(x)
Si x=1 alors y=xn=1=x.
Si x1 alors ln(x)0 puis 1=nm. Or n,m donc n=m=1 puis x=y.

Finalement, la relation est antisymétrique.
Soient x,y,z>0. Si xy et yz alors il existe n,m tels que y=xn et z=ym.
On a z=xmn avec mn donc xz. La relation est transitive.

Finalement, est une relation d’ordre.
Cet ordre n’est pas total car, par exemple, 2 et 3 ne sont pas comparables.

 
Exercice 2  1522  

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

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

    Montrer que est une relation d’ordre sur E.

  • (b)

    S’agit-il d’une relation d’ordre totale?

 
Exercice 3  4486   

(Ordre lexicographique)

Sur E=2, on définit une relation binaire par

(x,y)(x,y)x<x ou (x=x et yy).
  • (a)

    Vérifier que définit une relation d’ordre sur E.

  • (b)

    S’agit-il d’une relation d’ordre totale?

 
Exercice 4  4487   

Soit la relation binaire définie sur le demi-plan E={(a,b)2|ab} par

(a,b)(a,b)(a,b)=(a,b) ou ba.
  • (a)

    Montrer que est une relation d’ordre sur E.

  • (b)

    S’agit-il d’une relation d’ordre totale?

 
Exercice 5  1520   Correction  

On définit une relation binaire sur {z|Im(z)0} par:

zz|z|<|z| ou (|z|=|z| et Re(z)Re(z)).

Montrer qu’il s’agit d’une relation d’ordre total.

Solution

est clairement réflexive.
Si zz et zz alors nécessairement |z|=|z| et Re(z)=Re(z) donc z=z car Im(z),Im(z)0.
Si zz et zz′′ alors si |z|<|z′′| alors zz′′ et sinon |z|=|z|=|z′′| et donc Re(z)Re(z)Re(z′′) ce qui permet à nouveau d’affirmer zz′′.
Pour z,z{z|Im(z)0}.
Si |z|<|z| alors zz
Si |z|>|z| alors zz.
Si |z|=|z| alors dans le cas où Re(z)Re(z) on a zz et, dans le cas complémentaire, on a zz.
Dans tout les cas z et z sont comparables, la relation d’ordre est totale.

 
Exercice 6  1521  Correction  

Soit E l’ensemble des couples (I,f) formé d’un intervalle I et d’une fonction réelle définie sur I.
On définit une relation sur E par: (I,f)(J,g)IJ et g|I=f.
Montrer que est une relation d’ordre sur E.

Solution

La relation est clairement réflexive.
Si (I,f)(J,g) et (J,g)(I,f) alors IJ, JI et g|I=f donc I=J et f=g.
Si (I,f)(J,g) et (J,g)(K,h) alors IJK et hI=(h|J)|I=g|I=f donc (I,f)(K,h).

Finalement, est une relation d’ordre.

 
Exercice 7  1523   Correction  

Soient A,B deux parties d’un ensemble E ordonné par .
On suppose que A et B ont chacun un plus grand élément.
Qu’en est-il de AB lorsque l’ordre est total? lorsqu’il ne l’est pas?
Que dire de AB?

Solution

Si l’ordre est total AB possède un plus grand élément: max(AB)=max(max(A),max(B)).
Si l’ordre n’est pas total, les plus grands éléments de A et de B peuvent ne pas être comparés aux éléments de A et B. Dans (*,), pour A={2,4} et B={3,9}, A et B ont un plus grand élément alors que AB n’en a pas.
AB peut ne pas posséder de plus grand élément, cet ensemble peut notamment être vide.

 
Exercice 8  1525   Correction  

Soit E un ensemble ordonné par une relation .
Un tableau à n lignes et p colonnes est formé d’éléments ai,jE avec i indice de ligne(1in) et j indice de colonne(1jp).
On note le plus petit élément de chaque colonne et l’on prend le plus grand de ces plus petits:

max1jp(min1inai,j).

On note aussi le plus grand élément de chaque ligne et l’on prend le plus petit de ces plus grands:

min1in(max1jpai,j).
  • (a)

    Comparer ces deux nombres.

  • (b)

    Donner un exemple de non égalité.

Solution

  • (a)

    Pour tout 1mp,

    ai,mmax1jpai,j

    donc

    min1inai,mmin1inmax1jpai,j

    puis

    max1mpmin1inai,mmin1inmax1jpai,j.
  • (b)

    Pour le tableau (1432)

    max1j2min1i2ai,j=2 et min1i2max1j2ai,j=3.
 
Exercice 9  2055   Correction  

Montrer qu’il n’existe pas de suite strictement décroissante d’entiers naturels.

Solution

Par l’absurde, supposons que (un) soit une telle suite.
A={un|n} est une partie non vide de , elle possède donc un plus petit élément m.
Puisque mA, il existe n tel que m=un. Mais alors un+1<unm=minA. Absurde.

 
Exercice 10  1524   Correction  

Soit (E,) un ensemble ordonné tel que toute partie non vide admet un plus petit élément et un plus grand élément.
Montrer que E est fini.

Solution

Par l’absurde supposons E infini.
Posons x0=minE, x1=minE{x0},…, xn=minE{x0,x1,,xn-1},…
L’ensemble {x0,,xn,} n’a pas de plus grand élément. Absurde.

[<] Relations d'équivalence



Édité le 08-11-2019

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