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