Chapitre 1 • Structures ordonnées Applications des treillis
8
Ces díviseurs forment un treillis dont le dia gramme de Hasse est donné par la figure 1.4.
La b.s. de deux élé ments quel conques est leur p.p.c.m ; la b.i., leur p.g.c.d. Ainsi :
5 ~ 6 5 5 3 6 5 30 et 5 ` 6 5 1 ; 6 ~ 15 5 2 3 3 3 5 5 30 et 6 ` 15 5 3, etc.
L’élé ment uni ver sel de ce treillis est 30, l’élé ment nul, 1.
D’une manière géné rale N* 5 N 2 506, ordonné par la rela -
tion x | y (x divise y), pré sente une struc ture de treillis infini.
L’élé ment nul est tou jours 1 ; il n’y a pas d’élé ment uni ver sel.
On montre que tout treillis T ayant un nombre fini d’éléments
comporte un élément nul et un élément universel.
b) Un treillis, comportant un élé ment nul et un uni ver sel, que
nous dési gne rons, res pec ti ve ment par n et U, est complémenté
si, à tout élé ment x de T, on peut asso cier au moins un élé ment de T, noté x tel que :
6. x ~ x 5 U et 6r. x ` x 5 n.
Le treillis de la figure 1.4 est complémenté. En effet : 1 ~ 30 5 30, 1 ` 30 5 1 ;
2 ~ 15 5 30, 2 ` 15 5 1 ; 3 ~ 10 5 30, 3 ` 10 5 1 ; 5 ~ 6 5 30, 5 ` 6 5 1. Ainsi
n = 1 est le complément de U = 30 et réciproquement ; de même 3 et 10 sont le complément l’un de l’autre, tout comme 5 et 6.
Pro priété. On a, d’après 4 : x ` 1 x ~ x2 5 x. Or, x ` 1 x ~ x2 5 x ` U 5 x. D’où :
x ` U 5 x.
De même :
x ~ n 5 x.
N.B. Le sys tème d’axiomes (1 à 4), (1r à 4r) n’est pas mini mal; mais il est pra tique
pour le cal cul. On peut, en effet, mon trer que l’absorp tion entraîne l’idempotence.
c) Un treillis est dis tri bu tif lors qu’aux axiomes 1 à 4 et 1r à 4r, s’ajoute le sui vant :
7. x ` 1 y ~ z 2 5 1 x ` y2 ~ 1 x ` z 2 , quels que soient x, y et zPT.
Cet axiome entraîne (cf. Execrcice 1 ci-dessous) :
7r. x ~ 1 y ` z 2 5 1 x ~ y2 ` 1 x ~ z 2 .
Inver se ment, 7r entraîne 7.
Exercices.
1. Soit à démon trer, à par tir des axiomes 1 à 4, 1r à 4r et 7, que :
7r. x ~ 1 y ` z 2 5 1 x ~ y 2 ` 1 x ~ z 2 .
Grâce à 4, on peut écrire le pre mier membre de 7r sous la forme :
3x ~ 1 x ` y2 4 ~ 1 y ` z 2 , en remplaçant x par x ~ 1 x ` y 2 .
Grâce à 2, cette expression est égale à :
x ~ 3 1 x ` y2 ~ 1 y ` z 2 4 (par associativité de ~ ).
et, en vertu de 1r, elle est aussi égale à :
x ~ 3 (y ` x) ~ (y ` z) 4 (par commutativité de ` ).
Figure 1.4
8
Ces díviseurs forment un treillis dont le dia gramme de Hasse est donné par la figure 1.4.
La b.s. de deux élé ments quel conques est leur p.p.c.m ; la b.i., leur p.g.c.d. Ainsi :
5 ~ 6 5 5 3 6 5 30 et 5 ` 6 5 1 ; 6 ~ 15 5 2 3 3 3 5 5 30 et 6 ` 15 5 3, etc.
L’élé ment uni ver sel de ce treillis est 30, l’élé ment nul, 1.
D’une manière géné rale N* 5 N 2 506, ordonné par la rela -
tion x | y (x divise y), pré sente une struc ture de treillis infini.
L’élé ment nul est tou jours 1 ; il n’y a pas d’élé ment uni ver sel.
On montre que tout treillis T ayant un nombre fini d’éléments
comporte un élément nul et un élément universel.
b) Un treillis, comportant un élé ment nul et un uni ver sel, que
nous dési gne rons, res pec ti ve ment par n et U, est complémenté
si, à tout élé ment x de T, on peut asso cier au moins un élé ment de T, noté x tel que :
6. x ~ x 5 U et 6r. x ` x 5 n.
Le treillis de la figure 1.4 est complémenté. En effet : 1 ~ 30 5 30, 1 ` 30 5 1 ;
2 ~ 15 5 30, 2 ` 15 5 1 ; 3 ~ 10 5 30, 3 ` 10 5 1 ; 5 ~ 6 5 30, 5 ` 6 5 1. Ainsi
n = 1 est le complément de U = 30 et réciproquement ; de même 3 et 10 sont le complément l’un de l’autre, tout comme 5 et 6.
Pro priété. On a, d’après 4 : x ` 1 x ~ x2 5 x. Or, x ` 1 x ~ x2 5 x ` U 5 x. D’où :
x ` U 5 x.
De même :
x ~ n 5 x.
N.B. Le sys tème d’axiomes (1 à 4), (1r à 4r) n’est pas mini mal; mais il est pra tique
pour le cal cul. On peut, en effet, mon trer que l’absorp tion entraîne l’idempotence.
c) Un treillis est dis tri bu tif lors qu’aux axiomes 1 à 4 et 1r à 4r, s’ajoute le sui vant :
7. x ` 1 y ~ z 2 5 1 x ` y2 ~ 1 x ` z 2 , quels que soient x, y et zPT.
Cet axiome entraîne (cf. Execrcice 1 ci-dessous) :
7r. x ~ 1 y ` z 2 5 1 x ~ y2 ` 1 x ~ z 2 .
Inver se ment, 7r entraîne 7.
Exercices.
1. Soit à démon trer, à par tir des axiomes 1 à 4, 1r à 4r et 7, que :
7r. x ~ 1 y ` z 2 5 1 x ~ y 2 ` 1 x ~ z 2 .
Grâce à 4, on peut écrire le pre mier membre de 7r sous la forme :
3x ~ 1 x ` y2 4 ~ 1 y ` z 2 , en remplaçant x par x ~ 1 x ` y 2 .
Grâce à 2, cette expression est égale à :
x ~ 3 1 x ` y2 ~ 1 y ` z 2 4 (par associativité de ~ ).
et, en vertu de 1r, elle est aussi égale à :
x ~ 3 (y ` x) ~ (y ` z) 4 (par commutativité de ` ).
Figure 1.4