Ćwiczenia 13: dobre ufundowanie

Zadania

1. Czy zbiór \(\langle \NN^{*}, \leq_{lex}\rangle\) jest dobrze ufundowany?
2. Czy zbiór \(\langle \NN^{2}, \leq_{lex}\rangle\) jest dobrze ufundowany?
3. Podać trzy przykłady zbiorów dobrze ufundowanych mocy \(\aleph_{0}\) takich, że żadne dwa nie są izomorficzne.
4.  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\}\).
   a) Które z nich są dobrze ufundowane?
   b) Które z nich są izomorficzne?
5. (do dokończenia) Niech \(\langle A, \leq\rangle\) będzie zbiorem dobrze ufundowanym. W zbiorze P(A) uporządkowanym przez porządek częściowy \( \sqsubseteq \) tak:
   \[ X \sqsubseteq Y \hbox{ wtw. } X = Y \hbox{ lub } (Y \neq \emptyset\wedge \forall x\in X\forall y\in Y x \leq y). \]
   Udowodnić, że zbiór \(\langle P(A), \sqsubseteq \rangle\) jest dobrze ufundowany.
6. (do dokończenia) Niech \(D = \{0, 1, 2, \ldots, 9\}\) i niech \(C = \NN \to D\). Określamy relację równoważności \(\sim\) w zbiorze \(C\), przyjmując \(a \sim b\) wtedy i tylko wtedy, gdy ciągi \(a\) i \(b\) są wzajemnie swoimi podciągami. Jakiej mocy jest zbiór ilorazowy \(C/_{\sim}\)?

Zaliczenie ćwiczeń

• Prace domowe są zaliczone od 50 punktów.  Osoby, które mają pomiędzy 40 i 50 punktów, powinny na następne ćwiczenia (25.01.2016) rozwiązać zadania dodatkowe. Jako zadanie dodatkowe należy wybrać zadania ze zbioru zadań, które nie mają w zbiorze rozwiązania i które nie były rozwiązywane na ćwiczeniach. Trzeba zrobić tyle zadań dodatkowych, ile brakuje do 50 punktów. Na przykład: osoba, która ma 45 punktów, powinna zrobić 5 zadań dodatkowych.
• Kartkówki są zaliczone od 26 punktów.
• Klasówka jest zaliczona o 15 punktów.
• Zaliczenie ćwiczeń otrzymują osoby, które zaliczą prace domowe, kartkówki i klasówkę.

Ćwiczenia 12: lemat Kuratowskiego-Zorna

Zadania

1. Niech A będzie dowolnym zbiorem i niech \(B \subseteq A \times A\). Udowodnić, że istnieje maksymalny zbiór \( C \subseteq A\) taki, że \(C \times C \subseteq A\).
2. Udowodnić, że każdy porządek częściowy można rozszerzyć do porządku liniowego.

Praca domowa - dla chętnych

Zadanie 408 ze zbioru

Ćwiczenia 11: relacje i równoważności i moce

Zadania

1. W zbiorze \(\RR[x]\) wielomianów jednej zmiennej o współczynnikach rzeczywistych określmy relację równoważności:
   \[ f r g \hbox{ wtw. } f - g \hbox{ jest funkcją liniową.} \]
   Znaleźć moc zbioru ilorazowego i moc każdej klasy abstrakcji.
2. Pokazać, że jeśli moc A jest równa \(\mathfrak{m}\) oraz \(0 \neq \mathfrak{n} \leq \mathfrak{m}\), to istnieje relacja równoważności w A spełniająca warunek \(| A_{/r}| = \mathfrak{n}\).
3. Znaleźć moc zbioru funkcji ciągłych \(\RR \to \RR\).
4. Znaleźć moc zbioru Cantora.
5. Niech \(\sim\) będzie relacją równoważności w \(\NN^{\NN}\) określoną następująco:
   \[ f \sim g \hbox{ wtw. } |f(n) - g(n)| \hbox{ jest różnowartościowa.} \]
   Jaka jest moc zbioru ilorazowego?
6. Znaleźć moc zbioru wszystkich funkcji wyboru dla \(P(\NN) - \{\emptyset\}\).

Praca domowa

Zadania 269 i 305.
Zadanie do przemyślenia pod choinką: Udowodnić, że każdy porządek częściowy można rozszerzyć do porządku liniowego.

Ćwiczenia 10: relacje równoważności

Zadania

1. Jaka jest najmniejsza i największa (w sensie zawierania) relacja równoważności z zbiorze A?
2.  Czy istnieje relacja równoważności w \(\NN\), która ma:
   a) dokładnie dwie klasy abstrakcji po 37 elementów,
   b) dwie klasy abstrakcji po 37 elementów, trzy klasy abstrakcji po 33 elementy i jedną nieskończoną klasę abstrakcji,
   c) nieskończenie wiele klas abstrakcji, każda o nieskończonej liczbie elementów.
3. Niech \(r \subseteq P(\NN) \times P(\NN)\) będzie taka, że
   \[ \langle X, Y \rangle \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\).
4. Niech \(r \subseteq \NN^\NN \times \NN^\NN\) będzie określona tak:
   \[ \langle f, g \rangle \hbox{ wtw. } f(\NN) = g(\NN).\]
   a) Udowodnić jednym krótkim zdaniem, że r jest relacją równoważności.
   b) Znaleźć \([\lambda x.1]_r\) i \([id_{\NN}]_r\).
   c) Czy zbiór wszystkich funkcji różnowartościowych jest klasą abstrakcji tej relacji?
   d) Czy istnieje dwuelementowa klasa abstrakcji?
   e) Znaleźć moc zbioru \(\NN \to \NN_{/r}\).
