Ćwiczenia 4: funkcje cz. 2

Zadania

1. 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
   \[ g(A)(n) = \{ i \in \mathbb{N} \mid \alpha(n,i) \in A \}. \]
   Udowodnić, że g jest bijekcją.
2. 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
   \[ g(i) = (f^i)^{-1}(X) \]
   była różnowartościowa.
3. Podać 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 = id_{\mathbb{N}}\),
   c) \(g \circ f = f\),
   d) f jest funkcją na \(\mathbb{N}\),
   e) obrazem zbioru liczb naturalnych parzystych jest zbiór liczb naturalnych nieparzystych.
4. Skonstruować bijekcję \(f : \mathcal{D} \times (\mathcal{E} \oplus \mathcal{H}) \to  (\mathcal{D} \times \mathcal{E}) \oplus (\mathcal{D} \times \mathcal{H})\).
5. 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\)?
6. Permutacją zbioru X nazwiemy dowolną bijekcję \(\pi : X \to X\). Powiemy, że funkcja \( f : \mathbb{N} \to  \mathbb{N}\) jest niezmiennicza ze względu na permutacje 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.

Praca domowa

1. 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\).
   a) Czy f jest różnowartościowa?
   b) Czy f jest na \(P(\mathbb{N} \times \mathbb{N})\)?
   c) Znaleźć \( f^{-1}(P(\mathcal{P} \times \mathcal{P}))\), gdzie \(\mathcal{P}\) to zbiór liczb parzystych.
   
2. 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}\)?