Релација (математика)

Из Википедије, слободне енциклопедије

У математици, релација је непразан подскуп Декартовог производа скупова.

Дефиниције[уреди]

Релација ρ дужине n је непразан подскуп Декартовог производа n скупова. Када је n = 2 тада говоримо о бинарној релацији, дакле о релацији између елемента x са елементом y, односно о уређеном пару (x, y) из Декартовог производа A\times B. Ако је (x, y)\in\rho тада кажемо да је елемент x\, у релацији са елементом y\, и пишемо x\rho y\,.

За бинарну релацију \rho\subset A\times B могуће је дефинисати следеће изразе:

  • Домен, тј. област дефинисаности \mathcal{D(\rho)}=\{x\in A|(\exists y\in B)x\rho y)\};
  • кодомен, тј. област вредности \mathcal{K(\rho)}=\{y\in B|(\exists x\in A)x\rho y\};
  • инверзна релација \rho ^{-1}=\{(y,x)\};\,
  • комплемент \bar \rho=(A\times B)\backslash\rho;
  • композиција релација \rho\circ\sigma :
ако је \sigma \subset A\times B и \rho \subset B\times C, тада релацију \rho\circ\sigma\subset A\times C, дату са \rho\circ\sigma=\{(x,y)|(\exists z\in B)x\rho z\wedge z\rho y\} називамо композиција релација \rho\, и \sigma\,.

Примери релација[уреди]

Граф релације
  1. Дати су скупови: A=\{ a, b, c \},\; B=\{1, 2, 3\},\, Декартов производ је скуп уређених парова A\times B=\{(a,1),(a,2),(a,3),(b,1),(b,2),(b,3),(c,1),(c,2),(c,3)\},\, а (једна од) релација је \rho=\{(a,1),(a,2),(b,2),(c,2)\},\, на слици десно. Пишемо нпр. (a,2)\in \rho.\, и кажемо уређен пар а, 2 је елемент релације ро, односно читамо, а је у релацији ро са 2.
  2. Релација једнакости бројева. Пишемо и x\rho y\, односно x=y\, и читамо, број х једнак је броју у.
  3. Релација је бити паралелан, у скупу правих. За две праве a,\; b\, кажемо да су паралелне и пишемо a||b\, ако је то једна иста права, или ако су то две праве које леже у истој равни и немају заједничких тачака.
  4. Релација мање или једнако у скупу реалних бројева.

Основне особине[уреди]

Основне четири особине су:

  • Рефлексивност: (\forall x)(x \in X)  x \rho x. Другим речима, дата релација је рефлексивна ако и само ако је сваки елемент у релацији са собом.
  • Симетричност: (\forall x,y) (x,y \in X) \; x\rho y \Rightarrow y\rho x. Другим речима, ако за сваки уређени пар елемената који је у релацији постоји и пар са обрнутим поретком.
  • Антисиметричност: (\forall x,y) (x,y \in X)\; x\rho y \land y\rho x \Rightarrow x=y.\, Другим речима, ако у датој релацији имамо оба поретка једног пара елемената, онда их не можемо имати на начин да то мора бити само један елемент (тај је у релацији сам са собом).
  • Транзитивност: (\forall x,y,z)(x,y,z \in X)\; x\rho y \land y\rho z \Rightarrow x\rho z. Ако је први елемент у релацији са другим, други са трећим, онда мора бити и први са трећим!

Када нека релација има особину рефлексивности, симетричности, антисиметричности, или транзитивности кажемо да је та релација рефлексивна, симетрична, антисиметрична, односно транзитивна.

Релација еквиваленције је она која има све три особине РСТ заједно (Рефлексивност, Симетричност и Транзитивност). Привремено је можемо означавати са "~" тилда.

Класа еквиваленције је мноштво међусобно еквивалентних елемената: C_x=\{y|y~x\}.\,

Количнички скуп је скуп класа еквиваленције.

Релација поретка је она која има особине РАТ (Рефлексивност, Антисиметричност, Транзитивност).

Остале особине[уреди]

Из дефиниција се лако могу добити следећа својства релација:

  • \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}.

Релација \rho\subset A^2 је линеарна или тотална ако важи (\forall x,y\in A)x\rho y\vee y\rho x. Приметите да су линеарне релације обавезно рефлексивне.

Антисиметрична, транзитивна и линеарна релација неког скупа назива се релација линеарног поретка (или тоталног уређења) датог скупа.

Релација предуређења је рефлексивна и транзитивна. Релација квазиуређења је транзитивна релација. Последња два назива појављују се у Теорији друштвеног избора, тј. области математичке економије.

Види још[уреди]