Binarne relacije

[uredi] Definicija

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:

 = {{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:

 = {{1,2},{1,3},{1,4},{2,3},{2,4},{3,4}}

Ova relacija nije refleksivna zato jer za ni jedan uredeni par ne vrijedi da je x<x (x manji od samog sebe, sto je nemoguce), npr. da bi relacija bila refleksivna za (1,2) trebao bi postojati element skupa $\mathcal{R} \subseteq S \times S$ oblika (1,1) sto ne postoji.

Takoder nije simetricna jer za ni jedan uredeni 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 antisimetricna zato jer ne vrijedi x<y i y<x iz cega bi sljedilo 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$ ;