Treillis (ensemble ordonné)

Enmathématiques, untreillis(enanglais:lattice) est une desstructures algébriquesutilisées enalgèbre générale. C'est unensemble partiellement ordonnédans lequel chaquepaired'éléments admetune borne supérieure et une borne inférieure. Un treillis peut être vu comme letreillis de Galoisd'unerelation 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.
Tout ensemble muni d'une relation d'ordre totalest un treillis.
Par exemple, tout ensemble de réels muni de l'ordre usuel.
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 ».
Un treillis est unensembleEmuni de deuxlois interneshabituellement notées ⋁ et ⋀ vérifiant :
La loi d'absorption entraîne l'idempotencede tout élémentadeEpour les deux lois:
À partir d'une telle structure on peut définir surEunerelation 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 latransitivité. La propriété d'idempotenceassure laré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(E,≤){\displaystyle (E,\leq )}est bien un treillis au sens des ordres.
Un treillis est un ensembleEmuni d'une relation d'ordre vérifiant :
Pour munirEd'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.
Un ensemble ordonné dans lequel chaque couple d'éléments possède une borne supérieure (ou une borne inférieure) est undemi-treillis.
Unmorphismede demi-treillis de (L, ∨L) vers (M, ∨M) est une applicationf:L→Mtelle que pour tousa,b∈L,f(a∨Lb) =f(a) ∨Mf(b). On dit que c'est unplongement(de demi-treillis) sifest de plusinjective. Les définitions d'un morphisme et d'un plongement de treillis vont alors de soi.Exemple : le treillis despartitionsd'un ensembleX—isomorpheautreillis des relations d'équivalencesurX— se plonge dans letreillis des sous-groupesdugroupe symétriqueS(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 unmorphisme (resp. plongement) d'ensembles ordonnésmais lesréciproquessont fausses, et même : tout treillis se plonge dans le treillis des relations d'équivalence sur un certain ensemble, qui peut d'ailleurs être choisi fini si le treillis l'est.
Un treillis est ditdistributif(en)si la loi ⋁ estdistributivepar rapport à la loi ⋀, ou encore (ce qui dans un treillis est équivalent) si la loi ⋀ est distributive par rapport à la loi ⋁.
Un treillis est ditborné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 ditcomplémentési chacun de ses élémentsxpossède un complémentyvérifiantx⋀y= 0 etx⋁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 unealgèbre de Boole.
Un treillisEest ditcompletsi toute partie deEpossède une borne supérieure, ou encore (ce qui est équivalent,voir plus bas) si toute partie deEpossède une borne inférieure.
Dans un treillisEpossédant un minimum que l'on note 0, lesatomessont leséléments minimauxdeE\ {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érieurde leuradhérence) d'un espace topologique muni de l'inclusion.
Unidéaldu treillisEest une partie non videIqui est stable par l'opération ⋁ et qui est telle que six∈Eety∈I, alorsx⋀y∈I.
Étant donné une partieAd'un ensembleX, l'ensemble des parties deAest un idéal du treillis de l'ensemble des parties deX.
Dans un treillis, toute partie finie deEpossède une borne supérieure et une borne inférieure, mais ce n'est pas toujours le cas pour des parties infinies, même s'il est borné : 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 Birkhoffa introduit le sens suivant de l'épithète « complet » : un ensemble ordonné est ditcompletsi toute partie admet une borne supérieure (y compris l'ensemble vide, ce qui impose queEait un minimum). Ceci est équivalentà ce que toute partie possède une borne inférieure (y compris l'ensemble vide, ce qui impose queEait un maximum).
On dit aussi queEest un espacecomplètementréticulé. Eninformatique théorique, lesigleanglaisCPO, 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, celle au sens desespaces métriquesou plus généralement desespaces uniformes,Bourbakiavait proposé le termeachevé, qui ne s'est pas imposé. Ainsi, ℝ (qui est complet pour ladistanceusuelle) n'est pas achevé maisℝ= ℝ ⋃{–∞, +∞}l'est, d'où son nom dedroite réelle achevée.ℝest en fait lecomplété(en)(au sens deDedekind-MacNeille(en)) de ℝ, c'est-à-dire le plus petit treillis complet contenant ℝ.
Autres exemples.
Théorème de Knaster-Tarski: toute application croissante d'un treillis complet dans lui-même possède unpoint fixe.
Si(E,∨,∧,≤){\displaystyle (E,\vee ,\wedge ,\leq )}est un treillis, alors sontreillis dualest(E,∧,∨,≥){\displaystyle (E,\wedge ,\vee ,\geq )}.
Principe 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∨{\displaystyle \vee }par∧{\displaystyle \wedge }(et réciproquement) et toutes les occurrences de≤{\displaystyle \leq }par≥{\displaystyle \geq }(et réciproquement) est un théorème vrai pour tous les treillis.