Relacija

1. PREUSMJERI Predložak:Uklopi u

U matematici, relacija je neprazan podskup Descartesovog produkta 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 sa elementom y, odnosno o uređenom paru (x, y) iz Descartesovog proizvoda [math]\displaystyle{ A\times B. }[/math] Ako je [math]\displaystyle{ (x, y)\in\rho }[/math] tada kažemo da je element [math]\displaystyle{ x\, }[/math] u relaciji sa elementom [math]\displaystyle{ y\, }[/math] i pišemo [math]\displaystyle{ x\rho y\, }[/math].

Za binarnu relaciju [math]\displaystyle{ \rho\subset A\times B }[/math] moguće je definirati sljedeće izraze:

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

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

Primjeri relacija

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

Osnovne osobine

Osnovne četiri osobine su:

• Refleksivnost: [math]\displaystyle{ (\forall x) x\rho x. }[/math] Drugim riječima, data relacija je refleksivna ako i samo ako je svaki element u relaciji sa sobom.
• Simetričnost: [math]\displaystyle{ (\forall x,y) \; x\rho y \Rightarrow y\rho x. }[/math] Drugim riječima, za svaki uređeni par elemenata koji je u relaciji postoji i par sa obrnutim poretkom.
• Antisimetričnost: [math]\displaystyle{ (\forall x,y)\; x\rho y \land y\rho x \Rightarrow x=y.\, }[/math] 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: [math]\displaystyle{ (\forall x,y,z)\; x\rho y \land y\rho z \Rightarrow x\rho z. }[/math] Ako je prvi element u relaciji sa drugim, drugi sa trećim, onda mora biti i prvi sa 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: [math]\displaystyle{ C_x=\{y|y~x\}.\, }[/math]

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:

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

Relacija [math]\displaystyle{ \rho\subset A^2 }[/math] je linearna ili totalna ako vrijedi [math]\displaystyle{ (\forall x,y\in A)x\rho y\vee y\rho x. }[/math] 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.