1.1 Notions sur les struc tures ordonnées
© Dunod – Toute reproduction non autorisée est un délit.
7
Insistons sur le fait que les élé ments par ti cu liers défi nis en a), b), c), d) et e)
n’existent pas néces sai re ment dans un ensemble par tiel le ment ordonné, ce qui est
illustré par l’exemple ci-dessous.
Exemples. Soit X 5 {1, 2, 3, 5, 10, 20, 30} un ensemble par tiel le ment ordonné par
la rela tion x | y (x divise y). Nous invi tons le lec teur à se repor ter au dia gramme de
Hasse asso cié (Fig. 1.2).
1. Pre nons P 5 {2, 3, 5, 10}. P est inclus dans X
Il existe un majo rant de P : 30, un mino rant : 1, deux élé ments maximaux : 3 et
10, trois élé ments mini maux : 2, 3, 5, ni plus grand élé ment, ni plus petit élé ment
de P. La b.s. de P est 30, la b.i. est 1. X n’admet pas d’élé ment uni ver sel, mais un
élé ment nul : 1.
2. Pre nons main te nant P 5 {2, 5, 10}.
Ρ compte trois majo rants : 10, 20, 30, un mino rant : 1, un élé ment maximal : 10,
deux élé ments mini maux : 2 et 5, un plus grand élé ment : 10, pas de plus petit élé
ment. La borne supé rieure de Ρ est 10, la borne infé rieure est 1.
Pour une par tie réduite à deux élé ments (ou « paire ») {x, y}, d’un ensemble
ordonné, il peut exis ter une borne supé rieure et/ou une borne infé rieure ; la b.s., lors -
qu’elle existe, est notée x ~ y et la b.i. par x ` y.
1.1.4 Treillis
a) On appelle treillis (ou encore lat tis ou ensemble réti culé) un ensemble par tiel le -
ment ordonné dans lequel, pour toute paire d’élé ments, existent une borne supé rieure
(b.s.) et une borne infé rieure (b.i.).
À cette défi ni tion on peut subs ti tuer la défi ni tion axio ma tique sui vante. Soit un
ensemble T, dont les élé ments sont munis de deux lois de compo si tion, ~ et ` , véri
fiant, quels que soient x, y et zPT, les pro prié tés ci- après :
1. x ~ y 5 y ~ x
( commu ta ti vité) 1r. x ` y 5 y ` x
2. x ~ 1 y ~ z 2 5 1 x ~ y2 ~ z (associativité)
2r. x ` 1 y ` z 2 5 1 x ` y2 ` z
3. x ~ x 5 x
( idempotence)
3r. x ` x 5 x
4. x ~ 1 x ` y2 5 x
( absorp tion)
4r. x ` (x ~ y ) 5 x
alors T consti tue un ensemble ordonné par la rela tion a telle que :
5. 3x a y4 équi vaut à 3x ` y4 5 x et équi vaut à 3x ~ y 4 5 y.
On appelle alors T un treillis. On peut aisément démontrer l’équivalence de ces deux
définitions.
Exemple. Consi dé rons, par exemple, les divi seurs de 30 : 1, 2, 3, 5, 6, 10, 15, 30
(ils sont au nombre de 8 car 1 1 1 12 # 1 1 1 12 # 1 1 1 12 5 8 et 30 5 2
1 # 3
1 # 5
1
2 ,
ordon nés par la rela tion x | y (x divise y). Rap pe lons que si, n 5 p
a # q
b # r
g c est la
décom po si tion en pro duit de fac teurs premiers de l’entier n 1 n > 22 , alors n admet
1 a 1 12 1 b 1 12 1 g 1 12 c divi seurs (y compris 1 et n).
© Dunod – Toute reproduction non autorisée est un délit.
7
Insistons sur le fait que les élé ments par ti cu liers défi nis en a), b), c), d) et e)
n’existent pas néces sai re ment dans un ensemble par tiel le ment ordonné, ce qui est
illustré par l’exemple ci-dessous.
Exemples. Soit X 5 {1, 2, 3, 5, 10, 20, 30} un ensemble par tiel le ment ordonné par
la rela tion x | y (x divise y). Nous invi tons le lec teur à se repor ter au dia gramme de
Hasse asso cié (Fig. 1.2).
1. Pre nons P 5 {2, 3, 5, 10}. P est inclus dans X
Il existe un majo rant de P : 30, un mino rant : 1, deux élé ments maximaux : 3 et
10, trois élé ments mini maux : 2, 3, 5, ni plus grand élé ment, ni plus petit élé ment
de P. La b.s. de P est 30, la b.i. est 1. X n’admet pas d’élé ment uni ver sel, mais un
élé ment nul : 1.
2. Pre nons main te nant P 5 {2, 5, 10}.
Ρ compte trois majo rants : 10, 20, 30, un mino rant : 1, un élé ment maximal : 10,
deux élé ments mini maux : 2 et 5, un plus grand élé ment : 10, pas de plus petit élé
ment. La borne supé rieure de Ρ est 10, la borne infé rieure est 1.
Pour une par tie réduite à deux élé ments (ou « paire ») {x, y}, d’un ensemble
ordonné, il peut exis ter une borne supé rieure et/ou une borne infé rieure ; la b.s., lors -
qu’elle existe, est notée x ~ y et la b.i. par x ` y.
1.1.4 Treillis
a) On appelle treillis (ou encore lat tis ou ensemble réti culé) un ensemble par tiel le -
ment ordonné dans lequel, pour toute paire d’élé ments, existent une borne supé rieure
(b.s.) et une borne infé rieure (b.i.).
À cette défi ni tion on peut subs ti tuer la défi ni tion axio ma tique sui vante. Soit un
ensemble T, dont les élé ments sont munis de deux lois de compo si tion, ~ et ` , véri
fiant, quels que soient x, y et zPT, les pro prié tés ci- après :
1. x ~ y 5 y ~ x
( commu ta ti vité) 1r. x ` y 5 y ` x
2. x ~ 1 y ~ z 2 5 1 x ~ y2 ~ z (associativité)
2r. x ` 1 y ` z 2 5 1 x ` y2 ` z
3. x ~ x 5 x
( idempotence)
3r. x ` x 5 x
4. x ~ 1 x ` y2 5 x
( absorp tion)
4r. x ` (x ~ y ) 5 x
alors T consti tue un ensemble ordonné par la rela tion a telle que :
5. 3x a y4 équi vaut à 3x ` y4 5 x et équi vaut à 3x ~ y 4 5 y.
On appelle alors T un treillis. On peut aisément démontrer l’équivalence de ces deux
définitions.
Exemple. Consi dé rons, par exemple, les divi seurs de 30 : 1, 2, 3, 5, 6, 10, 15, 30
(ils sont au nombre de 8 car 1 1 1 12 # 1 1 1 12 # 1 1 1 12 5 8 et 30 5 2
1 # 3
1 # 5
1
2 ,
ordon nés par la rela tion x | y (x divise y). Rap pe lons que si, n 5 p
a # q
b # r
g c est la
décom po si tion en pro duit de fac teurs premiers de l’entier n 1 n > 22 , alors n admet
1 a 1 12 1 b 1 12 1 g 1 12 c divi seurs (y compris 1 et n).