Binarne relacije

Izvor: Wikipedija
Skoči na: orijentacija, traži

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 (manji od) 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 zato 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);
  • simetrična: ako (ako je u relaciji sa onda i mora biti u relaciji sa );
  • tranzitivna: ako (ako je u relaciji sa , i u relaciji sa onda je i u relaciji sa );
  • antisimetrična: ako (ako je u relaciji sa i u relaciji sa , onda je ;

Relacija ekvivalencije[uredi VE | uredi]

Binarna relacija je relacije ekvivalencije, ako je refleksivna, simetrična i tranzitivna.

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

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.