Ćwiczenia 12: 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. Ile jest relacji równoważności w zbiorze liczb naturalnych, które są jednocześnie częściowymi porządkami?
3.  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.
4. 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?
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 \(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 istnieje dwuelementowa klasa abstrakcji?

Praca domowa - dla chętnych

Zadania 193 i 206. Ta praca domowa nie jest obowiązkowa.

Ćwiczenia 11: logika

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)\),
   b) formuły \(\forall x P(x,y) \to \exists xQ(x,z)\),
   przy wartościowwaniu \(v(y) = 7, v(z)=1\).
   
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 \NN, \leq \rangle\) i \(\langle \ZZ, \leq\rangle\).
4. 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.
   c) Liczba jest pierwsza.
5. 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}}\).

Praca domowa

Zadania 563 d,e i 569 e,g.

Ćwiczenia 10: powtórzenie przed klasówką

Zadania

1. Czy zbiór \(\{0^n1 \mid n \in \NN\}\) ma kres górny (dolny) w zbiorze \(\{0,1\}^{\NN}\) uporządkowanym leksykograficznie?
2. Udowodnić, że nie istnieje słowo w takie, że \(a \cdot w = w \cdot b\).
3. Zdefiniować na listach operację dopisania liczby n na końcu listy.
4. Funkcję \(F : (\NN \to P(\NN)) \to P(\NN)\) jest określona warunkiem
   \[ F(x) = \bigcup \{x(i) \mid i \in \NN\}.\]
   a) Czy F jest różnowartościowa?
   b) Czy F jest na \(P(\NN)\)?
   c) Czy istnieje zbiór \(A \subseteq \NN\) taki, że \(F^{-1}(\{A\})\) jest jednoelementowy?
   d) Czy istnieje zbiór \(A \subseteq \NN\) taki, że \(F^{-1}(\{A\})\) jest czteroelementowy?
5. Podać przykład funkcji \(f : \NN \to \NN\) i zbioru \(X \subseteq \NN\), aby funkcja \(g:\NN\to P(\NN)\) określona wzorem:
   \[ g(i) = (f^i)^{-1}(X)\]
   była różnowartościowa.

Ze względu na klasówkę w tym tygodniu nie ma pracy domowej.

Ćwiczenia 9: porządki cz. 3

Zadania

1. Niech funkcja \(f: P(\NN \times \NN) \to P(\NN \times \NN)\) będzie określona tak:
   \[ f(s) = s \cdot s.
   \]
   Udowodnić, że f jest ciągła ze względu na uporządkowanie przez inkluzję, tj.
   \[ f(\bigcup X) = \bigcup f(X) \]
   dla dowolnej skierowanej rodziny relacji \(X \subseteq P(\NN\times\NN)\).
2. 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\). 
3. W zbiorze funkcji \(\NN \to \{2,3\}\) dany jest następujący porządek częściowy:
   \[ f \leq g \hbox{ wtw. } f^{-1}(\{2\}) \subseteq g^{-1}(\{2\}). \]
   Czy ten porządek:
   a) jest liniowy?
   b) ma elementy minimalne, maksymalne, najmniejsze, największe?
   c) jest kratą zupełną?

Praca domowa

Zadania 406 abdc i 487.

Ćwiczenia 8: porządki cz. 2

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{R}\). Które z nich są izomorficzne? 
2. Rozpatrzmy porządek częściowy \(\langle P(\NN)^{\NN}, \leq \rangle\), gdzie
   \[ f \leq g \hbox{ wtw. } \forall n(f(n) \subseteq g(n)). \]
   a) Wskazać elementy najmniejsze, największe, minimalne, maksymalne.
   b) Czy ten porządek jest liniowy?
   c) Czy ten porządek jest kratą zupełną.
3. Podać przykład częściowego porządku zupełnego, który nie jest kratą zupełną. (Odpowiedź: funkcje częściowe z porządkiem rozszerzania.)
4. Niech \(r\) będzie częściowym porządkiem w A i niech \(f : A \to A\) będzie bijekcją. Rozpatrzmy funkcję \(g: A \times A \to A \times A\):
   \[ g(x,y) = \langle f(x), f(y) \rangle. \]
   Udowodnić, że \(g(r) \subseteq r\) wtedy i tylko wtedy, gdy f jest monotoniczna.

Praca domowa

Zadania 364 i 399 a,c,d.

Ćwiczenia 7: porządki

Zadania

