Relacje równoważności

\(\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\) ?