Binarne relacije

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

Primjer:

Neka je S neprazan skup, [math]\displaystyle{ S }[/math] = {1,2,3,4}, Kartezijev produkt skupa S sa samim sobom je:

[math]\displaystyle{ SxS }[/math] = {{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 [math]\displaystyle{ \lt }[/math] ("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 [math]\displaystyle{ x \mathcal{R} y }[/math], tj. u ovom primjeru x<y:

[math]\displaystyle{ \mathcal{R} \subseteq S \times S }[/math] = {{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 [math]\displaystyle{ \mathcal{R} \subseteq S \times S }[/math] 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 [math]\displaystyle{ \mathcal{R} \subseteq S \times S }[/math] 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 [math]\displaystyle{ x\mathcal{R} x,\forall x \in S }[/math] (svaki element je u relaciji sam sa sobom);
antirefleksivna (irefleksivna): ako je [math]\displaystyle{ \neg(x\mathcal{R} x) ,\forall x \in S }[/math] (niti jedan element ne smije biti u relaciji sam sa sobom);
simetrična: ako [math]\displaystyle{ x\mathcal{R} y \Rightarrow y\mathcal{R} x, \forall x,y\in S }[/math] (ako je [math]\displaystyle{ x }[/math] u relaciji sa [math]\displaystyle{ y }[/math] onda i [math]\displaystyle{ y }[/math] mora biti u relaciji sa [math]\displaystyle{ x }[/math]);
antisimetrična: ako [math]\displaystyle{ (x\mathcal R y) \land (y\mathcal R x) \Rightarrow x=y }[/math] (ako je [math]\displaystyle{ x }[/math] u relaciji sa [math]\displaystyle{ y }[/math] i [math]\displaystyle{ y }[/math] u relaciji sa [math]\displaystyle{ x }[/math], onda je [math]\displaystyle{ x = y }[/math]);
asimetrična: ako [math]\displaystyle{ x\mathcal{R} y \Rightarrow \neg (y\mathcal{R} x) , \forall x,y\in S }[/math] (ako je [math]\displaystyle{ x }[/math] u relaciji sa [math]\displaystyle{ y }[/math] onda [math]\displaystyle{ y }[/math] ne smije biti u relaciji sa [math]\displaystyle{ x }[/math]);
tranzitivna: ako [math]\displaystyle{ (x\mathcal R y) \land (y\mathcal R z) \Rightarrow x\mathcal R z }[/math] (ako je [math]\displaystyle{ x }[/math] u relaciji sa [math]\displaystyle{ y }[/math], i [math]\displaystyle{ y }[/math] u relaciji sa [math]\displaystyle{ z }[/math] onda je [math]\displaystyle{ x }[/math] i u relaciji sa [math]\displaystyle{ z }[/math]);

Relacija ekvivalencije

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.

Parcijalni uređaj i totalni uređaj

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 [math]\displaystyle{ (\forall x,y \in S) }[/math], [math]\displaystyle{ (x\mathcal R y \lor y\mathcal R x) }[/math], za relaciju kažemo da je totalni uređaj, a navedeno svojstvo relacije nazivamo usporedivost ili potpunost.

Izvori

Prirodoslovno matematički fakultet u Zagrebu Mladen Vuković: Neki osnovni pojmovi teorije skupova, 2004. str. 3 (pristupljeno 8. listopada 2019.)