Ćwiczenia 5: relacje

Zadania

1. Czy dla każdego \(A\) i dla każdej relacji \(R \subseteq A \times A\) zachodzi:
   a) \(R^{-1} \cdot R \subseteq I_A\);
   b) \(I_A \subseteq R^{-1} \cdot R\)?
2.  Niech \(R, S \subseteq A \times A\). Czy z tego, że \(R \cdot S = S \cdot R\) wynika, że \(R = S\) lub \(R = I_A\), lub \(S = I_A\)?
3. Podać przykład 5-elementowej relacji na zbiorze liczb naturalnych takiej, że jest ona
   a) symetryczna,
   b) przechodnia,
   c) zwrotna.
4. Udowodnić, że relacja \(R\) jest przechodnia wtedy i tylko wtedy, gdy \(R \cdot R \subseteq R\).
5. Niech \(\mathcal{R}\) będzie niepustą rodziną relacji przechodnich. Udowodnić, że \(\bigcap \mathcal{R}\) jest relacją przechodnią.
6. 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ą.
7. Relację \(r \in P(A \times A)\) nazwiemy krzaczastą wtedy i tylko wtedy, gdy
   \[\forall abc (a r b \wedge a r c \to \neg b r c \wedge \neg c r b)\]
   a) Czy złożenie relacji krzaczastych jest relacją krzaczastą?
   b) Czy iloczyn dowolnej niepustej rodziny relacji krzaczastych jest relacją krzaczastą?
   c) Czy suma dowolnej rodziny relacji krzaczastych jest relacją krzaczastą?
   d) Niech \(r_i\) krzaczaste dla \(i \in \mathbb{N}\) i niech \(\forall ij (i \leq j \to r_i \subseteq r_j\). Czy \(\bigcap_{i\in \mathbb{N}} r_i\) jest relacją krzaczastą?

Praca domowa

Jak zwykle, praca domowa zostanie opublikowana w poniedziałek po południu na stronie wykładu. Termin oddania: 18 listopada 2013 r.