Treillis (ensemble ordonné)

Pour les articles homonymes, voir Treillis.

Le terme treillis provient de la forme du diagramme de Hasse associé à la relation d'ordre.

Un treillis (en anglais : lattice) est, en mathématiques, un ensemble partiellement ordonné dans lequel chaque couple d'éléments admet une borne supérieure et une borne inférieure. On parle aussi d'espace réticulé. Un treillis peut être vu comme le treillis de Galois d'une relation binaire.

Il existe en réalité deux définitions équivalentes du treillis, une concernant la relation d'ordre citée précédemment, l'autre algébrique.

Définition algébrique

Un treillis est un ensemble E muni de deux lois internes habituellement notées et vérifiant :

• les deux lois sont commutatives et associatives
• pour tous a et b de E : (loi d'absorption)

La loi d'absorption entraîne l'idempotence de tout élément a de E pour les deux lois^[1]:

et .

À partir d'une telle structure on peut définir sur E une relation d'ordre, ici notée , de la manière suivante :

On peut montrer que cette relation est bien une relation d'ordre (éventuellement partielle). La propriété d'associativité assure la transitivité. La propriété d'idempotence assure la réflexivité. La définition même assure l'antisymétrie. Grâce aux deux propriétés d'absorption, on peut aussi montrer que

On peut alors vérifier que

ce qui assure que (E , ) est bien un treillis au sens des ordres.

Définition par relation d'ordre

Un treillis est un ensemble E muni d'une relation d'ordre vérifiant :

pour tous éléments a et b de E, il existe une borne supérieure et une borne inférieure à l'ensemble {a,b}.

Pour munir E d'une structure de treillis algébrique, on remarque que la borne supérieure et la borne inférieure définissent alors deux lois internes :

Les propriétés de treillis algébrique pour ces deux lois découlent assez directement de la définition.

On définit donc indifféremment les treillis de façon algébrique ou par une relation d'ordre.

Exemples

• L'ensemble des parties d'un ensemble muni de l'inclusion forme un treillis où la borne supérieure est l'union et la borne inférieure l'intersection.
• Dans le même ordre d'idée, l'ensemble des ouverts d'un espace topologique (toujours muni de l'inclusion) forme un treillis. L'ensemble des ouverts réguliers (ouverts égaux à l'intérieur de leur adhérence) d'un espace topologique forme un treillis sans atomes (voir plus loin la définition d'atome).
• L'ensemble des entiers naturels muni de son ordre usuel est un exemple de treillis incomplet, et même non borné (voir plus loin les définitions d'un treillis complet et d'un treillis borné) : il n'admet pas d'élément maximum.
• L'ensemble des entiers naturels muni de la relation "divise" forme un treillis, où la borne supérieure est le PPCM et la borne inférieure est le PGCD. C'est un treillis borné (l'élément minimum est 1, l'élément maximum est 0) et même complet.
• Soient f,g deux fonctions boréliennes sur R, intégrables au sens de Lebesgue et vérifiant f<g. L'ensemble des fonctions boréliennes h comprises entre f et g est un treillis non complet qui devient complet si on identifie deux fonctions égales presque partout (attention ! la borne supérieure d'une famille de fonctions boréliennes peut être non mesurable ; lorsqu'on quotiente modulo l'égalité presque-partout, on regarde ce qu'on appelle une borne essentielle supérieure, laquelle, en revenant aux fonctions, majore presque-partout chaque élément de la famille).

Dualité

Si (E, , , ≤) est un treillis, alors son treillis dual est (E, , , ≥).

Théorème de dualité : Si un théorème T est vrai pour tous les treillis alors le théorème dual de T, obtenu en remplaçant toutes les occurrences de par (et réciproquement) et toutes les occurrences de ≤ par ≥ (et réciproquement) est un théorème vrai pour tous les treillis.

Glossaire des treillis

