Una relazione  definita in
S ´ S = S2 si dice
binaria in S.
Se x, y sono elementi che stanno nella relazione
 si scrive xÂy
e si legge " x è in relazione Â
con y", mentre si scrive xÂy
per indicare che x non è in relazione
 con y.
Ricordiamo che una relazione Â
è un sottoinsieme di S2 e quindi
gli elementi di  sono le
coppie ordinate di S2 (x,y) tali che xÂy.
Esempio 1.- Sia
S = {1, 2, 3, 4, 5}. Costruiamo il prodotto cartesiano S2
e poi la relazione
xÂy
se e sole se x +
y £ 5.
Il prodotto cartesiano S2 è il seguente
insieme:
S2 = { (1,1),
(2,1), (3,1), (4,1), (5,1), (1,2), (2,2), (3,2), ( 4,2),
(5,2), (1,3), (2,3), (3,3), (4,3),
(5,3), (1,4), (2,4), (3,4), (4,4), (5,4), (1,5), (2,5),
(3,5), (4,5), (5,5)}
|
Prodotto cartesiano di S2 |
| |
1 |
2 |
3 |
4 |
5 |
| 1 |
(1,1) |
(1,2) |
(1,3) |
(1,4) |
(1,5) |
| 2 |
(2,1) |
(2,2) |
(2,3) |
(2,4) |
(2,5) |
| 3 |
(3,1) |
(3,2) |
(3,3) |
(3,4) |
(3,5) |
| 4 |
(4,1) |
(4,2) |
(4,3) |
(4,4) |
(4,5) |
| 5 |
(5,1) |
(5,2) |
(5,3) |
(5,4) |
(5,5) |
La relazione è invece il sottoinsieme:
 = {
(1,1),
(2,1),
(3,1),
(4,1),
(1,2),
(2,2),
(3,2),
(1,3),
(2,3),
(1,4) }Ì
S2
formato dalle coppie (x, y) la cui somma è minore
o uguale a 5.
Esempio 2.-
Sono esempi di relazioni binarie la relazione di
uguaglianza tra elementi di uno stesso insieme; la
relazione di perpendicolarità (o di parallelismo) tra
rette del piano, la relazione di similitudine tra
triangoli del piano.
Proprietà di una relazione
Una relazione binaria Â
definita in
S può essere:
Riflessiva
x  x
"xÎ
S
Simmetrica
x  y
Þ
y  x
Transitiva
( x  y
e y  z
) Þ
y  z
Asimmetrica
( x  y
e y  x
) Þ
x
= y
Antiriflessiva
x  x
" x Î
S
Antisimmetrica
( x  y
e y ¹ x
) Þ
y Â
x
Esempio 3.-
Dato l'insieme S = {0, 1} e la relazione Â
= {(0,0), (0,1), (1,1)}, verificare che Â
è riflessiva, transitiva, asimmetrica, ma non
simmetrica.
Esempio 4.-
Dato l'insieme S = {0, 1, 2, 3} e la relazione Â
= S2, verificare che Â
è riflessiva, , simmetrica, transitiva, ma non
asimmetrica.
Provare che l'affermazione è vera qualunque sia
l'insieme S non costituito da un unico elemento.
Esempio 5.-
Dato l'insieme S = {1, 2, 3, 4} e la relazione
Â: " xÂy
Û
x + y
è pari ".
Verificare che Â
è riflessiva, simmetrica, ma non transitiva.
La relazione è:
 = {
(1,1),
(3,1),
(2,4), (2,2),
(1,3),
(4,2), (4,4) }Ì
S2
La relazione  è riflessiva
perché la somma di due numeri uguali pari o dispari è
sempre pari. Ad esempio 1Â1
perché 1+1= 2 e 2 è pari, e lo stesso vale per gli
elementi 2, 3, 4 dell'insieme S.
La relazione
 è simmetrica perché dal
fatto che 1Â3 segue che 3Â1
e da 2Â4 segue che 4Â2.
Non è invece transitiva perché tre elementi distinti di
S non verificano mai la proprietà transitiva: 1Â3
ma addirittura 3 e 4 non sono proprio in relazione.
Esempio 6.-
Dato l'insieme S = {1, 2, 3, 4} e la relazione
Â: " xÂy
Û
x + y
> 4 ".
Verificare che Â
è non riflessiva, simmetrica e non transitiva.
La relazione è:
 = {
(1,4), (2,3), (2,4), (3,2),
(3,3), (3,4), (4,1), (4,2),(4,3),
(4,4) }Ì
S2
La relazione  non è
riflessiva perché non è vero che ogni elemento di S è in
relazione con se stesso. Ad esempio 1 non è in relazione
con 1 perché la somma 1 + 1 = 2 non è maggiore di 4.
La relazione
 è simmetrica perché:
da 2Â3 segue che 3Â2
da 1Â4 segue che 4Â1
da 2Â4 segue che 4Â2.
da 3Â4 segue che 4Â3
La relazione  non è
transitiva perché tre elementi distinti di S non
verificano mai la proprietà transitiva:
( 1Â4 e 4Â2
) non implica che 1 è in relazione con 2, in
quanto 1+2 = 3 e non è maggiore di 4.
Relazione d'equivalenza
Una relazione
Â
binaria in un insieme S
che sia riflessiva, simmetrica e transitiva si dice
relazione d'equivalenza in S
In tal caso se x e y sono
in relazione Â
(xÂy)
si dice che x ed y sono equivalenti. Tutti gli elementi
y di S equivalenti ad x formano un sottoinsieme di S che
si dice classe d'equivalenza e si indica con il simbolo
[x]
Risulta:
xÂy
se e sole se [x] = [y]
