Binarne relacije

Izvor: Wikipedija

[uredi] 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 (a, b) \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;

[uredi] Relacija ekvivalencije

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

[uredi] 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.