Zadania
- 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.
- Sformułować poprawne zaprzeczenia stwierdzeń:
a) Liczby m i n są pierwsze.
b) Liczby m in są względnie pierwsze.
- 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\).
- 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) \).
Zadania
- 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\).
- 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) \).
- Udowodnić, że każdy porządek częściowy można rozszerzyć do porządku liniowego.
Praca domowa (nieobowiązkowa)
- 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}\).
Zadania
- 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?
- Czy zbiory \(\QQ \times (0,1]\) i \((0,1] \times \QQ\) uporządkowane leksykograficznie są izomorficzne?
- Czy zbiór \(\langle \mathbb{N}^*, \leq_{lex}\rangle\) jest dobrze ufundowany?
- Czy zbiór \(\langle \mathbb{N}^2, \leq_{lex}\rangle\) jest dobrze ufundowany?
- Podaj trzy przykłady zbiorów dobrze uporządkowanych mocy \(\aleph_0\) tak, aby żadne dwa nie były ze sobą izomorficzne.
- 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\).
- 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.
- 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). \)
- 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
-
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?
- 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).\]