Binarne relacije

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

Binarna relacija na skupu S je svaki podskup \mathcal{R} \subseteq S \times S (podskup Kartezijevog produkta skupa S sa samim sobom). Ako je uređeni par (x, y) \in \mathcal{R} onda kažemo da je x u relaciji \mathcal{R} s y, i pišemo x \mathcal{R} y ili \mathcal{R}(x, y).

Primjer:

Neka je S neprazan skup, S = {1,2,3,4}, Kartezijev produkt skupa S sa samim sobom je:

SxS = {{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 x \mathcal{R} y, tj. u ovom primjeru x<y:

\mathcal{R} \subseteq S \times S = {{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 \mathcal{R} \subseteq S \times S 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 \mathcal{R} \subseteq S \times S 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 x\mathcal{R} x,\forall x \in S (svaki element je u relaciji sam sa sobom);
  • simetrična: ako x\mathcal{R} y \Rightarrow y\mathcal{R} x, \forall x,y \in S (ako je x u relaciji sa y onda i y mora biti u relaciji sa x);
  • tranzitivna: ako (x\mathcal R y) \land (y\mathcal R z) \Rightarrow x\mathcal R z (ako je x u relaciji sa y, i y u relaciji sa z onda je x i u relaciji sa z);
  • antisimetrična: ako (x\mathcal R y) \land (y\mathcal R x) \Rightarrow x=y (ako je x u relaciji sa y i y u relaciji sa x, onda je x = y;

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 (\forall x,y \in S), (x\mathcal R y \lor y\mathcal R x), za relaciju kažemo da je totalni uređaj.