Ćwiczenia 14: dobre ufundowanie

Zadania

1. Niech \(A = \{ 3 - \frac{1}{2n} \mid n \in \mathbb{N} - \{0\}\}\),
   \(B = \{ \pi - \frac{2}{n} \mid n \in \mathbb{N} - \{0\}\} \cup \{4\}\),
   \(C = \{0\} \cup \{ \frac{1}{n} \mid n \in \mathbb{N} - \{0\}\} \cup \{ 2 - \frac{1}{n} \mid n \in \mathbb{N} - \{0\}\}\).
   Rozpatrzmy zbiory A, B, C, \(\mathbb{N}\), \(\mathbb{Z}\), \(\mathbb{Q}\), \(\mathbb{Q} - \{0\}\), \(\mathbb{R}\), \(\mathbb{R} - \{0\}\). Które z nich są izomorficzne?
2. Czy zbiór \(\langle \NN^{*}, \leq_{lex}\rangle\) jest dobrze ufundowany?
3. Czy zbiór \(\langle \NN^{2}, \leq_{lex}\rangle\) jest dobrze ufundowany?
4. Podać trzy przykłady zbiorów dobrze ufundowanych mocy \(\aleph_{0}\) takich, że żadne dwa nie są izomorficzne.
5. Udowodnić, że jeśli \(\langle A, \leq_A \rangle\), \(\langle B, \leq_B \rangle\) są dobrze ufundowane i \( A \cap B \neq \emptyset\), to porządek \(\langle A \cup B, \leq\>\) zdefiniowany tak:
   \[ x \leq y \hbox{ wtw. } x \leq_A y \vee x \leq_B y \vee (x \in A \wedge y \in B)\]
   jest dobrze ufundowany.
6. Niech \(\langle A, \leq\rangle\) będzie zbiorem dobrze uporządkowanym, w którym wszystkie antyłańcuchy są skończone. Niech \((a_i)_{i \in \NN}\) będzie dowolnym ciągiem elementów. Udowodnić, że istnieją \(i < j\) takie, że \(a_i \leq a_j\).

Ćwiczenia 13: moce cz. 2

Zadania

1. Znaleźć moc zbioru skończonych podzbiorów \(\NN\).
2. Znaleźć moc zbioru funkcji z \(\NN\) do \(\NN\).
3. Znaleźć moc zbioru ciągów liczb wymiernych stałych od pewnego miejsca.
4. Znaleźć moc zbioru funkcji niemalejących z \(\NN\) do \(\NN\).
5. Znaleźć moc zbioru funkcji nierosnących z \(\NN\) do \(\NN\).
6. Znaleźć moc zbioru wszystkich relacji równoważności w \(\NN\).

Ciekawe zadanie dla rozrywki

 Niech \(r\) będzie taką relacją w zbiorze \(\QQ^\NN\), że
\[ \langle f, g\rangle \in r \hbox{ wtw. różnica }f-g\hbox{ jest zbieżna do zera.}\] Znaleźć moce klas abstrakcji relacji \(r\). Znaleźć moc zbioru ilorazowego.

Ćwiczenia 12: moce cz. 1

Zadania

1. Pokazać, że \(\NN \times \NN \sim \NN\).
2. Pokazać, że \(\QQ \sim \NN\). 
3. Pokazać, że \(\RR \sim  (0,1)\).  
4. Pokazać, że \((0,1) \sim(0,1) \times (0,1)\).
5. Jakiej mocy jest zbiór wszystkich prostych na płaszczyźnie?
6. Niech \(\mathcal{R}\) oznacza zbiór relacji równoważności w \(\NN\). Jakiej mocy są zbiory:
   a) \(A =\{ r \in \mathcal{R} \mid [0]_r = \NN - \{7\}\}\),
   b) \(B =\{ r \in \mathcal{R} \mid [0]_r = \NN - \{7,49\}\}\),
   c) \(C =\{ r \in \mathcal{R} \mid [0]_r = \{7, 49\}\}\).
7. Pokazać, że \(\RR \not\sim \NN\).
8. Udowodnić, że jeśli A jest dowolnym zbiorem parami rozłącznych przedziałów na prostej, to moc zbioru A jest mniejsza lub równa \(\aleph_0\).
9. Niech P będzie zbiorem wszystkich prostokątów na płaszczyźnie i niech \(r\) będzie relacją podobieństwa trójkątów (to jest relacja równoważności w P). Znaleźć moc zbioru \(P/_r\).

Praca domowa

Zadania 271, 273.
Dla chętnych: zadanie 256.