réseau complet

En mathématiques , un treillis complet est un ensemble partiellement ordonné dont tous les sous-ensembles possèdent une borne supérieure ( ou supremum ) et une borne inférieure (ou infimum ). Un treillis conditionnellement complet satisfait au moins une de ces propriétés pour les sous-ensembles bornés et non vides. Par comparaison, dans un treillis général , seules les paires d'éléments doivent posséder une borne supérieure et une borne inférieure. Tout treillis fini non vide est complet, mais les treillis infinis peuvent être incomplets.

Les treillis complets apparaissent dans de nombreuses applications en mathématiques et en informatique . La théorie de l'ordre et l'algèbre universelle les étudient toutes deux comme une classe particulière de treillis.

Il ne faut pas confondre les treillis complets avec les ordres partiels complets (OPC), une classe plus générale d'ensembles partiellement ordonnés. Les treillis complets les plus spécifiques sont les algèbres de Boole complètes et les algèbres de Heyting complètes (locales).ensemble partiellement ordonné ( L , ≤) tel que chaque sous-ensemble A de L a à la fois une borne inférieure maximale (l' infimum , ou rencontre ) et une borne supérieure minimale (le supremum , ou jointure ) dans ( L , ≤).

La rencontre est notée , et la jonction par .

Dans le cas particulier où A est l' ensemble vide , l'intersection de A est le plus grand élément de L. De même, la jointure de l'ensemble vide est le plus petit élément de L. Ainsi, les treillis complets forment une classe particulière de treillis bornés .

