Informatyka MIMUW

1.
$\displaystyle \begin{align*} (x,z)\in T \circ ( S \circ R ) \Leftrightarrow \\ \exists_{u} [(x,u)\in ( S \circ R ) \wedge (u,z)\in T]\Leftrightarrow \\ \exists_{u} [\exists_{v}( (x,v)\in R\wedge (v,u)\in S) \wedge (u,z)\in T]\Leftrightarrow \\ \exists_{u} \exists_{v}[ (x,v)\in R\wedge (v,u)\in S \wedge (u,z)\in T]\Leftrightarrow \\ \exists_{v} \exists_{u}[ (x,v)\in R\wedge ((v,u)\in S \wedge (u,z)\in T)]\Leftrightarrow \\ \exists_{v} [ (x,v)\in R\wedge \exists_{u}((v,u)\in S \wedge (u,z)\in T)]\Leftrightarrow \\ \exists_{v} [ (x,v)\in R\wedge (v,z)\in T \circ S]\Leftrightarrow \\ (x,z) \in (T \circ S) \circ R \\ \end{align*}$
2.
$\displaystyle \begin{align*} (x,z)\in (S \circ R )^{-1} \Leftrightarrow \\ (z,x) \in S\circ R \Leftrightarrow \\ \exists_{y} [(z,y) \in R \wedge (y,x)\in S] \Leftrightarrow \\ \exists_{y} [(y,z) \in R^{-1} \wedge (x,y)\in S^{-1}] \Leftrightarrow \\ (x,z)\in R^{-1} \circ S^{-1} \\ \end{align*}$
3.
$\displaystyle \begin{align*} (x,z)\in R \Rightarrow \\ \exists_{y} (x,u) \in R \wedge \exists_{v} (v,y)\in R \Leftrightarrow \\ x\in R_L \wedge y\in R_P \Leftrightarrow \\ (x,y) \in R_L \times R_P \end{align*}$
4.
$\displaystyle \begin{align*} x \in (S \circ R)_L \Leftrightarrow \\ \exists_{z} (x,z)\in S\circ R \Leftrightarrow \\ \exists_{z} \exists_{y} [(x,y)\in R \wedge (y,z)\in S ] \Rightarrow \\ \exists_{z} \exists_{y} (x,y)\in R \Leftrightarrow \\ \exists_{y} (x,y)\in R \Leftrightarrow \\ x \in R_L \end{align*}$
5. Dowód $\displaystyle (S \circ R)_P \subset S_P$ jest analogiczny do poprzedniego.
6.
$\displaystyle \begin{align*} x\in (R^{-1} )_L \Leftrightarrow \\ \exists_{y} (x,y)\in R^{-1} \Leftrightarrow \\ \exists_{y} (y,x)\in R \Leftrightarrow \\ x\in R_P \end{align*}$

W poniższych punktach (1-4) pokażemy, że dowolna para należy do zbioru po lewej stronie odpowiedniej równości wtedy i tylko wtedy, gdy należy do prawej. W punkcie 5, pokazujemy jedynie implikację w prawą stronę, gdyż mamy udowodnić inkluzję.

1.
$\displaystyle \begin{align*} (x,y)\in (R\cup S)^{-1} \Leftrightarrow \\ (y,x)\in (R\cup S) \Leftrightarrow \\ (y,x)\in R \vee (y,x) \in S \Leftrightarrow \\ (x,y)\in R^{-1} \vee (x,y) \in S^{-1} \Leftrightarrow \\ (x,y)\in R^{-1} \cup S^{-1} \end{align*}$

2. Dowód drugiej równości jest analogiczny do dowodu pierwszej, wystarczy użyć $\displaystyle \cap$ w miejsce $\displaystyle \cup$ oraz $\displaystyle \wedge$ w miejsce $\displaystyle \vee$.

3.
$\displaystyle \begin{align*} (x,y)\in (R^{-1})^{-1} \Leftrightarrow \\ (y,x)\in R^{-1} \Leftrightarrow \\ (x,y)\in R \end{align*}$

