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)$.

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.