Ćwiczenia 10: moce cz. 2

Zadania

1. Znaleźć moc zbioru funkcji nierosnących z \(\mathbb{N}\) do \(\mathbb{N}\).
2. Znaleźć moc zbioru wszystkich relacji równoważności w \(\mathbb{N}\).
3. 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\).
4.  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?
5. 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}\}\)?
6. Jaka jest moc zbioru \(\mathbb{R}^\mathbb{N}\)?
7. 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

1. Jaka jest moc rodziny tych relacji równoważności w \(\mathbb{N}\), które mają skończenie wiele klas abstrakcji?
   
2. 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!

Ćwiczenia 9: równoliczność, moce

Zadania

1. Pokazać, że \(P(A) \sim \{0,1\}^{A}\).
2. Pokazać, że jeśli \(A \sim B\), to \(P(A) \sim P(B)\).
3. Znaleźć moc zbioru skończonych podzbiorów \(\mathbb{N}\).
4. Znaleźć moc zbioru ciągów liczb wymiernych stałych od pewnego miejsca.
5. Znaleźć moc zbioru funkcji z \(\mathbb{N}\) do \(\mathbb{N}\).
6. Znaleźć moc zbioru funkcji niemalejących z \(\mathbb{N}\) do \(\mathbb{N}\).

Praca domowa

1. 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.
2. Znaleźć moc zbioru wszystkich ciągów liczb wymiernych, które są zbieżne do zera.

Ćwiczenia 8: 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 relacja równoważności może być częściowym porządkiem?
3. 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.
4. 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\).
5. 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?
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 \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.

Ć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.
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

1. 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\).
   
2. 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\).
3. Dla chętnych: skończyć zadanie 4 z zajęć.

Wykład "Ataki na aplikacje internetowe"

Zapraszam na wykład mojego kolegi z pracy Michała Kołodziejskiego pt. "Ataki na aplikacje internetowe". Wykład odbędzie się w czwartek 20 listopada 2014 roku o godzinie 14 (bez kwadransa) w sali 5070.

Ćwiczenia 6: porządki

Zadania

1. W zbiorze \(\{1,2,3,5,12,15,18,180\}\) uporządkowanym przez relację podzielności wskazać elementy minimalne, maksymalne, najmniejsze, największe. Czy istnieją w tym zbiorze pięcioelementowe łańcuchy? a trzyelementowe antyłańcuchy? Wskaż kres dolny zbioru \(\{3,12\}\) oraz kres górny zbioru \(\{2,5\}\).
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\}^{\mathbb{N}}\):
   \[ 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 antyłańcuch nieskończony?
   d) Czy ma element największy, najmniejszy, minimalny, maksymalny?
4. Czy zbiór \(\{01^n \mid n \in \mathbb{N}\}\) ma kres górny (dolny) w zbiorze \(\{0,1\}^{*}\) uporządkowanym leksykograficznie?
5. Czy zbiór \(\{0^n1 \mid n \in \mathbb{N}\}\) ma kres górny (dolny) w zbiorze \(\{0,1\}^{*}\) uporządkowanym leksykograficznie?
6. Dany jest następujący częściowy porządek w zbiorze \(P(\mathbb{N} - \{\emptyset\}\):
   \[X \leq Y \hbox{wtw.} ((\min(X) < \min(Y))
   \vee (\min(X) = \min(Y) \wedge X \subseteq Y).\]
   a) Czy ten porządek jest liniowy?
   b) Czy istnieje w tym zbiorze nieskończony ciąg malejący?
   c) Wskaż elementy minimalne, maksymalne, największe, najmniejsze.

 Praca domowa

1. Jeśli \(\leq\) jest cześciowym porządkiem w A, to relację < nazywamy ostrym uporządkowaniem wyznaczonym przez \(\leq\). Pokazać, że ostre uporządkowania wyznaczone przez porządki częściowe to dokładnie te relacje, które są przechodnie i przeciwzrotne.
2. Niech \(\langle X, r \rangle, \langle Y, s \rangle \) będą niepustymi zbiorami częściowo uporządkowanymi. Pokazać, że
   a) \(\langle X \oplus Y, r \oplus s \rangle \) jest zbiorem częściowo uporządkowanym bez elementu największego.
   b) Dla dowolnego \(a \in X \oplus Y\) element a jest minimalny w \(\langle X \oplus Y, r \oplus s \rangle \) wtedy i tylko wtedy, gdy a jest elementem minimalnym w \(\langle X, r \rangle\) lub \(\langle Y, s \rangle \).

