Ćwiczenia 11: relacje i równoważności i moce

Zadania

1. W zbiorze \(\RR[x]\) wielomianów jednej zmiennej o współczynnikach rzeczywistych określmy relację równoważności:
   \[ f r g \hbox{ wtw. } f - g \hbox{ jest funkcją liniową.} \]
   Znaleźć moc zbioru ilorazowego i moc każdej klasy abstrakcji.
2. Pokazać, że jeśli moc A jest równa \(\mathfrak{m}\) oraz \(0 \neq \mathfrak{n} \leq \mathfrak{m}\), to istnieje relacja równoważności w A spełniająca warunek \(| A_{/r}| = \mathfrak{n}\).
3. Znaleźć moc zbioru funkcji ciągłych \(\RR \to \RR\).
4. Znaleźć moc zbioru Cantora.
5. Niech \(\sim\) będzie relacją równoważności w \(\NN^{\NN}\) określoną następująco:
   \[ f \sim g \hbox{ wtw. } |f(n) - g(n)| \hbox{ jest różnowartościowa.} \]
   Jaka jest moc zbioru ilorazowego?
6. Znaleźć moc zbioru wszystkich funkcji wyboru dla \(P(\NN) - \{\emptyset\}\).

Praca domowa

Zadania 269 i 305.
Zadanie do przemyślenia pod choinką: Udowodnić, że każdy porządek częściowy można rozszerzyć do porządku liniowego.

Ćwiczenia 10: relacje równoważności

Zadania

1. Jaka jest najmniejsza i największa (w sensie zawierania) relacja równoważności z 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 P(\NN) \times P(\NN)\) będzie taka, że
   \[ \langle X, Y \rangle \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\).
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?
   e) Znaleźć moc zbioru \(\NN \to \NN_{/r}\).
5. Niech A będzie niepustym zbiorem i niech \(f:\NN \to \NN\).
   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?
   c) Podać przykłąd takich A, f, że r  ma nieskończenie wiele skończonych klas abstrakcji, każda o innej liczbie elementów. Można zrobić rysunek.

Praca domowa

Zadania 179 i 194 ze zbioru zadań.

Ćwiczenia 8: moce cz. 1

Zadania

1. Pokazać, że \( (A^B)^C \sim A^{B \times C}\).
2. Znaleźć moc zbioru skończonych podzbiorów \(\NN\).
3. Znaleźć moc zbioru ciągów liczb wymiernych stałych od pewnego miejsca.
4. Znaleźć moc zbioru funkcji z \(\NN\) do \(\NN\).
5. Znaleźć moc zbioru funkcji niemalejących z \(\NN\) do \(\NN\).

Praca domowa

Zadania 262 i 327.

Ćwiczenia 7: porządki cz. 2

Zadania

1. 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ą?
2. Udowodnij, że \(\langle A \leadsto B, \leq \rangle\) jest częściowym porządkiem zupełnym.
3. 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)\).
4. 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.
   Czy można wybrać f tak, aby punkt stały f nie istniał?
5. 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

Zadania 355 i 348 (pytanie o bijekcję tylko dla chętnych).

Ćwiczenia 6: porządki cz. 1

Zadania

1.  Niech funkcja \(\varphi: P(\NN \times \NN) \to P(\NN \times \NN)\) będzie taka, że
   \[ \varphi(r) = \bigcap \{ r^n \mid n > 0 \}. \]
   Niech Z to rodzina relacji zwrotnych w \(\NN\). Znaleźć \(\varphi(Z)\).
2. (Utajnione) Zadanie z kartkówki.
3. 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.
4. 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?
5. Czy zbiór \(\{01^n \mid n \in \NN\}\) ma kres górny (dolny) w zbiorze \(\{0,1\}^{\NN}\) uporządkowanym leksykograficznie?
6. Czy zbiór \(\{0^n1 \mid n \in \NN\}\) ma kres górny (dolny) w zbiorze \(\{0,1\}^{\NN}\) uporządkowanym leksykograficznie?

Warianty - do przemyślenia w domu dla chętnych

1. Zadanie 1 dla rodziny relacji przechodnich, symetrycznych, antysymetrycznych, ...
2. Zadanie 1: znaleźć \(\varphi^{-1}(Z)\).
3. Zadanie 4: jaki dostaniemy porządek, gdy utożsamimy ciągi zerojedynkowe z funkcjami charakterystycznymi podzbiorów liczb naturalnych?

Praca domowa

Zadania 351 i 353.

Ćwiczenia 5: relacje

Zadania

1. Czy dla każdego A i dla każdej relacji \(r \subseteq A \times A\) zachodzi
   a) \(r^{-1} \cdot r \subseteq I_A\),
   b) \(I_A \subseteq r^{-1} \cdot r\)?
2. Niech \(R, S \subseteq A \times A\). Czy z tego, że \( R \cdot S = S \cdot R\) wynika, że \(R = S\) lub \(R = I_A\), lub \(S = I_A\)?
3. Podać przykład pięcioelementowej relacji na zbiorze liczb naturalnych, która jest
   a) symetryczna,
   b) przechodnia,
   c) zwrotna.
