Informatyka MIMUW

\(\def\NN{\mathbb{N}}
\def\RR{\mathbb{R}}
\def\pot#1{{\sf P}(#1)}
\def\<{\langle}
\def\>{\rangle}
\def\incl{\subseteq}
\def\A{{\cal A}}
\def\B{{\cal B}}
\def\tz{\;\;|\;\;}
\def\to{\rightarrow}
\def\poz{\vphantom{f}}
\def\pusty{\varnothing}
\)

Zadanie 0

Dla podanych poniżej \(A\) i \(B\) odpowiedz ile jest funkcji z \(A\) w \(B\), funkcji częściowych z \(A\) w \(B\), funkcji różnowartościowych z \(A\) w \(B\), funkcji z \(A\) na \(B\).

1. \(A=\pusty\), \(B=\pusty\)
2. \(A=\pusty\), \(B=\{b\}\)
3. \(A=\{a\}\), \(B=\pusty\)
4. \(A=\{a\}\), \(B=\{b\}\)
5. \(A=\{a\}\), \(B=\{b_1,b_2\}\)
6. \(A=\{a_1,a_2\}\), \(B=\{b_1,b_2\}\)

Zadanie 1

Udowodnij, że jeśli \(f:A \to B\) i \(g:B \to C\) są funkcjami różnowartościowymi to \(g \circ f: A \to C\) też jest funkcją różnowartościową.

Zadanie 2

Niech \(f : A \to B\). Udowodnij, że \(f\) jest na \(B\) wtedy i tylko wtedy gdy dla dowolnego \(C\) i dowolnych \(g,h : B\to C\) zachodzi implikacja \(g\circ f = h \circ f \to g = h\).

Zadanie 3

Podaj przykład \(A\), \(B\), \(f:A\to B\), \(X \subseteq A\) i \(Y \subseteq B\), takich że:

1. \(f\poz^{-1}(f(X)) \not = X\)
2. \(f( f\poz^{-1}(Y))\not= Y\)

Zadanie 4 (przykład z wykładu - pierwsza część)

Niech \(f : \pot{\NN} \times \pot{\NN} \to \pot{\NN}\) będzie taka, że \(f(\< C,D \> ) = C \cap D\) dla dowolnych \(C, D \subseteq \NN\). Czy \(f\) jest różnowartościowa i czy jest na \(\pot{\NN}\)?
Dla \(B \subseteq \NN\) znaleźć \(f(\pot{B} \times \pot{B})\) i \( f\poz^{-1}(\{\NN\})\).

Zadanie 5

Niech \(f : A^{A} \to \pot{A}\) będzie taka, że \(f(\varphi) =\varphi(A)\). Dla jakich zbiorów \(A\) ta funkcja jest różnowartościowa, a dla jakich zbiorów \(A\) jest na \(\pot{A}\)?

Zadanie 6

Niech \(F : \NN^{\NN}\to \pot{\NN}\) będzie taka, że \(F(f) = f\poz^{-1}(\{1\})\). Czy \(F\) jest różnowartościowa i czy jest na \(\pot{\NN}\)? Znajdź obraz zbioru funkcji stałych i przeciwobraz zbioru \(\{\{10\}\}\).

Zadanie 7 (przykład z wykładu)

Pokaż, że funkcja \(\varphi : \pot{A\times B} \to \pot{A}^B\) taka, że dla dowolnych \(\Delta\in \pot{A\times B},\ b\in B\),

Zadanie 8

Znajdź przykład \(f:\NN\to\NN\), takiej że przeciwobraz każdego zbioru jednoelementowego jest:

1. jednoelementowy
2. dwuelementowy
3. nieskończony.

Zadanie 9

Które z poniższych zdań są prawdziwe, a które fałszywe?

1. \(\forall f \in\NN^{\NN}\, \exists B\subseteq\NN
   ( f\poz^{-1}(B)\not=\pusty \wedge B\not=\NN)\)
2. \(\exists B\subseteq\NN\, \forall f\in\NN^{\NN}
   ( f\poz^{-1}(B)\not=\pusty \wedge B\not=\NN)\)
3. \(\exists f \in\NN^{\NN}\, \forall B\subseteq\NN
   ( f\poz^{-1}(B)\not=\pusty \to B=\NN)\)
4. \(\forall B\subseteq\NN\, \exists f \in\NN^{\NN}
   ( f\poz^{-1}(B)\not=\pusty \to B=\NN)\)

Zadanie 10 (równoliczność)

Udowodnij, że \(\NN \times \NN\) i \(\NN\) są równoliczne używając funkcji \(f(\< m,n \>) = 2^m*(2*n+1)-1\).

Zadanie 11 (równoliczność)

Udowodnij, że jeśli \(A \sim B\) to \(\pot{A} \sim \pot{B} \).

Zadanie 12 (równoliczność)

Udowodnij, że \((A^B)^C \sim A^{C\times B}\).