Zadania
- Jaka jest najmniejsza i największa (w sensie zawierania) relacja równoważności z zbiorze A?
- Czy istnieje relacja równoważności w \(\NN\), która ma:
a) dokładnie dwie klasy abstrakcji po 37 elementów,
b) dwie klasy abstrakcji po 37 elementów, trzy klasy abstrakcji po 33 elementy i jedną nieskończoną klasę abstrakcji,
c) nieskończenie wiele klas abstrakcji, każda o nieskończonej liczbie elementów.
- Niech \(r \subseteq P(\NN) \times P(\NN)\) będzie taka, że
\[ \langle X, Y \rangle \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\).
- Niech \(r \subseteq \NN^\NN \times \NN^\NN\) będzie określona tak:
\[ \langle f, g \rangle \hbox{ wtw. } f(\NN) = g(\NN).\]
a) Udowodnić jednym krótkim zdaniem, że r jest relacją równoważności.
b) Znaleźć \([\lambda x.1]_r\) i \([id_{\NN}]_r\).
c) Czy zbiór wszystkich funkcji różnowartościowych jest klasą abstrakcji tej relacji?
d) Czy istnieje dwuelementowa klasa abstrakcji?
e) Znaleźć moc zbioru \(\NN \to \NN_{/r}\).
- Niech A będzie niepustym zbiorem i niech \(f:\NN \to \NN\).
a) Udowodnić, że jeśli f jest różnowartościowa, to relacja \(r \subseteq A \times A\) dana warunkiem
\[ x r y \hbox{ wtw. } \exists n \in \NN (f^n(x) = y \hbox{ lub } f^n(y) = x) \]
jest relacją równoważności.
b) Czy prawdziwe jest twierdzenie odwrotne, tj. jeśli r jest relacją równoważności, to f musi być różnowartościowa?
c) Podać przykłąd takich A, f, że r ma nieskończenie wiele skończonych klas abstrakcji, każda o innej liczbie elementów. Można zrobić rysunek.
Praca domowa
Zadania 179 i 194 ze zbioru zadań.
Brak komentarzy:
Prześlij komentarz