1. (Utajnione) Zadanie z kartkówki. 
2. Podać przykład zbioru częściowo uporządkowanego z dwoma elementami maksymalnymi, jednym minimalnym, bez elementu najmniejszego i z takim czteroelementowym antyłańcuchem, który jest ograniczony z góry, ale nie ma kresu górnego.
3.  Rozpatrzmy częściowe uporządkowanie zbioru \(\{0,1\}^{\NN}\) takie, że
   \[ f \leq g \hbox{ wtw. }\forall x (f(x) \leq g(x)). \]
   a) Czy ten porządek jest liniowy?
   b) Czy istnieje w nim łańcuch nieskończony?
   c) Czy istnieje w nim antyłańcuch nieskończony?
   d) Czy ma element maksymalny, minimalny, najmniejszy, największy?
4. Czy zbiór \(\{01^n \mid n \in \NN\}\) ma kres górny (dolny) w zbiorze \(\{0,1\}^{*}\) uporządkowanym leksykograficznie?

Praca domowa

Zadanie 358 ze zbioru zadań.

Uwaga: Relacja \(r \subseteq A \times A\) jest przeciwzrotna wtedy i tylko wtedy, gdy \(\forall x \in A (\langle a, a\rangle \not\in r)\) .

Ćwiczenia 6: równoliczność, relacje

Zadania

1. Pokazać, że jeśli \(A \sim B\), to \(P(A) \times P(B) \sim \{0,1,2,3\}^A\).
2. Znaleźć przykład pięcioelementowej relacji na zbiorze liczb naturalnych, która jest
   a) przechodnia,
   b) symetryczna,
   c) zwrotna.
3. Czy dla każdego \(A\) i dla każdego \(R \subseteq A \times A\) zachodzi:
   a) \(R^{-1} \cdot R \subseteq id_{A}\),
   b) \(id_{A} \subseteq R^{-1} \cdot R \subseteq \)?
4.  Niech \(\mathcal{R}\) będzie taką rodziną relacji przechodnich, że dla dowolnych \(r, s \in \mathcal{R}\) zachodzi \(r \subseteq s\) lub \(s \subseteq r\). Udowodnić, że \(\bigcup \mathcal{R}\) jest relacją przechodnią.
5. Niech \(\mathcal{R}\) będzie niepustą rodziną relacji w \(A \times B\) i niech \(s \subseteq B \times C\). Udowodnić, że
   \[ (\bigcup R) \cdot s = \bigcup \{ r \cdot s \mid r \in \mathcal{R} \}. \]

Praca domowa

Zadania 156 i 164.

Ćwiczenia 5: funkcje

Zadania

1.  Ile jest funkcji, funkcji częściowych, funkcji różnowartościowych, funkcji na
   a) \(\emptyset \to \emptyset\),
   b) \(\emptyset \to \{ \cdot \}\),
   c) \(\{ \cdot \}\to \emptyset\),
   d) \(\{ \cdot \}\to \{ \cdot \}\),
   e) \(\{ \cdot, \square \}\to \{ \cdot \}\),
   f) \(\{ \cdot \}\to \{ \cdot, \square \}\)?
    
2. Podać przykład \(f : A \to B\), \(X \subseteq A\), \(Y \subseteq B\) takich, że
   a) \(f^{-1}(f(X)) \neq X\),
   b) \(f(f^{-1}(Y)) \neq Y\).
3. Niech \(F : \NN^{\NN} \to P(\NN)\) będzie taka, że \(F(f) = f^{-1}(\{1\})\).
   a) Czy \(F\) jest różnowartościowa?
   b) Czy \(F\) jest na \(P(\NN)\)?
   c) Znaleźć obraz zbioru funkcji stałych.
   d) Znaleźć przeciwobraz zbioru \(\{\{ 10 \}\}\).
4. Pokazać, że funkcja \(\varphi: P(A\times B) \to P(A)^B\) dana wzorem:
   \[ \varphi(\Delta)(b) = \{ a\in A \mid \langle a,b\rangle \in \Delta \}\]
   jest bijekcją.

Praca domowa

Zadania 84 i 151 ze zbioru zadań

Ćwiczenia 4: iloczyn kartezjański, funkcje

Zadania

1. Czy następująca równość zachodzi dla dowolnego zbioru A:
   \[ \bigcap \{P(B) \mid B \subseteq A\} = \{ \bigcap P(B) \mid B\subseteq A\}?\]
2. Kiedy \(A \times B = B \times A\)?
3. Czy dla dowolnych niepustych rodzin \(\mathcal{A}\) i \(\mathcal{B}\) zachodzi \(\bigcup \mathcal{A} \times  \bigcup \mathcal{B} = \bigcup \{ \alpha \times \beta \mid \alpha \in  \mathcal{A}, \beta \in  \mathcal{B}\}\)?
4. Niech \(f:A\to B\). Pokazać, że f jest różnowartościowa wtedy i tylko wtedy, gdy dla każdego C i dla każdych \(g,h: C \to A\) zachodzi \(f \circ g = f\circ h \to g=h\).

