Relacije

Relacije so posebne vrste množic

(N-mestna) relacija: množica urejenih n-teric
(N-mestna) relacija v množici A: množica $R\subseteq A\times A\times ...\times A$
Prazna relacija: $\varnothing \subseteq A\times A$
Univerzalna relacija: $U_A:=A\times A\subseteq A\times A$
Relacija identitete na množici A: $i{d}_A=\{(x,x);x\in A\}$
Namesto $(x,y)\in R$ pišemo $xRy$
Domena oz. definicijsko območje relacije R: $D_R=\{x;\exists y:xRy\}$
Zaloga vrednosti relacije R: $Z_R=\{y;\exists x:xRy\}$

Grafična predstavitev relacije:

• Elemente $A$ predstavimo kot točke v ravnini
• Relacijo med $a$ in $b$ ($aRb$) predstavimo kot usmerjeno puščico od a do b

Lastnosti relacij

1. Refleksivnost:

$$\begin{array}{r}\forall x\in A:xRx\\ i{d}_A\subseteq R\end{array}$$

flowchart TD
	A((x)) --> A;

2. Simetričnost:

$$\begin{array}{rl}\forall x,y\in A:xRy& ⟹yRx\\ R^{-1}& =R\end{array}$$

flowchart LR
	B((x)) --> C((y));
	C --> B;

3. Antisimetričnost:

$$\begin{array}{rl}\forall x,y\in A:xRy\wedge yRx& ⟹x=y\\ R^{-1}\cap R& \subseteq i{d}_A\end{array}$$

(Ni para nasprotno usmerjenih povezav)
4. Tranzitivnost:

$$\begin{array}{rl}\forall x,y,z\in A:xRy\wedge yRz& ⟹xRz\\ R^2& \subseteq R\end{array}$$

flowchart LR
	G((x)) --> H((y));
	H --> I((z));
	G --> I;

5. Sovisnost:

$$\begin{array}{rl}\forall x,y\in A:x\ne y& ⟹xRy\vee yRx\\ i{d}_A\cup R\cup R^{-1}& =U_a\end{array}$$

(Vsaki dve točki sta povezani)
6. Enoličnost:

$$\begin{array}{rl}\forall x,y,z\in A:xRy\wedge xRz& ⟹y=z\\ R^{-1}\ast R& \subseteq i{d}_A\end{array}$$

(Iz vsake točke gre največ ena puščica)

Operacije z relacijami

Poleg navadnih operacij množic definiramo:
Komplement: $R^C:=(A\times A)\setminus R=U_A\setminus R$
Inverzna relacija relacije R: $R^{-1}:=\{(y,x);(x,y)\in R\}$
Produkt relacij R in S: $R\ast S:=\{(x,y);\exists y(xRy\wedge ySz)\}$
Na grafu:

flowchart LR
	G((x)) -->|R| H((y));
	H -->|S| I((z));
	G -->|R*S| I;

Lastnosti operacij z relacijami:

1. $(R^{-1}{)}^{-1}=R$
2. $(R\ast S{)}^{-1}=S^{-1}\ast R^{-1}$
3. $(R\ast S)\ast T=R\ast (S\ast T)=R\ast S\ast T$
4. $R\ast (S\cup T)=R\ast S\cup R\ast T$
5. $(R\cup S)\ast T=R\ast T\cup S\ast T$
6. $R\ast i{d}_A=i{d}_A\ast R=R$ (nevtralni element)
7. $R\subseteq S⟹R\ast T\subseteq S\ast T\wedge T\ast R\subseteq T\ast S$

Potence relacij:

$$\begin{array}{rl}{R}^0& =i{d}_A\\ R^{n+1}& =R^n\ast R\\ R^{-n}& =(R^{-1}{)}^n\end{array}$$

Potence relacij lahko beremo iz grafa: $R^k$ - od $x$ do $y$ se da priti preko $k$ zaporednih povezavah

Tranzitivna ovojnica relacije R: $R^{+}={\bigcup }_{k=1}^{\infty }{R}^k$ … na grafu lahko od $x$ do $y$ pridemo v $\ge 1$ korakih
Tranzitivno-refleksivna ovojnica relacije R: $R^{\ast }={\bigcup }_{k=0}^{\infty }{R}^k$ … na grafu lahko od $x$ do $y$ pridemo v $\ge 0$ korakih

Ekvivalenčna relacija je refleksivna, simetrična in tranzitivna
Ekvivalenčni razred elementa x: $R[x]=\{y\in A;yRx\}$ … množica vseh elementov, ki so v relaciji z $x$

Relacija R delno ureja relacijo A, če je R refleksivna, antisimetrična in tranzitivna (npr. $\subseteq$ delno ureja množice)
Relacija R linearno ureja relacijo A, če R delno ureja A in je R sovisna (npr. $\le$ linearno ureja naravna števila)

Hassejev diagram: slikovni prikaz delne urejenosti:

• elementi A … točke v ravnini
• a < b … a narišemo nižje od b in ju povežemo z daljico

Preslikave

Relacija $f\subseteq A\times B$ je preslikava iz A v B, če velja:

• f je enolična,
• $D_f=A$
• $Zf\subseteq B$

Pišemo tudi $f:A\to B$ oz. $y=f(x)$

Preslikava je:

• injektivna: $\forall x,y\in A:f(x)=f(y)⟹x=y$
• surjektivna: $Z_f=B$
• bijektivna: injektivna in surjektivna

Identiteta na A: $i{d}_A:A\to A$
Inverzna preslikava: $f^{-1}:B\to A$ obstaja, le je $f$ bijektivna
Kompozitum preslikav: $f\subseteq A\times B\wedge g\subseteq B\times C⟹g\circ f=f\ast g(\subseteq A\times C)$

Dirichletov princip: Naj bosta $A,B$ končni množici, $f:A\to B$ ter $|A|=|B|$. Tedaj so naslednje trditve enakovredne:

• $f$ je injektivna
• $f$ je surjektivna
• $f$ je bijektivna