Ćwiczenia 5: relacje

Zadania

1.  Znaleźć przykład pięcioelementowej relacji na zbiorze liczb naturalnych, która jest
   a) przechodnia,
   b) symetryczna,
   c) zwrotna.
2. Dla jakich relacji \(r \subseteq A \times A\) zachodzą równości \(r \cdot r^{-1} = r^{-1} \cdot r = 1_A\)?
3. Udowodnić, że \(r^+ = \bigcup_{n > 0} r^n\).
4. Niech \(r, s \subseteq A \times A\). Czy dla dowolnych relacji \(r,s\) prawdziwa jest równość \((r^*)^{-1} = (r^{-1})^*\)?

Praca domowa

1. 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ą.
2. Niech\(\varphi : P(\mathbb{N}) \to P(P(\mathbb{N}) \times P(\mathbb{N}))\) będzie taką funkcją, że dla dowolnego \(Z \in P(\mathbb{N})\)
   \[\varphi(Z) = \{\langle X, Y\rangle \mid Z \subseteq X \cap Y\}.\]
   a) Czy \(\varphi\) jest różnowartościowa?
   b) Czy \(\varphi\) jest na?
   c) Która z poniższych równości zachodzi dla dowolnych \(Z_1, Z_2 \in P(\mathbb{N})\)
   • \(\varphi(Z_1 \cap Z_2) = \varphi(Z_1) \cap \varphi(Z_2)\),
   • \(\varphi(Z_1 \cup Z_2) = \varphi(Z_1) \cup \varphi(Z_2)\)?

Ćwiczenia 4: funkcje cz. 2

Zadania

1. Niech \(\alpha : \mathbb{N} \times \mathbb{N} \to  \mathbb{N}\) będzie bijekcją i niech \(g : P(\mathbb{N}) \to (\mathbb{N} \to P(\mathbb{N}))\) będzie taką funkcją, że
   \[ g(A)(n) = \{ i \in \mathbb{N} \mid \alpha(n,i) \in A \}. \]
   Udowodnić, że g jest bijekcją.
2. Podać przykład takiej funkcji \( f : \mathbb{N} \to  \mathbb{N}\) i zbioru \( X \subseteq \mathbb{N}\), aby funkcja \(g: \mathbb{N} \to  P(\mathbb{N})\) określona wzorem
   \[ g(i) = (f^i)^{-1}(X) \]
   była różnowartościowa.
3. Podać przykład pary funkcji \( f, g : \mathbb{N} \to  \mathbb{N}\) spełniających wszystkie poniższe warunki:
   a) \(\forall x( g(x) \neq x)\),
   b) \(g \circ  g = id_{\mathbb{N}}\),
   c) \(g \circ f = f\),
   d) f jest funkcją na \(\mathbb{N}\),
   e) obrazem zbioru liczb naturalnych parzystych jest zbiór liczb naturalnych nieparzystych.
4. Skonstruować bijekcję \(f : \mathcal{D} \times (\mathcal{E} \oplus \mathcal{H}) \to  (\mathcal{D} \times \mathcal{E}) \oplus (\mathcal{D} \times \mathcal{H})\).
5. Czy istnieje taka bijekcja \( f : \mathbb{N} \to  \mathbb{N}\), że dla dowolnych \(m,n \in \mathbb{N}\) jeśli \(n \geq 1\), to \(f^n(m) \neq m\)?
6. Permutacją zbioru X nazwiemy dowolną bijekcję \(\pi : X \to X\). Powiemy, że funkcja \( f : \mathbb{N} \to  \mathbb{N}\) jest niezmiennicza ze względu na permutacje wtedy i tylko wtedy, gdy dla każdej permutacji  \( \pi : \mathbb{N} \to  \mathbb{N}\) oraz dla każdej liczby \(n \in \mathbb{N}\) zachodzi równość \(f(\pi(n)) = \pi (f(n))\). Znaleźć zbiór wszystkich funkcji niezmienniczych ze względu na permutacje.

