tag:blogger.com,1999:blog-58684708885912899212024-03-08T09:13:23.332-08:00Podstawy matematykisemestr zimowy 2014/2015, grupa nr 1<br>
poniedziałki 14.15-15.45, sala 3120Agnieszka Kozubek-Krycuńhttp://www.blogger.com/profile/10270486475902515407noreply@blogger.comBlogger14125tag:blogger.com,1999:blog-5868470888591289921.post-1208151796571480822015-01-26T10:52:00.001-08:002015-01-26T10:52:34.539-08:00Ćwiczenia 13: logika<h2>
Zadania</h2>
<ol>
<li>Zapisać następujące stwierdzenia w języku arytmetyki liczb
naturalnych \((+, \cdot, 0, 1, =)\) używając symboli logicznych i
kwantyfikatorów:<br />a) Liczba a jest mniejsza lub równa liczbie b.<br />b) Liczba a jest resztą z dzielenia b przez c.<br />c) Liczba a jest pierwsza.<br />d) Liczba a jest największym wspólnym dzielnikiem liczb b i c chyba, że jest parzysta.<br />e) Liczby x i y mają te same dzielniki pierwsze.</li>
<li>Sformułować poprawne zaprzeczenia stwierdzeń:<br />a) Liczby m i n są pierwsze.<br />b) Liczby m in są względnie pierwsze.</li>
<li>Dla każdej z następujących par struktur wskazać formułę prawdziwą w jednej, a w drugiej nie.<br />a) \(\langle \mathbb{Q}, +, \cdot, 0, 1\rangle\) i \(\langle \mathbb{R}, +, \cdot, 0, 1\rangle\),<br />b) \(\langle \mathbb{N}, +, 0\rangle\) i \(\langle \mathbb{R}, +, 0 \rangle\),<br />c) \(\langle P_2, \parallel \rangle\) i \(\langle P_2, \bot \rangle\), gdzie \(P_2\) to zbiór prostych w \(\mathbb{R}^2\),<br />d) \(\langle P_2, \bot\rangle\) i \(\langle P_3, \bot \rangle\), gdzie \(P_n\) to zbiór prostych w \(\mathbb{R}^n\)<br />e) \(\langle \mathbb{R}, +, \cdot, 0, 1\rangle\) i \(\langle P(\mathbb{N}), \cup, \cap, \emptyset, \mathbb{N}\rangle\),<br />f) \(\langle \mathbb{N}, \leq, 0\rangle\) i \(\langle \mathbb{R}, \leq, 0\rangle\),<br />g) \(\langle \mathbb{N}, \leq\rangle\) i \(\langle \mathbb{R}, \leq\rangle\),<br />h) \(\langle \mathbb{N}, +, 0\rangle\) i \(\langle\{a,b\}^*, \cdot, \epsilon\rangle\).</li>
<li> Czy następujące formuły są tautologiami? Czy są spełnialne?<br />a) \(\forall x (p(x) \to q(x)) \vee \forall x (q(x) \to p(x))\), <br />b) \(\exists x (P(x) \to \forall y P(y))\),<br />c) \( (\exists x \exists y P(x,y) \to \forall y R(y)) \to \forall x(P(x,x) \to R(x)) \),<br />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) \).</li>
</ol>
Unknownnoreply@blogger.com0tag:blogger.com,1999:blog-5868470888591289921.post-23347755932842144022015-01-19T09:20:00.004-08:002015-01-19T09:20:49.800-08:00Ćwiczenia 12: lemat Kuratowskiego-Zorna<h2>
Zadania</h2>
<ol>
<li>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\).</li>
<li>Niech \(B \subseteq \RR_+\). Udowodnić, że istnieje zbiór \(C \subseteq \RR\) taki, że</li>
<ul>
<li>\( \forall x,y \in C (x \neq y \to | x -y | \in B) \),</li>
<li>\( \forall x \not\in C (\exists y \in C | x -y | \not \in B) \).</li>
</ul>
<li>Udowodnić, że każdy porządek częściowy można rozszerzyć do porządku liniowego.</li>
</ol>
<h2>
Praca domowa (nieobowiązkowa)</h2>
<ol>
<li>Dowolny podzbiór \(\ZZ\) nazwiemy <i>zeznaniem</i>. Zbiór zeznań \(\mathcal{R}\) jest <i>sprzeczny</i>, 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}\).</li>
</ol>
Unknownnoreply@blogger.com0tag:blogger.com,1999:blog-5868470888591289921.post-37432950601562743072015-01-12T11:39:00.000-08:002015-01-12T11:40:03.471-08:00Ćwiczenia 11: izomorfizm porządków, dobre ufundowanie<h2>
Zadania</h2>
<ol>
<li>Niech \(A = \{ 3 - \frac{1}{2n} \mid n \in \mathbb{N} - \{0\}\}\),<br />
\(B = \{ \pi - \frac{2}{n} \mid n \in \mathbb{N} - \{0\}\} \cup \{4\}\),<br />
\(C = \{0\} \cup \{ \frac{1}{n} \mid n \in \mathbb{N} - \{0\}\} \cup \{ 2 - \frac{1}{n} \mid n \in \mathbb{N} - \{0\}\}\).<br />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?<br />
</li>
<li>Czy zbiory \(\QQ \times (0,1]\) i \((0,1] \times \QQ\) uporządkowane leksykograficznie są izomorficzne?</li>
<li>Czy zbiór \(\langle \mathbb{N}^*, \leq_{lex}\rangle\) jest dobrze ufundowany?</li>
<li>Czy zbiór \(\langle \mathbb{N}^2, \leq_{lex}\rangle\) jest dobrze ufundowany?</li>
<li>Podaj trzy przykłady zbiorów dobrze uporządkowanych mocy \(\aleph_0\) tak, aby żadne dwa nie były ze sobą izomorficzne.</li>
<li>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\).</li>
<li>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.</li>
<li>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:<br />a) \(\forall a \in D \exists b \in D (a < b \wedge f(b) = b), \)<br />b) \(\forall a \in D \exists b \in D (a < b \wedge f(b) > b). \)</li>
<li>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)\).</li>
</ol>
<h2>
Praca domowa</h2>
<ol>
<li>
Relacja r częściowo porządkująca zbiór \(\NN\) jest <i>przyjemna</i>, jeżeli ma nieskończony łańcuch i jest dobrym ufundowaniem, ale nie jest dobry porządkiem. Jakiej mocy jest rodzina wszystkich relacji przyjemnych?<br />
</li>
<li>Niech \(P_{fin}(\NN)\) to zbiór skończonych podzbiorów zbioru \(\NN\). Zdefiniować dobry porządek \( \preccurlyeq\) w zbiorze \(P_{fin}(\NN)\), żeby <br />\[\forall A, B \in P_{fin}(\NN) (A \subseteq B \to A \preccurlyeq B).\]</li>
</ol>
Unknownnoreply@blogger.com0tag:blogger.com,1999:blog-5868470888591289921.post-56355365180098710632014-12-15T08:55:00.000-08:002014-12-15T10:21:54.922-08:00Ćwiczenia 10: moce cz. 2<h2>
Zadania</h2>
<ol>
<li>Znaleźć moc zbioru funkcji nierosnących z \(\mathbb{N}\) do \(\mathbb{N}\). </li>
<li>Znaleźć moc zbioru wszystkich relacji równoważności w \(\mathbb{N}\).</li>
<li>Znaleźć moc zbioru Cantora. Zbiór Cantora to przecięcie ciągu zbiorów:<br />\(C_0 = (0,1)\),<br />\(C_1 = (0,\frac{1}{3}) \cup (\frac{2}{3},1)\),<br />\(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)\),<br />...<br />\(C = \bigcap_{n\in \mathbb{N}}C_n\).</li>
<li> Funkcję \(f : \mathbb{N} \to \mathbb{N}\) nazywamy <i>zygzakiem </i>wtedy i tylko wtedy, gdy spełnia warunek<br />\[ \begin{multline*}\forall_{x>0} ((f(x)>f(x-1) \to f(x) > f(x+1)) \\<br /> \wedge (f(x)<f(x-1) \to f(x) < f(x+1))).\end{multline*}\]<br />Jakiej mocy jest zbiór wszystkich zygzaków?</li>
<li>a) Jaka jest moc zbioru \(A = \{ f :\mathbb{N} \to \mathbb{N} \mid \forall_x( f(x) \leq x)\}\)?<br />b) Jaka jest moc zbioru \(B = \{ f \in A \mid f \hbox{ jest na }\mathbb{N}\}\)?<br />c) Jaka jest moc zbioru \(C = \{ f \in A \mid f \hbox{ jest różnowartościowa}\}\)?</li>
<li>Jaka jest moc zbioru \(\mathbb{R}^\mathbb{N}\)?</li>
<li>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?</li>
</ol>
<h2>
Praca domowa</h2>
<ol>
<li>Jaka jest moc rodziny tych relacji równoważności w \(\mathbb{N}\), które mają skończenie wiele klas abstrakcji?<br />
</li>
<li>Ile jest takich funkcji \(f: \mathbb{N} \to \mathbb{N}\), że każdy zbiór \(f^{-1}(\{n\})\) jest skończony?</li>
</ol>
<br />
<div style="text-align: center;">
<span style="color: #38761d;"><span style="font-size: large;"><b>Wesołych Świąt!</b></span></span><br />
<br />
<br /></div>
Unknownnoreply@blogger.com0tag:blogger.com,1999:blog-5868470888591289921.post-59885036984805419312014-12-08T10:08:00.001-08:002014-12-08T11:30:54.295-08:00Ćwiczenia 9: równoliczność, moce<h2>
Zadania</h2>
<ol>
<li>Pokazać, że \(P(A) \sim \{0,1\}^{A}\).</li>
<li>Pokazać, że jeśli \(A \sim B\), to \(P(A) \sim P(B)\).</li>
<li>Znaleźć moc zbioru skończonych podzbiorów \(\mathbb{N}\).</li>
<li>Znaleźć moc zbioru ciągów liczb wymiernych stałych od pewnego miejsca. </li>
<li>Znaleźć moc zbioru funkcji z \(\mathbb{N}\) do \(\mathbb{N}\).</li>
<li>Znaleźć moc zbioru funkcji niemalejących z \(\mathbb{N}\) do \(\mathbb{N}\).</li>
</ol>
<h2>
Praca domowa</h2>
<ol>
<li>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.
</li>
<li>Znaleźć moc zbioru wszystkich ciągów liczb wymiernych, które są zbieżne do zera.</li>
</ol>
Unknownnoreply@blogger.com0tag:blogger.com,1999:blog-5868470888591289921.post-8784105070066327162014-12-01T08:58:00.001-08:002014-12-01T08:58:32.124-08:00Ćwiczenia 8: relacje równoważności<h2>
Zadania</h2>
<ol>
<li>Jaka jest najmniejsza i największa (w sensie zawierania) relacja równoważności w zbiorze \(A\)?</li>
<li>Czy relacja równoważności może być częściowym porządkiem? </li>
<li>Czy istnieje relacja równoważności na \(\mathbb{N}\), która ma:<br />a) dokładnie 2 klasy abstrakcji po 37 elementów,<br />b) 2 klasy abstrakcji po 17 elementów, 3 klasy po 33 elementy i jedną nieskończoną,<br />c) nieskończenie wiele klas abstrakcji, każda o nieskończonej liczbie elementów.</li>
<li>Niech \(r \subseteq P(\mathbb{N}) \times P(\mathbb{N})\) będzie taka, że<br />\[ \langle X, Y \rangle \in r \hbox{ wtw istnieje skończony }Z\hbox{ taki, że } X \cup Z =Y \cup Z. \]<br />a) Udowodnić, że r jest relacją równoważności.<br />b) Znaleźć \([\emptyset]_r\).</li>
<li>Niech \(r \subseteq (\mathbb{N} \to \mathbb{N}) \times (\mathbb{N} \to \mathbb{N} )\) będzie określona w następujący sposób:<br />\[\langle f, g\rangle \in r \hbox{ wtw } f(\mathbb{N}) = g(\mathbb{N}).\]<br />a) Udowodnić jednym krótkim zdaniem, że r jest relacją równoważności.<br />b) Znaleźć klasy \([\lambda x.1]_r\) i \([id_{\mathbb{N}}]_r\).<br />c) Czy zbiór wszystkich funkcji różnowartościowych jest klasą abstrakcji tej relacji?<br />d) Czy istnieje dwuelementowa klasa abstrakcji?</li>
<li>Niech A będzie niepustym zbiorem i niech \(f : A \to A\).<br />a) Udowodnić, że jeśli f jest różnowartościowa, to relacja \(r \subseteq A \times A\) dana warunkiem<br />\[ x r y \Leftrightarrow \exists n\in \mathbb{N} (f^n(x) = y \wedge f^n(y) = x)\]<br />jest relacją równoważności.<br />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.)</li>
</ol>
<br />
<b><span style="color: red;">Dziś nie ma pracy domowej.</span></b>Unknownnoreply@blogger.com0tag:blogger.com,1999:blog-5868470888591289921.post-24544110997398964122014-11-24T09:30:00.001-08:002015-01-11T02:48:09.629-08:00Ćwiczenia 7: porządki cz. 2<h2>
Zadania</h2>
<ol>
<li>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ą?</li>
<li>Udowodnij, że \(\langle A \leadsto B, \leq \rangle\) jest częściowym porządkiem zupełnym.</li>
<li>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:<br />a) \(\forall a \in A \forall b \in B (a \leq g(b) \leftrightarrow f(a) \leq b )\)<br />b) \(\forall a \in A (a \leq g(f(a))) \wedge \forall b \in B (f(g(b)) \leq b)\).</li>
<li>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.</li>
<li>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\).</li>
</ol>
<h2>
Praca domowa</h2>
<ol>
<li>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\):<br />a) Jeśli w X istnieje \(\sup A\) i \(\sup B\), to istnieje \(\sup (A \cup B)\).<br />b) Jeśli w X istnieje \(\sup (A \cup B)\), to istnieją.\(\sup A\) i \(\sup B\).<br />
</li>
<li>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\).</li>
<li><b>Dla chętnych:</b> skończyć zadanie 4 z zajęć.</li>
</ol>
<ol>
</ol>
Unknownnoreply@blogger.com0tag:blogger.com,1999:blog-5868470888591289921.post-40777094385025168152014-11-17T10:11:00.001-08:002014-11-17T10:11:39.306-08:00Wykład "Ataki na aplikacje internetowe"Zapraszam na wykład mojego kolegi z pracy Michała Kołodziejskiego pt. "<b>Ataki na aplikacje internetowe</b>". Wykład odbędzie się w czwartek 20 listopada 2014 roku o godzinie 14 (bez kwadransa) w sali 5070. <br />
<br />
<br />Unknownnoreply@blogger.com0tag:blogger.com,1999:blog-5868470888591289921.post-48055814810149498452014-11-17T10:04:00.000-08:002014-11-17T23:54:56.550-08:00Ćwiczenia 6: porządki<h2>
Zadania</h2>
<ol>
<li>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\}\).</li>
<li>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.</li>
<li>Rozpatrzmy częściowe uporządkowanie zbioru \(\{0,1\}^{\mathbb{N}}\):<br />\[ f \leq g \hbox{ wtw. } \forall_x f(x) \leq g(x)\]<br />a) Czy ten porządek jest liniowy?<br />b) Czy istnieje w nim łańcuch nieskończony?<br />c) Czy istnieje antyłańcuch nieskończony?<br />d) Czy ma element największy, najmniejszy, minimalny, maksymalny?</li>
<li>Czy zbiór \(\{01^n \mid n \in \mathbb{N}\}\) ma kres górny (dolny) w zbiorze \(\{0,1\}^{*}\) uporządkowanym leksykograficznie?</li>
<li>Czy zbiór \(\{0^n1 \mid n \in \mathbb{N}\}\) ma kres górny (dolny) w zbiorze \(\{0,1\}^{*}\) uporządkowanym leksykograficznie?</li>
<li>Dany jest następujący częściowy porządek w zbiorze \(P(\mathbb{N} - \{\emptyset\}\):<br />\[X \leq Y \hbox{wtw.} ((\min(X) < \min(Y)) <br />\vee (\min(X) = \min(Y) \wedge X \subseteq Y).\]<br />a) Czy ten porządek jest liniowy?<br />b) Czy istnieje w tym zbiorze nieskończony ciąg malejący?<br />c) Wskaż elementy minimalne, maksymalne, największe, najmniejsze.</li>
</ol>
<h2>
Praca domowa</h2>
<ol>
<li>Jeśli \(\leq\) jest cześciowym porządkiem w A, to relację < nazywamy <i>ostrym uporządkowaniem</i> 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.</li>
<li>Niech \(\langle X, r \rangle, \langle Y, s \rangle \) będą niepustymi zbiorami częściowo uporządkowanymi. Pokazać, że <br />a) \(\langle X \oplus Y, r \oplus s \rangle \) jest zbiorem częściowo uporządkowanym bez elementu największego.<br />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 \).</li>
</ol>
Unknownnoreply@blogger.com0tag:blogger.com,1999:blog-5868470888591289921.post-24138377528266663842014-11-03T13:43:00.001-08:002014-11-03T13:43:36.106-08:00Ćwiczenia 5: relacje<h2>
Zadania</h2>
<ol>
<li> Znaleźć przykład pięcioelementowej relacji na zbiorze liczb naturalnych, która jest<br />a) przechodnia,<br />b) symetryczna,<br />c) zwrotna. </li>
<li>Dla jakich relacji \(r \subseteq A \times A\) zachodzą równości \(r \cdot r^{-1} = r^{-1} \cdot r = 1_A\)?</li>
<li>Udowodnić, że \(r^+ = \bigcup_{n > 0} r^n\).</li>
<li>Niech \(r, s \subseteq A \times A\). Czy dla dowolnych relacji \(r,s\) prawdziwa jest równość \((r^*)^{-1} = (r^{-1})^*\)?</li>
</ol>
<h2>
Praca domowa</h2>
<ol>
<li>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ą.</li>
<li>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})\)<br />\[\varphi(Z) = \{\langle X, Y\rangle \mid Z \subseteq X \cap Y\}.\]<br />a) Czy \(\varphi\) jest różnowartościowa?<br />b) Czy \(\varphi\) jest na?<br />c) Która z poniższych równości zachodzi dla dowolnych \(Z_1, Z_2 \in P(\mathbb{N})\)<ul>
<li>\(\varphi(Z_1 \cap Z_2) = \varphi(Z_1) \cap \varphi(Z_2)\),</li>
<li>\(\varphi(Z_1 \cup Z_2) = \varphi(Z_1) \cup \varphi(Z_2)\)?</li>
</ul>
</li>
</ol>
Unknownnoreply@blogger.com0tag:blogger.com,1999:blog-5868470888591289921.post-70986651319991416212014-10-27T12:00:00.001-07:002014-10-27T12:00:54.203-07:00Ćwiczenia 4: funkcje cz. 2<h2>
Zadania</h2>
<ol>
<li>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<br />\[ g(A)(n) = \{ i \in \mathbb{N} \mid \alpha(n,i) \in A \}. \]<br />Udowodnić, że g jest bijekcją.</li>
<li>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<br />\[ g(i) = (f^i)^{-1}(X) \]<br />była różnowartościowa.</li>
<li>Podać przykład pary funkcji \( f, g : \mathbb{N} \to \mathbb{N}\) spełniających wszystkie poniższe warunki:<br />a) \(\forall x( g(x) \neq x)\),<br />b) \(g \circ g = id_{\mathbb{N}}\),<br />c) \(g \circ f = f\),<br />d) f jest funkcją na \(\mathbb{N}\),<br />e) obrazem zbioru liczb naturalnych parzystych jest zbiór liczb naturalnych nieparzystych.</li>
<li>Skonstruować bijekcję \(f : \mathcal{D} \times (\mathcal{E} \oplus \mathcal{H}) \to (\mathcal{D} \times \mathcal{E}) \oplus (\mathcal{D} \times \mathcal{H})\).</li>
<li>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\)?</li>
<li><i>Permutacją </i>zbioru X nazwiemy dowolną bijekcję \(\pi : X \to X\). Powiemy, że funkcja \( f : \mathbb{N} \to \mathbb{N}\) jest <i>niezmiennicza ze względu na permutacje</i> 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.</li>
</ol>
<h2>
Praca domowa</h2>
<ol>
<li>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\).<br />a) Czy f jest różnowartościowa?<br />b) Czy f jest na \(P(\mathbb{N} \times \mathbb{N})\)?<br />c) Znaleźć \( f^{-1}(P(\mathcal{P} \times \mathcal{P}))\), gdzie \(\mathcal{P}\) to zbiór liczb parzystych.<br />
<ol>
</ol>
</li>
<li>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}\)? </li>
</ol>
Unknownnoreply@blogger.com0tag:blogger.com,1999:blog-5868470888591289921.post-65676887700659855302014-10-20T10:54:00.000-07:002014-10-20T10:54:16.504-07:00Ćwiczenia 3: funkcje<h2>
Zadania</h2>
<ol>
<li>Ile jest funkcji, funkcji częściowych, funkcji na, funkcji różnowartościowych:<br />a) \(\emptyset \to \emptyset\),<br />b) \(\emptyset \to \{ \cdot \}\),<br />c) \(\{ \cdot \} \to \emptyset\),<br />d) \(\{ \cdot \} \to \{ \cdot \}\),<br />e) \(\{ \cdot, \square \} \to \{ \cdot \}\),<br />f) \(\{ \cdot \} \to \{ \cdot, \square \}\)?</li>
<li>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<br />\[f \circ g = f\circ h \to g=h\].</li>
<li>Podać przykład \(f : A \to B, X\subseteq A, Y \subseteq B\) takich, że<br />a) \(\vec{f^{-1}}(\vec{f}(X)) \neq X\),<br />b) \(\vec{f}(\vec{f^{-1}}(X)) \neq X\),<br />c) \(\vec{f}(C \cap D) = \vec{f}(C)\cap \vec{f}(D)\).</li>
<li>Niech \( \varphi : \mathbb{N} \times \mathbb{N} \to \mathbb{N}\) będzie taka, że<br />\[ \varphi(\langle n, k\rangle) = n \cdot k. \]<br />a) Czy \(\varphi\) jest różnowartościowa?<br />b) Czy \(\varphi\) jest na?<br />c) Znaleźć \(\varphi(P \times \mathbb{N})\).<br />d) Znaleźć \(\varphi^{-1}(\{10\})\).<br />e) Znaleźć \(\varphi^{-1}(\mathbb{N} - P)\).<br />Tutaj P oznacza zbiór liczb parzystych.</li>
<li>Funkcja \(F : (\mathbb{N} \to P(\mathbb{N})) \to P(\mathbb{N})\) wzorem<br />\[ F(x) = \bigcup \{ x(i) \mid i \in \mathbb{N} \}.\]<br />a) Czy F jest różnowartościowa?<br />b) Czy F jest na?<br />c) Czy istnieje zbiór \(A \subseteq \mathbb{N}\) taki, że \(F^{-1}(\{ A\})\) jest zbiór jednoelementowy?<br />d) Czy istnieje zbiór \(A \subseteq \mathbb{N}\) taki, że \(F^{-1}(\{ A\})\) jest zbiór czteroelementowy?</li>
<li>Niech \( a \not \in A, b \not \in B\). Pokazać, że następujące warunki są równoważne.<br />a) Istnieje bijekcja z \(A\) do \(B\).<br />b) Istnieje bijekcja z \(A \cup \{a\}\) do \(B \cup \{b\}\).</li>
<li>Zdefiniujmy \(F : (\mathbb{N} \to \mathbb{N}) \to (P(\mathbb{N}) \to P(\mathbb{N}))\) wzorem<br />\(F(f)(X) = f(X)\). Czy F jest na?</li>
</ol>
<h2>
Praca domowa</h2>
<ol>
<li>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<br />
\[g \circ f = h\circ f \to g=h\]. </li>
<li> Niech \(\varphi : (\mathbb{N} \to \mathbb{N}) \to (P(\mathbb{N}) \to P(\mathbb{N}))\) będzie określona tak<br />\[ \varphi(f)(A) = f^{-1}(A).\]<br />a) Czy \(\varphi\) jest różnowartościowa?<br />b) Czy \(\varphi\) jest na?<br />c) Znaleźć \(\varphi^{-1}(\{id_{P(\mathbb{N})}\})\).<br />d) Czy istnieje \(f \in Rg\varphi\), która jest różnowartościowa?<br />e) Czy każda funkcja \(f \in Rg\varphi\) jest różnowartościowa?</li>
</ol>
Unknownnoreply@blogger.com0tag:blogger.com,1999:blog-5868470888591289921.post-54205563491452485222014-10-13T10:37:00.002-07:002014-10-14T05:41:11.350-07:00Ćwiczenia 2: suma uogólniona, iloczyn uogólniony, iloczyn kartezjański<ol>
<li>a) Czy jeśli \(A \subseteq B\), to \(\bigcap A \subseteq \bigcap B\)?<br />b) Czy jeśli \(A \subseteq B\), to \(\bigcap B \subseteq \bigcap A\)?</li>
<li>Czy dla dowolnych niepustych \(A\), \(B\) o niepustym przecięciu zachodzą równości:<br />a) \(\bigcap A \cap \bigcap B = \bigcap (A \cap B)\),<br />b) \(\bigcap A \cap \bigcap B = \bigcap (A \cup B)\),<br />c) \(\bigcup A \cup \bigcup B = \bigcup (A \cap B)\)?</li>
<li>Które z następujących równości zachodzą dla dowolnego zbioru A:<br />a) \( \bigcap \{ P(B) \mid B \subseteq A\} = \{ \bigcap P(B) \mid B \subseteq A \}\),<br />b) \( \bigcup \{ P(B) \mid B \subseteq A\} = \{ \bigcup P(B) \mid B \subseteq A \}\)?</li>
<li>Kiedy \(A \times B = B \times A\)?</li>
<li>Czy następująca równość zachodzi dla dowolnych niepustych rodzin \(A\), \(B\): <br />\[\bigcap A \times \bigcap B = \bigcap \{ \alpha \times \beta \mid \alpha \in A \wedge \beta \in B\}?\]</li>
<li>Znaleźć \(\bigcup_{t \in \mathbb{R}^+} A_t\) i \(\bigcap_{t \in \mathbb{R}^+} A_t\), gdzie <br />\[A_t = \{\langle x, y \rangle \in \mathbb{R} \times \mathbb{R} \mid | x - t | + |y | \leq 1\}.\]</li>
</ol>
<h2>
Praca domowa</h2>
<ol>
<li> Czy dla dowolnych niepustych \(A\), \(B\) o niepustym przecięciu zachodzą równości:<br />a) \(\bigcap A \cup \bigcap B = \bigcap (A \cup B)\),<br />b) \(\bigcup A \cap \bigcup B = \bigcup (A \cap B)\).</li>
<li>Udowodnić, że dla dowolnych niepustych A, B, X, Y zachodzi równoważność<br />\[ A \times B \subseteq X \times Y \Leftrightarrow A \subseteq X \wedge B \subseteq Y. \]<br />Czy założenie niepustości jest istotne?</li>
</ol>
Unknownnoreply@blogger.com0tag:blogger.com,1999:blog-5868470888591289921.post-45320188328848176432014-10-06T10:30:00.001-07:002014-10-06T10:40:00.128-07:00Ćwiczenia 1: rachunek zbiorów, zbiór potęgowy, suma uogólniona<h2>
Zadania </h2>
<ol>
<li>Czy dla dowolnych zbiorów \(A\), \(B\), \(C\) zachodzą równości:<br />a) \(A - (B \cup C) = (A - B) - C\),<br />b) \(A - (B - C) = (A - B) \cup C\) ?</li>
<li>Sprawdzić, czy dla dowolnych zbiorów w \(A\), \(B\), \(C\) zachodzi następująca implikacja:<br />
a) jeśli \( A - B = B - A \), to \( A = B\),<br />
b) jeśli \(C - B \subseteq C - A\), to \(A \subseteq B\),<br/>
c) jeśli \(A \cup B = C\), to \(C - B = A - B\).</li>
<li>Zbadać, czy dla dowolnych \(A\), \(B\) zachodzi:<br />a) \(P (A \cup B) = P(A) \cup P(B)\),<br />b) \(P (A \cap B) = P(A) \cap P(B)\).</li>
<li>Która z implikacji jest prawdziwa dla dowolnych zbiorów \(A\), \(B\):<br />\[ A \subseteq B \hbox{ wtw. } P(A) \subseteq P(B) ? \]</li>
<li>Udowodnić, że \(\bigcup P(A) = A\) dla dowolnego A.</li>
<li>Czy jeśli \(A \subseteq B\), to \( \bigcup A \subseteq \bigcup B\)?<br />Czy jeśli \( \bigcup A \subseteq \bigcup B\), to \(A \subseteq B\)? </li>
<li>Sprawdzić, czy dla dowolnych \(A\), \(B\) zachodzi<br />\[ \bigcup A \cup \bigcup B = \bigcup (A \cup B) ?\]</li>
</ol>
<h2>
Praca domowa</h2>
<ol>
<li>Czy dla dowolnych zbiorów \(A\), \(B\), \(C\) zachodzą równości:<br />
a) \(A \cup (A \cap B) = A\),<br/>
b) \(A - (B \cup C) = (A-B)\cup(A-C)\).</li>
<li>Czy istnieją zbiory A, B takie, że \(P(A-B) = P(A) - P(B)\)? </li>
</ol>Agnieszka Kozubek-Krycuńhttp://www.blogger.com/profile/10270486475902515407noreply@blogger.com0