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.