Binarna relacija na skupu
je svaki podskup
(podskup Kartezijevog produkta skupa
sa samim sobom). Ako je uređeni par
onda kažemo da je
u relaciji
s
, i pišemo
ili
.
Primjer:
Neka je S neprazan skup,
= {1,2,3,4}, Kartezijev produkt skupa S sa samim sobom je:
= ((1,1},{1,2},{1,3},{1,4},{2,1},{2,2},{2,3},{2,4},{3,1},{3,2},{3,3},{3,4},{4,1},{4,2},{4,3},{4,4))
Binarna relacija
("uobičajena" relacija biti manji od nasljeđena iz skupa realnih brojeva) na skupu SxS je onaj podskup skupa SxS za kojeg vrijedi da je
, tj. u ovom primjeru x<y:
= ((1,2},{1,3},{1,4},{2,3},{2,4},{3,4))
Ova relacija nije refleksivna jer za niti jedan uređeni par ne vrijedi da je x<x (x manji od samog sebe),
npr. da bi relacija bila refleksivna za (1,2) trebao bi postojati element skupa
oblika (1,1).
Također nije simetrična jer za niti jedan uređeni par ne vrijedi da je y<x, ako vrijedi da je x<y
npr. ne postoji element
za (2,3) oblika (3,2)
Ova relacija je tranzitivna jer za x<y i y<z vrijedi da je x<z
npr. za (1,2) i (2,3) postoji element (1,3)
Nije antisimetrična jer ne vrijedi x<y i y<x iz čega bi slijedilo da je x=y.
Binarna relacija može biti:
- refleksivna: ako je
(svaki element je u relaciji sam sa sobom);
- antirefleksivna (irefleksivna): ako je
(niti jedan element ne smije biti u relaciji sam sa sobom);
- simetrična: ako
(ako je
u relaciji sa
onda i
mora biti u relaciji sa
);
- antisimetrična: ako
(ako je
u relaciji sa
i
u relaciji sa
, onda je
);
- asimetrična: ako
(ako je
u relaciji sa
onda
ne smije biti u relaciji sa
);
- tranzitivna: ako
(ako je
u relaciji sa
, i
u relaciji sa
onda je
i u relaciji sa
);
Binarna relacija je relacija ekvivalencije, ako je refleksivna, simetrična i tranzitivna.
U slučaju kada se domena relacije podudara sa skupom na kojem je relacija zadana, dovoljan uvjet da ona bude relacija ekvivalencije je da bude simetrična i tranzitivna (refleksivnost će slijediti iz spomenutih svojstava). Vidi klasa ekvivalencije.
Binarna relacija je (strogi) parcijalni uređaj ako je antirefleksivna i tranzitivna. Ako dodatno dopustimo jednakost elemenata uz tako definiranu relaciju, novonastala relacija naziva se refleksivna relacija parcijalnog uređaja, relacija koja je refleksivna, tranzitivna i antisimetrična.
Ako dodatno vrijedi i
,
, za relaciju kažemo da je totalni uređaj, a navedeno svojstvo relacije nazivamo usporedivost ili potpunost.