Treillis

Un treillis est un ensemble ordonné qui possède en plus la propriété suivante : pour deux éléments quelconques du treillis, la borne supérieure et la borne inférieure existent et appartiennent aussi à ce treillis.

Cônes supérieur et inférieur

Au départ, on a un ensemble M muni d’un ordre ≤. Cet ordre peut être quelconque, mais il doit vérifier les conditions d’une relation d’ordre.

On prend ensuite un élément a de l’ensemble M. Le cône supérieur de l’élément a dans M est l’ensemble de tous les x ∈ M qui sont supérieurs ou égaux à a, c’est-à-dire tels que a ≤ x.

Si on prend pour ensemble celui des entiers naturels non nuls ℕ^* et pour élément a = 7, le cône supérieur est l’ensemble de nombres {7 ; 8 ; 9 ; …}. Dans les nombres réels, on obtiendrait l’intervalle [7 ; +∞[.

Prenons maintenant l’ensemble M = 2^ℕ* : c’est l’ensemble des parties de ℕ^*, c’est-à-dire de tous les ensembles qu’on peut construire à l’aide des entiers naturels non nuls. L’ordre est donné par l’inclusion. On a donc par exemple {3 ; 5} ≤ {3 ; 4 ; 5}.

Le cône supérieur de l’ensemble {1 ; 2 ; 3 ; 4} est formé de tous les ensembles qui contiennent les éléments 1, 2, 3, 4. Par exemple l’ensemble {1 ; 2 ; 3 ; 4 ; 5 ; 6 ; 9} ou l’ensemble {1 ; 2 ; 3 ; 4 ; 2323 ; 454645}. L’ensemble {1 ; 2 ; 3 ; 4} lui-même appartient aussi à son cône supérieur.

Le cône inférieur se définit de façon analogue : il contient les éléments qui sont inférieurs ou égaux à l’élément a. Pour a = 7 dans ℕ^*, on obtient l’ensemble {1 ; 2 ; 3 ; 4 ; 5 ; 6 ; 7} : ce sont les entiers naturels non nuls inférieurs ou égaux à sept.

Pour l’ensemble {1 ; 2 ; 3 ; 4}, on obtient toutes les parties de cet ensemble.

Cônes supérieur et inférieur de plusieurs éléments

Dans la partie précédente, nous avons défini les cônes pour un seul élément. On peut aussi les définir pour plusieurs éléments. Si on a un ensemble M et des éléments a et b, leur cône supérieur commun contient les éléments qui sont supérieurs ou égaux à a et à b en même temps. Autrement dit, on calcule les cônes supérieurs des deux éléments et on prend leur intersection. On obtient ainsi les éléments qui sont à coup sûr supérieurs à a et supérieurs à b.

Restons dans les entiers naturels non nuls, avec a = 3 et b = 5. Les éléments supérieurs ou égaux à a forment l’ensemble {3 ; 4 ; 5 ; 6 ; …}, ceux supérieurs ou égaux à b forment {5 ; 6 ; 7 ; 8 ; …}. L’intersection est de nouveau l’ensemble {5 ; 6 ; 7 ; 8 ; …}. Si l’ensemble est totalement ordonné, il suffit de trouver le plus grand des deux éléments et de calculer son cône supérieur.

Avec des ensembles, ce n’est plus aussi simple. Essayons de calculer le cône inférieur de a = {1 ; 2 ; 3} et b = {2 ; 3 ; 4}. Ce sont tous les ensembles qui sont à la fois des parties de a et de b. L’ensemble {1 ; 2 ; 3} est-il une partie de a ? Oui. Est-il aussi une partie de b ? Non. Cet ensemble n’appartient donc pas au cône inférieur.

Cherchons le plus grand ensemble qui soit une partie de a et de b. Ce sera visiblement l’ensemble {2 ; 3}, c’est-à-dire l’intersection a ∩ b. Il appartient au cône inférieur, et toutes ses parties aussi. En effet, si par exemple ∅ ⊂ {2 ; 3} et en même temps {2 ; 3} ⊂ a et {2 ; 3} ⊂ b, alors on a certainement aussi ∅ ⊂ a et ∅ ⊂ b. Cela découle de la transitivité.

Pour finir, définissons les cônes supérieur et inférieur pour un ensemble entier, et pas seulement pour une paire d’éléments. Soit un ensemble M et une partie A ⊂ M dont on veut calculer les cônes supérieur et inférieur. Alors :

$$\begin{array}{rcl}H(A)& =& \{x|\mathrm{\forall }a\in A:x\ge a\}\\ D(A)& =& \{x|\mathrm{\forall }a\in A:x\le a\}\end{array}$$

Borne supérieure et borne inférieure

Grâce aux cônes, on peut facilement définir la borne inférieure et la borne supérieure. Si on a un ensemble M et un élément a ∈ M, la borne supérieure et la borne inférieure de l’élément a sont de nouveau cet élément a lui-même.

Pour trouver la borne supérieure de deux éléments a et b de M, il faut en revanche procéder autrement. La borne supérieure de a et b, notée a ∨ b ou sup(a ; b), est égale au plus petit élément du cône supérieur de a et b. On calcule donc tous les éléments supérieurs ou égaux à a et à b, et parmi eux on prend le plus petit élément. Pas un élément minimal, le plus petit. En général, un plus petit élément n’existe pas forcément, donc la borne supérieure n’existe pas forcément non plus.

Pour la borne inférieure, on trouve d’abord le cône inférieur des deux éléments, puis on y cherche le plus grand élément.

Exemple : nous savons déjà que le cône supérieur des nombres 3 et 5 est l’ensemble {5 ; 6 ; 7 ; …}. Son plus petit élément est égal à cinq. Donc sup(3 ; 5) = 5.

Nous savons aussi que le cône inférieur des ensembles a = {1 ; 2 ; 3} et b = {2 ; 3 ; 4} est l’ensemble de toutes les parties de {2 ; 3}. Ce sont les ensembles {2 ; 3}, {2}, {3} et ∅, et le plus grand est justement {2 ; 3}. Cet ensemble est donc la borne inférieure de a et b. On note a ∧ b = {2 ; 3} ou inf(a ; b) = {2 ; 3}.

Définition d’un treillis

Un treillis S est un ensemble ordonné dans lequel, pour deux éléments quelconques a, b ∈ S, il existe une borne supérieure et une borne inférieure, qui appartiennent toutes deux à l’ensemble S. On peut donc dire qu’un ensemble ordonné S est un treillis si

$$\mathrm{\forall }a,b\in S:sup(a;b)\in S\text{et}inf(a;b)\in S$$

Un exemple simple de treillis est l’ensemble des nombres réels muni de l’ordre usuel. On a sup(a ; b) = max(a ; b) et inf(a ; b) = min(a ; b), qui sont toujours des nombres réels.

Un ensemble d’ensembles ordonné par l’inclusion, comme nous l’avons vu plus haut, est aussi un treillis. On a sup(a ; b) = a ∪ b et inf(a ; b) = a ∩ b. Ce sont de nouveau des ensembles de ce système.

Si on prend pour système d’ensembles S toutes les parties à deux éléments de ℕ^* (par exemple {1 ; 2}, {7 ; 19}, …), alors cet ensemble n’est pas un treillis, car par exemple sup({1 ; 2} ; {3 ; 4}) = {1 ; 2 ; 3 ; 4} et l’ensemble {1 ; 2 ; 3 ; 4} n’est pas un élément de l’ensemble des parties à deux éléments de ℕ^*.