Praca domowa

1. Niech \( P'(\mathbb{N}) = P(\mathbb{N})- \{\emptyset\}\) i niech \( f : P'(\mathbb{N}) \times P'(\mathbb{N}) \to P(\mathbb{N} \times \mathbb{N})\) będzie taka, że \(f(\langle C, D\rangle) = C \times D\).
   a) Czy f jest różnowartościowa?
   b) Czy f jest na \(P(\mathbb{N} \times \mathbb{N})\)?
   c) Znaleźć \( f^{-1}(P(\mathcal{P} \times \mathcal{P}))\), gdzie \(\mathcal{P}\) to zbiór liczb parzystych.
   
2. Dla \(a \in \mathbb{N}\) określamy \(a^*: ( \mathbb{N} \to  \mathbb{N}) \to \mathbb{N}\) wzorem \(a^*=\lambda f.f(a)\). Czy funkcja \(\lambda a:\mathbb{N}.a^*\) jest różnowartościowa i czy jest na \(( \mathbb{N} \to  \mathbb{N}) \to \mathbb{N}\)?

Ćwiczenia 3: funkcje

Zadania

1. Ile jest funkcji, funkcji częściowych, funkcji na, funkcji różnowartościowych:
   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. Niech \(f: A \to B\). Pokazać, że \(f\) jest różnowartościowa wtedy i tylko wtedy, gdy dla każdego zbioru \(C\) i dla każdych funkcji \(g,h:C\to A\) zachodzi implikacja
   \[f \circ g = f\circ h \to g=h\].
3. Podać przykład \(f : A \to B, X\subseteq A, Y \subseteq B\) takich, że
   a) \(\vec{f^{-1}}(\vec{f}(X)) \neq X\),
   b) \(\vec{f}(\vec{f^{-1}}(X)) \neq X\),
   c) \(\vec{f}(C \cap D) = \vec{f}(C)\cap \vec{f}(D)\).
4. Niech \( \varphi : \mathbb{N} \times \mathbb{N} \to \mathbb{N}\) będzie taka, że
   \[ \varphi(\langle n, k\rangle) = n \cdot k. \]
   a) Czy \(\varphi\) jest różnowartościowa?
   b) Czy \(\varphi\) jest na?
   c) Znaleźć \(\varphi(P \times \mathbb{N})\).
   d) Znaleźć \(\varphi^{-1}(\{10\})\).
   e) Znaleźć \(\varphi^{-1}(\mathbb{N} - P)\).
   Tutaj P oznacza zbiór liczb parzystych.
5. Funkcja \(F : (\mathbb{N} \to P(\mathbb{N})) \to P(\mathbb{N})\) wzorem
   \[ F(x) = \bigcup \{ x(i) \mid i \in \mathbb{N} \}.\]
   a) Czy F jest różnowartościowa?
   b) Czy F jest na?
   c) Czy istnieje zbiór \(A \subseteq \mathbb{N}\) taki, że \(F^{-1}(\{ A\})\) jest zbiór jednoelementowy?
   d) Czy istnieje zbiór \(A \subseteq \mathbb{N}\) taki, że \(F^{-1}(\{ A\})\) jest zbiór czteroelementowy?
6. Niech \( a \not \in A, b \not \in B\). Pokazać, że następujące warunki są równoważne.
   a) Istnieje bijekcja z \(A\) do \(B\).
   b) Istnieje bijekcja z \(A \cup \{a\}\) do \(B \cup \{b\}\).
7. Zdefiniujmy \(F : (\mathbb{N} \to \mathbb{N}) \to (P(\mathbb{N}) \to P(\mathbb{N}))\) wzorem
   \(F(f)(X) = f(X)\). Czy F jest na?

 Praca domowa

1. Niech \(f: A \to B\). Pokazać, że \(f\) jest na wtedy i tylko wtedy, gdy dla każdego zbioru \(C\) i dla każdych funkcji \(g,h:B\to C\) zachodzi implikacja
   \[g \circ f = h\circ f \to g=h\]. 