4. Niech \(\mathcal{R}\) będzie taką niepustą rodziną relacji przechodnich w zbiorze \(A\), ż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 \(\varphi : \NN \to P(\NN \times \NN)\) będzie zdefiniowana tak:
   \[ \varphi(n) = \{\langle x, n\rangle \mid x \leq n\} \cup \{\langle n, y\rangle \mid n \leq y\}.\]
   a) Znaleźć \(\varphi^{-1}(\mathcal{T})\), gdzie \(\mathcal{T}\) to rodzina relacji przechodnich w \(\NN\).
   b) Czy \(\bigcup \varphi(\NN)\) jest relacją przechodnią w \(\NN\)?
6. Niech funkcja \(\varphi :  P(\NN \times \NN)\) będzie określona tak:
   \[ \varphi(r) = \bigcap \{ r^n \mid n > 0\}.\]
   a) Czy \(\varphi\) jest różnowartościowa?
   b) Niech \(\mathcal{Z}\) oznacza rodzinę wszystkich relacji zwrotnych w \(\NN\). Znaleźć \(\varphi(\NN)\).

Praca domowa

Zadanie 474 a, b, e oraz zadanie 71.

Ćwiczenia 4: funkcje

Zadania

1.  Pokazać, że funkcja \(\varphi : P(A)^B \to P(A \times B)\), taka że dla dowolnego \(f : B \to  P(A)\) zachodzi
   \[ \varphi(f) = \{ \langle a, b \rangle \in A \times B \mid a \in f(b)\},\]
   jest różnowartościowa i na.
2. Zdefiniujmy funkcję \( F : (\NN \to \NN) \to (P(\NN) \to P(\NN))\) wzorem
   \[ F(f)(X) = f(X).\]
   a) Czy F jest na?
   b) Czy F jest różnowartościowa?
3. Znaleźć przykład takiej funkcji \(f: \NN\to\NN\), że przeciwobraz każdego zbioru jednoelementowego jest
   a) jednoelementowy,
   b) dwuelementowy,
   c) nieskończony.
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?

Praca domowa

Zadanie 137 i zadanie 147.

Ćwiczenia 3: iloczyn kartezjański, funkcje

Zadania

1.  Kiedy \(A \times B = B \times A\)?
2. Czy dla dowolnych niepustych rodzin \(\mathcal{A}\) i \(\mathcal{B}\) zachodzi:
   a) \(\bigcap \mathcal{A} \times  \bigcap \mathcal{B} = \bigcap \{ \alpha \times \beta \mid \alpha \in  \mathcal{A}, \beta \in  \mathcal{B}\}\),
   b) \(\bigcup \mathcal{A} \times  \bigcup \mathcal{B} = \bigcup \{ \alpha \times \beta \mid \alpha \in  \mathcal{A}, \beta \in  \mathcal{B}\}\)?
3. 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 \}\)?
4. 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\).
5. 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)\)?

Praca domowa

Zadanie 132 i zadanie 103 ze zbioru zadań.

Ćwiczenia 2: sumy uogólnione, iloczyn uogólnione

Zadania

1. Udowodnić, że \(\bigcup P(A) = A\) dla dowolnego A.
2. a) Czy jeśli \(\mathcal{A} \subseteq \mathcal{B}\), to \(\bigcup \mathcal{A} \subseteq \bigcup\mathcal{B}\)?
   b) Czy jeśli \(\bigcup \mathcal{A} \subseteq \bigcup \mathcal{B}\), to \(\mathcal{A} \subseteq \mathcal{B}\)?
3.  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}\)?
4. Czy dla dowolnych niepustych A, B takich, że \(A \cap B \neq \emptyset\) zachodzi:
   a) \(\bigcap A \cap\bigcap B = \bigcap (A \cap B)\),
   b) \(\bigcap A \cap\bigcap B = \bigcap (A \cup B)\)?
5. Które z równości zachodzą dla dowolnego A:
   a) \(\bigcap \{P(B) \mid B \subseteq A \} = \{ \bigcap P(B) \mid B \subseteq A \} \),
   b) \(\bigcup \{P(B) \mid B \subseteq A \} = \{ \bigcup P(B) \mid B \subseteq A \} \)?
6. 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 34 i 38 ze zbioru zadań na stronie wykładu.

Ćwiczenia 1: 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 \cup B \cup C) - (A \cup B) = C\),
   d) \( 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 \(A \cup B = C\), to \(C - B = A - B\),
   c) 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. Która z implikacji jest prawdziwa dla dowolnych zbiorów \(A\), \(B\):
   \[ A \subseteq B \hbox{ wtw. } P(A) \subseteq P(B) ? \]

Praca domowa

1. Czy dla dowolnych zbiorów A, B, C zachodzi równoważność:
   \[ A \cap B = A  \hbox{ wtw. } A \cup B \cup C = (C-A) \cup B. \]
2. Dla każdej z poniższych implikacji sprawdź, czy jest ona prawdziwa:
   a) \(A \cup B \subseteq A \cup C \to A - C \subseteq A - B\),
   b) \(A \cap B \subseteq A \cap C \to A - C \subseteq A - B\).