AlgèbreNotion · Glossaire
Ordre partiel
Un ordre partiel sur un ensemble est une relation binaire réflexive, antisymétrique et transitive. Contrairement à un ordre total, deux éléments d'un ensemble muni d'un ordre partiel ne sont pas nécessairement comparables. L'ensemble des parties d'un ensemble ordonné par l'inclusion est un exemple classique d'ordre partiel. Un ensemble muni d'un ordre partiel est appelé un ensemble partiellement ordonné ou poset.
Sommaire
Ce que vous allez apprendre
- Identifier les trois propriétés d'un ordre partiel.
- Tester si deux parties sont comparables par inclusion.
- Distinguer ordre partiel, ordre total, élément maximal et maximum.
- Reconnaître une borne supérieure dans un exemple fini.
En clair
Prenons les sous-ensembles de {a, b, c} et rangeons-les par inclusion. L'ensemble {a} vient avant {a, b}, car le second contient tout le premier. En revanche, {a} et {b} restent incomparables : aucun ne contient l'autre.
Un ordre partiel organise donc certains couples sans imposer un classement général. Il autorise plusieurs branches, tout en gardant des comparaisons cohérentes le long de chacune.
Définition
Soit un ensemble E et une relation binaire, notée ≼, entre ses éléments. Cette relation est un ordre partiel lorsqu'elle satisfait trois conditions. Elle est réflexive : chaque élément est en relation avec lui-même. Elle est antisymétrique : si deux éléments sont chacun en relation avec l'autre, ils sont égaux. Elle est transitive : deux comparaisons successives donnent la comparaison des extrémités.
Deux éléments x et y sont comparables lorsque x ≼ y ou y ≼ x. L'ordre reste partiel si certains couples distincts ne vérifient aucune de ces deux relations. Si tous les couples sont comparables, il s'agit du cas particulier d'un ordre total. L'ensemble E muni de ≼ est appelé un ensemble partiellement ordonné, ou poset. Sur l'ensemble des parties d'un ensemble, la relation d'inclusion ⊆ fournit l'exemple classique.
Un exemple, pas à pas
On considère l'ensemble E = {a, b, c}. Les objets à ordonner sont ses huit parties, de l'ensemble vide ∅ jusqu'à E. La relation choisie est l'inclusion ⊆.
1. Comparons {a} et {a, b}. Tout élément du premier appartient au second, donc {a} ⊆ {a, b}.
2. Comparons {a} et {b}. L'élément a n'appartient pas à {b}, tandis que b n'appartient pas à {a}. Aucune inclusion ne vaut : ces deux parties sont incomparables.
3. Cherchons une partie contenant à la fois {a} et {b}. Les deux candidates sont {a, b} et {a, b, c}. La plus petite pour l'inclusion est {a, b} : c'est leur borne supérieure.
Le diagramme de Hasse associé relie deux parties lorsqu'une seule lettre est ajoutée. Il permet de contrôler le résultat : {a, b} est au-dessus de {a} et de {b}, et aucun sommet situé plus bas n'est au-dessus des deux.
En pratique
Pour organiser des sous-ensembles, on vérifie directement les inclusions. Deux collections peuvent alors être situées l'une par rapport à l'autre sans leur attribuer artificiellement un rang unique.
Pour réunir deux exigences représentées par {a} et {b}, on cherche leurs majorants, puis le plus petit d'entre eux. Dans l'exemple, {a, b} est préférable à {a, b, c}, car il ajoute seulement ce qui est nécessaire.
Si le problème exige que chaque paire soit classée, cet ordre ne suffit pas : il faut choisir un ordre total compatible ou ajouter un critère de départage. Le couple {a}, {b} révèle immédiatement ce besoin.
À ne pas confondre
Ordre total. Dans un ordre total, toute paire d'éléments est comparable. Dans un ordre partiel, cette comparabilité générale n'est pas exigée. Pour trancher, il suffit donc de trouver une paire incomparable : {a} et {b} le sont pour l'inclusion.
Relation d'ordre et simple relation binaire. Toute relation d'ordre relie des couples, mais elle doit aussi être réflexive, antisymétrique et transitive. Une relation qui échoue à l'un de ces trois tests n'est pas un ordre partiel.
Limites et pièges
Antisymétrique ne signifie pas asymétrique. La réflexivité impose x ≼ x, donc la relation accepte qu'un élément soit relié à lui-même. L'antisymétrie interdit seulement que deux éléments distincts soient reliés dans les deux sens.
Maximal ne signifie pas nécessairement maximum. Un élément maximal n'a aucun élément strictement plus grand au-dessus de lui. Un maximum doit en plus être supérieur ou égal à tous les éléments ; plusieurs maximaux incomparables peuvent donc coexister sans maximum.
Une borne supérieure n'existe pas toujours. Même quand deux éléments ont des majorants, aucun ne doit forcément être le plus petit. Il faut vérifier l'existence et l'unicité de ce plus petit majorant avant de parler de borne supérieure.
Un diagramme de Hasse omet des relations sans les supprimer. Les boucles réflexives et les arêtes déduites par transitivité ne sont pas tracées. Il faut les rétablir mentalement pour lire toute la relation d'ordre.
Pour aller plus loin
La fiche relation d'ordre replace les trois propriétés dans le cadre général des relations binaires.
La fiche Inclusion approfondit la relation utilisée dans l'exemple des parties de {a, b, c}.
La fiche Borne supérieure précise comment reconnaître le plus petit des majorants lorsqu'il existe.
Explorez les mathématiques autrement
Retrouvez nos magazines, podcasts et jeux pour explorer les mathématiques autrement.
Découvrir les offres