Ćwiczenia 14: 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 zbiór \(\langle \NN^{*}, \leq_{lex}\rangle\) jest dobrze ufundowany?
3. Czy zbiór \(\langle \NN^{2}, \leq_{lex}\rangle\) jest dobrze ufundowany?
4. Podać trzy przykłady zbiorów dobrze ufundowanych mocy \(\aleph_{0}\) takich, że żadne dwa nie są izomorficzne.
5. Udowodnić, że jeśli \(\langle A, \leq_A \rangle\), \(\langle B, \leq_B \rangle\) są dobrze ufundowane i \( A \cap B \neq \emptyset\), to porządek \(\langle A \cup B, \leq\>\) zdefiniowany tak:
   \[ x \leq y \hbox{ wtw. } x \leq_A y \vee x \leq_B y \vee (x \in A \wedge y \in B)\]
   jest dobrze ufundowany.
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 \NN}\) będzie dowolnym ciągiem elementów. Udowodnić, że istnieją \(i < j\) takie, że \(a_i \leq a_j\).

Ćwiczenia 13: moce cz. 2

Zadania

1. Znaleźć moc zbioru skończonych podzbiorów \(\NN\).
2. Znaleźć moc zbioru funkcji z \(\NN\) do \(\NN\).
3. Znaleźć moc zbioru ciągów liczb wymiernych stałych od pewnego miejsca.
4. Znaleźć moc zbioru funkcji niemalejących z \(\NN\) do \(\NN\).
5. Znaleźć moc zbioru funkcji nierosnących z \(\NN\) do \(\NN\).
6. Znaleźć moc zbioru wszystkich relacji równoważności w \(\NN\).

Ciekawe zadanie dla rozrywki

 Niech \(r\) będzie taką relacją w zbiorze \(\QQ^\NN\), że
\[ \langle f, g\rangle \in r \hbox{ wtw. różnica }f-g\hbox{ jest zbieżna do zera.}\] Znaleźć moce klas abstrakcji relacji \(r\). Znaleźć moc zbioru ilorazowego.

Ćwiczenia 12: moce cz. 1

Zadania

1. Pokazać, że \(\NN \times \NN \sim \NN\).
2. Pokazać, że \(\QQ \sim \NN\). 
3. Pokazać, że \(\RR \sim  (0,1)\).  
4. Pokazać, że \((0,1) \sim(0,1) \times (0,1)\).
5. Jakiej mocy jest zbiór wszystkich prostych na płaszczyźnie?
6. Niech \(\mathcal{R}\) oznacza zbiór relacji równoważności w \(\NN\). Jakiej mocy są zbiory:
   a) \(A =\{ r \in \mathcal{R} \mid [0]_r = \NN - \{7\}\}\),
   b) \(B =\{ r \in \mathcal{R} \mid [0]_r = \NN - \{7,49\}\}\),
   c) \(C =\{ r \in \mathcal{R} \mid [0]_r = \{7, 49\}\}\).
7. Pokazać, że \(\RR \not\sim \NN\).
8. Udowodnić, że jeśli A jest dowolnym zbiorem parami rozłącznych przedziałów na prostej, to moc zbioru A jest mniejsza lub równa \(\aleph_0\).
9. Niech P będzie zbiorem wszystkich prostokątów na płaszczyźnie i niech \(r\) będzie relacją podobieństwa trójkątów (to jest relacja równoważności w P). Znaleźć moc zbioru \(P/_r\).

Praca domowa

Zadania 271, 273.
Dla chętnych: zadanie 256.

Ćwiczenia 11: 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 istnieje relacja równoważności w \(\NN\), która ma:
   a) dokładnie dwie klasy abstrakcji po 37 elementów,
   b) dwie klasy abstrakcji po 37 elementów, trzy klasy abstrakcji po 33 elementy i jedną nieskończoną klasę abstrakcji,
   c) nieskończenie wiele klas abstrakcji, każda o nieskończonej liczbie elementów.
3. Niech \(R \subseteq \NN^\NN \times \NN^\NN\) będzie określona tak:
   \[ \langle f, g \rangle \hbox{ wtw. } \forall n(f(n) - g(n) \hbox{ jest liczbą parzystą. })\]
   a) Pokazać, że R jest relacją równoważności.
   b) Opisać klasę abstrakcji funkcji identycznościowej.
   c) Czy zbiór \((\NN\to\NN)/_R\) jest nieskończony?
   d) Czy zbiór \(\{f: \NN\to \NN \mid f(0) = 2\}\) jest klasa abstrakcji tej relacji?
