Binarne relacije
Izvor: Wikipedija
[uredi] Definicija
Binarna relacija na skupu S je svaki podskup (podskup Kartezijevog produkta skupa S sa samim sobom). Ako je uređeni par
onda kažemo da je x u relaciji
s y, i pišemo
ili
.
Binarna relacija može biti:
- refleksivna: ako je
(svaki element je u relaciji sam sa sobom);
- simetrična: ako
(ako je x u relaciji sa y onda i y mora biti u relaciji sa x);
- tranzitivna: ako
(ako je x u relaciji sa y, i y u relaciji sa z onda je x i u relaciji sa z);
- antisimetrična: ako
(ako je x u relaciji sa y i y u relaciji sa x, onda je x = y;
[uredi] Relacija ekvivalencije
Binarna relacija je relacije ekvivalencije ako je refleksivna, simetrična i tranzitivna.
[uredi] Parcijalni uređaj i totalni uređaj
Binarna relacija je parcijalni uređaj ako je refleksivna, antisimetrična i tranzitivna.
Ako dodatno vrijedi i ,
, za relaciju kažemo da je totalni uređaj.