Ćwiczenia 13: logika

Zadania

1. Zapisać następujące stwierdzenia w języku arytmetyki liczb naturalnych \((+, \cdot, 0, 1, =)\) używając symboli logicznych i kwantyfikatorów:
   a) Liczba a jest mniejsza lub równa liczbie b.
   b) Liczba a jest resztą z dzielenia b przez c.
   c) Liczba a jest pierwsza.
   d) Liczba a jest największym wspólnym dzielnikiem liczb b i c chyba, że jest parzysta.
   e) Liczby x i y mają te same dzielniki pierwsze.
2. Sformułować poprawne zaprzeczenia stwierdzeń:
   a) Liczby m i n są pierwsze.
   b) Liczby m in są względnie pierwsze.
3. Dla każdej z następujących par struktur wskazać formułę prawdziwą w jednej, a w drugiej nie.
   a) \(\langle \mathbb{Q}, +, \cdot, 0, 1\rangle\) i \(\langle \mathbb{R}, +, \cdot, 0, 1\rangle\),
   b) \(\langle \mathbb{N}, +, 0\rangle\) i \(\langle \mathbb{R}, +, 0 \rangle\),
   c) \(\langle P_2, \parallel \rangle\) i \(\langle P_2, \bot \rangle\), gdzie \(P_2\) to zbiór prostych w \(\mathbb{R}^2\),
   d) \(\langle P_2, \bot\rangle\) i \(\langle P_3, \bot \rangle\), gdzie \(P_n\) to zbiór prostych w \(\mathbb{R}^n\)
   e) \(\langle \mathbb{R}, +, \cdot, 0, 1\rangle\) i \(\langle P(\mathbb{N}), \cup, \cap, \emptyset, \mathbb{N}\rangle\),
   f) \(\langle \mathbb{N}, \leq, 0\rangle\) i \(\langle \mathbb{R}, \leq, 0\rangle\),
   g) \(\langle \mathbb{N}, \leq\rangle\) i \(\langle \mathbb{R}, \leq\rangle\),
   h) \(\langle \mathbb{N}, +,  0\rangle\) i \(\langle\{a,b\}^*, \cdot, \epsilon\rangle\).
4.  Czy następujące formuły są tautologiami? Czy są spełnialne?
   a) \(\forall x (p(x) \to q(x)) \vee \forall x (q(x) \to p(x))\),
   b) \(\exists x (P(x) \to \forall y P(y))\),
   c) \( (\exists x \exists y P(x,y) \to \forall y R(y)) \to \forall x(P(x,x) \to R(x)) \),
   d) \( \forall x \exists y \forall u \exists v P(x,y,u,v) \to  \forall u \exists v \forall x \exists y  P(x,y,u,v) \).

Ć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 B\).
2. Niech \(B \subseteq \RR_+\). Udowodnić, że istnieje zbiór \(C \subseteq \RR\) taki, że
• \( \forall x,y \in C (x \neq y \to | x -y | \in B) \),
• \( \forall x \not\in C (\exists y \in C | x -y | \not \in B) \).
3. Udowodnić, że każdy porządek częściowy można rozszerzyć do porządku liniowego.

Praca domowa (nieobowiązkowa)

1. Dowolny podzbiór \(\ZZ\) nazwiemy zeznaniem. Zbiór zeznań \(\mathcal{R}\) jest sprzeczny, jeśli istnieje w nim takie \(i \in \ZZ\), że \(i, -i \in \bigcup \mathcal{R}\). Udowodnić, że jeśli \(\mathcal{R}\) jest dowolną rodziną zeznań, to istnieje maksymalna niesprzeczna podrodzina \(R \subseteq \mathcal{R}\).

Ć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).\]

Ćwiczenia 10: moce cz. 2

Zadania

1. Znaleźć moc zbioru funkcji nierosnących z \(\mathbb{N}\) do \(\mathbb{N}\).
2. Znaleźć moc zbioru wszystkich relacji równoważności w \(\mathbb{N}\).
3. 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\).
4.  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?
5. 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}\}\)?
6. Jaka jest moc zbioru \(\mathbb{R}^\mathbb{N}\)?
7. 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

1. Jaka jest moc rodziny tych relacji równoważności w \(\mathbb{N}\), które mają skończenie wiele klas abstrakcji?
   
2. 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!

Ćwiczenia 9: równoliczność, moce

Zadania

1. Pokazać, że \(P(A) \sim \{0,1\}^{A}\).
2. Pokazać, że jeśli \(A \sim B\), to \(P(A) \sim P(B)\).
3. Znaleźć moc zbioru skończonych podzbiorów \(\mathbb{N}\).
4. Znaleźć moc zbioru ciągów liczb wymiernych stałych od pewnego miejsca.
5. Znaleźć moc zbioru funkcji z \(\mathbb{N}\) do \(\mathbb{N}\).
6. Znaleźć moc zbioru funkcji niemalejących z \(\mathbb{N}\) do \(\mathbb{N}\).

Praca domowa

1. 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.
2. Znaleźć moc zbioru wszystkich ciągów liczb wymiernych, które są zbieżne do zera.

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

Zadania

1. Jaka jest najmniejsza i największa (w sensie zawierania) relacja równoważności w zbiorze \(A\)?
2. Czy relacja równoważności może być częściowym porządkiem?
3. 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.
4. 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\).
5. 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?
6. 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.

Ć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.
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

1. Które z następujących stwierdzeń jest prawdziwe dla dowolnego zbioru częściowo uporządkowanego  \(\langle X, \leq \rangle\) i dowolnych \(A, B \subseteq X\):
   a) Jeśli w X istnieje \(\sup A\) i \(\sup B\), to istnieje \(\sup (A \cup B)\).
   b) Jeśli w X istnieje \(\sup (A \cup B)\), to istnieją.\(\sup A\) i \(\sup B\).
   
2. Niech X będzie zbiorem częściowo uporządkowanym i niech \(A \subseteq X\) nie ma elementu największego. Niech \(B = \{b \in X \mid \forall a \in A (b > a) \}. \) Pokazać, że jeśli istnieje \(\inf B\), to istnieje \(\sup A\) oraz \(\sup A = \inf B \in B\).
3. Dla chętnych: skończyć zadanie 4 z zajęć.