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