Zadania
- Znaleźć moc zbioru funkcji nierosnących z \(\mathbb{N}\) do \(\mathbb{N}\).
- Znaleźć moc zbioru wszystkich relacji równoważności w \(\mathbb{N}\).
- Znaleźć moc zbioru Cantora. Zbiór Cantora to przecięcie ciągu zbiorów:
\(C_0 = (0,1)\),
\(C_1 = (0,\frac{1}{3}) \cup (\frac{2}{3},1)\),
\(C_2= (0,\frac{1}{9}) \cup (\frac{2}{9},\frac{1}{3}) \cup (\frac{2}{3},\frac{8}{9}) \cup (\frac{8}{9},1)\),
...
\(C = \bigcap_{n\in \mathbb{N}}C_n\).
- Funkcję \(f : \mathbb{N} \to \mathbb{N}\) nazywamy zygzakiem wtedy i tylko wtedy, gdy spełnia warunek
\[ \begin{multline*}\forall_{x>0} ((f(x)>f(x-1) \to f(x) > f(x+1)) \\
\wedge (f(x)<f(x-1) \to f(x) < f(x+1))).\end{multline*}\]
Jakiej mocy jest zbiór wszystkich zygzaków?
- a) Jaka jest moc zbioru \(A = \{ f :\mathbb{N} \to \mathbb{N} \mid \forall_x( f(x) \leq x)\}\)?
b) Jaka jest moc zbioru \(B = \{ f \in A \mid f \hbox{ jest na }\mathbb{N}\}\)?
c) Jaka jest moc zbioru \(C = \{ f \in A \mid f \hbox{ jest różnowartościowa}\}\)?
- Jaka jest moc zbioru \(\mathbb{R}^\mathbb{N}\)?
- Jaka jest moc zbioru F tych funkcji \(f : P(\mathbb{N}) \to P(\mathbb{N})\) takich, że dla każdego skończonego \(Z \subseteq \mathbb{N}\) wartość \(f(Z)\) jest skończona?
Praca domowa
- Jaka jest moc rodziny tych relacji równoważności w \(\mathbb{N}\), które mają skończenie wiele klas abstrakcji?
- Ile jest takich funkcji \(f: \mathbb{N} \to \mathbb{N}\), że każdy zbiór \(f^{-1}(\{n\})\) jest skończony?
Wesołych Świąt!
Zadania
- Pokazać, że \(P(A) \sim \{0,1\}^{A}\).
- Pokazać, że jeśli \(A \sim B\), to \(P(A) \sim P(B)\).
- Znaleźć moc zbioru skończonych podzbiorów \(\mathbb{N}\).
- Znaleźć moc zbioru ciągów liczb wymiernych stałych od pewnego miejsca.
- Znaleźć moc zbioru funkcji z \(\mathbb{N}\) do \(\mathbb{N}\).
- Znaleźć moc zbioru funkcji niemalejących z \(\mathbb{N}\) do \(\mathbb{N}\).
Praca domowa
- Niech s będzie relacją w \(\mathbb{Q}^{\mathbb{N}}\) taką, że \(\langle f, g \rangle \in s\) wtedy i tylko wtedy, gdy różnica \(f - g\) jest zbieżna do zera. Pokazać, że s jest relacją równoważności. Wskazać trzy różne klasy abstrakcji.
- Znaleźć moc zbioru wszystkich ciągów liczb wymiernych, które są zbieżne do zera.
Zadania
- Jaka jest najmniejsza i największa (w sensie zawierania) relacja równoważności w zbiorze \(A\)?
- Czy relacja równoważności może być częściowym porządkiem?
- 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.
- 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\).
- 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?
- 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)
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.)
Dziś nie ma pracy domowej.