Ćwiczenia 5: relacje

Zadania

1.  Znaleźć przykład pięcioelementowej relacji na zbiorze liczb naturalnych, która jest
   a) przechodnia,
   b) symetryczna,
   c) zwrotna.
2. Dla jakich relacji \(r \subseteq A \times A\) zachodzą równości \(r \cdot r^{-1} = r^{-1} \cdot r = 1_A\)?
3. Udowodnić, że \(r^+ = \bigcup_{n > 0} r^n\).
4. Niech \(r, s \subseteq A \times A\). Czy dla dowolnych relacji \(r,s\) prawdziwa jest równość \((r^*)^{-1} = (r^{-1})^*\)?

Praca domowa

1. Niech \(\mathcal{R}\) będzie taką niepustą rodziną relacji przechodnich w zbiorze A, że dla dowolnych \(r, s \in \mathcal{R}\)  zachodzi \(r \subseteq s\) lub \(s \subseteq r\). Udowodnić, że \(\bigcup \mathcal{R}\) jest relacją przechodnią.
2. Niech\(\varphi : P(\mathbb{N}) \to P(P(\mathbb{N}) \times P(\mathbb{N}))\) będzie taką funkcją, że dla dowolnego \(Z \in P(\mathbb{N})\)
   \[\varphi(Z) = \{\langle X, Y\rangle \mid Z \subseteq X \cap Y\}.\]
   a) Czy \(\varphi\) jest różnowartościowa?
   b) Czy \(\varphi\) jest na?
   c) Która z poniższych równości zachodzi dla dowolnych \(Z_1, Z_2 \in P(\mathbb{N})\)
   • \(\varphi(Z_1 \cap Z_2) = \varphi(Z_1) \cap \varphi(Z_2)\),
   • \(\varphi(Z_1 \cup Z_2) = \varphi(Z_1) \cup \varphi(Z_2)\)?