Lattis

Prenons les diviseurs de 12 et rangeons-les par divisibilité. Les nombres 3 et 4 ne sont pas comparables : aucun ne divise l’autre. Pourtant, ils ont un plus grand diviseur commun, 1, et un plus petit multiple commun présent dans l’ensemble, 12.

Un lattis garantit précisément ces deux choix extrêmes pour chaque paire. L’un rassemble vers le haut, l’autre vers le bas, même quand les deux éléments ne peuvent pas être placés l’un avant l’autre.

Un lattis, aussi appelé treillis, est un ensemble muni d’un ordre partiel. Pour deux éléments quelconques x et y, il existe un unique plus petit majorant commun, appelé leur join, et un unique plus grand minorant commun, appelé leur meet. Le join se note $x\vee yx\; \backslash vee\; y$ et le meet $x\wedge yx\; \backslash wedge\; y$.

Un ordre est partiel lorsque certains éléments peuvent rester incomparables. Dans un ordre total, toute paire est comparable : son join est son maximum et son meet son minimum. L’ensemble des parties d’un ensemble, ordonné par inclusion, forme aussi un lattis ; le join est l’union et le meet l’intersection.

Les sous-espaces vectoriels d’un même espace vectoriel, ordonnés par inclusion, donnent un autre exemple. Le meet de deux sous-espaces est leur intersection. Leur join est leur somme, c’est-à-dire le plus petit sous-espace qui les contient tous les deux. Cette structure intervient notamment en logique, en algèbre et en informatique théorique.

On considère les diviseurs positifs de 12 : 1, 2, 3, 4, 6 et 12. L’ordre choisi est la divisibilité. La paire étudiée est formée de 3 et 4.

1. Parmi ces diviseurs, 3 et 4 n’en divisent aucun l’un l’autre. Ils sont donc incomparables.

2. Le seul diviseur commun de 3 et 4 est 1. Le plus grand minorant commun est donc 1 : $3\wedge 4=13\; \backslash wedge\; 4\; =\; 1$.

3. Le seul multiple commun de 3 et 4 qui reste dans l’ensemble est 12. Le plus petit majorant commun est donc 12 : $3\vee 4=123\; \backslash vee\; 4\; =\; 12$.

4. Le contrôle se refait directement : 1 divise 3 et 4, tandis que 3 et 4 divisent 12. Aucun minorant commun supérieur à 1 ni aucun majorant commun inférieur à 12 n’appartient à cet ensemble.

Avec des diviseurs ordonnés par divisibilité, on cherche le meet par le plus grand diviseur commun et le join par le plus petit multiple commun. Si tous les nombres doivent plutôt être comparés par leur taille, l’ordre usuel convient mieux.

Avec des ensembles ordonnés par inclusion, on combine deux collections par intersection et par union. Lorsque l’on veut conserver les répétitions ou l’ordre des objets, une structure de listes est préférable à cet ensemble de parties.

Avec des sous-espaces vectoriels, on prend l’intersection pour descendre et la somme pour monter. L’union ordinaire ne convient que si l’un des deux sous-espaces contient l’autre ; sinon, elle n’est pas un sous-espace.

Ordre total. Dans un ordre total, toute paire est comparable. Un lattis n’exige pas cette comparabilité : 3 et 4 sont incomparables pour la divisibilité, mais possèdent bien un meet et un join.

Lattis complet. Un lattis garantit meet et join pour chaque paire. Un lattis complet les garantit pour toute famille d’éléments, y compris la famille vide ; ce critère supplémentaire sépare les deux notions.

Majorant et join. Un majorant commun n’est pas forcément le join. Pour 2 et 3 parmi les diviseurs de 12, 6 et 12 sont des majorants communs, mais seul 6 est le plus petit.

Un ensemble partiellement ordonné n’est pas automatiquement un lattis. Si une paire n’a aucun plus petit majorant ou aucun plus grand minorant dans l’ensemble, le test échoue ; il faut alors compléter l’ensemble ou travailler avec un ordre partiel plus général.

L’existence pour toutes les paires ne garantit pas des bornes pour une famille infinie. Il faut vérifier séparément la complétude avant d’employer des joins ou meets arbitraires.

Dans un diagramme de Hasse, placer les grands éléments en haut est une convention graphique, pas une donnée de l’ordre. Il faut lire les arêtes et la relation déclarée avant d’interpréter la hauteur.

Pour des sous-espaces vectoriels, le join n’est généralement pas leur union. Si aucun ne contient l’autre, cette union n’est pas stable par addition ; il faut prendre leur somme.

Ordre partiel — Pour examiner la relation qui sert de socle à tout lattis et comprendre pourquoi certains éléments restent incomparables.

Borne supérieure — Pour préciser le rôle des majorants et la condition qui distingue le supremum des autres bornes.

algèbre de Boole — Pour prolonger l’étude vers un lattis doté d’opérations et de propriétés algébriques supplémentaires.

espace vectoriel — Pour revoir le cadre dans lequel intersections et sommes de sous-espaces fournissent meet et join.