Ćwiczenia 10: porządki (niekoniecznie świąteczne)

Zadania

1. Które z następujących zbiorów są równoliczne:
   \[\mathbb{Q}\times\mathbb{Z},\mathbb{R}\times\mathbb{Q}, \mathbb{R}-\mathbb{Q}, 2^{\mathbb{N}}, 2^{\mathbb{R}}, P(\mathbb{Q}\times\mathbb{Z}), \bigcup_{n\in \mathbb{N}}\mathbb{N}^n ? \]
2. W zbiorze \(\{1,2,3,5,12,18,120,300\}\) uporządkowanym przez relację podzielności wskazać elementy minimalne, maksymalne, najmniejsze, największe. Czy istnieją w tym zbiorze trzyelementowe łańcuchy lub antyłańcuchy? Wskaż kres dolny zbioru \(\{5,12\}\) oraz kres górny zbioru \(\{3,12\}\).
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\}^{\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?
5. Czy zbiór \(\{01^n \mid n \in \mathbb{N}\}\) ma kres górny (dolny) w zbiorze \(\{0,1\}^{*}\) uporządkowanym leksykograficznie?
6. Czy zbiór \(\{0^n1 \mid n \in \mathbb{N}\}\) ma kres górny (dolny) w zbiorze \(\{0,1\}^{*}\) uporządkowanym leksykograficznie?
7. Czy relacja równoważności może być częściowym porządkiem?
8. Znaleźć moc zbioru wszystkich porządków częściowych w \(\mathbb{N}\).

Praca domowa

Praca domowa pojawi się w poniedziałek po południu na stronie wykładu. Termin oddania: 13.01.2014 r.

Życzę Państwu odpoczynku w czasie przerwy świątecznej. Nie zapomnijcie, że łańcuch to nie tylko ozdoba choinkowa :)

Wesołych Świąt! 
Szczęśliwego Nowego Roku 2014!

Więcej matematycznych choinek

Ćwiczenia 9: moce cz. 2

Zadania

1. Jaka jest moc zbioru ciągów liczb wymiernych stałych od pewnego miejsca?
2. Znaleźć moc zbioru \(\mathbb{R}^{\mathbb{Q}}\).
3. Pokazać, że \((A^{B})^C \sim A^{B \times C}\).
4. Znaleźć moc zbioru wszystkich bijekcji z \(\mathbb{N}\) do \(\mathbb{N}\).
5. Niech r będzie taką relacją w zbiorze  \(\mathbb{Q}^{\mathbb{N}}\), że \(\langle f,g \rangle \in r\) wtedy i tylko wtedy, gdy różnica f - g jest zbieżna do zera. Znaleźć moc zbioru ilorazowego i moce klas abstrakcji relacji r.

Praca domowa

Kolejna praca domowa zostanie opublikowana w poniedziałek po południu na stronie wykładu. Termin oddania: 16 grudnia 2013 r.

Ćwiczenia 8: moce

Przypominam, że w tym tygodniu, w czwartek na wykładzie, jest klasówka.

Twierdzenie Cantora-Bernsteina

Jeśli \(\overline{\overline{A}} \leq \overline{\overline{B}}\) i \(\overline{\overline{B}} \leq \overline{\overline{A}}\), to \(\overline{\overline{A}} = \overline{\overline{B}}\).

W praktyce: szukamy mocy zbioru C.

1. Znajdujemy dwa (być może różne) zbiory A, B takie, że \(\overline{\overline{A}} = \overline{\overline{B}}\). 
2. Znajdujemy dwie funkcje różnowartościowe \(f : A \to C\) i \(g: C \to B\).
3. Twierdzenie Cantora-Bernsteina mówi, że \(\overline{\overline{C}} = \overline{\overline{A}}= \overline{\overline{B}}\).

Wskazówka: dobrze jest zacząć od znalezienia typu zbioru C. Typ zbioru C daje nam zawsze ograniczenie górne na moc zbioru C.
Przykład: Znaleźć moc zbioru C wszystkich relacji w \(\mathbb{N}\), które ...
Rozwiązanie: Zbiór wszystkich relacji w \(\mathbb{N}\) to \(P(\mathbb{N}\times\mathbb{N})\). Zatem \(C \subseteq P(\mathbb{N}\times\mathbb{N})\), a stąd dostajemy:
\[\overline{\overline{C}} \leq \overline{\overline{P(\mathbb{N}\times\mathbb{N})}} = \mathfrak{C}\]
I już wiemy, że moc zbioru C nie może być równa np. \(2^{\mathbb{\mathfrak{C}}}\).

Zadania

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

Zadanie do przemyślenia

Zadanie dla osób, które po przygotowaniu do klasówki będą się nudzić:

1. Znaleźć moc zbioru wszystkich funkcji ciągłych z \(\mathbb{R}\) do \(\mathbb{R}\).

W tym tygodniu nie ma pracy domowej.

Klasówka

Przypominam, że 5 grudnia na wykładzie będzie klasówka. Materiał obowiązujący na klasówce:

