treillis (suite)
Définitions et propriétés générales
Un inf demi-treillis (resp. sup) est un ensemble ordonné dans lequel tout couple d’éléments admet un plus grand minorant (resp. plus petit majorant).
Un treillis est donc un ensemble ordonné qui est à la fois un inf et un sup demi-treillis. Le supremum (resp. infimum) est aussi appelé borne supérieure (resp. inférieure).
Dans un sup demi-treillis (resp. inf), tout sous-ensemble fini admet un plus petit majorant (resp. plus grand minorant). En effet, si a1, a2, ..., an sont n éléments d’un sup demi-treillis E, les éléments a1 et a2 ont un plus petit majorant. Si les éléments a1, a2, ..., an–1 ont un plus petit majorant b, b et an ont un supremum c qui majore a1, a2, ..., an. Si m est un majorant commun aux éléments a1, a2, ..., an, m majore a1, a2, ..., an–1, donc majore b, donc b et an et par suite c ; c est bien le plus petit majorant de a1, a2, ..., an.
Un sup demi-treillis (resp. inf) est complet si toute partie y admet un plus petit majorant (resp. plus grand minorant). Un treillis complet est à la fois un inf demi-treillis complet et un sup demi-treillis complet. Le treillis 
est complet.
Dans un treillis, les deux opérations ou lois de composition internes qui à deux éléments a et b font correspondre leur infimum, a ∧ b, et leur supremum, a ∨ b, possèdent les propriétés suivantes, quels que soient les éléments x, y et z du treillis.
Toutes ces propriétés résultent de la définition du supremum et de l’infimum. Ce sont des propriétés algébriques, donc susceptibles de calculs, ce qui facilite l’étude des treillis. Il est donc important de savoir, en partant d’un ensemble E muni de deux lois de composition internes vérifiant les axiomes ci-dessus, s’il est possible de définir algébriquement un treillis.
Définition algébrique d’un treillis
Si E est un ensemble muni de deux lois de composition internes, notées ⊤ et ⎷, idempotentes, commutatives, associatives et liées par la loi d’absorption, on peut, à l’aide de l’une des deux lois, définir deux relations d’ordre opposées, par un choix arbitraire. L’une des deux lois définira l’infimum et l’autre le supremum, ou inversement, suivant l’ordre adopté. En effet, on peut définir dans l’ensemble E la relation, notée 
, « inférieur ou égal » par
Comme ⊤ est idempotente, a ⊤ a = a ou a a (réflexivité). De plus, si a b et b a, a ⊤ b = a, b ⊤ a = b ; mais comme ⊤ est commutative, a ⊤ b = b ⊤ a = a = b (antisymétrie). Enfin, a b et b c ou a ⊤ b = a et b ⊤ c = b entraînent
(a ⊤ b) ⊤ c = a ⊤ c = a ⊤ (b ⊤ c) = a ⊤ b = a,
d’où a c (transitivité). On définit bien ainsi une relation d’ordre. De plus, a ⊤ b b, puisque
(a ⊤ b) ⊤ b = a ⊤ (b ⊤ b) =
= a ⊤ b,
et a ⊤ b a, puisque
(a ⊤ b) ⊤ a = a ⊤ (b ⊤ a) = a ⊤ (a ⊤ b) = (a ⊤ a) ⊤ b = a ⊤ b ;
donc a ⊤ b est un minorant pour a et b. Enfin, si m est tel que m a et m b, c’est-à-dire m ⊤ a = m et m ⊤ b = m,
m ⊤ (a ⊤ b) = (m ⊤ a) ⊤ b = m ⊤ b = m.
Donc a ⊤ b est le plus grand minorant de a et b.
On définit donc dans E une structure d’inf demi-treillis où la borne inférieure de a et b est a ∧ b = a ⊤ b. À partir de la loi ⊤, on peut définir l’ordre opposé, ou dual, du précédent : a b ⇔ a ⊤ b = b. De plus, le vocabulaire utilisé, « inférieur ou égal à », « plus grand minorant », peut être remplacé, quel que soit l’ordre adopté, par le vocabulaire dual.
D’autre part, on obtient un sup demi-treillis. En effet, a ⊤ (a ⎷ b) = a d’après la loi d’absorption ; donc a a ⎷ b. De même, b ⊤ (b ⎷ a) = b = b ⊤ (a ⎷ b) ; d’où b a ⎷ b. Ainsi, a ⎷ b est un majorant pour a et b. De plus, si a ⊤ b = a, d’après la loi d’absorption, a ⎷ b = (a ⊤ b) ⎷ b = b ⎷ (b ⊤ a) = b, et inversement a ⎷ b = b entraîne a ⊤ b = a ⊤ (a ⎷ b) = a. Par suite, a ⊤ b = a ⇔ a ⎷ b = b, et l’ordre, défini par la loi ⊤, tel que a b ⇔ a ⊤ b = a, peut être défini par la loi ⎷, tel que a b ⇔ a ⎷ b = b. Si, dans ces conditions, m est tel que a m et b m, on a a ⎷ m = m et b ⎷ m = m, d’où
(a ⎷ b) ⎷ m = a ⎷ (b ⎷ m) = a ⎷ m = m,
ce qui montre que a ⎷ b est le plus petit majorant de a et b.
On a donc bien un sup demi-treillis dans lequel la borne supérieure de a et b est a ∨ b = a ⎷ b.
La construction algébrique d’un treillis est un bel exemple de ce qu’on appelle l’algèbre moderne : on part d’êtres mathématiques vérifiant un certain nombre d’axiomes et, des définitions et des axiomes posés, on déduit toutes les conséquences logiques.
Treillis distributif, treillis complémenté
Un treillis distributif est un treillis dans lequel chacune des lois ∧ et ∨, permettant de définir respectivement l’infimum et le supremum de deux éléments quelconques, est distributive par rapport à l’autre :
Ces deux relations ne sont pas indépendantes et elles sont équivalentes : (1) ⇔ (2). Il suffit donc, pour qu’un treillis soit distributif, de postuler l’un ou l’autre des axiomes (1) ou (2). Mais ces axiomes sont indépendants de ceux qui traduisent l’associativité, la commutativité, l’idempotence et la loi d’absorption des deux lois internes d’un treillis. En effet, dans un treillis quelconque, de b b ∨ c et c b ∨ c, on déduit :
d’où (a ∧ b) ∨ (a ∧ c) a ∧ (b ∨ c) ; de même, b ∧ c b et b ∧ c c entraînent
Ainsi, a priori, un treillis n’est pas distributif. est un treillis distributif.
Dans un treillis, l’élément minimum, s’il existe, est appelé élément nul ; l’élément maximum, s’il existe, est appelé élément universel, respectivement notés z et u.
On appelle complément de l’élément a d’un treillis tout élément a′ du treillis tel que
a ∧ a′ = z et a ∨ a′ = u.
Dans un treillis distributif, le complément est unique.
Un treillis complémenté est un treillis à élément nul et élément universel, dans lequel tout élément a au moins un complément.