4. Niech \(r \subseteq \NN^\NN \times \NN^\NN\) będzie określona tak:
   \[ \langle f, g \rangle \hbox{ wtw. } f(\NN) = g(\NN).\]
   a) Udowodnić jednym krótkim zdaniem, że r jest relacją równoważności.
   b) Znaleźć \([\lambda x.1]_r\) i \([id_{\NN}]_r\).
   c) Czy zbiór wszystkich funkcji różnowartościowych jest klasą abstrakcji tej relacji?
   d) Czy istnieje dwuelementowa klasa abstrakcji?
5. Niech \(r\) będzie relacją równoważności w \(\NN\) i niech \(f : \NN \times \NN \to P(\NN)\) będzie taka, że:
   \[f(\langle x,y \rangle) = [x]_r \cup [y]_r\]
   a) Czy f jest różnowartościowa?
   b) Czy f jest na \(P(\NN)\)?
   c) Znaleźć \(f^{-1}(\{ [3]_r \})\).
   d) Znaleźć \(f(r)\).
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 \hbox{ wtw. } \exists n \in \NN (f^n(x) = y \hbox{ lub } f^n(y) = x) \]
   jest relacją równoważności.
   b) Czy prawdziwe jest twierdzenie odwrotne, tj. jeśli r jest relacją równoważności, to f musi być różnowartościowa?

Praca domowa

Zadania 180, 186.
Dla chętnych: zadanie 192.

Ćwiczenia 10: logika pierwszego rzędu

Zadania

1.  W strukturze \(\mathcal{A} =\langle \NN, P^{\mathcal{A}},Q^{\mathcal{A}}\rangle\), gdzie:
   \( \langle a,b \rangle \in P^{\mathcal{A}}\) wtedy i tylko wtedy, gdy \(a+b \geq 6\),
   \( \langle a,b \rangle \in Q^{\mathcal{A}}\) wtedy i tylko wtedy, gdy \(b = a + 2\),
   wyznaczyć wartość
   a) formuły \(\forall x P(x,y) \to \exists xQ(x,y)\), przy wartościowwaniu \(v(y) = 7\),
   b) formuły \(\forall x P(x,y) \to \forall xQ(x,y)\), przy wartościowwaniu \(v(y) = 7\),
   c) formuły \(\forall x P(x,y) \to \exists xQ(x,z)\), przy wartościowwaniu \(u(y) = 3, u(z) = 2\).
   
2. Podać przykład modelu i wartościowania, przy którym formuła
   \[ P(x,f(x)) \to \forall x \exists y P(f(y), x) \]
   jest a) spełniona b) niespełniona.
3. Dla każdej z następujących par struktur wskaż formułę prawdziwą w jednej z nich a w drugiej nie (dla utrudnienia można oczekiwać formuły otwartej spełnialnej w jednej strukturze, a w drugiej nie):
   a) \(\langle \QQ, +, \cdot, 0, 1\rangle\) i \(\langle \RR, +, \cdot, 0, 1\rangle\),
   b) \(\langle \NN, +, 0 \rangle\) i \(\langle \NN, \cdot, 1\rangle\),
   c) \(\langle P_2, \parallel \rangle\) i \(\langle P_2, \bot \rangle\), gdzie \(P_2\) to zbiór prostych w \(\RR^2\),
   d) \(\langle P_2, \bot \rangle\) i \(\langle P_3, \bot \rangle\), gdzie \(P_2\) to zbiór prostych w \(\RR^2\), a \(P_3\) to zbiór prostych w \(\RR^3\),
   e) \(\langle \NN, \leq \rangle\) i \(\langle \ZZ, \leq\rangle\).
4. Sygnatura \(\Sigma\) składa się z symbolu równości i dwóch jednoargumentowych symboli relacyjnych R, S i jednego jednoragumentowego symbolu funkcyjnego f.
   a) Napisać zdanie prawdziwe dokładnie w tych modelach \(\mathcal{A} =\langle A, R^{\mathcal{A}},S^{\mathcal{A}}, f^{\mathcal{A}}\rangle\), w których obraz zbioru \(R^{\mathcal {A}}\) przy funkcji \(f^{\mathcal {A}}\) zawiera się w zbiorze \(S^{\mathcal {A}}\).
   b) Napisać zdanie prawdziwe dokładnie w tych modelach \(\mathcal{A} =\langle A, R^{\mathcal{A}},S^{\mathcal{A}}, f^{\mathcal{A}}\rangle\), w których zbiór \(S^{\mathcal {A}}\) jest przeciwobrazem zbioru \(R^{\mathcal {A}}\) przy funkcji \(f^{\mathcal {A}}\).
