poniedziałek, 14 grudnia 2015

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

Zadania

  1. Jaka jest najmniejsza i największa (w sensie zawierania) relacja równoważności z zbiorze A?
  2.  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.
  3. 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\).
  4. 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}\).
  5. 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