Relacija

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

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" ($\le$), 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.

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 $\le$
• 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 $\mathrm{\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=\mathrm{\varnothing }$ se imenuje prazna relacija. Definirana je kot: $\mathrm{\varnothing }=\{x\mid x\ne x\}$.
• Relacija identitete ali enakosti $i{d}_A$ v množici $A$ je množica urejenih parov z enakima koordinatama: $i{d}_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\wedge \mathrm{\neg }(xRy)\}$.
• Produkt relacij $R*S$ je definiran z naslednjim opisom: $xR*Sy$ natanko tedaj, ko $\mathrm{\exists }z(xRz\wedge 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 \mathrm{\exists }y\in A(xRy)\}$

$Z_R=\{y\mid \mathrm{\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 $⟺\mathrm{\forall }x\in A(xRx)$

• $R$ simetrična $⟺\mathrm{\forall }x,y\in A(xRy\Rightarrow yRx)$

• $R$ antisimetrična $⟺\mathrm{\forall }x,y\in A(xRy\wedge yRx\Rightarrow x=y)$

• $R$ tranzitivna $⟺\mathrm{\forall }x,y,z\in A(xRy\wedge yRz\Rightarrow xRz)$

• $R$ sovisna $⟺\mathrm{\forall }x,y\in A(x=y\Rightarrow xRy\vee yRx)$

• $R$ enolična $⟺\mathrm{\forall }x,y,z\in A(xRy\wedge 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 $ℒ$, 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 i{d}_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}^{\mathrm{\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}^{\mathrm{\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)\}$.