Binarne relacije

Izvor: Wikipedija
Prijeđi na navigaciju Prijeđi na pretraživanje

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: 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 );

Relacija ekvivalencije[uredi VE | uredi]

Binarna relacija je relacije 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).

Parcijalni uređaj i totalni uređaj[uredi VE | uredi]

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.