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.

En mathématiques, un treillis[1] (en anglais : lattice) est une des structures algébriques utilisées en algèbre générale. C'est un ensemble partiellement ordonné dans lequel chaque paire d'éléments admet une borne supérieure et une borne inférieure. 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, des exemples 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.
  • Si une partie d'un treillis est stable par borne supérieure et borne inférieure, elle forme un treillis (pour l'ordre restreint). 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.
  • Cette condition de stabilité n'est pas nécessaire :
  • 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.
  • Pour tout entier n ≥ 3, l'ensemble des entiers de 1 à n, muni de la relation d'ordre « divise », n'est pas un treillis car la paire {n, n – 1} n'a pas de borne supérieure ni même de majorant (car tout multiple de n et n – 1 est multiple de n(n – 1), qui est > n).
  • Il ne suffit pas que chaque paire possède des majorants et des minorants pour obtenir un treillis. Ainsi, dans la relation décrite par le diagramme de Hasse ci-contre, la paire {b, c} admet trois majorants d, e et f, mais pas de borne supérieure car {d, e, f} ne possède pas de plus petit élément.

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[2] :

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 commutativité 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 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 :

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 morphisme de demi-treillis de (L, ∨L) vers (M, ∨M) est une application f : LM telle que pour tous a, bL, f(aLb) = f(a) ∨M f(b). On dit que c'est un plongement (de demi-treillis) si f est de plus injective. Les définitions d'un morphisme et d'un plongement de treillis vont alors de soi.Exemple : le treillis des partitions d'un ensemble Xisomorphe au treillis des relations d'équivalence sur X — se plonge dans le treillis des sous-groupes du groupe symétrique S(X), en associant à chaque partition π le sous-groupe A∈πS(A).Tout morphisme (resp. tout plongement) de treillis (ou même de demi-treillis) est un morphisme (resp. plongement) d'ensembles ordonnés mais les réciproques sont fausses, et même : tout treillis se plonge dans le treillis des relations d'équivalence sur un certain ensemble[3], qui peut d'ailleurs être choisi fini si le treillis l'est[4].

Un treillis est dit distributif (en) si la loi ⋁ est distributive par rapport à la loi ⋀, ou encore (ce qui dans un treillis est équivalent[5]) 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 +, ainsi que 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[6], 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 est un treillis, alors son treillis dual est .

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.

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

  1. N. Bourbaki, Éléments de mathématique : Théorie des ensembles [détail des éditions], p. ER.28, aperçu sur Google Livres, parle d'« ensemble réticulé, ou réseau ordonné (ou lattis) ».
  2. En effet, , et de même en intervertissant les deux lois.
  3. (en) Philip M. Whitman (en), « Lattices, equivalence relations, and subgroups », Bull. Amer. Math. Soc., vol. 52,‎ , p. 507-522 (lire en ligne).
  4. (en) Pavel Pudlák et Jiří Tůma, « Every finite lattice can be embedded in a finite partition lattice », Algebra universalis, vol. 10,‎ , p. 74-95 (lire en ligne).
  5. En effet, si par exemple ⋁ est distributive par rapport à ⋀ alors
    donc ⋀ est distributive par rapport à ⋁.
  6. 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]