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 $\vee$ et $\wedge$ vérifiant :

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

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

$a \vee a = a$ et $a \wedge a = a$.

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

$a\subseteq b \Leftrightarrow a \vee b = b$

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

$a \subseteq b \Leftrightarrow a \wedge b = a$

On peut alors vérifier que

$\sup(a, b) = a \vee b \qquad\text{et}\qquad\inf(a, b) = a \wedge b,$

ce qui assure que (E , $\subseteq$ ) 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 $\subseteq$ 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 :

• $a \vee b = \sup(a, b)$
• $a \wedge b = \inf(a, b)$

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, $\vee$, $\wedge$, ≤) est un treillis, alors son treillis dual est (E, $\wedge$, $\vee$, ≥).

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 $\vee$ par $\wedge$ (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 $\vee$ est distributive par rapport à la loi $\wedge$, ou encore (ce qui dans un treillis est équivalent^[2]) si la loi $\wedge$ est distributive par rapport à la loi $\vee$.

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 $x \wedge y = 0$ et $x \vee y =1$, 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 $\vee$ et qui est telle que :

si $x\in E$ et $y\in I$, alors $x \wedge y \in I.$

É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

1. ↑ En effet, $a \lor a=a\lor(a\land(a\lor a))=a$, et de même en intervertissant les deux lois.
2. ↑ En effet, si par exemple $\or$ est distributive par rapport à $\and$ alors

   $(a\and c)\or(b\and c)=[a\or(b\and c)]\and[c\or(b\and c)]=(a\or b)\and(a\or c)\and c=(a\or b)\and c$

   donc $\and$ est distributive par rapport à $\or$.
3. ↑ cf Espace complet#Autre acception du terme

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