$\def\NN{\mathbb{N}} \def\RR{\mathbb{R}} \def\ZZ{\mathbb{Z}} \def\r{\,r\,} \def\R{\cal R} \def\pot#1{{\sf P}(#1)} \def\la{\langle} \def\ra{\rangle} \def\poz{\vphantom{f}} \def\alz{\aleph_0} \def\C{{\mathfrak C}} \def\card#1{\overline{\overline{#1}}}$

Zadania wstępne

Zadanie A

Dla podanych poniżej $A$ i $r$, sprawdź czy $r$ jest relacją równoważności na $A$.

1. $A=\RR\;, x \r y \Leftrightarrow x^2 = y^2$,
2. $A=\RR\;, x \r y \Leftrightarrow x^2 \not = y^2$,
3. $A=\ZZ\;, x \r y \Leftrightarrow x \leq y$,
4. $A=\pot{\NN}\;, x \r y \Leftrightarrow x \cap \textrm{Parz}= y \cap \textrm{Parz}$, gdzie $\textrm{Parz}$ to zbiór wszystkich liczb parzystych.

Zadanie B

Czy częściowy porządek może być relacją równoważności?

Zadanie C

Jaka jest najmniejsza i największa (w sensie zawierania) relacja równoważności w danym zbiorze?

Zadanie D

Które z następujących relacji to relacje równoważności w $\RR$?

1. $\{\la x,y\ra \;|\; xy \geq 0\}$,
2. $\{\la x,y\ra \;|\; xy > 0\}$,
3. $\{\la x,y\ra \;|\; x^2-5y+1=y^2-5x+1\}$,
4. $\{\la x,y\ra \;|\; (x \leq 1 \land y \leq 1) \lor (x > 1 \land y > 1) \}$,
5. $\{\la x,y\ra \;|\; (x\leq 1 \land y \leq 1) \lor (x\geq 1 \land y \geq 1) \}$.

Zadanie E

Które z następujących relacji to relacje równoważności w zbiorze $A=\{2,3,4,5\}$?
A które w zbiorze $A=\{2,3,4,5,6\}$?

1. $\{ \la a,b\ra \;|\; a=b \lor a+b \in A \}$,
2. $\{ \la a,b\ra \;|\; a=b \lor ab \leq 7 \}$,
3. $\{ \la a,b\ra \;|\; a|b \lor b|a \}$.

Zadanie F

Czy istnieje relacja równoważności na $\NN$ która ma:

1. 22 klasy abstrakcji a w każdej klasie po 37 elementów? (było na wykładzie)
2. 2 klasy abstrakcji po 17 elementów, 5 klas po 33 elementy i jedną nieskończoną?
3. nieskończenie wiele nieskończonych klas abstrakcji?

Zadania

Zadanie 1

Niech $r$ będzie relacją binarną w $\NN^\NN$ taką, że $f \r g$ wtedy i tylko wtedy gdy dla każdego $n \in \NN$ różnica $f(n) - g(n)$ jest parzysta. Udowodnij, że $r$ jest relacją równoważności. Jaka jest moc klasy abstrakcji funkcji identycznościowej? Jaka jest moc zbioru wszystkich klas abstrakcji?

Zadanie 2

Niech $A$ będzie niepustym zbiorem i niech $f : A \to A$.

1. Udowodnij, że jeśli $f$ jest różnowartościowa to relacja $r\subseteq A\times A$, dana warunkiem
   $x \r y \quad \Leftrightarrow \quad \exists n\in\NN (f^n(x) = y \vee f^n(y) = x)$
   jest relacją równoważności.
2. Czy prawdziwe jest twierdzenie odwrotne, tj. czy jeśli $r$ jest relacją równoważności to $f$ musi być różnowartościowa?
3. Podaj przykład takich $A$ i $f$, że $r$ ma nieskończenie wiele skończonych klas abstrakcji, każda o innej liczbie elementów. (Można zrobić rysunek.)

Zadanie 3

Czy suma, przecięcie i złożenie dwóch relacji równoważności jest zawsze relacją równoważności?

Zadanie 4

Udowodnij, że dla każdego $A$ i dowolnej relacji binarnej $r$ na $A$ istnieje najmniejsza relacja równoważności zawierająca $r$.

Zadanie 5

Niech $r$ będzie relacją równoważności w zbiorze $\NN$, i niech $f : \NN \times\NN \to \pot{\NN}$ będzie taka, że $f(\la x, y\ra) = [x]_r \cup [y]_r$, dla dowolnych $x, y \in \NN$. Czy funkcja $f$ jest różnowartościowa? Czy jest na $\pot{\NN}$? Znajdź $f\poz^{-1}(\{[3]_r\})$ oraz $f(r)$.

Zadanie 6

Niech $\R$ będzie zbiorem wszystkich relacji równoważności w $\NN$ i niech $f : \R \to \pot{\NN}$ będzie taka, że $f(r) = [1]_r$, dla dowolnego $r \in \R$. Znajdź $\bigcup_{r\in\R}f(r)$ i $\bigcap_{r\in\R}f(r)$.

Zadanie 7

Jaka jest moc zbioru wszystkich relacji równoważności w $\NN$?

Zadanie 8

Czy istnieje taka relacja równoważności $r$ w zbiorze $\RR$, w której:
(a) każda klasa abstrakcji jest mocy $\alz$ oraz $\card{\RR/r} = \alz$ ?
(b) każda klasa abstrakcji jest mocy $\alz$ oraz $\card{\RR/r} = \C$ ?
(c) każda klasa abstrakcji jest mocy $\C$ oraz $\card{\RR/r} = \alz$ ?
(d) każda klasa abstrakcji jest mocy $\C$ oraz $\card{\RR/r} = \C$ ?