treillis (suite)
Treillis de Boole
C’est un treillis distributif et complémenté. Un treillis est distributif et complémenté, z = ∅ et u = E, si A ∈ , A′ = ∁E A, car A ∩ A′ = ∅ et A ∪ A′ = E ; est un treillis de Boole. On a : ∁ (A ∪ B) = ∁ A ∩ ∁ B, et la relation duale
∁ (A ∩ B) = ∁ A ∪ ∁ B.
De façon générale, (a ∧ b)′ = a′ ∨ b′ et (a ∨ b)′ = a′ ∧ b′.
Un treillis de Boole peut être structuré en anneau commutatif et idempotent avec élément unité.
En posant a + b = (a′ ∧ b′) ∨ (a ∧ b), on définit l’addition de l’anneau ; d’ailleurs, à l’aide de la distributivité, on a a + b = (a′ ∨ b) ∧ (a ∨ b′).
Cette addition est associative, car
(a + b) + c =
= (a ∧ b ∧ c) ∨ (a′ ∧ b′ ∧ c) ∨ (a′ ∧ b ∧ c′) ∨ (a ∧ b′ ∧ c′),
qui est symétrique en a, b et c, d’où (a + b) + c = a + (b + c). D’autre part, a + u = a et a + a = a′ ∨ a = u ; donc, l’élément universel u est neutre pour l’addition, et l’élément a est son propre opposé. D’où le groupe additif abélien.
En posant a · b = a ∨ b, on définit la multiplication. Elle est associative, commutative et idempotente ; elle admet z comme élément unité puisque a · z = a ∨ z = a. Elle est distributive par rapport à l’addition, car
(a + b) c = (a′ ∨ b ∨ c) ∧ (a ∨ b′ ∨ c) = ac + bc.
Dans le treillis , les opérations définies ci-dessus sont la somme symétrique et l’union : A et B étant deux parties de l’ensemble E, la somme A + B est formée des éléments de l’ensemble E appartenant à la fois à A et à B, ou n’appartenant ni à A ni à B. On peut aussi choisir la différence symétrique et l’intersection :
A ∆ B = (A ∩ B′) ∪ (A′ ∩ B) et A ∩ B,
ou, dans un treillis quelconque, a + b = (a′ ∧ b) ∨ (a ∧ b′) et a · b = a ∧ b.
Inversement, tout anneau idempotent avec élément unité peut être structuré en treillis de Boole de manière que l’anneau de Boole associé par la construction ci-dessus coïncide avec l’anneau initial. En effet, tout anneau idempotent est commutatif et de caractéristique deux, c’est-à-dire que 2 a = 0, quel que soit l’élément a de l’anneau. D’autre part, on définit
a ∨ b = ab et a ∧ b = a + b + ab.
On obtient alors un treillis distributif à élément nul z = 1, élément unité de l’anneau, et à élément universel u = 0. Enfin, a′ = 1 + a.
L’étude des treillis — qui se poursuit, en particulier, par celle des treillis modulaires et des treillis géométriques — donne lieu à de nombreuses applications.
E. S.
➙ Anneau / Ensemble / Relation binaire.
M. L. Dubreuil-Jacotin, L. Lesieur et R. Croisot, Leçons sur la théorie des treillis, des structures algébriques ordonnées et des treillis géométriques (Gauthier-Villars, 1953). / G. Szasz, Introduction to Lattice Theory (en hongrois, Budapest, 1959 ; trad. angl., New York, 1963). / P. Dubreuil et M. L. Dubreuil-Jacotin, Leçons d’algèbre moderne (Dunod, 1961). / D. E. Rutherford, Introduction to Lattice Theory (New York, 1965). / M. Barbut et B. Monjardet, Ordre et classification. Algèbre et combinatoire (Hachette, 1970 ; 2 vol.).