Logique et ensemblesNotion · Glossaire
treillis - algèbre -
Un treillis (également appelé lattis ou ensemble réticulé) est un ensemble ordonné dans lequel toute paire d'éléments admet à la fois une borne inférieure (le plus grand minorant commun, appelé infimum ou meet) et une borne supérieure (le plus petit majorant commun, appelé supremum ou join). Cette structure algébrique est fondamentale en théorie des ordres et trouve des applications en logique, en théorie des treillis de Boole et en informatique théorique.
Sommaire
Ce que vous allez apprendre
- Identifier les deux conditions qui font d'un ensemble ordonné un treillis.
- Calculer l'infimum et le supremum de 2 et 3 parmi les diviseurs de 6.
- Distinguer un treillis d'un ordre partiel, d'un ordre total et d'une algèbre de Boole.
- Repérer les pièges liés à l'ordre choisi et aux bornes de familles de plus de deux éléments.
En clair
Prenons les diviseurs de 6 : 1, 2, 3 et 6. Rangeons-les selon la divisibilité. Pour deux nombres choisis, nous cherchons le plus grand nombre qui divise les deux, puis le plus petit qu'ils divisent tous les deux.
Avec 2 et 3, ces deux repères sont 1 et 6. Un ensemble ordonné forme un treillis lorsque ce choix est possible pour chaque paire d'éléments. Il organise donc deux gestes complémentaires : descendre vers le meilleur élément commun et monter vers le meilleur élément commun.
Définition
Un treillis, aussi nommé lattis ou ensemble réticulé, est un ensemble muni d'un ordre partiel. Pour deux éléments quelconques, il doit exister un unique plus grand minorant commun et un unique plus petit majorant commun. Ces deux éléments appartiennent au treillis.
Notons les deux éléments x et y. Leur plus grand minorant, appelé infimum ou meet, se note . Leur plus petit majorant, appelé supremum ou join, se note . « Plus grand » et « plus petit » se comprennent toujours relativement à l'ordre choisi, pas nécessairement à l'ordre usuel des nombres.
La condition porte sur chaque paire, y compris une paire formée deux fois du même élément. Elle fait du treillis une structure centrale de la théorie des ordres. Les opérations d'infimum et de supremum interviennent aussi en logique, dans les treillis de Boole et en informatique théorique.
Un exemple, pas à pas
Considérons l'ensemble des diviseurs positifs de 6, ordonné par divisibilité. Le diagramme de Hasse de cet exemple rend visibles les liens d'ordre utiles sans ajouter les relations déduites par transitivité.
Données.
L'ensemble contient 1, 2, 3 et 6.
La relation « est inférieur ou égal » signifie ici « divise ».
La paire étudiée est formée de 2 et 3.
L'ensemble contient 1, 2, 3 et 6.
La relation « est inférieur ou égal » signifie ici « divise ».
La paire étudiée est formée de 2 et 3.
1. Cherchons les minorants communs de 2 et 3. Seul 1 divise les deux nombres. Le plus grand minorant commun est donc 1.
2. Cherchons les majorants communs présents dans l'ensemble. Seul 6 est divisible à la fois par 2 et par 3. Le plus petit majorant commun est donc 6.
3. Avec la notation du treillis, le calcul donne . Le résultat se contrôle directement : 1 divise 2 et 3, tandis que 2 et 3 divisent 6. Le même test sur les autres paires confirme que cet ensemble ordonné est un treillis.
En pratique
Pour organiser des nombres par divisibilité, le treillis sert à retrouver deux synthèses d'une paire : le plus grand diviseur commun et le plus petit multiple commun dans l'ensemble étudié. Si certaines paires n'ont pas ces deux résultats, un simple ensemble partiellement ordonné décrit mieux la situation.
En logique, un treillis de Boole organise des propositions et leurs combinaisons. On choisit ce cadre lorsque les deux opérations d'infimum et de supremum sont disponibles pour chaque paire ; une seule relation d'ordre ne suffit pas.
En informatique théorique, le langage des treillis aide à raisonner sur des informations ordonnées et sur leurs bornes communes. Le bon réflexe consiste d'abord à préciser l'ordre, puis à vérifier l'existence des deux bornes pour toutes les paires.
À ne pas confondre
Ensemble partiellement ordonné. Il impose seulement une relation d'ordre partiel. Un treillis exige en plus un infimum et un supremum pour chaque paire. Si une paire n'a pas l'une de ces bornes, l'ensemble reste éventuellement ordonné, mais ce n'est pas un treillis.
Ensemble totalement ordonné. Tous ses éléments sont comparables deux à deux. Dans un treillis, deux éléments peuvent être incomparables : 2 ne divise pas 3 et 3 ne divise pas 2 dans l'exemple des diviseurs de 6, même si leur infimum et leur supremum existent.
Algèbre de Boole. C'est un treillis doté de propriétés et d'opérations supplémentaires, notamment un complément pour chaque élément. Une chaîne de trois éléments forme un treillis, mais son élément intermédiaire n'a pas de complément : ce cas tranche en faveur du simple treillis.
Limites et pièges
Une paire sans borne commune suffit à faire échouer la définition. Le symptôme est l'impossibilité de choisir un plus grand minorant ou un plus petit majorant dans l'ensemble. Il faut alors parler d'ensemble partiellement ordonné, pas de treillis.
Infimum ne signifie pas minimum global. L'infimum de 2 et 3 vaut 1 dans l'exemple, mais il dépend de la paire examinée. Il faut chercher les bornes communes de cette paire selon l'ordre déclaré, sans sélectionner automatiquement le plus petit élément de tout l'ensemble.
L'ordre usuel peut induire en erreur. Pour la divisibilité, 2 et 3 sont incomparables malgré l'inégalité numérique 2 < 3, qui n'est pas la relation retenue. Il faut toujours reformuler le symbole d'ordre en mots avant de déterminer les bornes.
Les paires ne garantissent pas toutes les familles. La définition d'un treillis assure les bornes pour deux éléments à la fois. Pour exiger un infimum et un supremum pour chaque sous-ensemble, y compris vide, il faut vérifier la propriété plus forte de treillis complet.
Pour aller plus loin
Relation d'ordre — Pour préciser le cadre qui rend comparables certains éléments et donne un sens aux minorants et aux majorants.
Algèbre de Boole — Pour étudier un treillis enrichi par des opérations et des propriétés adaptées au raisonnement logique.
Explorez les mathématiques autrement
Retrouvez nos magazines, podcasts et jeux pour explorer les mathématiques autrement.
Découvrir les offres