Relation d’ordre : Cours et exercices corrigés

Cette page a pour but de présenter les relations d’ordre à l’aide d’une partie cours et de quelques exercices corrigés.

Cours

Définition

Une relation ≤ sur un ensemble E est une relation d’ordre sur E si elle vérifie ces trois propriété :

• Réflexivité : Pour tout de x de E, x≤x
• Antisymétrie : Pour tout (x,y) de E, si x≤y et y≤x alors x=y
• Transitivité : Pour tout (x,y,z) de E si xRy et yRz alors xRz

Si pour tout couple, on a x ≤ y ou y ≤ x, on dit que le relation d’ordre est totale.

Exemple détaillé

On définit une relation d’équivalence sur l’ensemble des entiers naturels par

x \leq  y \iff x | y 

Elle est bien réflexive. On a bien :

\forall x \in \N , x | x 

Donc

x \leq x 

De plus, si x|y et y|x, alors

\exists, k,k' \in \N, x= ky , y=k'x 

Ce qui fait qu’on en déduit si x est non nul

x = kk'x \iff kk' = 1

Et donc, comme k et k’, sont entiers, on en déduit :

k = k' = 1

D’où x = y.
Si x est nul, alors comme on peut écrire y = kx, nécessairement y est nul.
Donc la relation est bien antisymétrique.

De plus, la relation de transitivité est bien connu pour la divisibilité. Si :

x |y, y|z, \exists k ,k'\in\N, y=kx,z=ky

Et donc,

z = kk'x

D’où

x|z

Finalement, la relation est bien une relation d’ordre.

Exemples

Voici quelques exemples de relation d’ordre

• L’ordre lexicographique qui est l’ordre “du dictionnaire”.
• La relation classique ≤ sur les entiers ou les réels.
• La relation < sur les réels n’est pas une relation d’ordre : on n’a pas x < x.
• La relation d’inclusion pour les ensembles. On note A ⊂ B si A est inclus dans B.

Exercices

Allez plutôt sur notre page dédiée !

Exercices corrigés

Exercice 1052

La relation est bien réflexive :

x-x = 0 \in \N \Rightarrow x \mathcal{R}x

La relation est antisymétrique : si

x \mathcal{R} y , y \mathcal{R} x

Alors

\exists k,k' \in \N, x-y = k, y-x= k'

On a donc :

k ' = y-x = -(x-y) = -k  \in \N

Donc k = k ‘ = 0. D’où x = y.

La relation est transitive. Si

x \mathcal{R} y, y \mathcal{R} z

Alors

\exists k,k' \in \N, x-y = k, y-z= k'

Et donc

x-z = (x-y)+(y-z) = k+k' \in \N

La relation est donc bien transitive. Maintenant, si x = 0, et y = 1/2. Alors

x-y \notin \N, y-x \notin \N

Et donc, la relation d’ordre n’est pas totale car on a trouvé un couple non ordonné.

Exercice 1055

Montrons qu’une condition nécessaire et suffisante est : “f est injective”

Supposons que f n’est pas injective. On peut donc trouver x et y distincts tels que f(x) = f(y). On n’a pas dans ce cas la relation d’antisymétrie. En effet

\begin{array}{lcl}
f(x) = f(y)& \Rightarrow& (f(x) \leq f(y) \wedge  f(y) \leq f(x)) \\
&\iff&  x \mathcal{R}y \wedge y \mathcal{R}x
\end{array}

Et comme x et y sont distincts, l’antisymétrie n’est pas vérifiée.
Supposons maintenant que f est injective.
La relation est bien réflexive :

f(x) \leq f(x) \Rightarrow x \mathcal{R}x 

Et elle est bien antisymétrique : Si

x \mathcal{R}y \wedge y \mathcal{R}x 

Alors

f(x) \leq f(y) \wedge f(y) \leq f(x)

Et donc,

f(x) = f(y)

Puis par injectivité, x=y.
La relation est transitive. Si

x \mathcal{R} y \wedge y \mathcal{R} z

On a alors

f(x) \leq f(y) \wedge f(y) \leq f(z)

D’où

f(x) \leq f(z)

Ainsi,

x \mathcal{R}z

On a donc bien démontré que cette relation est une relation d’ordre si et seulement si f est injective.