• rachunek zbiorów,
• funkcje,
• relacje,
• relacje równoważności,
• równoliczność,
• zbiory przeliczalne.

Jeśli są jakieś zadania (z ćwiczeń, ze zbioru zadań lub inne) albo zagadnienia, które chcielibyście powtórzyć przed klasówką, proszę napisać w komentarzu.

Ćwiczenia 7: równoliczność

Zadania

1. Pokazać, że \(\mathbb{N} \times \mathbb{N} \sim \mathbb{N}\).
2. Pokazać, że \(P(A) \sim \{0,1\}^{\mathbb{N}}\).
3. Pokazać, że jeśli \(A \sim B\), to \(P(A) \sim P(B)\).
4. Pokazać, że \(\mathbb{N} \not \sim \mathbb{R}\).
5. Znaleźć moc zbioru skończonych podzbiorów \(\mathbb{N}\).

Praca domowa

Treść kolejnej pracy domowy zostanie opublikowana w poniedziałek na stronie wykładu. Termin oddania: 2 grudnia 2013 r.

Ćwiczenia 6: 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 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.
3. 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\).
4. 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?
   e) Czy iloraz \((\mathbb{N} \to \mathbb{N})/r\) jest skończony?

Ciekawe zadanie

Nie zdążyliśmy zrobić tego zadania na ćwiczeniach, a jest bardzo ciekawe. To jedno z moich ulubionych zadań na relacje równoważności. Polecam! :-)

1. 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) Czy prawdziwe jest twierdzenie odwrotne, czyli jeśli r jest relacją równoważności, to f musi być różnowartościowa?
   c) 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.)

 Praca domowa

Treść kolejnej pracy domowej zostanie opublikowana w poniedziałek po południu na stronie wykładu. Termin oddania: 25 listopada 2013 r.

Ć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 5-elementowej relacji na zbiorze liczb naturalnych takiej, że jest ona
   a) symetryczna,
   b) przechodnia,
   c) zwrotna.
4. Udowodnić, że relacja \(R\) jest przechodnia wtedy i tylko wtedy, gdy \(R \cdot R \subseteq R\).
5. Niech \(\mathcal{R}\) będzie niepustą rodziną relacji przechodnich. Udowodnić, że \(\bigcap \mathcal{R}\) jest relacją przechodnią.
6. 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ą.
7. Relację \(r \in P(A \times A)\) nazwiemy krzaczastą wtedy i tylko wtedy, gdy
   \[\forall abc (a r b \wedge a r c \to \neg b r c \wedge \neg c r b)\]
   a) Czy złożenie relacji krzaczastych jest relacją krzaczastą?
   b) Czy iloczyn dowolnej niepustej rodziny relacji krzaczastych jest relacją krzaczastą?
   c) Czy suma dowolnej rodziny relacji krzaczastych jest relacją krzaczastą?
   d) Niech \(r_i\) krzaczaste dla \(i \in \mathbb{N}\) i niech \(\forall ij (i \leq j \to r_i \subseteq r_j\). Czy \(\bigcap_{i\in \mathbb{N}} r_i\) jest relacją krzaczastą?

Praca domowa

Jak zwykle, praca domowa zostanie opublikowana w poniedziałek po południu na stronie wykładu. Termin oddania: 18 listopada 2013 r.

Ćwiczenia 4: funkcje cz.2

Zadania

1. Pokazać, że funkcja \(\varphi : P(A \times B) \to (B \to P(A))\) dana wzorem
   \[\varphi(\Delta)(b) =\{ a \in A \mid \langle a,b \rangle \in \Delta\}\]
   jest bijekcją.
2. Niech \(F : \mathbb{N}^{\mathbb{N}}\to P(\mathbb{N})\) będzie taka, że \( F(f) = f^{-1}(\{1\}).\)
   a) Czy F jest różnowartościowa i czy jest na \(P(\mathbb{N})\)?
   b) Znaleźć obraz zbioru funkcji stałych.
   c) Znaleźć przeciwobraz zbioru \(\{\{10\}\}\).
3. Podaj 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\) jest identycznością na \(\mathbb{N}\),
   c) \(f \circ g= f\),
   d) \(f\) jest funkcją na \(\mathbb{N}\),
   e) obrazem zbioru liczb naturalnych parzystych w odwzorowaniu \(g\) jest zbiór liczb naturalnych nieparzystych.
4.  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?
   
   Pozostałe podpunkty tego zadania. Zachęcam do ich rozwiązania.
   c) Znaleźć \(\varphi^{-1}(\{ id_{P(\mathbb(N)}\})\).
   d) Czy istnieje funkcja \(f \in Rg \hbox{ } \varphi\), która jest różnowartościowa?
   e) Czy każda funkcja \(f \in Rg \hbox{ } \varphi\) jest różnowartościowa?

Zadania dodatkowe

• Dualną wersją zadania 1 jest zadanie 96 w zbiorze zadań. 
• Podpunkty c-e w zadaniu 4.

Praca domowa

Praca domowa pojawi się w poniedziałek po południu na stronie wykładu. Termin oddania: 4 listopada 2013 r.

