Treillis (ensemble ordonné)

Un article de Wikipédia, l'encyclopédie libre.
Aller à : navigation, rechercher
Page d'aide sur l'homonymie 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.

Exemples et contre-exemples préliminaires[modifier | modifier le code]

Tout ensemble muni d'une relation d'ordre total est un treillis. Par exemple, tout ensemble de réels muni de l'ordre usuel.

Diagramme de Hasse d'une relation d'ordre non associée à un treillis

Parmi les ensembles munis d'une relation d'ordre partiel, les exemples les plus simples de treillis sont issus des relations d'ordre « est inclus dans » et « divise ».

  • 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. Il en est de même de tout ensemble de parties d'un ensemble stable par union et intersection. C'est ainsi que l'ensemble des ouverts d'un espace topologique (toujours muni de l'inclusion) et un filtre sur un ensemble forment des treillis. Mais cette condition de stabilité n'est pas nécessaire. Ainsi l'ensemble des intervalles fermés de ℝ (y compris l'ensemble vide) est un treillis dont la borne inférieure est l'intersection et dont la borne supérieure n'est pas toujours l'union : la borne supérieure des intervalles [1, 3] et [4, 5] est l'intervalle [1, 5].
  • 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. L'ensemble des entiers naturels de 1 à 100 n'est pas un treillis car certaines paires, comme {25, 12} n'ont pas de majorant donc pas de borne supérieure.

Il ne suffit pas que chaque paire possède des majorants et des minorants pour obtenir un treillis. Ainsi dans l'exemple ci-contre, la paire {b, c} admet des majorants mais pas de borne supérieure.

Définition algébrique[modifier | modifier le code]

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

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 commutativité 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[modifier | modifier le code]

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 :

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

Glossaire des treillis[modifier | modifier le code]

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 (en) 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. Ainsi l'ensemble des entiers naturels muni de la relation d'ordre ≤ n'est pas borné mais le même ensemble muni de la relation d'ordre « divise » est un treillis borné dont le minimum est 1 et le maximum 0.

Un treillis borné est dit complémenté si chacun de ses éléments x possède un complément y vérifiant xy = 0 et xy = 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 est équivalent) si toute partie de E possède une borne inférieure.

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.. Certains treillis possédant un minimum peuvent ne pas posséder d'atomes. C'est par exemple le cas de l'ensemble des ouverts réguliers (ouverts égaux à l'intérieur de leur adhérence) d'un espace topologique muni de l'inclusion.

Un idéal du treillis E est une partie non vide I qui est stable par l'opération ⋁ et qui est telle que si xE et yI, alors xyI.

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

Treillis complet[modifier | modifier le code]

Dans un treillis borné, toute partie finie de E possède une borne supérieure et une borne inférieure, mais ce n'est pas toujours le cas pour des parties infinies : l'ensemble des rationnels compris entre 0 et 2 est un treillis borné mais il n'est pas complet car l'ensemble des rationnels de cet ensemble dont le carré est inférieur à 2 n'a pas de borne supérieure.

Garrett Birkhoff a introduit le sens suivant de l'épithète « complet » : un ensemble ordonné est dit complet si toute partie admet une borne supérieure (y compris l'ensemble vide, ce qui impose que E ait un minimum). Ceci est équivalent à ce que toute partie possède une borne inférieure (y compris l'ensemble vide, ce qui impose que E ait un maximum)

On dit aussi que E est un espace complètement réticulé. En informatique théorique, le sigle anglais CPO, bien que sa traduction littérale soit « ordre partiel complet » , a un sens différent. Pour éviter toute confusion avec une autre notion d'espace complet[3], celle au sens des espaces métriques ou plus généralement des espaces uniformes, Bourbaki avait proposé le terme achevé, qui ne s'est pas imposé. Ainsi, ℝ (qui est complet pour la distance usuelle) n'est pas achevé mais = ℝ ⋃ {–∞, +∞} l'est, d'où son nom de droite réelle achevée. est en fait le complété (en) (au sens de Dedekind-MacNeille (en)) de ℝ, c'est-à-dire le plus petit treillis complet contenant ℝ.

Autres exemples.

  • Tout segment est un treillis complet.
  • L'ensemble des parties d'un ensemble est un treillis complet pour l'inclusion.
  • L'ensemble des entiers naturels est un treillis complet pour la relation de divisibilité.
  • En théorie de l'intégration, si f et g sont deux fonctions boréliennes sur ℝ, 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).

Théorème de Knaster-Tarski : toute application croissante d'un treillis complet dans lui-même possède un point fixe.

Dualité[modifier | modifier le code]

Si (E, \vee, \wedge, \subseteq) est un treillis, alors son treillis dual est (E, \wedge, \vee, \supseteq).

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 \subseteq par \supseteq (et réciproquement) est un théorème vrai pour tous les treillis.

Notes et références[modifier | modifier le code]

  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 ⋁ est distributive par rapport à ⋀ alors
    (a\and c)\lor(b\and c)=[a\lor(b\and c)]\and[c\lor(b\and c)]=(a\lor b)\and(a\lor c)\and c=(a\lor b)\and c
    donc ⋀ est distributive par rapport à ⋁.
  3. Voir aussi les pages d'homonymie Complétude Page d'aide sur l'homonymie et Complet Page d'aide sur l'homonymie.

Bibliographie[modifier | modifier le code]

Ressources disponibles en ligne :

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, 3e éd., 1967

Voir aussi[modifier | modifier le code]