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}$.