Logique et ensemblesNotion · Glossaire
Réticulé
Un treillis (ou réticulé) est un ensemble partiellement ordonné dans lequel toute paire d'éléments admet une borne supérieure (le supremum ou join) et une borne inférieure (l'infimum ou meet). Un exemple fondamental est l'ensemble des sous-ensembles d'un ensemble ordonné par l'inclusion. Les treillis distributifs vérifient la distributivité du meet sur le join et vice versa. Les treillis interviennent en logique, en informatique théorique, en algèbre universelle et en topologie.
Sommaire
Ce que vous allez apprendre
- Définir précisément un treillis à partir d'un ordre partiel.
- Déterminer le meet et le join de deux sous-ensembles.
- Distinguer treillis, ordre total et simple ordre partiel.
- Repérer ce que la distributivité et la complétude ajoutent à la définition.
En clair
Prenons toutes les parties de l'ensemble {a, b, c} et rangeons-les par inclusion. Pour deux parties, comme {a, b} et {b, c}, on peut toujours trouver leur plus grand contenu commun : ici {b}. On peut aussi former la plus petite partie qui les contient toutes deux : ici {a, b, c}.
Un tel ordre est un treillis, aussi appelé réticulé. Les deux opérations reviennent, dans cet exemple, à prendre l'intersection et la réunion. L'idée essentielle est que chaque paire possède ces deux résultats bien déterminés.
Définition
Un treillis, ou réticulé, est un ensemble muni d'un ordre partiel tel que toute paire d'éléments possède un supremum et un infimum. Pour deux éléments nommés x et y, le supremum, noté x ∨ y et appelé aussi join, est le plus petit élément qui majore à la fois x et y. L'infimum, noté x ∧ y et appelé aussi meet, est le plus grand élément qui minore à la fois x et y. Ces deux éléments sont uniques dès qu'ils existent.
Dans l'ensemble des parties d'un ensemble, ordonné par inclusion, le meet est l'intersection et le join est la réunion. Cette structure est un treillis distributif : chacune des deux opérations se distribue sur l'autre. Pour trois éléments x, y et z, les deux identités sont :
La distributivité est une propriété supplémentaire : la définition d'un treillis n'impose que l'existence du meet et du join pour chaque paire.
Les treillis fournissent ainsi un langage commun pour organiser et combiner des éléments comparables ou non. Ils interviennent notamment en logique, en informatique théorique, en algèbre universelle et en topologie.
Un exemple, pas à pas
On travaille dans l'ensemble des parties de {a, b, c}, ordonné par inclusion. Les données sont la partie A = {a, b} et la partie B = {b, c}. Le diagramme associé rend visibles A, B et les deux éléments obtenus en les combinant.
1. Cherchons les parties incluses à la fois dans A et dans B. La plus grande est leur intersection : A ∧ B = {b}.
2. Cherchons les parties contenant à la fois A et B. La plus petite est leur réunion : A ∨ B = {a, b, c}.
3. Vérifions le meet : {b} est inclus dans A et B, tandis qu'aucune partie commune ne contient davantage d'éléments.
4. Vérifions le join : A et B sont inclus dans {a, b, c}, et retirer a ou c ferait perdre l'une de ces inclusions.
2. Cherchons les parties contenant à la fois A et B. La plus petite est leur réunion : A ∨ B = {a, b, c}.
3. Vérifions le meet : {b} est inclus dans A et B, tandis qu'aucune partie commune ne contient davantage d'éléments.
4. Vérifions le join : A et B sont inclus dans {a, b, c}, et retirer a ou c ferait perdre l'une de ces inclusions.
La paire (A, B) possède donc bien un infimum {b} et un supremum {a, b, c}. Le même contrôle par inclusion fonctionne pour toute autre paire de parties de {a, b, c}.
En pratique
Avec des ensembles. On ordonne des collections par inclusion, puis on combine deux collections par intersection ou par réunion. Si seul le classement des collections importe, un ordre partiel suffit ; si chaque paire doit être combinée dans les deux sens, le treillis est le cadre adapté.
En logique. On peut ordonner des éléments selon qu'ils apportent plus ou moins d'information, puis rechercher leur combinaison commune ou leur combinaison la moins contraignante. Le critère décisif est l'existence d'un meet et d'un join pour toute paire.
En informatique théorique et en algèbre. Le treillis sert lorsque deux états ou deux objets doivent être rapprochés par deux opérations compatibles avec un ordre. Si l'une des deux combinaisons manque pour une paire, il faut conserver la structure d'ordre partiel sans l'appeler treillis.
À ne pas confondre
Ordre partiel. Un ordre partiel autorise des éléments incomparables, mais ne garantit pas leur meet ni leur join. Un ordre où une paire n'a aucune plus petite borne supérieure n'est donc pas un treillis.
Ordre total. Dans un ordre total, deux éléments sont toujours comparables. Dans un treillis, ils peuvent ne pas l'être : {a, b} et {b, c} sont incomparables par inclusion, tout en ayant une intersection et une réunion.
Quadrillage géométrique. Le mot « treillis » peut désigner un réseau de lignes ou de points. En théorie de l'ordre, il désigne une structure définie par l'existence d'un infimum et d'un supremum pour chaque paire, indépendamment de son dessin.
Limites et pièges
Une borne quelconque ne suffit pas. Le join doit être la plus petite des bornes supérieures et le meet la plus grande des bornes inférieures, dans l'ensemble ordonné considéré. Le symptôme du piège est de choisir un majorant ou un minorant sans vérifier son caractère extrémal.
Les éléments peuvent être incomparables. L'absence de comparaison directe entre x et y n'empêche pas l'existence de x ∧ y et de x ∨ y. Il faut chercher leurs bornes communes, et non forcer l'un des deux à précéder l'autre.
« Toute paire » ne signifie pas « toute partie ». Un treillis garantit meet et join pour les sous-ensembles à deux éléments. Pour exiger un infimum et un supremum pour toute partie, y compris vide ou infinie, on parle de treillis complet.
La distributivité n'est pas automatique. Les deux identités distributives doivent être vérifiées pour tous les triplets. Un seul triplet qui met une identité en défaut suffit à montrer que le treillis n'est pas distributif ; il reste néanmoins un treillis si tous les meets et joins binaires existent.
Pour aller plus loin
Ordre partiel — Pour revoir la relation d'ordre qui sert de socle à tout treillis.
Borne supérieure — Pour préciser la notion de plus petit majorant utilisée dans la définition du join.
Borne inférieure — Pour approfondir la notion de plus grand minorant utilisée dans la définition du meet.
Explorez les mathématiques autrement
Retrouvez nos magazines, podcasts et jeux pour explorer les mathématiques autrement.
Découvrir les offres