Aller au contenu Aller au menu Politique d'accessibilité

Free Sciences Site sur les mathématiques, la physique, et l'informatique.

Relation d'ordre

Si nous avons deux nombres a,b, alors on peut dire que l'un est «plus petit» que l'autre, et on note si a est plus petit que b, a<b. On peut facilement définir cette notion de manière formelle avec ce qui a été vu précédemment, on a tout simplement:

a,b,a<bab

Et si a<b, on peut écrire aussi b>a.

En plus de la notion de «plus petit que» on définit «plus petit ou égal à» et si a est plus petit ou égal à b, on note: ab ou ab. On le définit comme ceci:

a,b,ab(aba=b)

On va dire que nous définissons ainsi une relation d'ordre sur car on introduit l'idée d'«ordre» entre les éléments.

Il reste à définir ce qu'est vraiment une relation d'ordre de manière générale, car on rencontrera ce type de relation dans d'autres ensembles que dans . On va voir qu'en fait «» est une relation d'ordre et que «<» est une relation d'ordre strict.

Définition

Sans surprise, on va définir la relation d'ordre comme une relation binaire.

Définition 2.

On dit que la relation binaire R est une relation d'ordre sur un ensemble E, si elle est réflexive, antisymétrique et transitive (si x et y sont en relation, on écrit xRy):

  1. réflexive: xE,xRx,
  2. antisymétrique: (x,y)E2,(xRy)(yRx)x=y,
  3. transitive: (x,y,z)E3,(xRy)(yRz)xRz.

On peut facilement se rendre compte que «» est une relation d'ordre.

On définit aussi la notion de relation d'ordre strict: une relation d'ordre strict est une relation binaire irréflexive et transitive. On dit qu'une relation est irréflexive si aucun élément n'est en relation avec lui-même:

xE,¬(xRx)

On peut facilement se rendre compte que «<» est une relation d'ordre strict.

Ordre totale et partiel

Définition 3.

Si R est une relation d'ordre sur l'ensemble E et qu'elle vérifie:

(x,y)E2,(xRy)(yRx)

alors on dit que c'est une relation d'ordre totale. On dit aussi que E est totalement ordonné ou que (E,R) est un ordre totale.