Relacija

Relacija je matematično orodje, s katerim opišemo odnos med elementi množic. V matematiki se z relacijami srečujemo pogosto, pri čemer so primeri relacij: enakost ($=$), relacija "manjše ali enako" ($\leq$), inkluzija množic ($\subseteq$) in deljivost števil ($|$). Slednji primeri relaciji so dvomestne ali binarne relacije – možno pa je definirati tudi relacije za več elementov iz več različnih množic.

Relacijski graf $R$: $R=\{(1,2),(1,3),(3,4),(4,2)\}$

Formalno je (dvomestna) relacija $R$ iz množice $A$ v množico $B$ podmnožica kartezičnega produkta $A\times B$:

$R\subseteq A\times B$ .

Ponavadi uporabimo zapis $aRb$ ($a$ je v relaciji $R$ z $b$), da označimo dejstvo, da je $(a,b)\in R$.

Zgledi

• Relacija $R=\{(a,b),(b,c),(c,d)(c,c)\}$ v množici $A=\{a,b,c,d\}$.
• Relacija ekvipolence $\sim$
• Relacija urejenosti $\leq$
• Relacija "je večje kot" $>$ v množici naravnih števil $\mathbb {N}$. Relacija $>$ je enaka: $\{(2,1),(3,1),(3,2)...,(4,1),...\}$. Vmesni način zapisa $4>1$ je veliko bolj naraven kot zapis $(4,1)\in \;>$.
• Vsaka funkcija $f:A\to B$ je enočlena relacija, saj je njen graf $\Gamma =\{(a,f(a))\mid a\in A\}$. Pri funkciji vsakemu $a\in A$ priredimo natanko en $f(a)\in B$. Torej ima lastnost enoličnosti. To pri splošni relaciji ni nujno, poleg tega pa je element $a$ lahko povezan z več elementi iz $B$.

Posebne relacije in operacije

• $R$ imenujemo polna relacija, če je $R=A\times B$.

• $R=\emptyset$ se imenuje prazna relacija. Definirana je kot: $\emptyset =\{x\mid x\neq x\}$.
• Relacija identitete ali enakosti $id_{A}$ v množici $A$ je množica urejenih parov z enakima koordinatama: $id_{A}=\{(a,a)\;|\;a\in A\}$.
• $R^{-1}$ imenujemo inverzna relacija. Pridelamo jo tako, da zamenjamo koordinati v vseh parih relacije $R$: $R^{-1}=\{(y,x)\;|\;(x,y)\in R\}$.
• $R^{c}$ je komplement relacije. Definiran je kot množica vseh parov iz $A\times B$, ki niso v relaciji $R$: $R^{c}=\{(x,y)\mid (x,y)\in A\times A\land \neg (xRy)\}$.
• Produkt relacij $R*S$ je definiran z naslednjim opisom: $xR*Sy$ natanko tedaj, ko $\exists z(xRz\land zSy)$.

Definicijsko območje in zaloga vrednosti

Naj bo $R$ relacija v množici $A$. Definicijsko območje relacije $R$, označeno z $D_{R}$, je množica vseh prvih koordinat parov iz relacije $R$. Zaloga vrednosti relacije $R$, označena z $Z_{R}$, je množica vseh drugih koordinat parov iz relacije $R$:

$D_{R}=\{x\mid \exists y\in A\,(xRy)\}$

$Z_{R}=\{y\mid \exists x\in A\,(xRy)\}$

Na primer, za relacijo $R=\{(a,b),(b,c),(c,d),(c,c)\}$ je definicijsko območje $D_{R}=\{a,b,c\}$, zaloga vrednosti pa $Z_{R}=\{b,c,d\}$.

Lastnosti relacij

Naj bo $R$ relacija v množici $A$. Pravimo, da je relacija:

• $R$ refleksivna $\Longleftrightarrow \forall x\in A\;(xRx)$

• $R$ simetrična $\Longleftrightarrow \forall x,y\in A\;(xRy\Rightarrow yRx)$

• $R$ antisimetrična $\Longleftrightarrow \forall x,y\in A\;(xRy\land yRx\Rightarrow x=y)$

• $R$ tranzitivna $\Longleftrightarrow \forall x,y,z\in A\;(xRy\land yRz\Rightarrow xRz)$

• $R$ sovisna $\Longleftrightarrow \forall x,y\in A\;(x\not =y\Rightarrow xRy\lor yRx)$

• $R$ enolična $\Longleftrightarrow \forall x,y,z\in A\;(xRy\land xRz\Rightarrow y=z)$.

Zgornje lastnosti relacij se odražajo tudi grafično na relacijskem grafu. Na primer, če je $R$ refleksivna, potem je v vsaki točki relacije grafa $G_{R}$ zanka (zanka v $G_{R}$ je usmerjena povezava, ki povezuje vozlišče samo s seboj). Če je $R$ simetrična, potem vse povezave v $G_{R}$ nastopajo v parih. To pomeni, da če imamo povezavo od $x$ do $y$, obstaja tudi obratna povezava. Če je $R$ tranzitivna, potem velja – če iz nekega vozlišča grafa $G_{R}$ lahko pridemo v drugo v dveh korakih, lahko pridemo tudi v enem.

Ekvivalenčna relacija

Kadar je relacija $R$ hkrati refleksivna, simetrična in tranzitivna, je $R$ ekvivalenčna relacija.

Ovojnice relacij

Ovojnica relacije je najmanjša relacija z določeno lastnostjo ${\mathcal {L}}$, ki vsebuje dano relacijo. Najpogosteje obravnavane ovojnice so refleksivna ovojnica, simetrična ovojnica, tranzitivna ovojnica in tranzitivno-refleksivna ovojnica. Refleksivna ovojnica relacije $R$ je enaka $R\cup id_{A}$, njena simetrična ovojnica pa je enaka $R\cup R^{-1}$.

Tranzitivno ovojnico relacije $R$ označimo z $R^{+}$. Je unija vseh pozitivnih potenc relacije $R$:

$R^{+}=\bigcup _{k=1}^{\infty }R^{k}.$

Tranzitivno-refleksivno ovojnico relacije $R$ označimo z $R^{*}$, definirana je zelo podobna kot $R^{+}$. Velja da je $R^{*}$ unija vseh nenegativnih potenc relacije $R$:

$R^{*}=\bigcup _{k=0}^{\infty }R^{k}.$

Zgled tranzitivne ovojnice

Naj bo relacija $R=\{(a,b),(b,c),(c,d)\}$ na množici $A=\{a,b,c,d\}$. Relacija $R$ sama po sebi ni tranzitivna, saj na primer velja $aRb$ in $bRc$, ampak ne velja $aRc$. Da lahko pridelamo $R$ v tranzitivno relacijo, ji moramo dodati vse pare, ki manjkajo zaradi tranzitivnosti. Tranzitivna ovojnica $R^{+}$ je torej:

$R^{+}=\{(a,b),(b,c),(c,d),(a,c),(b,d),(a,d)\}$.