4.
$\displaystyle \begin{align*} (x,z)\in (R \cup S ) \circ T \Leftrightarrow \\ \exists_y [(x,y) \in T \wedge (y,z)\in (R \cup S )] \Leftrightarrow \\ \exists_y [(x,y) \in T \wedge ((y,z)\in R \vee (y,z)\in S ))] \Leftrightarrow \\ \exists_y [((x,y) \in T \wedge (y,z)\in R) \vee ((x,y) \in T \wedge (y,z)\in S ))] \Leftrightarrow \\ [\exists_y ((x,y) \in T \wedge (y,z)\in R)] \vee [\exists_y ((x,y) \in T \wedge (y,z)\in S )] \Leftrightarrow \\ (x,z)\in (R \circ T) \vee (x,z)\in (S \circ T) \Leftrightarrow \\ (x,z)\in (R \circ T) \cup (S \circ T) \end{align*}$

5.
$\displaystyle \begin{align*} (x,z)\in (R \cap S ) \circ T \Leftrightarrow \\ \exists_y [(x,y) \in T \wedge (y,z)\in (R \cap S )] \Leftrightarrow \\ \exists_y [(x,y) \in T \wedge ((y,z)\in R \wedge (y,z)\in S ))] \Leftrightarrow \\ \exists_y [((x,y) \in T \wedge (y,z)\in R) \wedge ((x,y) \in T \wedge (y,z)\in S ))] \Rightarrow \\ [\exists_y ((x,y) \in T \wedge (y,z)\in R)] \wedge [\exists_y ((x,y) \in T \wedge (y,z)\in S )] \Leftrightarrow \\ (x,z)\in (R \circ T) \wedge (x,z)\in (S \circ T) \Leftrightarrow \\ (x,z)\in (R \circ T) \cap (S \circ T) \end{align*}$

Pokażemy najpierw, że dla każdej relacji $\displaystyle R$ mamy

$\displaystyle \bigcup \bigcup R = R_L \cup R_P. \quad \mbox{(3.12)}$

Zaczniemy od inkluzji $\displaystyle \subset$. Weźmy dowolny element $\displaystyle x \in \bigcup \bigcup R$, wtedy musi istnieć element $\displaystyle y\in \bigcup R$ taki, że $\displaystyle x\in y$. Skoro $\displaystyle y\in \bigcup R$, to musi istnieć para $\displaystyle (a,b) \in R$ taka, że $\displaystyle y\in (a,b)$. Wobec tego z definicji pary uporządkowanej $\displaystyle y=\{a\}$ lub $\displaystyle y=\{a,b\}$. Ponieważ $\displaystyle x\in y$, to $\displaystyle x=a$ i wtedy $\displaystyle x\in R_L$ lub $\displaystyle x=b$ i wtedy $\displaystyle x\in R_P$. Wobec tego $\displaystyle x\in R_L \cup R_P$.

Pokażemy teraz prawdziwość inkluzji $\displaystyle \supset$ w równaniu 3.12. Weźmy dowolny element $\displaystyle a\in R_L$ wtedy istnieje element $\displaystyle b\in R_P$ taki, że $\displaystyle (a,b)\in R$, a więc $\displaystyle \{(a,b)\} \subset R$. Stąd otrzymujemy

$\displaystyle \bigcup \bigcup \{(a,b)\} \subset \bigcup \bigcup R.$

Ponieważ $\displaystyle \bigcup \bigcup \{(a,b)\}= \bigcup \{\{a\},\{a,b\}\} = \{a,b\}$, to otrzymujemy $\displaystyle \{a,b\} \subset R$, a więc $\displaystyle a\in R$. Analogiczne rozumowanie można przeprowadzić dla elementu $\displaystyle b\in R_P$. Zakończyliśmy więc dowód równości 3.12.

W temacie ćwiczenia implikacja w lewą stronę jest oczywista. Jeśli $\displaystyle A$ jest zbiorem, to $\displaystyle \bigcup \bigcup A$ jest zbiorem i $\displaystyle A$ jest podzbiorem iloczynu kartezjańskiego dwóch zbiorów, więc musi być relacją. Dla implikacji w prawą stronę załóżmy, że $\displaystyle A$ jest relacją, wtedy

$\displaystyle A \subset A_L \times A_P \subset (A_L \cup A_P) \times (A_L \cup A_P) = (\bigcup \bigcup A) \times ( \bigcup \bigcup A)$