Treillis (ensemble ordonné)

Un article de Wikipédia, l'encyclopédie libre.

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 un ensemble 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.

[modifier] 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 tout a de E, $a \vee a = a$ et $a \wedge a = a$ (idempotence)
pour tout a et b de E: $a \wedge (a \vee b) = a$ et $a \vee (a\wedge b) = a$ (absorption)

Pour démontrer que E est un treillis en tant qu'ensemble ordonné, il faut définir une relation d'ordre généralement 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 partiel). 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 à l'idempotence, 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$
$Inf(a, b) = a \wedge b$

Ce qui assure que (E , $\subseteq$ ) est bien un treillis.

[modifier] 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 montrer que E est un treillis algébrique, il faut construire deux lois internes

$a \vee b = Sup(a, b)$
$a \wedge b = Inf(a, b)$

Il est évident que les lois sont commutatives. On peut démontrer qu'elles sont associatives. On démontre aussi l'idempotence et l'absorbance.

Donc, sur tout treillis avec relation d'ordre, on peut construire deux lois qui lui confèrent des propriétés de treillis algébrique.

On trouvera alors des treillis dans lesquels on précise les deux lois internes et la relation d'ordre.

[modifier] 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.
L'ensemble des entiers naturels muni de son ordre usuel est un exemple de treillis incomplet : il n'admet pas lui-même de borne supérieure.
Soient f,g deux fonctions boréliennes sur R, intégrables pour la mesure 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).

[modifier] 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.

[modifier] Cas particuliers

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

Un treillis E est complet si pour tout sous-ensemble F de E, F possède une borne supérieure et une borne inférieure ; on dit aussi que E est un espace complètement réticulé.

Un treillis est distributif si la loi $\vee$ est distributive sur la loi $\wedge$ ou si la loi $\wedge$ est distributive sur la loi $\vee$ . En fait, les deux distributivités sont équivalentes, si un treillis en possède un type, il possède l'autre.