• Tout réseau fini non vide est trivialement complet.
• L' ensemble des parties d'un ensemble donné, ordonné par inclusion . Le supremum est donné par l' union et l'infimum par l' intersection des sous-ensembles.
• Les entiers non négatifs sont ordonnés par divisibilité . Le plus petit élément de ce treillis est 1, car il divise tout autre nombre. De façon peut-être surprenante, le plus grand élément est 0, car il est divisible par tout autre nombre. La borne supérieure d'un ensemble fini est donnée par son plus petit commun multiple ( PPCM) et la borne inférieure par son plus grand commun diviseur (PGCD). Pour les ensembles infinis, la borne supérieure est toujours 0, tandis que la borne inférieure peut être supérieure à 1. Par exemple, l'ensemble des nombres pairs a 2 comme PGCD. Si l'on retire 0 de cette structure, elle reste un treillis, mais n'est plus complète.
• Les sous-groupes d'un groupe donné par inclusion. (L' infimum est ici l'intersection ensembliste usuelle, tandis que le supremum d'un ensemble de sous-groupes est le sous-groupe engendré par l'union ensembliste des sous-groupes, et non l'union ensembliste elle-même.) Si e est l'élément neutre de G , alors le groupe trivial { e } est le sous-groupe minimal de G , et le sous-groupe maximal est le groupe G lui-même.
• Les idéaux d'un anneau , ordonnés par inclusion. Le supremum est donné par la somme des idéaux et l'infimum par leur intersection.
• Les ouverts d'un espace topologique , ordonnés par inclusion, sont les ensembles qui le composent. Le supremum est donné par l'union des ouverts et l'infimum par l' intérieur de leur intersection.
• Les sous-ensembles bornés des nombres réels munis de leur ordre habituel ≤ forment un treillis complet.
• Les nombres réels munis de leur ordre usuel ≤ forment un treillis conditionnellement complet, mais pas un treillis complet, car les suites peuvent devenir arbitrairement grandes ou petites. Cependant, un treillis complet est formé en ajoutant droite réelle étendue .
• Les nombres naturels avec leur ordre habituel ≤ forment un treillis conditionnellement complet, et les nombres naturels étendus (qui ajoutent nombres ordinaux et les nombres cardinaux forment des treillis conditionnellement complets.

Un treillis complet L est dit localement fini si le supremum de tout sous-ensemble infini est égal à l'élément supremum. En notant cet élément supremum « 1 », la condition est équivalente à ce que l'ensemble soit fini pour tout . Cette notation peut prêter à confusion avec d'autres notations, comme dans le cas du treillis ( N , |), c'est-à-dire l' ensemble des entiers non négatifs ordonnés par divisibilité . Dans ce treillis localement fini, l'élément infimal, noté « 0 » dans la théorie des treillis, est le nombre 1 de l'ensemble N et l'élément supremum, noté « 1 » dans la théorie des treillis, est le nombre 0 de l' ensemble N.

Les morphismes classiques entre treillis complets, prenant les treillis complets comme objets d'une catégorie , sont les homomorphismes complets (ou homomorphismes de treillis complets ). Ils sont caractérisés comme des fonctions qui préservent toutes fonction entre deux treillis complets L et M est un homomorphisme complet si

• et
• ,

Pour tout sous-ensemble A de L , de telles fonctions sont automatiquement monotones , mais la condition d'homomorphisme complet est en réalité beaucoup plus spécifique. C'est pourquoi il peut être utile de considérer des notions de morphisme plus faibles, telles que celles qui exigent seulement la préservation de toutes les jointures (définissant une catégorie Sup ) ou de toutes les intersections (définissant une catégorie Inf ), conditions qui sont en effet inéquivalentes. Ces notions peuvent également être considérées comme des homomorphismes de semi-treillis d'intersection complets ou de semi-treillis de jointure complets, respectivement.

La situation des treillis complets munis d'homomorphismes complets est plus complexe. En fait, les treillis complets libres n'existent généralement pas. Bien sûr, on peut formuler un problème de mots similaire à celui des treillis , mais l'ensemble de tous les mots (ou « termes ») possibles serait alors une classe stricte , car les opérations de rencontre et de jointure arbitraires comprennent des opérations pour des ensembles d'arguments de toute cardinalité .

Cette propriété n'est pas problématique en soi : comme le montre l'exemple des semi-treillis complets libres ci-dessus, il est tout à fait possible que la solution du problème des mots ne laisse subsister qu'un ensemble de classes d'équivalence. Autrement dit, il est possible que les classes propres de tous les termes aient la même signification et soient ainsi identifiées dans la construction libre. Cependant, les classes d'équivalence pour le problème des mots des treillis complets sont « trop petites », de sorte que le treillis complet libre serait encore une classe propre, ce qui est interdit.

On pourrait encore espérer qu'il existe des cas utiles où l'ensemble des générateurs est suffisamment petit pour qu'un réseau libre et complet puisse exister. Malheureusement, cette limite est très basse, et nous avons le théorème suivant :

Le treillis complet libre sur trois générateurs n'existe pas ; c'est une classe propre .

Johnstone en donne une preuve. L'argument original est attribué à Alfred W. Hales ; voir aussi l'article sur les réseaux libres .

Si un treillis complet est librement engendré à partir d'un ensemble partiellement ordonné donné , utilisé à la place de l'ensemble des générateurs considérés précédemment, on parle alors de complétion de cet ensemble. La définition du résultat de cette opération est similaire à la définition des objets libres donnée plus haut, où les « ensembles » et les « fonctions » sont remplacés par des « ensembles partiellement ordonnés » et des « applications monotones ». De même, on peut décrire le processus de complétion comme un foncteur de la catégorie des ensembles partiellement ordonnés munis de fonctions monotones vers une catégorie de treillis complets munis de morphismes appropriés, adjoints à gauche du foncteur d'oubli dans le sens inverse.

Dès lors que l'on considère les fonctions préservant les points d'intersection ou de jonction comme des morphismes, on peut aisément y parvenir grâce à la complétion de Dedekind-MacNeille . Dans ce processus, les éléments du poset sont transformés en coupures (de Dedekind) , lesquelles peuvent ensuite être transformées en posets sous-jacents de treillis complets arbitraires, de manière similaire à ce qui a été fait précédemment pour les ensembles et les (semi-)treillis complets libres.

Le résultat mentionné précédemment, selon lequel les treillis complets libres n'existent pas, implique qu'une construction libre correspondante à partir d'un ensemble partiellement ordonné (poset) est également impossible. Cela se vérifie aisément en considérant les posets d'ordre discret, où chaque élément n'est en relation qu'avec lui-même. Ce sont précisément les posets libres sur un ensemble sous-jacent. S'il existait une construction libre de treillis complets à partir de posets, alors les deux constructions seraient composables, ce qui contredit le résultat négatif énoncé ci-dessus.

L'ouvrage de G. Birkhoff, *Lattice Theory*, présente une méthode de représentation très utile. Elle associe un treillis complet à toute relation binaire entre deux ensembles en construisant une connexion de Galois à partir de cette relation, ce qui conduit à deux systèmes de fermeture dualement isomorphes . Les systèmes de fermeture sont des familles d'ensembles fermées par intersection. Ordonnés par la relation d'inclusion ⊆ , ils forment des treillis complets.

Un cas particulier de la construction de Birkhoff part d'un ensemble partiellement ordonné (P, ≤ ) et construit la connexion de Galois à partir de la relation d'ordre ≤ entre P et lui-même. Le treillis complet résultant est le complété de Dedekind-MacNeille . Appliqué à un ensemble partiellement ordonné qui est déjà un treillis complet, ce complété donne un résultat isomorphe au treillis initial. Ainsi, tout treillis complet est représenté par la méthode de Birkhoff, à isomorphisme près.

Cette construction est utilisée en analyse formelle de concepts , où l'on représente des données du monde réel par des relations binaires (appelées contextes formels ) et où l'on utilise les treillis complets associés (appelés treillis de concepts ) pour l'analyse des données. Les mathématiques sous-jacentes à l'analyse formelle de concepts sont donc la théorie des treillis complets.

On obtient une autre représentation : un sous-ensemble d'un treillis complet est lui-même un treillis complet (lorsqu'il est ordonné selon l'ordre induit) si et seulement s'il est l'image d'une application croissante et idempotente (mais pas nécessairement extensive) de lui-même. L'application identité possède ces deux propriétés. Ainsi, tous les treillis complets existent.

Outre les résultats de représentation précédents, d'autres énoncés peuvent être formulés concernant les treillis complets, ou qui prennent une forme particulièrement simple dans ce cas. On peut citer le théorème de Knaster-Tarski , qui stipule que l'ensemble des points fixes d'une fonction monotone sur un treillis complet est lui-même un treillis complet. Ce résultat généralise aisément l'observation précédente concernant les images des fonctions croissantes et idempotentes.