5. 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 liczby b przez c.

Praca domowa

1. Dla każdej z następujących par struktur wskaż formułę prawdziwą w jednej z nich a w drugiej nie (dla utrudnienia można oczekiwać formuły otwartej spełnialnej w jednej strukturze, a w drugiej nie):
   a) \(\langle \RR, +, \cdot, 0, 1\rangle\) i \(\langle P(\NN), \cup, \cap, \emptyset, \NN\rangle\),
   b) \(\langle \NN, +, 0, \rangle\) i \(\langle \{a,b\}^*, \cdot, \epsilon \rangle\),
   c) \(\langle \ZZ, \leq \rangle\) i \(\langle \QQ, \leq \rangle\).
2. Sygnatura \(\Sigma\) składa się z symbolu równości i dwóch dwuargumentowych symboli relacyjnych R, S. Napisać zdanie prawdziwe dokładnie w tych modelach \(\mathcal{A} =\langle A, R^{\mathcal{A}},S^{\mathcal{A}}\rangle\), w których:
   a) złożenie relacji \(R^{\mathcal{A}}\) z relacją \(S^{\mathcal{A}}\) jest identyczne ze złożeniem relacji \(S^{\mathcal{A}}\) z relacją \(R^{\mathcal{A}}\),
   b) relacja \(S^{\mathcal{A}}\) jest najmniejszą relacją symetryczną zawierającą \(R^{\mathcal{A}}\).

Ćwiczenia 9: rachunek zdań

Zadania

1. Znaleźć, o ile istnieje, taką formułę zdaniową \(\alpha\), aby następujące formuła była tautologią rachunku zdań:
   a) \( (\alpha \to p) \to (p\to q) \),
   b)\( ((r \to (\neg q \wedge p)) \to \alpha) \to (\alpha \wedge (p\to q) \wedge r) \).
2.  Udowodnić, że dla dowolnej funkcji \(f: \{0,1\}^k \to \{0,1\}\) istnieje formuła zdaniowa \(\alpha\), w której występują tylko zmienne zdaniowe \(p_1, ...,p_k\) o tej własności, że dla dowolnego wartościowania zdaniowego \(v\) zachodzi:
   \[ [\alpha]_v = f(v(p_1), \ldots, v(p_k))\]
   Innymi słowy: formuła \(\alpha\) definiuje funkcję \(f\).
3. Czy następujące zbiory formuł są spełnialne?
   a) \( \{ p \to \neg q, q \to \neg r, r \to \neg p \} \),
   b) \( \{ p\to q, q \to r, r \vee s \leftrightarrow \neg q \} \),
   c) \( \{ s \to p, p \vee \neg q, \neg (s \wedge p), s \} \).
4. Zbadać, czy następujące rozumowania są logicznie poprawne. Każde stwierdzenie trzeba zastąpić zmienną zdaniowa, następnie należy stwierdzić czy konkluzja wynika z koniunkcji przesłanek.
   a) Jeśli Jones jest komunistą, to Jones jest ateista. Jonest jest ateistą. Zatem Jones jest komunistą.
   b) Jeśli temperatura i ciśnienie nie zmieniają się, nie ma deszczu. Temperatura nie zmieniła się. Zatem jeśli spadł deszcz, to ciśnienie się zmieniło.

Praca domowa

Zadanie 115 ze zbioru zadań.

Ćwiczenia 8: porządki cz. 2

Zadania

1.  Udowodnić, że jeśli w porządku częściowym każdy dwuelementowy podzbiór ma kres górny, to każdy niepusty podzbiór ma kres górny.
2. Podać przykład zupełnego porządku częściowego, który nie jest kratą zupełną. (Wskazówka: takim porządkiem jest zbiór funkcji częściowych z relacją zgodności.)
3. 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\), że \(a \leq b\).

Praca domowa

Zadania 381 i 366 (bez pytania o bijekcję).

Dla chętnych: zadanie 386. Definicja: Krata - częściowy porządek, w którym każdy dwuelementowy podzbiór ma kres górny.