Klasówka

Przypominam, że 5 grudnia na wykładzie będzie klasówka. Materiał obowiązujący na klasówce:

• rachunek zbiorów,
• funkcje,
• relacje,
• relacje równoważności,
• równoliczność,
• zbiory przeliczalne.

Jeśli są jakieś zadania (z ćwiczeń, ze zbioru zadań lub inne) albo zagadnienia, które chcielibyście powtórzyć przed klasówką, proszę napisać w komentarzu.

Ćwiczenia 7: równoliczność

Zadania

1. Pokazać, że \(\mathbb{N} \times \mathbb{N} \sim \mathbb{N}\).
2. Pokazać, że \(P(A) \sim \{0,1\}^{\mathbb{N}}\).
3. Pokazać, że jeśli \(A \sim B\), to \(P(A) \sim P(B)\).
4. Pokazać, że \(\mathbb{N} \not \sim \mathbb{R}\).
5. Znaleźć moc zbioru skończonych podzbiorów \(\mathbb{N}\).

Praca domowa

Treść kolejnej pracy domowy zostanie opublikowana w poniedziałek na stronie wykładu. Termin oddania: 2 grudnia 2013 r.

Ćwiczenia 6: relacje równoważności

Zadania

1. Jaka jest najmniejsza i największa (w sensie zawierania) relacja równoważności w zbiorze \(A\)?
2. Czy istnieje relacja równoważności na \(\mathbb{N}\), która ma:
   a) dokładnie 2 klasy abstrakcji po 37 elementów,
   b) 2 klasy abstrakcji po 17 elementów, 3 klasy po 33 elementy i jedną nieskończoną,
   c) nieskończenie wiele klas abstrakcji, każda o nieskończonej liczbie elementów.
3. Niech \(r \subseteq P(\mathbb{N}) \times P(\mathbb{N})\) będzie taka, że
   \[ \langle X, Y \rangle \in r \hbox{ wtw istnieje skończony }Z\hbox{ taki, że } X \cup Z =Y \cup Z.  \]
   a) Udowodnić, że r jest relacją równoważności.
   b) Znaleźć \([\emptyset]_r\).
4. Niech \(r \subseteq (\mathbb{N} \to \mathbb{N}) \times (\mathbb{N} \to \mathbb{N} )\) będzie określona w następujący sposób:
   \[\langle f, g\rangle \in r \hbox{ wtw } f(\mathbb{N}) = g(\mathbb{N}).\]
   a) Udowodnić jednym krótkim zdaniem, że r jest relacją równoważności.
   b) Znaleźć klasy \([\lambda x.1]_r\) i \([id_{\mathbb{N}}]_r\).
   c) Czy zbiór wszystkich funkcji różnowartościowych jest klasą abstrakcji tej relacji?
   d) Czy istnieje dwuelementowa klasa abstrakcji?
   e) Czy iloraz \((\mathbb{N} \to \mathbb{N})/r\) jest skończony?

Ciekawe zadanie

Nie zdążyliśmy zrobić tego zadania na ćwiczeniach, a jest bardzo ciekawe. To jedno z moich ulubionych zadań na relacje równoważności. Polecam! :-)

1. Niech A będzie niepustym zbiorem i niech \(f : A \to A\).
   a) Udowodnić, że jeśli f jest różnowartościowa, to relacja \(r \subseteq A \times A\) dana warunkiem
   \[ x r y \Leftrightarrow \exists n\in \mathbb{N} (f^n(x) = y \wedge f^n(y) = x)\]
   jest relacją równoważności.
   b) Czy prawdziwe jest twierdzenie odwrotne, czyli jeśli r jest relacją równoważności, to f musi być różnowartościowa?
   c) Podać przykład takich A, f, że r ma nieskończenie wiele skończonych klas abstrakcji, każdą o innej liczbie elementów. (Można zrobić rysunek.)

 Praca domowa

Treść kolejnej pracy domowej zostanie opublikowana w poniedziałek po południu na stronie wykładu. Termin oddania: 25 listopada 2013 r.

Ć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.