Ć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
   \[f \circ g = f\circ h \to g=h\].
   (Zobacz także Zadania dodatkowe.)
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 \(f : P(\mathbb{N}) \times P(\mathbb{N}) \to P(\mathbb{N})\) będzie dana wzorem:
   \[f(\langle C, D \rangle) = C \cap D.\]
   a) Czy \(f\) jest różnowartościowa?
   b) Czy \(f\) jest na?
   c) Znaleźć obraz \(\vec{f}(P(B) \times P(B))\).
   d) Znaleźć przeciwobraz \(\vec{f^{-1}}(\{\mathbb{N}\})\).

Zadanie do kontemplacji

1. Pokazać, że funkcja \(\varphi : P(A \times B) \to (B \to P(A))\) dana wzorem
   \[ \varphi(\Delta)(b) = \{a\in A \mid \langle a,b \rangle \in \Delta\}\]
   jest bijekcją.

To zadanie zrobimy na następnych ćwiczeniach.

W tym tygodniu nie ma pracy domowej.
 

Zadania dodatkowe

Osobom, które chcą sprawdzić, czy dobrze zrozumiały rozwiązania na ćwiczeniach polecam zadanie 121 - dualna wersja zadania 2 powyżej.

Osobom odważnym polecam zadanie 129, ze wskazówką, że to tak naprawdę zaszyfrowana wersja zadania 2 i zadania 121.

O twierdzeniu Fermata

Twierdzenie Fermata

Dla liczby naturalnej \(n > 2\) nie istnieją liczby całkowite \(x\), \(y\), \(z\) takie, że
\[ x^n + y^n = z^n.\]

Jak widać, sformułowanie twierdzenia jest bardzo proste. Dlaczego zatem to twierdzenie jest nazywane Wielkim Twierdzeniem Fermata?

Twierdzenie to sformułował w 1637 Francuz Pierre de Fermat, z wykształcenia prawnik, z zamiłowania matematyk (samouk!). Fermat sformułował to twierdzenie na marginesie książki "Arithmetica" Diofantosa. I zostawił dopisek:

Znalazłem zaiste zadziwiający dowód tego twierdzenia. Niestety, margines jest zbyt mały, by go pomieścić.

Przez stulecia twierdzenie Fermata (pedanci nazywali je wtedy hipotezą Fermata) fascynowało i inspirowało matematyków. Kolejne pokolenia próbowały znaleźć dowód, szczególnie ten "zadziwiający" dowód zapowiedziany przez Fermata. Znaleziono dowody dla wybranych niewielkich \(n\). W XX wieku z pomocą komputerów udowodniono twierdzenie dla wszystkich \(n < 1000000\). Obecnie uważa się, że dowód Fermata był błędny.

Poprawny dowód podał ostatecznie angielski matematyk Andrew Wiles w 1994 roku. Praca Wilesa miała ok. 100 stron i korzystała m.in. z teorii krzywych eliptycznych, która to teoria jest materiałem na dobrych kilka książek.

Osobom zainteresowanym historią twierdzenia Fermata i historią matematyki polecam wykłady Historia matematyki prof. Marka Kordosa (można je zaliczyć jako wykłady ogólnouniwersyteckie). Polecam również znakomitą książkę prof. Kordosa pt. Wykłady z historii matematyki.

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

Zadania 

1. Pokazać, że 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 \cap \bigcup B = \bigcup (A \cap B)\)?
3. Kiedy \(A \times B = B \times A\)?
4. 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\}?\]
5. Znaleźć \(\bigcup_{t \in \mathbb{R}^+} A_t\) i \(\bigcap_{t \in \mathbb{R}^+} A_t\), gdzie \(A_t = [\sqrt{t}, \sqrt{2t}]\).
6. Funkcja \(f : P(A) \to P(A)\) jest addytywna wtedy i tylko wtedy, gdy
   \[ f(X \cup Y) = f(X) \cup f(Y) \hbox{ dla } X, Y \subseteq A.\]
   Czy każda  funkcja addytywna ma własność \(f(X) = \bigcup_{x\in X} f(\{x\})\)?

Praca domowa

Jak zwykle, praca domowa nr 2  pojawi się na stronie wykładu w poniedziałek po południu. Termin oddania:  21 października 2013 r.

Dodatkowe zadania

Dodatkowe zadania, które można zrobić jako uzupełnienie ćwiczeń: zadanie 32, zadanie 34, zadanie 36, zadanie 37, zadanie 45. Numery zadań ze zbioru zadań.

Ć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 \(A - B = A - C\), to \(B = C\).
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. Czy jeśli \(A \subseteq B\), to \( \bigcup A \subseteq \bigcup B\)?
   Czy jeśli \( \bigcup A \subseteq \bigcup B\), to \(A \subseteq B\)? 
6. Sprawdzić, czy dla dowolnych \(A\), \(B\) zachodzi
   \[ \bigcup A \cup \bigcup B = \bigcup (A \cup B) ?\]

Praca domowa

Pracy domowa nr 1. Termin oddania: 14 października 2013 r. (następne ćwiczenia).