5. Niech A będzie niepustym zbiorem i niech \(f:\NN \to \NN\).
   a) Udowodnić, że jeśli f jest różnowartościowa, to relacja \(r \subseteq A \times A\) dana warunkiem
   \[ x r y \hbox{ wtw. } \exists n \in \NN (f^n(x) = y \hbox{ lub } f^n(y) = x) \]
   jest relacją równoważności.
   b) Czy prawdziwe jest twierdzenie odwrotne, tj. jeśli r jest relacją równoważności, to f musi być różnowartościowa?
   c) Podać przykłąd takich A, f, że r  ma nieskończenie wiele skończonych klas abstrakcji, każda o innej liczbie elementów. Można zrobić rysunek.

Praca domowa

Zadania 179 i 194 ze zbioru zadań.

Ćwiczenia 8: moce cz. 1

Zadania

1. Pokazać, że \( (A^B)^C \sim A^{B \times C}\).
2. Znaleźć moc zbioru skończonych podzbiorów \(\NN\).
3. Znaleźć moc zbioru ciągów liczb wymiernych stałych od pewnego miejsca.
4. Znaleźć moc zbioru funkcji z \(\NN\) do \(\NN\).
5. Znaleźć moc zbioru funkcji niemalejących z \(\NN\) do \(\NN\).

Praca domowa

Zadania 262 i 327.

Ćwiczenia 7: porządki cz. 2

Zadania

1. Rozważmy częściowy porządek \(\langle A \leadsto B, \leq \rangle\), gdzie \(A \leadsto B\) to zbiór funkcji częściowych z A do B i \(f \leq g\), wtedy i tylko wtedy, gdy dla każdego \(a \in A\) albo \(f(a)\) jest nieokreślone, albo obie funkcje są określone i \(f(a) = g(a)\). Czy \(\langle A \leadsto B, \leq \rangle\) jest kratą zupełną?
2. Udowodnij, że \(\langle A \leadsto B, \leq \rangle\) jest częściowym porządkiem zupełnym.
3. Niech A i B będą zbiorami częściowo uporządkowanymi i niech funkcje \(f : A \to B\) i \(g : B \to A\) będą monotoniczne. Udowodnić, że następujące warunki są równoważne:
   a) \(\forall a \in A \forall b \in B (a \leq g(b) \leftrightarrow f(a) \leq b  )\)
   b) \(\forall a \in A (a \leq g(f(a))) \wedge \forall b \in B (f(g(b)) \leq b)\).
4. Podaj przykład takiego przekształcenia monotonicznego f w kracie \(\langle P(\mathbb{N}), \subseteq \rangle\), że kres górny zbioru \( \{ f^n(\emptyset) \mid  n \in \mathbb{N}\} \) nie jest najmniejszym punktem stałym.
   Czy można wybrać f tak, aby punkt stały f nie istniał?
5. Niech A będzie częściowym porządkiem zupełnym i niech \(f : A \to A\) będzie ciągła. Udowodnić, że jeśli \(a \leq f(a)\), to istnieje taki punkt stały b funkcji f, że \(a \leq b\).

Praca domowa

Zadania 355 i 348 (pytanie o bijekcję tylko dla chętnych).

Ćwiczenia 6: porządki cz. 1

Zadania

1.  Niech funkcja \(\varphi: P(\NN \times \NN) \to P(\NN \times \NN)\) będzie taka, że
   \[ \varphi(r) = \bigcap \{ r^n \mid n > 0 \}. \]
   Niech Z to rodzina relacji zwrotnych w \(\NN\). Znaleźć \(\varphi(Z)\).
2. (Utajnione) Zadanie z kartkówki.
3. Podać przykład zbioru częściowo uporządkowanego z dwoma elementami maksymalnymi, jednym minimalnym, bez elementu najmniejszego i z takim czteroelementowym antyłańcuchem, który jest ograniczony z góry, ale nie ma kresu górnego.
4. Rozpatrzmy częściowe uporządkowanie zbioru \(\{0,1\}^{\NN}\) takie, że
   \[ f \leq g \hbox{ wtw. }\forall x (f(x) \leq g(x)). \]
   a) Czy ten porządek jest liniowy?
   b) Czy istnieje w nim łańcuch nieskończony?
   c) Czy istnieje w nim antyłańcuch nieskończony?
   d) Czy ma element maksymalny, minimalny, najmniejszy, największy?
5. Czy zbiór \(\{01^n \mid n \in \NN\}\) ma kres górny (dolny) w zbiorze \(\{0,1\}^{\NN}\) uporządkowanym leksykograficznie?
6. Czy zbiór \(\{0^n1 \mid n \in \NN\}\) ma kres górny (dolny) w zbiorze \(\{0,1\}^{\NN}\) uporządkowanym leksykograficznie?

Warianty - do przemyślenia w domu dla chętnych

1. Zadanie 1 dla rodziny relacji przechodnich, symetrycznych, antysymetrycznych, ...
2. Zadanie 1: znaleźć \(\varphi^{-1}(Z)\).
3. Zadanie 4: jaki dostaniemy porządek, gdy utożsamimy ciągi zerojedynkowe z funkcjami charakterystycznymi podzbiorów liczb naturalnych?

Praca domowa

Zadania 351 i 353.