Ordre

Les ordres sont une généralisation du concept d’ordre sur les nombres.

Définition et notation

On ordre sur un ensemble est une Relation qui satisfait les propriétés suivantes:

Un ordre qui est aussi une relation totale est appelé un ordre total. Un ordre qui n’est pas total est aussi appelé un ordre partiel. Un ensemble muni d’un ordre est appelé un ensemble (totalement/partiellement) ordonné, ou parfois simplement un ordre.

Ordres stricts

Un ordre strict est une relation irréflexive et transitive. Notez bien qu’un ordre strict n’est pas un ordre au sens de la définition précédente; on dit ordre large lorsque l’on veut rendre clair qu’on parle d’un ordre et non pas d’un ordre strict.

Exercice: Démontrer qu’une relation est irréflexive et transitive si et seulement si elle est asymétrique et transitive.

À tout ordre on peut associer un ordre strict de la façon suivante:

si et seulement si et .

Inversement, à tout ordre strict on peut associer un ordre de la façon suivante:

si et seulement si ou .

Exemples

Diagramme de Hasse

Les diagrammes de Hasse sont une façon de représenter graphiquement les ordres, surtout les ordres finis. On représente les éléments de l’ensemble par des sommet et les relations entre les éléments par des arêtes; ensuite on ôte les arêtes correspondant à la réflexivité et celles qu’on pourrait déduire de la transitivité.

Formellement, si est un ordre strict (associé à son ordre faible), on dessine un sommet pour chaque élément de l’ensemble et on dessine une arête entre deux éléments et (en général en allant du bas vers le haut) si et s’il n’y a pas déjà un chemin allant de vers . Le diagramme de Hasse n’est pas nécessairement unique.

Voici le diagramme de Hasse de l’ordre sur l’ensemble des parties de donnée par l’inclusion ensembliste:

Diagramme de Hasse de l'ensemble des parties de l'ensemble à trois éléments Cette image a été crée par KSmrq. Téléchargée de Wikimedia Commons.

Exercice: Démontrer par induction que le diagramme de Hasse de l’ordre sur les entiers est une droite.

Ordres bien fondés

Soit une relation et soit un sous-ensemble. On dit qu’un élément est minimal dans si pour tout on n’a pas .

On dit qu’une relation sur un ensemble est bien fondée si tout sous-ensemble de a un élément minimal. Un ordre dont l’ordre strict associé est bien fondé est appelé un ordre bien fondé; si, en plus, il est total il est appelé un bon ordre.

Note: Si l’ordre n’est pas total, l’élément minimal n’est pas nécessairement unique. Considérez par exemple l’ensemble des nombres premiers muni de la relation d’ordre .

Une chaîne est une suite d’éléments où chaque élément est en relation avec son successeur. Par exemple:

De façon équivalente, un ordre est bien fondé s’il n’y a pas de chaîne infinie strictement décroissante.

Exemples

Ordres bien fondés et induction

voir Induction, Récursivité.

Les ordres bien fondés sont à la base du principe d’Induction et de la programmation récursive.

Le principe d’induction, qui dans sa forme la plus simple parle des propriétés qu’on peut démontrer sur , peut être généralisé à tout ordre bien fondé, donnant ainsi ce que l’on appelle induction structurelle.

La programmation récursive est basée sur le fait que si un programme fait des appels récursifs avec des arguments strictement plus petits, il construit une chaîne strictement décroissante, qui ne peut donc pas être infinie dès lors que le domaine de la fonction est bien fondé.

Pour approfondir

Ordinaux

Deux bons ordres sont isomorphes s’il existe une fonction bijective monotone d’inverse monotone (i.e. une bijection telle que ) entre eux. Être isomorphe est une relation d’équivalence, et une telle classe d’équivalence est appelée un ordinal.

On peut imposer une relation d’ordre sur les ordinaux en posant si et seulement s’il existe une injection monotone de dans . De façon intéressante, cet ordre est un bon ordre (au moins dans des théories des ensembles standard, mais il existe aussi des théories anti-fondationnelles où il ne l’est pas).

Dans les ordinaux on retrouve un sous-ensemble isomorphe (en tant qu’ordre) aux nombres naturels, que l’on note habituellement . Les ordinaux constituent donc une généralisation des nombres naturels, dans laquelle on peut faire de l’induction, qu’on appelle induction transfinie.

Attention: Tout comme il n’existe pas d’ensemble de tous les ensembles, il n’existe pas d’ensemble de tous les ordinaux. En effet si un tel ensemble devait exister il serait isomorphe à un ordinal (puisque il y a un ordre total sur les ordinaux), mais alors cet ensemble se contiendrait lui même, violant ainsi le bon ordonnancement.

Fork me on GitHub