Matematické Fórum

tom317 · 17. 11. 2011 10:56

Dobrý den,
potřeboval bych pomoci s tímto příkladem:

Dokažte nebo vyvraťte protipříkladem pro libovolné dvě Relace $R_1$ , $R_2$ na množině X:
a) $\varrho(R_1 \cup R_2)=\varrho(R_1) \cup \varrho(R_2)$
b) $\sigma(R_1 \cap R_2)=\sigma(R_1) \cap \sigma(R_2)$
c) $\tau(R_1 \cup R_2)=\tau(R_1) \cup \tau(R_2)$
d) $\tau(R_1 \cap R_2)=\tau(R_1) \cap \tau(R_2)$
e) $\sigma(\tau(R_1))=\tau(\sigma(R_1))$
f) $\sigma(\varrho(R_1))=\varrho(\sigma(R_1))$
g) $\varrho(\tau(R_1))=\tau(\varrho(R_1))$

$\varrho$ je reflexivní uzávěr
$\sigma$ je symetrický uzávěr
$\tau$ je tranzitivní uzávěr

Podařilo se mi dospět k řešení některých důkazů:
ad c) $\tau(R_1 \cup R_2)=\tau(R_1) \cup \tau(R_2)$ - vyvrácení protipříkladem:
$X=\{1, 2, 3\}$
$R_1=\{(1, 2)\}$
$R_2=\{(2, 3)\}$
$\tau(R_1)=\{(1, 2)\}$
$\tau(R_2)=\{(2, 3)\}$
$\tau(R_1 \cup R_2)=\tau(\{(1, 2), (2, 3)\})=\{(1, 2), (2, 3), (1, 3)\}$
$\tau(R_1) \cup \tau(R_2)=\{(1, 2), (2, 3)\}$
$\tau(R_1 \cup R_2) \not= \tau(R_1) \cup \tau(R_2)$ dokázáno

ad e) $\sigma(\tau(R_1))=\tau(\sigma(R_1))$ - vyvrácení protipříkladem:
$X=\{1, 2, 3\}$
$R_1=\{(1, 2), (3, 2)\}$
$\tau(R_1) = \{(1, 2), (3, 2)\}$
$\sigma(\tau(R_1)) = \{(1, 2), (2, 1), (3, 2), (2, 3)\}$
$\sigma(R_1) = \{(1, 2), (2, 1), (3, 2), (2, 3)\}$
$\tau(\sigma(R_1)) = \{(1, 2), (2, 1), (3, 2), (2, 3), (1, 3), (3, 1)\}$
$\sigma(\tau(R_1)) \not= \tau(\sigma(R_1))$ dokázáno

ad f) $\sigma(\varrho(R_1))=\varrho(\sigma(R_1))$ - důkaz:
$R_1\subseteq X \times X$
1) $(x,y) \in \sigma(\varrho(R_1))$
$\Rightarrow (x,y) \in \varrho(R_1) \vee (x,y) \in (\varrho(R_1))^{-1}$
$\Rightarrow (x,y) \in \varrho(R_1) \vee (y,x) \in \varrho(R_1)$
$\Rightarrow (x,y) \in R_1 \vee (x,y) \in \Delta X \vee (y,x) \in R_1 \vee (y,x) \in \Delta X$
$\Rightarrow (x,y) \in R_1 \vee (x,y) \in (R_1)^{-1} \vee (x,y) \in \Delta X$
$\Rightarrow (x,y) \in (R_1 \cup (R_1)^{-1}) \vee (x,y) \in \Delta X$
$\Rightarrow (x,y) \in \sigma(R_1) \vee (x,y) \in \Delta X$
$\Rightarrow (x,y) \in (\sigma(R_1) \cup \Delta X)$
$\Rightarrow (x,y) \in \varrho(\sigma(R_1))$
2) $(x,y) \in \varrho(\sigma(R_1))$
$\Rightarrow (x,y) \in (\sigma(R_1) \cup \Delta X)$
$\Rightarrow (x,y) \in \sigma(R_1) \vee (x,y) \in \Delta X$
$\Rightarrow (x,y) \in (R_1 \cup (R_1)^{-1}) \vee (x,y) \in \Delta X$
$\Rightarrow (x,y) \in R_1 \vee (x,y) \in (R_1)^{-1} \vee (x,y) \in \Delta X \vee (x,y) \in \Delta X$
$\Rightarrow ((x,y) \in R_1 \vee (x,y) \in \Delta X) \vee ((x,y) \in (R_1)^{-1} \vee (x,y) \in \Delta X)$
$\Rightarrow (x,y) \in (R_1 \cup \Delta X) \vee (y,x) \in (R_1 \cup \Delta X)$
$\Rightarrow (x,y) \in \varrho(R_1) \vee (x,y) \in (\varrho(R_1))^{-1}$
$\Rightarrow (x,y) \in (\varrho(R_1) \cup (\varrho(R_1))^{-1})$
$\Rightarrow (x,y) \in \sigma(\varrho(R_1))$
1) + 2) dokázáno

Další příklady s průniky a sjednocením už nevím, jak obecně dokázat.
A u příkladů se vnořenými funkcemi nevím, jak dokázat tranzitivitu.
Pro symetrii platí $\sigma(W)=W \cup W^{-1}$ , to chápu.
Pro reflexivitu platí $\varrho(W) = W \cup \Delta X$ , tady vím jak s tím počítat, ale nechápu, co znamená $\Delta X$ a proč platí $\Delta X= (\Delta X)^{-1}$ ?

Předem děkuji, pokud mi bude někdo ochoten vysvětlit mé dotazy, případně naznačit, jakým způsobem dokázat ostatní části úlohy.

Tomáš