2.  Niech \(\varphi : (\mathbb{N} \to \mathbb{N}) \to (P(\mathbb{N}) \to P(\mathbb{N}))\) będzie określona tak
   \[ \varphi(f)(A) = f^{-1}(A).\]
   a) Czy \(\varphi\) jest różnowartościowa?
   b) Czy \(\varphi\) jest na?
   c) Znaleźć \(\varphi^{-1}(\{id_{P(\mathbb{N})}\})\).
   d) Czy istnieje \(f \in Rg\varphi\), która jest różnowartościowa?
   e) Czy każda funkcja \(f \in Rg\varphi\) jest różnowartościowa?

Ćwiczenia 2: suma uogólniona, iloczyn uogólniony, iloczyn kartezjański

1. a) Czy jeśli \(A \subseteq B\), to \(\bigcap A \subseteq \bigcap B\)?
   b) Czy jeśli \(A \subseteq B\), to \(\bigcap B \subseteq \bigcap A\)?
2. Czy dla dowolnych niepustych \(A\), \(B\) o niepustym przecięciu zachodzą równości:
   a) \(\bigcap A \cap \bigcap B = \bigcap (A \cap B)\),
   b) \(\bigcap A \cap \bigcap B = \bigcap (A \cup B)\),
   c) \(\bigcup A \cup \bigcup B = \bigcup (A \cap B)\)?
3. Które z następujących równości zachodzą dla dowolnego zbioru 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 \}\)?
4. Kiedy \(A \times B = B \times A\)?
5. Czy następująca równość zachodzi dla dowolnych niepustych rodzin \(A\), \(B\):
   \[\bigcap A \times \bigcap B = \bigcap \{ \alpha \times \beta \mid \alpha \in A \wedge  \beta \in B\}?\]
6. Znaleźć \(\bigcup_{t \in \mathbb{R}^+} A_t\) i \(\bigcap_{t \in \mathbb{R}^+} A_t\), gdzie
   \[A_t = \{\langle x, y \rangle \in \mathbb{R} \times \mathbb{R} \mid | x - t | + |y | \leq 1\}.\]

Praca domowa

1.  Czy dla dowolnych niepustych \(A\), \(B\) o niepustym przecięciu zachodzą równości:
   a) \(\bigcap A \cup \bigcap B = \bigcap (A \cup B)\),
   b) \(\bigcup A \cap \bigcup B = \bigcup (A \cap B)\).
2. Udowodnić, że dla dowolnych niepustych A, B, X, Y zachodzi równoważność
   \[ A \times B \subseteq X \times Y \Leftrightarrow A \subseteq X \wedge B \subseteq Y. \]
   Czy założenie niepustości jest istotne?

Ćwiczenia 1: rachunek zbiorów, zbiór potęgowy, suma uogólniona

Zadania

1. 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\) ?
2. 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\),
   c) jeśli \(A \cup B = C\), to \(C - B = A - B\).
3. 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)\).
4. Która z implikacji jest prawdziwa dla dowolnych zbiorów \(A\), \(B\):
   \[ A \subseteq B \hbox{ wtw. } P(A) \subseteq P(B) ? \]
5. Udowodnić, że \(\bigcup P(A) = A\) dla dowolnego A.
6. Czy jeśli \(A \subseteq B\), to \( \bigcup A \subseteq \bigcup B\)?
   Czy jeśli \( \bigcup A \subseteq \bigcup B\), to \(A \subseteq B\)? 
7. Sprawdzić, czy dla dowolnych \(A\), \(B\) zachodzi
   \[ \bigcup A \cup \bigcup B = \bigcup (A \cup B) ?\]

Praca domowa

1. Czy dla dowolnych zbiorów \(A\), \(B\), \(C\) zachodzą równości:
   a) \(A \cup (A \cap B) = A\),
   b) \(A - (B \cup C) = (A-B)\cup(A-C)\).
2. Czy istnieją zbiory A, B takie, że \(P(A-B) = P(A) - P(B)\)?