Un treillis est un ensemble partiellement ordonné (L, ≤) dans lequel chaque paire d'éléments x, y possède une borne inférieure la plus grande (meet, notée x ∧ y) et une borne supérieure la plus petite (join, notée x ∨ y). Les opérations meet et join sont associatives, commutatives, idempotentes et satisfont aux lois d'absorption.

Principe

Offrir un cadre algébrique pour la combinaison binaire d'informations d'ordre en garantissant l'existence des bornes supérieures et inférieures pour chaque paire ; équivalemment présenter comme une algèbre à deux opérations idempotentes, commutatives et associatives liées par l'absorption.

Démonstration

L'ensemble des parties P(S) d'un ensemble S, ordonné par l'inclusion, est un treillis : le meet est l'intersection, le join est l'union, et deux sous-ensembles ont toujours intersection et union. Un autre exemple est le treillis de divisibilité des entiers positifs avec pgcd comme meet et ppcm comme join.

Mauvaise application

Supposer qu'un treillis est un ordre total (chaîne) ou que meet et join coïncident avec des opérations arithmétiques peut induire en erreur ; par exemple traiter le treillis des sous-espaces comme si intersection et somme se comportaient toujours comme min et max néglige la dimension.

Conséquence

La présence de meet et join pour chaque paire permet des manipulations algébriques de l'information d'ordre, des théorèmes de point fixe basés sur les treillis et des décompositions structurelles utilisées en logique, topologie et algèbre (algèbres booléennes, treillis modulaires, systèmes de clôture).

Inversion

Supprimer l'exigence d'existence des deux bornes pour chaque paire donne des notions plus faibles : semi-treillis d'infimum (seulement pgcds) ou de supremum (seulement ppcm). Exiger la totalité donne des chaînes.

Limite

Les treillis exigent des meet et join binaires pour toutes les paires ; ils ne sont pas nécessairement distributifs, modulaires ou complémentaires sauf mention contraire. L'existence de meets/joins pour familles arbitraires (complétude) est une propriété plus forte non impliquée par les axiomes d'un treillis.

Tension sémantique

Distinguer treillis, posets et treillis algébriques : un treillis garantit des bornes binaires, tandis qu'un poset peut en être dépourvu, et la complétude (toutes les sous-ensembles ayant sup/inf) est une condition plus forte que certains confondent avec « treillis ».

Synthèse

Un treillis est la structure ordonnée où toute paire d'éléments admet meet et join, fournissant une paire d'opérations algébriques duales qui captent bornes inférieures et supérieures et servent de base à de nombreuses applications en théorie de l'ordre et en algèbre.