• Aide pour la navigation
  • Page d'accueil
  • Mise à jour
  • A faire
  • Rechercher
  • Plan du site
• Contacts
  • Connexion
  • Livre d'or
  • Forum
  • Auteurs
  • Liens
• Grandes parties
  • International (en)
  • Maths
  • Informatique
  • Smileys
  • Programmation
  • Nos Programmes
  • Nos jeux
  • Jeux vidéo
• Cours
  • Sommaire « cours de mathématiques »
  • Théorie des ensembles
  • Constructions mathématiques
  • Les fonctions
  • Ensembles ordonnés

Relations d'ordre

Définition

Imaginons le cas d'une famille, avec un Père, une Mère, une fille ainée Camille et deux frères jumeaux Jean et Pierre. On considère la relation "doit obéir à" noté ≤. En supposant que les enfants sont mineurs, et que chacun doit obéir aux membres plus agés, on peut par exemple dire que tous les enfants sont soumis à l'autorité de leur parents ("Jean ≤ Père", "Camille ≤ Père" etc), que les jumeaux doivent obéir à leur aînée lorsqu'elle est chargée de les surveiller ("Jean ≤ Camille" et "Pierre ≤ Camille") ou encore qu'un membre s'auto-commande lorsqu'il doit prendre ses propres décisions ("Jean ≤ Jean"). Ainsi, comme pour la relation d'équivalence, cette relation est symétrique (chacun est maître de soi) et transitive (par exemple Jean se fait commander par Camille, Camille se fait commander par sa Mère, et Jean se fait commander par sa Mère) mais pas symétrique : si un premier membre commande un second membre, ce second membre ne peut réciproquement commander le premier... sauf si on reprends le cas où on parle d'un membre soumis à sa propre autorité. La relation est dite antisymétrique...

Soit $E$ un ensemble et $R$ une relation sur cette ensemble. On dit que $R$ est une relation d'ordre sur $E$ si et seulement si elle possède les trois propriétés suivantes :

• Réflexivité : $\forall x\in ExRx$
• Antisymétrie : $\forall \left(x,y\right)\in ExRy\wedge yRx\Rightarrow x=y$
• Transitivité : $\forall \left(x,y\right)\in E^{2}xRy\wedge yRz\Rightarrow xRz$

