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).\]
Zadania
- Znaleźć moc zbioru funkcji nierosnących z \(\mathbb{N}\) do \(\mathbb{N}\).
- Znaleźć moc zbioru wszystkich relacji równoważności w \(\mathbb{N}\).
- 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\).
- 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?
- 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}\}\)?
- Jaka jest moc zbioru \(\mathbb{R}^\mathbb{N}\)?
- 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
- Jaka jest moc rodziny tych relacji równoważności w \(\mathbb{N}\), które mają skończenie wiele klas abstrakcji?
- 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!
Zadania
- Pokazać, że \(P(A) \sim \{0,1\}^{A}\).
- Pokazać, że jeśli \(A \sim B\), to \(P(A) \sim P(B)\).
- Znaleźć moc zbioru skończonych podzbiorów \(\mathbb{N}\).
- Znaleźć moc zbioru ciągów liczb wymiernych stałych od pewnego miejsca.
- Znaleźć moc zbioru funkcji z \(\mathbb{N}\) do \(\mathbb{N}\).
- Znaleźć moc zbioru funkcji niemalejących z \(\mathbb{N}\) do \(\mathbb{N}\).
Praca domowa
- 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.
- Znaleźć moc zbioru wszystkich ciągów liczb wymiernych, które są zbieżne do zera.
Zadania
- Jaka jest najmniejsza i największa (w sensie zawierania) relacja równoważności w zbiorze \(A\)?
- Czy relacja równoważności może być częściowym porządkiem?
- 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.
- 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\).
- 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?
- 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.
Zadania
- 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ą?
- Udowodnij, że \(\langle A \leadsto B, \leq \rangle\) jest częściowym porządkiem zupełnym.
- 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)\).
- 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.
- 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
- 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\).
- 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\).
- Dla chętnych: skończyć zadanie 4 z zajęć.