Voir la source de Treillis (ensemble ordonné)

{{Voir homonymes|Treillis}}
[[Image:Lattice of partitions of an order 4 set.svg|thumb|Le terme ''treillis'' provient de la forme du [[diagramme de Hasse]] associé à la relation d'ordre.]]

En [[mathématiques]], un '''treillis<ref>{{Bourbaki-Ensembles}}, {{p.|ER.28}}, {{Google Livres|VDGifaOQogcC|page=129|aperçu}}, parle d'{{Citation|''ensemble réticulé'', ou ''réseau ordonné'' (ou ''lattis'')}}.</ref>''' ({{En anglais|lattice}}) est une des [[Structure algébrique|structures algébriques]] utilisées en [[algèbre générale]]. C'est un [[Relation d'ordre|ensemble partiellement ordonné]] dans lequel chaque [[paire]] d'éléments admet [[Borne supérieure et borne inférieure|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 ==
Tout ensemble muni d'une relation d'[[ordre total]] est un treillis.
Par exemple, tout ensemble de réels muni de l'ordre usuel.

[[File:NoLatticeDiagram.svg|thumb|Ce [[Diagramme de Hasse]] représente un ensemble ordonné qui n'est pas 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 (de deux éléments), 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 (mathématiques)|filtre sur un ensemble]] forment des treillis.
* Cette condition de stabilité n'est pas nécessaire :
**l'ensemble des [[Intervalle (mathématiques)#Inventaire|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 : ainsi la borne supérieure des intervalles [1, 3] et [4, 5] est l'intervalle [1, 5] ;
**l'ensemble des [[Relation d'équivalence|relations d'équivalence]] sur un ensemble donné est un treillis (ordonné par la [[Relation binaire#Définitions|finesse entre relations binaires]]) dont la borne inférieure est l'intersection (sur les graphes) mais la borne supérieure est la [[relation d'équivalence engendrée]] par l'union.
* L'ensemble des [[Entier naturel|entiers naturels]] muni de la relation [[divisibilité|« divise »]] forme un treillis, où la borne supérieure est le [[Plus petit commun multiple|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 ==
Un treillis est un [[ensemble]] ''E'' muni de deux [[loi de composition interne|lois internes]] habituellement notées ⋁ et ⋀ vérifiant :
* les deux lois sont [[commutativité|commutatives]] et [[associativité|associatives]] ;
* pour tous {{math|''a''}} et {{math|''b''}} de ''E'' : <math>a \wedge (a \vee b) = a = a \vee (a\wedge b) </math> ([[loi d'absorption]]).
La loi d'absorption entraîne l'[[idempotence]] de tout élément ''a'' de ''E'' pour les deux lois<ref>En effet, <math>a \lor a=a\lor(a\land(a\lor a))=a</math>, et de même en intervertissant les deux lois.</ref> :
:<math>a \vee a = a \qquad\text{et}\qquad a \wedge a = a</math>.

À partir d'une telle structure on peut définir sur ''E'' une [[relation d'ordre]], ici notée ≤, de la manière suivante :
: <math>a\le b \Leftrightarrow a \vee b = b</math>.

On peut montrer que cette relation est bien une relation d'ordre (éventuellement partielle). La propriété d'associativité assure la [[relation transitive|transitivité]]. La propriété d'[[idempotence]] assure la [[relation réflexive|réflexivité]]. La commutativité assure l'[[Relation antisymétrique|antisymétrie]]. Grâce aux deux propriétés d'absorption, on peut aussi montrer que

:<math>a\le b \Leftrightarrow a \wedge b = a</math>.

On peut alors vérifier que
:<math> \sup(a, b) = a \vee b \qquad\text{et}\qquad\inf(a, b) = a \wedge b</math>,
ce qui assure que <math>(E,\le)</math> est bien un treillis au sens des ordres.

== Définition par relation d'ordre ==
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 borne inférieure|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 :
* <math> a \vee b = \sup(a, b)</math> ; 
* <math> a \wedge b  = \inf(a, b)</math>.
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 ==
{{ancre|demi-treillis|ancre pour la redirection}}
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'', ∨<sub>''L''</sub>) vers (''M'', ∨<sub>''M''</sub>) est une application ''f'' : ''L'' → ''M'' telle que pour tous ''a'', ''b'' ∈ ''L'', ''f''(''a''∨<sub>''L''</sub>''b'') = ''f''(''a'') ∨<sub>''M''</sub> ''f''(''b''). On dit que c'est un [[plongement]] (de demi-treillis) si ''f'' est de plus [[Injection (mathématiques)|injective]]. Les définitions d'un morphisme et d'un plongement de treillis vont alors de soi.{{Retrait|Exemple : le treillis des [[Partition (mathématiques)|partitions]] d'un ensemble {{math|''X''}} — [[Isomorphisme|isomorphe]] au [[#Exemples et contre-exemples préliminaires|treillis des relations d'équivalence]] sur {{math|''X''}} — se plonge dans le [[treillis des sous-groupes]] du [[groupe symétrique]] {{math|S(''X'')}}, en associant à chaque partition {{math|π}} le sous-groupe [[Produit direct d'une famille de groupes|{{math|∏{{ind|''A''∈π}}S(''A'')}}]].}}Tout morphisme (resp. tout plongement) de treillis (ou même de demi-treillis) est un [[Relation d'ordre#Applications croissantes|morphisme (resp. plongement) d'ensembles ordonnés]] mais les [[réciproque]]s sont fausses, et même : tout treillis se plonge dans le treillis des relations d'équivalence sur un certain ensemble<ref>{{Article|lang=en|auteur={{Lien|Philip M. Whitman}}|titre=Lattices, equivalence relations, and subgroups|revue=[[Bulletin of the American Mathematical Society|Bull. Amer. Math. Soc.]]|vol=52|année=1946|p.=507-522|url=http://www.ams.org/journals/bull/1946-52-06/S0002-9904-1946-08602-4}}.</ref>, qui peut d'ailleurs être choisi fini si le treillis l'est<ref>{{Article|lang=en|auteur=Pavel Pudlák|auteur2=Jiří Tůma|titre=Every finite lattice can be embedded in a finite partition lattice|revue=[[Algebra Universalis]]|vol=10|année=1980|p.=74-95|url=https://link.springer.com/content/pdf/10.1007%2FBF02482893.pdf}}.</ref>.

Un treillis est dit '''{{Lien|trad=Distributive lattice|Treillis distributif|texte=distributif}}''' si la loi ⋁ est [[distributive]] par rapport à la loi ⋀, ou encore (ce qui dans un treillis est équivalent<ref>En effet, si par exemple ⋁ est distributive par rapport à ⋀ alors

:<math>(a\land c)\lor(b\land c)=[a\lor(b\land c)]\land[c\lor(b\land c)]=(a\lor b)\land(a\lor c)\land c=(a\lor b)\land c</math>
donc ⋀ est distributive par rapport à ⋁.</ref>) si la loi ⋀ est distributive par rapport à la loi ⋁.

Un treillis est dit '''[[Extremum|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 ''x ''⋀ ''y ''= 0 et ''x ''⋁ ''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 (structure)|algèbre de Boole]].

Un treillis ''E ''est dit '''[[#Treillis complet|complet]]''' si toute partie de ''E'' possède une borne supérieure, ou encore (ce qui est équivalent, [[#Treillis complet|voir plus bas]]) 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ément minimal|éléments minimaux]] de ''E'' \ {0}. Par exemple dans le treillis de l'ensemble des parties d'un ensemble, les atomes sont les singletons<!-- énoncé correct même si l'ensemble est vide -->. Certains treillis possédant un minimum peuvent ne pas posséder d'atomes. C'est par exemple le cas de [[Nombre positif|ℝ{{ind|+}}]], ainsi que de l'ensemble des ouverts réguliers (ouverts égaux à l'[[Intérieur (topologie)|intérieur]] de leur [[Adhérence (mathématiques)|adhérence]]) d'un espace topologique muni de l'inclusion.

Un [[Idéal (théorie des ordres)|idéal]] du treillis ''E'' est une partie non vide ''I'' qui est stable par l'opération ⋁ et qui est telle que si ''x'' ∈ ''E'' et ''y'' ∈ ''I'', alors ''x'' ⋀ ''y'' ∈ ''I''.

Étant donné 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 ==

Dans un treillis, 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, 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 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<ref>{{Note autre projet|Wikiversité|Relation_(mathématiques)/Exercices/Relation_d'ordre#Exercice_2-9|cet exercice corrigé|début=Voir par exemple}}</ref> à 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 [[Ordre partiel complet (informatique)|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]]<ref>Voir aussi les pages d'homonymie {{Page h|Complétude}} et {{Page h|Complet}}.</ref>, celle au sens des [[espace métrique|espaces métriques]] ou plus généralement des [[espace uniforme|espaces uniformes]], [[Nicolas Bourbaki|Bourbaki]] avait proposé le terme ''achevé'', qui ne s'est pas imposé. Ainsi, ℝ (qui est complet pour la [[distance (mathématiques)|distance]] usuelle) n'est pas achevé mais {{surligner|ℝ}} = ℝ ⋃ {{math|<nowiki>{</nowiki>–∞, +∞<nowiki>}</nowiki>}} l'est, d'où son nom de ''[[droite réelle achevée]]''. {{surligner|ℝ}} est en fait le {{Lien|trad=Dedekind–MacNeille completion|Complétion de Dedekind-MacNeille|texte=complété}} (au sens de [[Richard Dedekind|Dedekind]]-{{Lien|Holbrook Mann MacNeille|texte=MacNeille}}) de ℝ, c'est-à-dire le plus petit treillis complet contenant ℝ.

Autres exemples.
* Tout [[Segment (mathématiques)|segment]] est un treillis complet.
* L'ensemble des parties d'un ensemble est un treillis complet pour l'inclusion.
* Pour toute partie ''G'' d'un treillis complet, le sous-treillis des [[majorant]]s de ''G'' est complet (et de même pour celui des minorants).
* En théorie de l'intégration, si ''f'' et ''g'' sont deux [[Fonction mesurable|fonctions boréliennes]] sur ℝ, intégrables [[intégrale de Lebesgue|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 l'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 [[Espace L∞#Borne supérieure essentielle|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é ==
Si <math>(E, \vee, \wedge,\le)</math> est un treillis, alors son '''treillis dual''' est <math>(E, \wedge, \vee,\ge)</math>.

'''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 <math>\vee</math> par <math>\wedge</math> (et réciproquement) et toutes les occurrences de <math>\le</math> par <math>\ge</math> (et réciproquement) est un théorème vrai pour tous les treillis.

== Notes et références ==
{{Références}}

== Voir aussi ==

=== Articles connexes ===
* [[Algèbre de Kleene]]
* [[Ensemble ordonné filtrant]]
* [[Morphologie mathématique]]

=== Bibliographie ===
*Ressources disponibles en ligne :
**{{Article|auteur=[[Garrett Birkhoff]]|url=http://www.numdam.org/item/AIHP_1949__11_5_227_0/|titre=Théorie et applications des treillis|revue=[[Annales Henri Poincaré|Annales de l'IHP]]|vol=11|numéro=5|année=1949|p.=227-240}}
**{{Article|auteur=Garrett Birkhoff|url=http://www.numdam.org/item/AIHP_1949__11_5_241_0/|titre=Groupes réticulés|revue=Annales de l'IHP|vol=11|numéro=5|année=1949|p.=241-250}}<!--Voir aussi https://www.apmep.fr/IMG/pdf/BR6_Le_cours_de_l_APM_I_Groupes_anneaux_corps_Revuz_A_G_APMEP_1962.pdf p.50-52-->
**{{en}} Stanley N. Burris et H. P. Sankappanavar, ''[http://www.thoralf.uwaterloo.ca/htdocs/ualg.html A Course in Universal Algebra]'', [[Springer Verlag]], 1981 {{ISBN|978-3-540-90578-3}}
**{{en}} Peter Jipsen et Henry Rose, ''[http://www1.chapman.edu/~jipsen/JipsenRoseVoL.html Varieties of Lattices]'', Springer Lecture Notes in Mathematics '''1533''', 1992 {{ISBN|978-0-387-56314-5}}
*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

{{Palette|Opérations binaires}}
{{Portail|mathématiques}}

[[Catégorie:Treillis|*]]