L'ensemble $E$ muni de la relation $R$, que l'on note $\left(E,R\right)$, est alors dit partiellement ordonné ou plus simplement ordonné. Remarquons que si on prend $E\text{'}\subset E$ alors il est clair que $\left(E\text{'},R_{\mid {E\text{'}}^2}\right)$ est aussi partiellement ordonné. Par abus de notation, on écrit aussi $R$ la restriction cette relation à ${E\text{'}}^2$.

Inégalités

On utilise les écritures et le vocabulaire suivant, pour une relation d'ordre $\le$ :

• Inégalités larges :
  • $x\le y$ se lit $x$ est inférieur / plus petit que $y$.
  • $x\ge y$ se lit $x$ supérieur / plus grand que $y$. C'est une autre façon de noter $x\le y$.
• Inégalités strictes :
  • $x<y$ se lit $x$ est strictement inférieur à $y$. C'est une autre façon de noter $x\le y\wedge x\ne y$
  • $x>y$ se lit $y$ est strictement supérieur à $y$. C'est une autre façon de noter $x\ge y\wedge x\ne y$.

Remarque : En fait, on verra que $<$ correspond à une relation d'ordre strict, par opposition à l'inégalité large $\le$.

Lorsque l'on prends deux membres de la famille, il arrive que l'on ne puisse dire qui doit obéir à l'autre : c'est le cas des parents. Dans le cas contraire, on dit que les éléments sont comparables :

$x$ et $y$ sont comparables ⇔ $x\le y\vee y\le x$

Isomorphisme

Gardons notre famille de cinq membres, et comparons-là avec deux généraux, un colonel et deux soldats. Bien que l'ensemble d'individus soit différents, les relations de commandement sont alors exactement les mêmes, en considérant que les parents sont les généraux, la fille le colonel et les jumeaux les deux soldats. A l'aide d'une application bijective entre les deux ensembles d'individus, on a pu passer d'un ensemble ordonné à un autre...

Soient $\left(A,{\le }_A\right)$ et $\left(B,{\le }_B\right)$deux ensembles ordonnés, et $f:A\to B$ une application. Alors $f$ est un isomorphisme d'ordre, si et seulement si :

• $f$ est bijective
• $\forall \left(x,x\text{'}\right)\in A^{2}x{\le }_{A}x\text{'}\Rightarrow f\left(x\right){\le }_{A}f\left(x\text{'}\right)$

On dit alors que $A$ et $B$ sont isomorphes, et l'on note $A\cong B$.

L'essentiel dans la notion d'isomorphisme est de voir qu'elle rend deux ensembles isomorphes indiscernables, du point de vue de leur structure. Ainsi soient $y,y\text{'}\in B$, tel que $y{\le }_{B}y\text{'}$. et $x,x\text{'}$ leur unique antécédents respectifs par f. Si $x{\ge }_{A}x\text{'}$, alors $y{\ge }_{B}y\text{'}$ donc $y=y\text{'}$ et $x=x\text{'}$. Ainsi on ne peut avoir que$f^{-1}\left(y\right){\le }_A{f}^{-1}\left(y\text{'}\right)$avec égalité si et seulement si $y=y\text{'}$. On passe ainsi indifféremment de l'ordre sur $A$ à l'ordre sur $B$...

Éléments particuliers d'un ensemble ordonné

Minimaux et maximaux

Des membres de la famille présentent une position particulière : les jumeaux ne peuvent commander personne et les parents ne reçoivent d'ordre d'aucun autre membre de la famille. On les appelle respectivement éléments minimaux ou maximaux de E (toujours pour la relation ≤) :

• x élément minimal de E ⇔ ∀y∈E, y≤x ⇒ x = y
• x élément maximal de E ⇔ ∀y∈E, x≤y ⇒ x = y

Extrema

Intérressons-nous à l'ensemble E auquel on retire un des jumeaux, disons Jean. Lorsque l'on prenait l'ensemble de la famile, Pierre ne pouvait se faire commander par son frère, mais dorénavant il doit obéir à tout les autres : on dit que c'est le minimum (pluriel : minima) de E. Le minimum un élément minimal puisqu'il est inférieur à tous ceux auquels il est comparable, mais de plus il est comparable, et donc inférieur, à tous les éléments de l'ensemble ! Dans le même ordre d'idée, si on retire un des parents à la famille, le parent restant est le maximum (pluriel : maxima) de E. On utilise aussi le terme plus général d'extremum (pluriel : extrema).

• $x$ minimum de $E$ si et seulement si $\forall y\in Ex\le y$
• $x$ maximum de $E$ si et seulement si $\forall y\in Ey\le x$

Remarque : On parle aussi de plus petit élément / plus grand élément de $E$.
On démontre facilement que le plus petit élément (ou le plus grand) d'un ensemble est unique (d'où l'article employé). En effet soit $x_1$ et $x_2$ deux plus petits éléments de $E$. Alors $x_1$étant par définition inférieur à tous les éléments de $E$, on a en particulier $x_1\le x_2$ . Pour les même raisons, $x_2\le x_1$, et par antisymétrie, $x_1=x_2$.

Minorants et majorants

Après l'avoir réduit, élargissons l'ensemble E en ajoutant par exemple des policiers. Comme chacun représente la loi, tous les membres de la famille doivent leur obéir, on dit qu'un policier est un majorant de E. La hiérarchie au sein de la police peut faire qu'un des policiers est sous les ordres de tous les autres : c'est le plus petit des majorants, appelé la borne supérieur. On défini de même un minorant et la borne inférieur

Soit $\left(E,\le \right)$ un ensemble partiellement ordonné et $F\subset E$. Pour tout élément $x\in E$, on a les définitions suivantes :

• $x$ majorant de $F$ si et seulement si $\forall y\in Fy\le x$
• $x$ minorant de $F$ si et seulement si $\forall y\in Fx\le y$
• $x$ borne supérieure F si et seulement si $x$ plus petit des majorants
• $x$ borne inférieure de F si et seulement si $x$ plus grand des minorants

Relations d'ordre particulières

Relation d'ordre stricte

Soit $E$ un ensemble et $R$ une relation sur cet ensemble. On dit que $R$ est une relation d'ordre stricte sur $E$ si et seulement si elle possède les trois propriétés suivantes :

• Irréflexivité : $\forall x\in E\neg \left(xRx\right)$
• Antisymétrie, équivalente à $\forall \left(x,y\right)\in E^2\neg \left(xRy\wedge yRx\right)$

  En effet si pour tout $x,y\in E$, $\left(xRy\wedge yRx\right)$ est faux alors l'implication $\left(xRy\wedge yRx\right)\Rightarrow x=y$ est vraie. Réciproquement, supposons cette implication vérifiée pour tout $x,y\in E$ . Si il existait $x,y$ tels que $\left(xRy\wedge yRx\right)$, on aurait $x=y$ donc $xRx$, ce contredit l'irréflexivité de $R$.

• Transitivité

Comme on l'a dit, une relation d'ordre strict est souvent notée $<$. On peut de plus indifféremment passer d'une relation d'ordre strict à une relation d'ordre $\le$ si on défini, pour tous éléments $x,y\in E$ :

• $x\le y$ si et seulement si $x<y\vee x=y$
• $x<y$ si et seulement si $x\le y\wedge x\ne y$

En effet supposons d'abord que $E$ est muni d'une relation d'ordre $\le$. Alors $x<x$ n'est pas possible, ou sinon $x\ne x$. De même, de même si $x<y\wedge y<x$ on a $x=y$ par transitivité de $\le$ mais aussi $x\ne y$ par définition de $<$. Enfin, si $x<y<z$, on a $x\le z$ par transitivité. Mais de plus on a $x\ne z$, ou sinon $x<y\wedge y<x$contredirait l'antisymétrie.

Réciproquement, supposons $E$ muni de la relation d'ordre strict $<$. La symétrie de $\le$ est obtenu directement, puisque $x=x$. Pour l'antisymétrie, si $x\le y\wedge y\le x$, alors la conjonction se simplifie en $\left(x<y\wedge y<x\right)\vee x<x\vee x=y$et la seule possibilité est donc $x=y$. Enfin si $x\le y$ et $y\le z$, en analysant tout les cas, on a soit $x<y<z$ donc $x<z$, soit les trois sont égaux, soit $y$ est égal à un des deux autres, donc $x<z$. Finalement on a bien $x\le z$.

Ensemble totalement ordonné et ensemble inductif

Prenons pour ensemble de référence E' dont les éléments sont Jean, Camille et leur Père. On est toujours capable de comparer deux éléments de E' : Jean ≤ Jean, Jean ≤ Camille, Jean ≤ Père, Camille ≤ Camille, Camille ≤ Père, Père ≤ Père. On dit que cet ensemble est totalement ordonné.

$\left(E,\le \right)$ totalement ordonné si et seulement si $\forall \left(x,y\right)\in E^{2}x\le y\vee y\le x$

Quand $E\text{'}$ est une partie totalement ordonnée de E, on dit aussi que c'est une chaîne de E. Un ensemble $\left(E,\le \right)$ est dit inductif si toutes chaînes possèdent un majorant. Il est dit strictement inductif si ces sous-ensembles possèdent de plus une borne supérieure.

Lemme de Zorn

Si $\left(E,\le \right)$ est un ensemble non vide inductif alors il possède un élément maximal.

Ce lemme se démontre par l'axiome du choix et lui est même équivalent.

Ensemble bien ordonné

Soit $\left(E,\le \right)$ un ensemble partiellement ordonné. On dit que $\le$ est un bon ordre sur $E$ ou que $\left(E,\le \right)$ est bien ordonné si toute partie non vide de $E$ possède un plus petit élément. On dit aussi que $E$ est bien ordonnable s'il peut être muni d'un bon ordre. On comprends aisément qu'un ensemble $\left(E,\le \right)$ bien ordonné est totalement ordonné. En effet, si $x,y\in E$, alors $\{x;y\}$ est une partie de $E$ et possède un plus petit élément : du coup, soit $x\le y$ soit $y\le x$. Parfois, on utilise la relation d'ordre $<$ stricte correspondante, comme on le verra pour les ordinaux.

L'exemple de l'ensemble totalement ordonné E' = {Jean, Camille, Père} était aussi un ensemble bien ordonné. Cependant, un ensemble totalement ordonné n'est pas forcément bien ordonné. C'est ainsi que ℤ et ℝ munis de leur relation ≤ classique sont totalement ordonnés sans être bien ordonné. {x∈ℤ / x ≤ -123} et ]0 ; 1] ne possède pas de plus petit élément.

Si $F\subset E$, alors on a : $F$ segment initial de ⇔$\forall x\in F\forall y\in Ey\le x\Rightarrow y\in F$

Théorème de Zermelo

Tout ensemble est bien ordonnable

Tout comme le lemme de Zorn, ce théorème est équivalent à l'axiome du choix. Il pose toutefois le problème de ne pas préciser de relation de bon ordre pour un ensemble donné, mais de se contenter d'affirmer son existence.

Retour à la page sur les constructions d'objets mathématiques usuels

Cette page est conforme aux normes du W3C - Auteur : Frédéric WANG - Dernière mise à jour : lundi 20 août 2007