1.1 Notions sur les struc tures ordonnées
© Dunod – Toute reproduction non autorisée est un délit.
3
Il faut se gar der de confondre ces qua li fi ca tifs avec non réflexif (il y a des élé
ments dans la dia go nale, mais non tous), non symé trique (il existe des élé ments
symé triques, mais tous ne le sont pas), non tran si tif (la tran si ti vité existe pour cer
tains couples, mais pas pour d’autres). La rela tion R 6 est, à la fois, non réflexive, non
symé trique et non tran si tive.
1.1.2 Préordre. Équi va lence. Ordre
a) une rela tion réflexive et tran si tive est une rela tion de préordre.
Exemple. Le Cri terium des cham pions a donné les résul tats sui vants (tableau 1.1) :
1
er
Camille
4
e
Ernest
Anatole
Désiré
5
e
Bernard
2
e
ex aequo {
A
B
C
D
E
(A, A) (A, B)
(A, D) (A, E)
(E, B)
(E, E)
(D, A) (D, B)
(D, D) (D, E)
(C, A) (C, B) (C, C) (C, D) (C, E)
(B, B)
A
B
C
D
E
T ableau 1.1
Tableau 1.2: relaTion R
Classons- les d’après la rela tion R « avoir obtenu un rang meilleur ou aussi bon
que ». Dans le tableau 1.2, le couple (A, B) signi fie qu’Anatole a obtenu un rang
meilleur ou aussi bon que Bernard : A s B. La rela tion est évi dem ment réflexive,
puis qu’elle contient la dia go nale ; elle est aussi tran si tive puisque si X a obtenu un
rang meilleur ou aussi bon que Y et Y un rang meilleur ou aussi bon que Z, X a évi
dem ment un rang meilleur ou aussi bon que Z : 3X s Y et Y s Z 4 entraîne 3X s Z 4.
Mais elle n’est pas symé trique, bien que A s D et D a A ; par exemple, A s E,
mais E O A ; elle n’est pas non plus anti sy mé trique, puisque 3A s D et D s A]
n’entraîne pas 3A ; D 4 (Anatole ne peut pas être confondu avec Dési ré).
b) une rela tion réflexive,tran si tive et symé trique est une rela tion d’équi va lence.
Par exemple, envi sa geons deux groupes de droites paral lèles : d’une part A || C ;
d’autre part B || D || E. Le tableau 1.3 ci-dessous cor res pond à la rela tion || : « être
paral lèle à ou confondu avec ». Le tableau 1.4, résulte de la par tition des droites en
classes d’équi va lence. Il y a deux classes {A, C} et {B, D, E}.
À titre d’exemple, repre nons main te nant le clas se ment du Cri terium des cham pions
dans l’ordre d’arri vée (A et D étant indif fé rents). L’exis tence d’une rela tion l’équi va lence
(donc réflexive, symé trique et tran si tive), « avoir le même rang que », est mani feste pour
A et D. Si l’on fait le quo tient du préordre par cette rela tion d’équi va lence, on trouve en
réa lité quatre classes ; {C}, {A, D}, {E}, {B} et, désor mais : C s 5A, D6 s 5E6 s 5B6,
la rela tion stricte S ayant le sens : « avoir un meilleur rang que ».
Posons 5C6 5 a, 5A, D6 5 b, 5E6 5 g et 5B6 5 d ; si l’on repré sente par le
tableau 1.6 la rela tion sur l’ensemble {a, b, g, d}, on constate qu’elle est ir réflexive,
asy mé trique ; en revanche, elle est tran si tive.
© Dunod – Toute reproduction non autorisée est un délit.
3
Il faut se gar der de confondre ces qua li fi ca tifs avec non réflexif (il y a des élé
ments dans la dia go nale, mais non tous), non symé trique (il existe des élé ments
symé triques, mais tous ne le sont pas), non tran si tif (la tran si ti vité existe pour cer
tains couples, mais pas pour d’autres). La rela tion R 6 est, à la fois, non réflexive, non
symé trique et non tran si tive.
1.1.2 Préordre. Équi va lence. Ordre
a) une rela tion réflexive et tran si tive est une rela tion de préordre.
Exemple. Le Cri terium des cham pions a donné les résul tats sui vants (tableau 1.1) :
1
er
Camille
4
e
Ernest
Anatole
Désiré
5
e
Bernard
2
e
ex aequo {
A
B
C
D
E
(A, A) (A, B)
(A, D) (A, E)
(E, B)
(E, E)
(D, A) (D, B)
(D, D) (D, E)
(C, A) (C, B) (C, C) (C, D) (C, E)
(B, B)
A
B
C
D
E
T ableau 1.1
Tableau 1.2: relaTion R
Classons- les d’après la rela tion R « avoir obtenu un rang meilleur ou aussi bon
que ». Dans le tableau 1.2, le couple (A, B) signi fie qu’Anatole a obtenu un rang
meilleur ou aussi bon que Bernard : A s B. La rela tion est évi dem ment réflexive,
puis qu’elle contient la dia go nale ; elle est aussi tran si tive puisque si X a obtenu un
rang meilleur ou aussi bon que Y et Y un rang meilleur ou aussi bon que Z, X a évi
dem ment un rang meilleur ou aussi bon que Z : 3X s Y et Y s Z 4 entraîne 3X s Z 4.
Mais elle n’est pas symé trique, bien que A s D et D a A ; par exemple, A s E,
mais E O A ; elle n’est pas non plus anti sy mé trique, puisque 3A s D et D s A]
n’entraîne pas 3A ; D 4 (Anatole ne peut pas être confondu avec Dési ré).
b) une rela tion réflexive,tran si tive et symé trique est une rela tion d’équi va lence.
Par exemple, envi sa geons deux groupes de droites paral lèles : d’une part A || C ;
d’autre part B || D || E. Le tableau 1.3 ci-dessous cor res pond à la rela tion || : « être
paral lèle à ou confondu avec ». Le tableau 1.4, résulte de la par tition des droites en
classes d’équi va lence. Il y a deux classes {A, C} et {B, D, E}.
À titre d’exemple, repre nons main te nant le clas se ment du Cri terium des cham pions
dans l’ordre d’arri vée (A et D étant indif fé rents). L’exis tence d’une rela tion l’équi va lence
(donc réflexive, symé trique et tran si tive), « avoir le même rang que », est mani feste pour
A et D. Si l’on fait le quo tient du préordre par cette rela tion d’équi va lence, on trouve en
réa lité quatre classes ; {C}, {A, D}, {E}, {B} et, désor mais : C s 5A, D6 s 5E6 s 5B6,
la rela tion stricte S ayant le sens : « avoir un meilleur rang que ».
Posons 5C6 5 a, 5A, D6 5 b, 5E6 5 g et 5B6 5 d ; si l’on repré sente par le
tableau 1.6 la rela tion sur l’ensemble {a, b, g, d}, on constate qu’elle est ir réflexive,
asy mé trique ; en revanche, elle est tran si tive.