poniedziałek, 18 listopada 2013

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

Brak komentarzy:

Prześlij komentarz