Relacija

Relacija

Predloženo je da se ovaj tekst uklopi u članak Binarne relacije. (Rasprava)

Relacija je matematički pojam koji označava neprazan podskup Kartezijeva produkta dvaju ili više skupova.

Definicije

Relacija ρ dužine n je neprazan podskup Descartesovog produkta n skupova. Kada je n = 2 tada govorimo o binarnoj relaciji, dakle o relaciji između elementa x s elementom y, odnosno o uređenom paru (x, y) iz Descartesovog proizvoda $A\times B.$ Ako je $(x,y)\in \rho$ tada kažemo da je element $x\,$ u relaciji s elementom $y\,$ i pišemo $x\rho y\,$.

Za binarnu relaciju $\rho \subset A\times B$ moguće je definirati sljedeće izraze:

• Domena, tj. područje definicije ${\mathcal {D(\rho )}}=\{x\in A|(\exists y\in B)x\rho y)\};$
• kodomena, tj. područje vrijednosti ${\mathcal {K(\rho )}}=\{y\in B|(\exists x\in A)x\rho y\};$
• inverzna ili transponirana relacija $\rho ^{-1}=\{(y,x)\};\,$
• komplement ${\bar {\rho }}=(A\times B)\backslash \rho ;$
• kompozicija relacija $\rho \circ \sigma :$

ako je $\sigma \subset A\times B$ i $\rho \subset B\times C,$ tada relaciju $\rho \circ \sigma \subset A\times C,$ datu sa $\rho \circ \sigma =\{(x,y)|(\exists z\in B)x\rho z\wedge z\rho y\}$ nazivamo kompozicija relacija $\rho \,$ i $\sigma \,.$

Primjeri relacija

1. Dati su skupovi: $A=\{a,b,c\},\;B=\{1,2,3\},\,$ Descartesov produkt je skup uređenih parova $A\times B=\{(a,1),(a,2),(a,3),(b,1),(b,2),(b,3),(c,1),(c,2),(c,3)\},\,$ a (jedna od) relacija je $\rho =\{(a,1),(a,2),(b,2),(c,2)\},\,$. Pišemo npr. $(a,2)\in \rho .\,$ i kažemo uređen par a, 2 je element relacije ro, odnosno čitamo, a je u relaciji ro s 2.
2. Relacija jednakosti brojeva. Pišemo i $x\rho y\,$ odnosno $x=y\,$ i čitamo, broj h jednak je broju u.
3. Relacija biti paralelan, u skupu pravaca. Za dva pravca $a,\;b\,$ kažemo da su paralelni i pišemo $a||b\,$ ako je to jedan te isti pravac, ili ako su to dva pravca koji leže u istoj ravnini i nemaju zajedničkih točaka.
4. Relacija manje ili jednako u skupu realnih brojeva.

Osnovne osobine

Osnovne četiri osobine su:

• Refleksivnost: $(\forall x)x\rho x.$ Drugim riječima, data relacija je refleksivna ako i samo ako je svaki element u relaciji sa sobom.
• Simetričnost: $(\forall x,y)\;x\rho y\Rightarrow y\rho x.$ Drugim riječima, za svaki uređeni par elemenata koji je u relaciji postoji i par s obrnutim poretkom.
• Antisimetričnost: $(\forall x,y)\;x\rho y\land y\rho x\Rightarrow x=y.\,$ Drugim riječima, ako u datoj relaciji imamo oba poretka jednog para elemenata, onda ih ne možemo imati na način da to mora biti samo jedan element (taj je u relaciji sam sa sobom).
• Tranzitivnost: $(\forall x,y,z)\;x\rho y\land y\rho z\Rightarrow x\rho z.$ Ako je prvi element u relaciji s drugim, drugi s trećim, onda mora biti i prvi s trećim!

Kada neka relacija ima osobinu refleksivnosti, simetričnosti, antisimetričnosti, ili tranzitivnosti kažemo da je ta relacija refleksivna, simetrična, antisimetrična, odnosno tranzitivna.

Relacija ekvivalencije je ona koja ima sve tri osobine RST zajedno (Refleksivnost, Simetričnost i Tranzitivnost). Privremeno je možemo označavati sa "~" tilda.

Klasa ekvivalencije je skup međusobno ekvivalentnih elemenata: $C_{x}=\{y|y~x\}.\,$

Količnički skup je skup klasa ekvivalencije.

Relacija poretka je ona koja ima osobine RAT (Refleksivnost, Antisimetričnost, Tranzitivnost).

Ostale osobine

Iz definicija se lako mogu dobiti sljedeća svojstva relacija:

• ${\mathcal {D}}(\rho )={\mathcal {K}}(\rho ^{-1}),\;{\mathcal {D}}(\rho ^{-1})={\mathcal {K}}(\rho );$
• $\left(\rho ^{-1}\right)^{-1}=\rho ;$
• $\left({\bar {\rho }}\right)^{-1}={\overline {\rho ^{-1}}};$
• $\left(\rho \circ \sigma \right)^{-1}=\sigma ^{-1}\circ \rho ^{-1};$
• $(\rho \cap \sigma )^{-1}=\rho ^{-1}\cap \sigma ^{-1};$
• $(\rho \cup \sigma )^{-1}=\rho ^{-1}\cup \sigma ^{-1}.$

Relacija $\rho \subset A^{2}$ je linearna ili totalna ako vrijedi $(\forall x,y\in A)x\rho y\vee y\rho x.$ Primijetite da su linearne relacije obavezno refleksivne.

Antisimetrična, tranzitivna i linearna relacija nekog skupa naziva se relacija linearnog poretka (ili totalnog uređaja) danog skupa.

Relacija preduređaja je refleksivna i tranzitivna. Relacija kvaziuređaja je tranzitivna relacija. Posljednja dva naziva pojavljuju se u Teoriji društvenog izbora, tj. oblasti matematičke ekonomije.