Treillis (ensemble ordonné)

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é.

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.

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:

$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 :

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 , $\subseteq$ ) est bien un treillis au sens des ordres.

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.

• 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).

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.

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) 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) 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, l'acronyme anglais CPO, bien 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.