Praca domowa

Zadanie 114.

Ćwiczenia 3: suma uogólniona i iloczyn uogólniony

Zadania

1.  a) Czy jeśli \(\mathcal{A} \subseteq \mathcal{B}\), to \(\bigcap \mathcal{A} \subseteq \bigcap \mathcal{B}\)?
   b) Czy jeśli \(\mathcal{A} \subseteq \mathcal{B}\), to \(\bigcap \mathcal{B} \subseteq \bigcap \mathcal{A}\)?
2. Czy dla dowolnych niepustych A, B takich, że \(A \cap B \neq \emptyset\) zachodzi:
   a) \(\bigcup A \cup\bigcup B = \bigcup (A \cup B)\)
   b) \(\bigcap A \cap\bigcap B = \bigcap (A \cap B)\)?
3. Które z poniższych implikaci są prawdziwe dla dowolnych zbiorów X, Y:
   a) jeśli \( P(Y) \subseteq X \), to \(Y \subseteq \bigcup X\),
   b) jeśli \(Y \subseteq \bigcup X\), to \( P(Y) \subseteq X \).
4. Znaleźć \( \bigcup_{t \in \RR_+} A_t \) i \( \bigcap_{t \in \RR_+} A_t \), gdzie \(A_t = (1-\frac{1}{t}, 2 + \sqrt{t})\) dla \(t \in \RR_+\).

Praca domowa

Zadania 40 d, e i 45 ze zbioru zadań.

Ćwiczenia 2: rachunek zbiorów, zbiór potęgowy

Zadania

1. Przypuśćmy, że zbiór A ma n elementów, a zbiór B ma n elementów. Ile elementów mają zbiory \(A \cup B\), \(A \cap B\), \(A - B\)?
2. Czy dla dowolnych zbiorów \(A\), \(B\), \(C\) zachodzą równości:
   a) \(A - (B \cup C) = (A - B) - C\),
   b) \(A - (B - C) = (A - B) \cup C\),
   c) \( A \cap (B \cup C) = (A \cap B) \cup (A \cap C) \)?
3. Sprawdzić, czy dla dowolnych zbiorów w \(A\), \(B\), \(C\) zachodzi następująca implikacja:
   a) jeśli \( A - B = B - A \), to \( A = B\),
   b) jeśli \(C - B \subseteq C - A\), to \(A \subseteq B\).
   
4. Zbadać, czy dla dowolnych \(A\), \(B\) zachodzi:
   a) \(P (A \cup B) = P(A) \cup P(B)\),
   b) \(P (A \cap B) = P(A) \cap P(B)\).
5. Udowodnić, że dla dowolnych \(A\), \(B\) zachodzi warunek: jeśli \(A \cap B = \emptyset\), to \(P(A) \cap P(B) = \{ \emptyset \}\).

Praca domowa 

Zadania 27 i 31.

Ćwiczenia 1: powtórzenie z logiki, indukcja

Zadania

1. Zaznaczyć na rysunku zbiory:
   a) \(\{\langle x, y\rangle \in \mathbb{R}^2 \mid x^2 + y^2 >1  \to y+x > 0\}\),
   b) \[\{\langle x, y\rangle \in \mathbb{R}^2 \mid(x^2 + y^2 >1 ) \to (x^2 + y^2 \leq 2) \wedge ( \neg (x \cdot y = 0) \to |y| = |x|)  \}\]
   c) \(\{\langle x, y\rangle \in \mathbb{R}^2 \mid  (\forall z(z+y < 0)) \to y+x<0 \}\),
   d) \(\{\langle x, y\rangle \in \mathbb{R}^2 \mid  x^2 + y^2 >1  \to \exists z (x^2 + (y-z)^2 \leq \frac{1}{4})\}\).
2. Zaznaczyć na rysunku zbiory:
   a) \( \{z \in \mathbb{R} \mid \forall x \exists x (x=1)\} \),
   b) \( \{z \in \mathbb{R} \mid \exists x \forall x (x=1)\} \),
   c) \( \{x \in \mathbb{R} \mid \forall x \exists x (x=1)\} \).
3. Udowodnić, że \(1 + 2 + 4 + \ldots + 2^n = 2^{n+1} -1\).

Praca domowa

Zadania 4b i 7c ze zbioru zadań.