Chapitre 1 • Structures ordonnées Applications des treillis
2
x
y
z
(x, x) (x, y) (x, z)
( y, x) ( y, y) ( y, z)
( z, x) ( z, y)
(z, z)
x
y
z
Produit cartésien ExE
x
y
z
(x, x)
(x, z)
( y, y)
( z, x)
x
y
z
x
y
z
(x, x) (x, y)
( y, z)
( z, x)
(z, z)
x
y
z
Relation R 1
Relation R 2
On nomme tout natu rel le ment rela tion dia go nale : D 5 5 1 x, x2 ; 1 y, y2 ; 1 z, z 2 6.
Une rela tion est, par défi ni tion, réflexive si elle contient la dia go nale. La rela tion
R 1 , est symé trique, mais elle n’est pas réflexive. Pour qu’une rela tion soit symé
trique, il faut, quels que soient a et b, qu’elle contienne le couple (b, a) si le couple
(a, b) lui appar tient. La rela tion R 2 est anti sy mé trique, mais elle n’est pas réflexive.
Pour qu’une rela tion soit anti sy mé trique, il faut, quels que soient a et b, qu’elle ne
contienne pas le couple (b, a) si le couple (a, b) lui appar tient, sauf si a 5 b, c’està-dire s’il s’agit d’un élé ment de la dia go nale.
x
y
z
x
y
z
t
(x, x) (x, y) (x, z)
(y, z)
(z, z)
(x, x) (x, y)
(x, t)
(y, x) (y, y)
(y, t)
(z, z)
(t, x)
(t, y)
(t, t)
x
y
z
Relation R 4
Relation R 3
Pour qu’une rela tion soit tran si tive, il faut qu’elle contienne (a, g) si elle contient
(a, b) et (b, g), quels que soient a, b, g.
La rela tion R 3 est tran si tive ; elle n’est pas non plus réflexive ; elle est anti sy mé -
trique. La rela tion R 4 est tran si tive ; elle est réflexive ; elle est symé trique.
NB : Le contraire de réflexif, symé trique, tran si tif est, res pec ti ve ment, ir réflexif, asy
mé trique, intran si tif. Une rela tion est ir réflexive si elle ne contient aucun élé ment de D ;
elle est asy mé trique, si elle n’est symé trique pour aucun couple ; elle est intran si tive si
elle n’est tran si tive pour aucune paire de couples ; c’est le cas de la rela tion R 5 .
x
y
z
x
y
z
(x, x) (x, y) (x, z)
( x, y)
( z, x)
( z, x)
( y, z)
( y, z)
x
y
z
x
y
z
Relation R 5
Relation R 6
2
x
y
z
(x, x) (x, y) (x, z)
( y, x) ( y, y) ( y, z)
( z, x) ( z, y)
(z, z)
x
y
z
Produit cartésien ExE
x
y
z
(x, x)
(x, z)
( y, y)
( z, x)
x
y
z
x
y
z
(x, x) (x, y)
( y, z)
( z, x)
(z, z)
x
y
z
Relation R 1
Relation R 2
On nomme tout natu rel le ment rela tion dia go nale : D 5 5 1 x, x2 ; 1 y, y2 ; 1 z, z 2 6.
Une rela tion est, par défi ni tion, réflexive si elle contient la dia go nale. La rela tion
R 1 , est symé trique, mais elle n’est pas réflexive. Pour qu’une rela tion soit symé
trique, il faut, quels que soient a et b, qu’elle contienne le couple (b, a) si le couple
(a, b) lui appar tient. La rela tion R 2 est anti sy mé trique, mais elle n’est pas réflexive.
Pour qu’une rela tion soit anti sy mé trique, il faut, quels que soient a et b, qu’elle ne
contienne pas le couple (b, a) si le couple (a, b) lui appar tient, sauf si a 5 b, c’està-dire s’il s’agit d’un élé ment de la dia go nale.
x
y
z
x
y
z
t
(x, x) (x, y) (x, z)
(y, z)
(z, z)
(x, x) (x, y)
(x, t)
(y, x) (y, y)
(y, t)
(z, z)
(t, x)
(t, y)
(t, t)
x
y
z
Relation R 4
Relation R 3
Pour qu’une rela tion soit tran si tive, il faut qu’elle contienne (a, g) si elle contient
(a, b) et (b, g), quels que soient a, b, g.
La rela tion R 3 est tran si tive ; elle n’est pas non plus réflexive ; elle est anti sy mé -
trique. La rela tion R 4 est tran si tive ; elle est réflexive ; elle est symé trique.
NB : Le contraire de réflexif, symé trique, tran si tif est, res pec ti ve ment, ir réflexif, asy
mé trique, intran si tif. Une rela tion est ir réflexive si elle ne contient aucun élé ment de D ;
elle est asy mé trique, si elle n’est symé trique pour aucun couple ; elle est intran si tive si
elle n’est tran si tive pour aucune paire de couples ; c’est le cas de la rela tion R 5 .
x
y
z
x
y
z
(x, x) (x, y) (x, z)
( x, y)
( z, x)
( z, x)
( y, z)
( y, z)
x
y
z
x
y
z
Relation R 5
Relation R 6