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