Un ensemble ordonné dans lequel chaque couple d'éléments possède une borne supérieure (ou une borne inférieure) est un demi-treillis.

Un treillis est dit distributif si la loi est distributive par rapport à la loi , ou encore (ce qui dans un treillis est équivalent^[2]) si la loi est distributive par rapport à la loi .

Un treillis est dit borné s'il possède un maximum et un minimum.

Un treillis borné est dit complémenté si chacun de ses éléments x possède un complément y vérifiant et , où 0 désigne l'élément minimum du treillis, et 1 l'élément maximum.

Un treillis distributif borné et complémenté s'appelle aussi une algèbre de Boole.

Un treillis E est dit complet si toute partie de E possède une borne supérieure, ou encore (ce qui dans un ensemble partiellement ordonné est équivalent^[3]) si toute partie de E possède une borne inférieure ; on dit aussi que E est un espace complètement réticulé. Un treillis complet est borné. (En informatique théorique, le sigle anglais CPO, bien que sa traduction littérale soit « ordre partiel complet » , a un sens différent.)

Dans un treillis E possédant un minimum que l'on note 0, les atomes sont les éléments minimaux de E \ {0}. Par exemple dans le treillis de l'ensemble des parties d'un ensemble, les atomes sont les singletons.

Un idéal du treillis E est une partie I qui est stable par l'opération et qui est telle que :

si et , alors

Étant donnée une partie A d'un ensemble X, l'ensemble des parties de A est un idéal du treillis de l'ensemble des parties de X.

Notes

Bibliographie

Ressources disponibles en ligne :

• Garrett Birkhoff, Théorie et applications des treillis, Annales de l'institut Henri Poincaré 11 no. 5 (1949), p. 227-240
• (en) Stanley N. Burris et H. P. Sankappanavar, A Course in Universal Algebra, Springer Verlag, 1981 (ISBN 978-3-540-90578-3)
• (en) Peter Jipsen et Henry Rose, Varieties of Lattices, Springer Lecture Notes in Mathematics 1533, 1992 (ISBN 978-0-387-56314-5)

Ouvrages de référence :

• (en) Thomas Donnellan, Lattice Theory, Pergamon Press, 1968
• (en) G. Grätzer, Lattice Theory: First concepts and distributive lattices, W. H. Freeman, 1971
• (en) B. A. Davey et H. A. Priestley, Introduction to Lattices and Order, Cambridge University Press, 2002
• (en) Garrett Birkhoff, Lattice Theory, AMS Colloquium Publications, vol. 25, 3^e éd., 1967

Voir aussi

• Treillis de Galois
• Algèbre de Kleene
• Morphologie mathématique

v · d · m Opérations binaires
Numériques En ensemble ordonné Structurelles Autres Élémentaires + Addition − Soustraction Multiplication Division Puissance Arithmétiques div Quotient euclidien mod Reste euclidien pgcd PGCD ppcm PPCM Combinatoires () Coefficient binomial A Arrangement Ensembles de parties Union Complémentation Intersection Δ Différence symétrique Ordre total min  Minimum max  Maximum Treillis Borne inférieure Borne supérieure Ensembles Produit cartésien Somme disjointe Puissance ensembliste Groupes Somme directe Produit libre Produit en couronne Modules Produit tensoriel Hom Homomorphisme Tor Torsion Ext Extension Arbres Enracinement Variétés connexes Somme connexe Espaces pointés Bouquet Smash produit Joint Fonctionnelles Composition de fonctions Produit de convolution Vectorielles Produit scalaire Produit vectoriel Produit vectoriel généralisé Algébriques [,] Crochet de Lie {,} Crochet de Poisson Produit extérieur Homologiques Cup produit Produit d'intersection Séquentielles + Concaténation
Logique booléenne : ET (conjonction) • OU (disjonction) • OU exclusif • IMP (implication) • EQV (équivalence)

• Portail des mathématiques