Binarne relacije

Binarna relacija na skupu $S$ je svaki podskup $ℛ\subseteq S\times S$ (podskup Kartezijevog produkta skupa $S$ sa samim sobom). Ako je uređeni par $(x,y)\in ℛ$ onda kažemo da je $x$ u relaciji $ℛ$ s $y$, i pišemo $xℛy$ ili $ℛ(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ℛy$, tj. u ovom primjeru x<y:

$ℛ\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 $ℛ\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 $ℛ\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ℛx,\mathrm{\forall }x\in S$ (svaki element je u relaciji sam sa sobom);
• antirefleksivna (irefleksivna): ako je $\mathrm{\neg }(xℛx),\mathrm{\forall }x\in S$ (niti jedan element ne smije biti u relaciji sam sa sobom);
• simetrična: ako $xℛy\Rightarrow yℛx,\mathrm{\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ℛy)\wedge (yℛ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ℛy\Rightarrow \mathrm{\neg }(yℛx),\mathrm{\forall }x,y\in S$ (ako je $x$ u relaciji sa $y$ onda $y$ ne smije biti u relaciji sa $x$);
• tranzitivna: ako $(xℛy)\wedge (yℛz)\Rightarrow xℛ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 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 $(\mathrm{\forall }x,y\in S)$, $(xℛy\vee yℛx)$, za relaciju kažemo da je totalni uređaj, a navedeno svojstvo relacije nazivamo usporedivost ili potpunost.

Izvori

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