Order relation

Prenons les quatre parties de l'ensemble {a, b} : ∅, {a}, {b} et {a, b}. On peut les ranger selon l'inclusion : chaque partie est incluse dans elle-même, et ∅ est incluse dans toutes les autres. En revanche, {a} et {b} ne se contiennent pas l'une l'autre.

Cette manière cohérente de dire qu'un élément vient « avant » un autre est une relation d'ordre. Elle peut comparer chaque paire, comme l'ordre usuel des nombres, ou laisser certaines paires incomparables, comme {a} et {b}.

Sur un ensemble E, une relation binaire notée ≼ est une relation d'ordre large lorsqu'elle est réflexive, antisymétrique et transitive. Pour tous les éléments x, y et z de E, ces trois conditions s'écrivent :

La première condition autorise chaque élément à être comparé à lui-même. La deuxième empêche deux éléments distincts d'être chacun inférieur à l'autre. La troisième assure la cohérence des comparaisons en chaîne. L'ordre strict associé, noté ≺, est défini par x ≺ y lorsque x ≼ y et x ≠ y. L'ordre est total si, pour toute paire x et y, x ≼ y ou y ≼ x. Il est partiel lorsque certaines paires peuvent ne vérifier aucune de ces deux relations. Sur les parties d'un ensemble comportant au moins deux éléments, l'inclusion ⊆ fournit un ordre partiel.

Pour décider si une relation binaire ≼ est une relation d'ordre large sur un ensemble E, il faut vérifier trois critères sur tous les éléments concernés : x ≼ x ; si x ≼ y et y ≼ x, alors x = y ; si x ≼ y et y ≼ z, alors x ≼ z.

Une fois ces critères établis, l'ordre est total si chaque paire est comparable. La présence d'une seule paire x, y telle que ni x ≼ y ni y ≼ x suffit à montrer que l'ordre n'est pas total.

Le test porte sur une relation binaire définie sur un ensemble précis : il faut connaître les éléments de l'ensemble et savoir, pour chaque couple utile, si la relation est vraie. La réflexivité doit couvrir chaque élément ; l'antisymétrie et la transitivité doivent couvrir tous les couples ou triplets auxquels leurs prémisses s'appliquent.

Un seul contre-exemple invalide le critère correspondant. Par exemple, la relation « être différent de » sur {a, b} n'est pas réflexive, car a n'est pas différent de lui-même : ce n'est donc pas une relation d'ordre large. Il faut alors abandonner cette qualification, plutôt que limiter la vérification aux couples qui conviennent.

Données. L'ensemble de départ est E = {a, b}. On considère ses quatre parties ∅, {a}, {b} et {a, b}, avec la relation d'inclusion ⊆.

1. Réflexivité. Chacune des quatre parties est incluse dans elle-même : la première condition est vérifiée.

2. Antisymétrie. Si une partie A est incluse dans une partie B et si B est incluse dans A, elles ont exactement les mêmes éléments ; donc A = B.

3. Transitivité. La chaîne ∅ ⊆ {a} ⊆ {a, b} entraîne bien ∅ ⊆ {a, b}. Le même raisonnement vaut pour toute chaîne d'inclusions. La figure rassemble toutes les inclusions immédiates de cet exemple.

4. Verdict et contrôle. L'inclusion est donc une relation d'ordre sur ces quatre parties. Elle n'est pas totale : {a} ⊈ {b} et {b} ⊈ {a}. Cette paire incomparable fournit un contrôle direct, tandis que toutes les autres paires distinctes sont reliées par inclusion dans un sens.

Pour reconnaître un ordre, on teste séparément réflexivité, antisymétrie et transitivité. Chercher d'abord un contre-exemple peut écourter le travail : une seule défaillance suffit à exclure la relation d'ordre.

Pour savoir si l'ordre est total, on cherche ensuite une paire incomparable. Dans l'exemple des parties de {a, b}, {a} et {b} donnent immédiatement le verdict : l'inclusion est ici un ordre partiel.

Pour passer de l'ordre large à l'ordre strict, on retire les comparaisons d'un élément avec lui-même. Ainsi, A ⊂ B signifie ici que A ⊆ B et A ≠ B.

Antisymétrique ne signifie pas symétrique. Une relation symétrique exige que x soit en relation avec y dès que y l'est avec x. L'antisymétrie dit seulement que les deux sens réunis forcent x = y. Pour l'inclusion, ∅ ⊆ {a} est vraie, mais {a} ⊆ ∅ est fausse : l'inclusion n'est pas symétrique, tout en étant antisymétrique.

Relation d'ordre et relation d'équivalence. Toutes deux peuvent être réflexives et transitives, mais la première impose l'antisymétrie, tandis que la seconde impose la symétrie. Le test des deux sens sépare les deux notions : dans un ordre, ils obligent les éléments à être égaux.

Une paire incomparable n'est pas une erreur. Dans un ordre partiel, ni x ≼ y ni y ≼ x ne doit nécessairement être vraie. Le symptôme devient un problème seulement si l'on prétend avoir un ordre total ; il faut alors conclure « ordre partiel », comme pour {a} et {b} avec l'inclusion.

Les trois propriétés sont indépendamment nécessaires. Vérifier seulement la réflexivité et la transitivité ne suffit pas. Il faut toujours tester l'antisymétrie dans les deux sens, car son échec empêche de conclure à une relation d'ordre.

L'ordre strict change le statut de l'égalité. La relation ≺ associée exclut x = y ; elle n'est donc pas réflexive. Il ne faut pas lui appliquer mot pour mot les trois axiomes de l'ordre large : pour revenir au large, on autorise l'égalité en plus de ≺.

Ordre partiel — Approfondir la comparabilité incomplète et la manière dont une structure ordonnée accepte des éléments sans ordre relatif.

Ordre total — Examiner le cas où chaque paire d'éléments est comparable et le distinguer du cas partiel.

Inclusion — Reprendre en détail la relation utilisée dans l'exemple conducteur entre les parties d'un ensemble.