Ć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) 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}, +,  0\rangle\) i \(\langle\{a,b\}^*, \cdot, \epsilon\rangle\).
4. Jakiej mocy jest zbiór wszystkich ciągłych w \(\mathbb{R}\)?

Ćwiczenia 12: dobre ufundowanie

Zadania

1. Niech \(B \subseteq \mathbb{R}_{+}\). Udowodnić, że istnieje zbiór \(C \subseteq \mathbb{R}_{+}\) taki, że
   
   • \(\forall_{x,y \in C}(x\neq y \to | x - y | \in B\),
   • \(\forall_x (x\not \in C \to \exists y \in C | x - y | \not\in B\).
2. Czy zbiór \(\langle \mathbb{N}^*, \leq_{lex}\rangle\) jest dobrze ufundowany?
3. Czy zbiór \(\langle \mathbb{N}^2, \leq_{lex}\rangle\) jest dobrze ufundowany?
4. Podaj trzy przykłady zbiorów dobrze uporządkowanych mocy \(\aleph_0\) tak, aby żadne dwa nie były ze sobą izomorficzne.
5. 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\).

Praca domowa

Ostatnia praca domowa zostanie ogłoszona w poniedziałek po południu. Termin oddania: czwartek 23 stycznia 2014 r. Praca domowa zostanie zebrana na wykładzie.

Ćwiczenia 11: porządki cz. 2

Przypominam, że jutro o 16 w sali 4420 jest klasówka poprawkowa.

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. 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ą?
3. Udowodnij, że \(\langle A \leadsto B, \leq \rangle\) jest częściowym porządkiem zupełnym.
4. 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\).

Praca domowa

Kolejna praca domowa pojawi się w poniedziałek po południu na stronie wykładu. Termin oddania: 20 stycznia 2014 r.

Ciekawe zadanie dodatkowe - dla chętnych

Udowodnić, że każdy porządek częściowy można rozszerzyć do porządku liniowego.