Ćwiczenia 11: izomorfizm porządków, 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 zbiory \(\QQ \times (0,1]\) i \((0,1] \times \QQ\) uporządkowane leksykograficznie są izomorficzne?
3. Czy zbiór \(\langle \mathbb{N}^*, \leq_{lex}\rangle\) jest dobrze ufundowany?
4. Czy zbiór \(\langle \mathbb{N}^2, \leq_{lex}\rangle\) jest dobrze ufundowany?
5. Podaj trzy przykłady zbiorów dobrze uporządkowanych mocy \(\aleph_0\) tak, aby żadne dwa nie były ze sobą izomorficzne.
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 \mathbb{N}}\) będzie dowolnym ciągiem elementów. Udowodnić, że istnieją i, j takie, że i<j i \(a_i \leq a_j\).
7. Udowodnić, że jeśli \(f : A \to B\) jest monotoniczną bijekcją między liniowymi porządkami \(\langle A, \leq\rangle\) i  \(\langle B, \leq\rangle\) to funkcja odwrotna też jest monotoniczna.
8. Podać przykład dobrego porządku \(\mathcal{D} = \langle D, \leq \rangle\) i rosnącej funkcji \(f : D \to D\), która spełnia jednocześnie następujące warunki:
   a) \(\forall a \in D \exists b \in D (a < b \wedge f(b) = b), \)
   b) \(\forall a \in D \exists b \in D (a < b \wedge f(b) > b). \)
9. Niech \(\langle A, \leq \rangle\) będzie nieskończonym zbiorem dobrze uporządkowanym. Pokazać, że nie istnieje taka różnowartościowa funkcja \(f : A \to A\), że dla dowolnych \(a,b \in A\) jeśli \(a \leq b\), to \(f(b) \leq f(a)\).

Praca domowa

1. Relacja r częściowo porządkująca zbiór \(\NN\) jest przyjemna, jeżeli ma nieskończony łańcuch i jest dobrym ufundowaniem, ale nie jest dobry porządkiem. Jakiej mocy jest rodzina wszystkich relacji przyjemnych?
   
2. Niech \(P_{fin}(\NN)\) to zbiór skończonych podzbiorów zbioru \(\NN\). Zdefiniować dobry porządek \( \preccurlyeq\) w zbiorze \(P_{fin}(\NN)\), żeby
   \[\forall A, B \in P_{fin}(\NN) (A \subseteq B \to A \preccurlyeq B).\]