Binarne relacije

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 $<$ ("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 $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 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);
• antirefleksivna: ako je $\neg (x{\mathcal {R}}x),\forall x\in S$ (niti jedan element ne smije biti 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$);
• 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$;
• asimetrična: ako$x{\mathcal {R}}y\Rightarrow \neg (y{\mathcal {R}}x),\forall x,y\in S$ (ako je $x$ u relaciji sa $y$ onda $y$ ne smije 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$);

Relacija ekvivalencije

Binarna relacija je relacije 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).

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