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