Binarne relacije

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:
$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:
$SxS$ = {{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 SxS 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 SxS 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$;

Relacija ekvivalencije

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

Parcijalni uređaj i totalni uređaj

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.