Ć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 pięcioelementowej relacji na zbiorze liczb naturalnych, która jest
   a) symetryczna,
   b) przechodnia,
   c) zwrotna.
4. 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ą.
5. Niech \(\varphi : \NN \to P(\NN \times \NN)\) będzie zdefiniowana tak:
   \[ \varphi(n) = \{\langle x, n\rangle \mid x \leq n\} \cup \{\langle n, y\rangle \mid n \leq y\}.\]
   a) Znaleźć \(\varphi^{-1}(\mathcal{T})\), gdzie \(\mathcal{T}\) to rodzina relacji przechodnich w \(\NN\).
   b) Czy \(\bigcup \varphi(\NN)\) jest relacją przechodnią w \(\NN\)?
6. Niech funkcja \(\varphi :  P(\NN \times \NN)\) będzie określona tak:
   \[ \varphi(r) = \bigcap \{ r^n \mid n > 0\}.\]
   a) Czy \(\varphi\) jest różnowartościowa?
   b) Niech \(\mathcal{Z}\) oznacza rodzinę wszystkich relacji zwrotnych w \(\NN\). Znaleźć \(\varphi(\NN)\).

Praca domowa

Zadanie 474 a, b, e oraz zadanie 71.