Obrazy i przeciwobrazy

Czasem warto spojrzeć na funkcję z szerszej perspektywy. Rozważmy pewną funkcję $f:X \rightarrow Y$ . Funkcja ta w naturalny sposób wyznacza pewną funkcję przekształcającą podzbiory zbioru $X$ w podzbiory zbioru $Y$ , przyporządkowując zbiorowi $A\subset X$ , zbiór elementów zbioru $Y$ , które są wartościami funkcji $f$ dla pewnych argumentów ze zbioru $A$ . Funkcję tą formalnie definujemy w poniższy sposób.

Definicja 3.1.

Każda funkcja $f:X \rightarrow Y$ wyznacza pewną funkcję $\vec{f} : \mathcal{P}(X) \rightarrow \mathcal{P}(Y)$ tak, że dla dowolnego zbioru $A\subset X$

$\vec{f}(A)= \{y\in Y: \exists_{x\in A} f(x)=y\}.$

Dla dowolnego zbioru $A\subset X$ zbiór $\vec{f}(A)$ nazywamy obrazem zbioru $A$ przez funkcję $f$ .

Przykład 3.2.

Niech $f:N \rightarrow N$ będzie określona wzorem $f(x)=2\cdot x$ . Wtedy

$\vec{f}(N)$ jest zbiorem liczb parzystych,

$\vec{f} (\emptyset)= \emptyset$ ,

$\vec{f} (\{1\})= \{2\}$ ,

$\vec{f} (\{1,2\})= \{2,4\}$ ,

5. obrazem zbioru liczb parzystych przez funkcję

$f$ jest zbiór liczb podzielnych przez 4.

W podobny sposób definiujemy przeciwobrazy zbiorów przez funkcję. Przeciwobrazem zbioru $B \subset Y$ przez funkcję $f:X \rightarrow Y$ nazwiemy zbiór tych elementów zbioru $X$ , którym funkcja przypisuje wartości ze zbioru $B$ .

Definicja 3.3.

Każda funkcja $f:X \rightarrow Y$ wyznacza pewną funkcję $\vec{f}^{-1} : \mathcal{P}(Y) \rightarrow \mathcal{P}(X)$ w następujący sposób. Dla dowolnego zbioru $B\subset Y$

$\vec{f}^{-1}(B)= \{x\in X: \exists_{y\in B} f(x)=y\}.$

Dla dowolnego zbioru $B\subset Y$ zbiór $\vec{f}^{-1}(B)$ nazywamy przeciwobrazem zbioru $B$ przez funkcję $f$ .

Przykład 3.4.

Niech $f:N \rightarrow N$ będzie określona wzorem $f(x)=2\cdot x$ . Wtedy

$\vec{f}^{-1}(N)=N$ ,

$\vec{f}^{-1} (\emptyset)= \emptyset$ ,

$\vec{f}^{-1} (\{1\})= \emptyset$ ,

$\vec{f}^{-1} (\{1,2\})= \{1\}$ ,

5. przeciwobrazem zbioru liczb nieparzystych przez funkcję

$f$ jest zbiór pusty,

6. przeciwobrazem zbioru liczb podzielnych przez 4, przez funkcję

$f$ jest zbiór liczb parzystych,

7. przeciwobrazem zbioru liczb parzystych przez funkcję

$f$ jest

$N$ .

Fakt 3.1.

Nietrudno zauważyć, że dla dowolnej funkcji częściowej $f$

$\vec{f}(\emptyset)=\emptyset=\vec{f}^{-1}(\emptyset).$

W poniższych ćwiczeniach badamy podstawowe własności obrazów i przeciwobrazów dowolnych funkcji.

Ćwiczenie 3.1

Dla dowolnej funkcji $f:X \rightarrow Y$ i dla dowolnych zbiorów $A_1,A_2 \subset X$ udowodnij następujące fakty:

$\vec{f}(A_1 \cup A_2)= \vec{f}(A_1) \cup \vec{f}(A_2)$ ,

$\vec{f}(A_1 \cap A_2) \subset \vec{f}(A_1) \cap \vec{f}(A_2)$ ,

$\vec{f}(X \setminus A_1) \supset \vec{f}(X) \setminus \vec{f}(A_1)$ .

Rozwiązanie 1

$\begin{array} {l} \vec{f}(A_1 \cup A_2) = \\ = \{y\in Y: \exists_{x\in A_1\cup A_2} f(x)=y\} = \\ = \{y\in Y: \exists_{x} [x \in A_1\cup A_2 \wedge f(x)=y]\} = \\ = \{y\in Y: \exists_{x} [(x\in A_1 \vee x \in A_2) \wedge f(x)=y]\} = \\ = \{y\in Y: \exists_{x} [(x\in A_1 \wedge f(x)=y )\vee (x \in A_2 \wedge f(x)=y)]\} = \\ = \{y\in Y: [\exists_{x} (x\in A_1 \wedge f(x)=y )]\vee [\exists_{x} (x \in A_2 \wedge f(x)=y)]\} = \\ = \{y\in Y: [\exists_{x} (x\in A_1 \wedge f(x)=y )]\} \cup \{y \in Y:[\exists_{x} (x \in A_2 \wedge f(x)=y)]\} = \\ = \{y\in Y: [\exists_{x\in A_1} f(x)=y ]\} \cup \{y \in Y:[\exists_{x \in A_2} f(x)=y)]\} = \\ = \vec{f}(A_1) \cup \vec{f}(A_2) \end{array}$

Rozwiązanie 2

Weźmy dowolny element

$y \in\vec{f}(A_1 \cap A_2)$ . Oznacza to, że istnieje element

$x\in A_1 \cap A_2$ taki, że

$f(x)=y$ . Skoro

$x\in A_1$ , to

$y=f(x) \in \vec{f}(A_1)$ . Podobnie skoro

$x\in A_2$ , to

$y=f(x) \in \vec{f}(A_2)$ . Mamy więc

$y \in \vec{f}(A_1)$ oraz

$y \in \vec{f}(A_2)$ , a więc należy także do ich przecięcia.

Rozwiązanie 3

Weźmy dowolny element

$y \in \vec{f}(X) \setminus \vec{f}(A_1)$ . Istnieje wtedy element

$x\in X$ , dla którego

$f(x)=y$ oraz skoro

$y \notin \vec{f}(A_1)$ , to

$x\notin A_1$ . Wobec tego

$y\in \vec{f}(X\setminus A_1)$ .

Ćwiczenie 3.2

Dla dowolnej funkcji $f:X \rightarrow Y$ i dowolnej rodziny $\kappa$ podzbiorów $X$ (czyli $\kappa \in \mathcal{P}(\mathcal{P}(X))$ ) udowodnij następujące fakty:

$\vec{f}(\bigcup \kappa)= \bigcup\{\vec{f}(A): A\in \kappa\}$ ,

$\vec{f}(\bigcap \kappa) \subset \bigcap\{\vec{f}(A): A\in \kappa\}$ .

Rozwiązanie 1

Niech

$A\in \kappa$ , wtedy

$\bigcup \kappa= \bigcup \kappa \cup A$ . Z poprzedniego ćwiczenia otrzymujemy

$\vec{f}(\bigcup \kappa)= \vec{f}(\bigcup \kappa) \cup \vec{f}(A),$

wobec tego dla dowolnego $A\in \kappa$ mamy $\vec{f}(\bigcup \kappa) \supset \vec{f}(A)$ . Więc również

$\vec{f}(\bigcup \kappa) \supset \bigcup \{\vec{f}(A):A\in \kappa \}.$

Dla inkluzji w drugą stronę weźmy dowolny element $y\in \vec{f}(\bigcup \kappa)$ . Wtedy istnieje $x\in \bigcup \kappa$ taki, że $f(x)=y$ . Skoro $x\in \bigcup \kappa$ , to istnieje $A_0\in \kappa$ taki, że $x\in A_0$ . Oznacza to, że $y\in \vec{f}(A_0)$ , a więc również $y\in \bigcup \{\vec{f}(A):A\in \kappa \}$ . Wobec tego

$\vec{f}(\bigcup \kappa) \subset \bigcup \{\vec{f}(A):A\in \kappa \}.$

Rozwiązanie 2

Niech

$A\in \kappa$ , wtedy

$\bigcup \kappa= \bigcup \kappa \cap A$ . Z poprzedniego ćwiczenia otrzymujemy

$\vec{f}(\bigcap \kappa) = \vec{f}(\bigcap \kappa \cap A) \subset \vec{f}(\bigcap \kappa) \cap \vec{f}(A).$

Wynika stąd, że $\vec{f}(\bigcap \kappa) \subset \vec{f}(A)$ dla dowolnego $A \in \kappa$ , a więc również

$\vec{f}(\bigcap \kappa) \subset \bigcap\{\vec{f}(A): A\in \kappa\}$

Ćwiczenie 3.3

Skonstruuj kontrprzykłady dla poniższych inkluzji:

$\vec{f}(A_1 \cap A_2) \supset \vec{f}(A_1) \cap \vec{f}(A_2)$ ,

$\vec{f}(X \setminus A_1) \subset \vec{f}(X) \setminus \vec{f}(A_1)$ ,

$\vec{f}(\bigcap \kappa) \supset \bigcap\{\vec{f}(A): A\in \kappa\}$ .

Rozwiązanie

Niech

$f=\{(0,0),(1,0)\}$ oraz

$A_1=\{0\}$ i

$A_2=\{1\}$ ,

$X=\{0,1\}$ i

$\kappa=\{A_1,A_2\}$ . Wtedy

$f(A_1\cap A_2)= f(\emptyset)=\emptyset$ , podczas gdy

$\vec{f}(A_1) \cap \vec{f}(A_2)= \{0\} \cap \{0\}=\{0\}$ , a więc zbiór niepusty.

$\vec{f}(X \setminus A_1)= \vec{f}(\{1\})=\{0\}$ , podczas gdy

$\vec{f}(X) \setminus \vec{f}(A_1)= \{0\} \setminus \{0\}= \emptyset$ .

3. sytuacja jest dokładnie taka jak w punkcie pierwszym.

Znacznie bardziej regularnie zachowują się przeciwobrazy funkcji. Podstawowe własności są tematem następnych ćwiczeń.

Ćwiczenie 3.4

Dla dowolnej funkcji $f:X \rightarrow Y$ i dla dowolnych zbiorów $B_1,B_2 \subset Y$ udowodnij następujące fakty:

$\vec{f}^{-1}(B_1 \cup B_2)= \vec{f}^{-1}(B_1) \cup \vec{f}^{-1}(B_2)$ ,

$\vec{f}^{-1}(B_1 \cap B_2) = \vec{f}(B_1) \cap \vec{f}(B_2)$ ,

$\vec{f}^{-1}(Y \setminus B_1) = \vec{f}^{-1}(Y) \setminus \vec{f}^{-1}(B_1)$ .

Rozwiązanie 1

$\begin{array} {l} x\in \vec{f}^{-1}(B_1 \cup B_2) \Leftrightarrow \\ \Leftrightarrow f(x) \in B_1 \cup B_2 \Leftrightarrow \\ \Leftrightarrow f(x)\in B_1 \vee f(x) \in B_2 \Leftrightarrow \\ \Leftrightarrow x\in \vec{f}^{-1}(B_1) \vee x\in \vec{f}^{-1}(B_2) \Leftrightarrow \\ \Leftrightarrow x\in \vec{f}^{-1}(B_1) \cup \vec{f}^{-1}(B_2) \end{array}$

Rozwiązanie 2

$\begin{array} {l} x\in \vec{f}^{-1}(B_1 \cap B_2) \Leftrightarrow \\ \Leftrightarrow f(x) \in B_1 \cap B_2 \Leftrightarrow \\ \Leftrightarrow f(x)\in B_1 \wedge f(x) \in B_2 \Leftrightarrow \\ \Leftrightarrow x\in \vec{f}^{-1}(B_1) \wedge x\in \vec{f}^{-1}(B_2) \Leftrightarrow \\ \Leftrightarrow x\in \vec{f}^{-1}(B_1) \cap \vec{f}^{-1}(B_2) \end{array}$

Rozwiązanie 3

$\begin{array} {l} x \in \vec{f}^{-1}(Y \setminus B_1) \Leftrightarrow \\ \Leftrightarrow f(x)\in Y \setminus B_1 \Leftrightarrow \\ \Leftrightarrow f(x)\in Y \wedge \neg (f(x) \in B_1) \Leftrightarrow \\ \Leftrightarrow x\in \vec{f}^{-1}(Y) \wedge \neg(x \in \vec{f}^{-1}(B_1)) \Leftrightarrow \\ \Leftrightarrow x \in \vec{f}^{-1}(Y) \setminus \vec{f}^{-1}(B_1) \end{array}$

Ćwiczenie 3.5
Dla dowolnej funkcji $f:X \rightarrow Y$ i dowolnej rodziny $\kappa$ podzbiorów $Y$ (czyli $\kappa \in \mathcal{P}(\mathcal{P}(Y))$ ) udowodnij następujące fakty:

$\vec{f}^{-1}(\bigcup \kappa)= \bigcup\{\vec{f}^{-1}(B): B\in \kappa\}$ ,

$\vec{f}^{-1}(\bigcap \kappa) \subset \bigcap\{\vec{f}^{-1}(B): B\in \kappa\}$ .

Rozwiązanie 1

$\begin{array} {l} x \in \vec{f}^{-1}(\bigcup \kappa) \Leftrightarrow \\ \Leftrightarrow f(x)\in \bigcup \kappa \Leftrightarrow \\ \Leftrightarrow \exists_{B\in \kappa} f(x)\in B \\ \Leftrightarrow \exists_{B \in \kappa} x\in \vec{f}^{-1}(B) \Leftrightarrow \\ \Leftrightarrow x \in \bigcup\{\vec{f}^{-1}(B): B\in \kappa\}_1) \end{array}$

Rozwiązanie 2

Metoda z poprzedniego punktu podziała i tutaj. Dla urozmaicenia prezentujemy nieco inne rozwiązanie. Niech

$\kappa'=\{Y\setminus B: B\in \kappa\}$ . Wtedy, używając wielokrotnie praw de'Morgana, dostaniemy

$\begin{array} {l} \vec{f}^{-1}(\bigcap \kappa) = \\ = \vec{f}^{-1}(Y \setminus \bigcup \kappa')= \\ = \vec{f}^{-1}(Y) \setminus \vec{f}^{-1}(\bigcup \kappa') = \\ = \vec{f}^{-1}(Y) \setminus \bigcup\{\vec{f}^{-1}(C): C\in \kappa' \} = \\ = \vec{f}^{-1}(Y) \setminus \bigcup\{\vec{f}^{-1}(Y\setminus B): B\in \kappa\} = \\ = \vec{f}^{-1}(Y) \setminus \bigcup\{\vec{f}^{-1}(Y)\setminus \vec{f}^{-1}(B): B\in \kappa\} = \\ = \bigcap \{\vec{f}^{-1}(Y) \setminus (\vec{f}^{-1}(Y)\setminus \vec{f}^{-1}(B)): B\in \kappa\}, \end{array}$ ponieważ

$\vec{f}^{-1}(Y)\supset \vec{f}^{-1}(B)$ , to

$\vec{f}^{-1}(Y) \setminus (\vec{f}^{-1}(Y)\setminus \vec{f}^{-1}(B))= \vec{f}^{-1}(B))$ więc kontynuując powyższe równości, dostajemy

$= \bigcap \{\vec{f}^{-1}(B): B\in \kappa\}.$ toggleSH(14)

Istnieje ścisły związek pomiędzy funkcjami a relacjami równoważności. Każda funkcja wyznacza pewną relację binarną w poniższy sposób.

Definicja 3.5.

Dla dowolnej funkcji $f:X \rightarrow Y$ definujemy relację binarną $\sim_{f} \subset X^2$ następująco:

$(x_1,x_2) \in \sim_{f} \Leftrightarrow f(x_1)=f(x_2).$

W myśl powyższej definicji elementy $x_1,x_2 \in X$ są w relacji $\sim_{f}$ , jeśli funkcja $f$ na tych elementach przyjmuje te same wartości. W poniższym ćwiczeniu dowodzimy, że relacja ta jest relacją równoważności na zbiorze $X$ . Relacja ta pełni ważną rolę w podstawowych konstrukcjach liczb, które będą tematem wykłady "Konstrukcje liczbowe, liczby całkowite, wymierne, konstrukcja Cantora liczb rzeczywistych".

Ćwiczenie 3.6

Udowodnij, że dla dowolnej funkcji $f:X \rightarrow Y$ relacja $\sim_{f}$ jest relacją równoważności na zbiorze $X$ .

Rozwiązanie

Przedstawiamy poniżej dwa różne dowody.

Dowód 1

Pokażemy, że relacja jest zwrotna przechodnia i symetryczna.

1. Zwrotność. Dla dowolnego elementu

$x \in X$ oczywiście jest spełnione

$f(x)=f(x)$ , a więc

$(x,x) \in \sim_{f}$ .

2. Symetryczność. Weźmy dowolne elementy

$x,y\in X$ takie, że

$(x,y)\in \sim_{f}$ . Wynika stąd, że

$f(x)=f(y)$ , a więc również

$f(y)=f(x)$ , co jest równoważne

$(y,x)\in \sim_{f}$ .

3. Przechodniość. Weźmy dowolne elementy

$x,y,z \in X$ takie, że

$(x,y),(y,z)\in \sim_{f}$ . Wtedy

$f(x)=f(y)$ i

$f(y)=f(z)$ , a więc również

$f(x)=f(z)$ , co oznacza, że

$(x,z)\in \sim_{f}$ .

Dowód 2

W Ćwiczeniu 3 pokazaliśmy, że $\vec{f}^{-1}(A \cap B) = \vec{f}^{-1}(A) \cap \vec{f}^{-1}(B)$ . Wynika stąd, że przeciwobrazy rozłącznych zbiorów są rozłączne. Rozważmy rodzinę zbiorów $F\stackrel{\textrm{def}}{\equiv} \{\vec{f}^{-1}(\{y\}): y \in \vec{f}(X)\}$ tworzy podział zbioru $X$ . Elementy tej rodziny są rozłączne, bo są przeciwobrazami rozłącznych zbiorów. Każdy element $x\in X$ należy do $\vec{f}^{-1}(\{f(x)\})$ , a więc należy do pewnego elementu tej rodziny. Wobec tego rodzina $F$ jest podziałem zbioru $X$ . Pokażemy teraz, że dowolne dwa elementy $x_1,x_2 \in X$ są w relacji $\sim_{f}$ wtedy i tylko wtedy, gdy należą do tego samego zbioru rodziny $F$ .

Przypuśćmy, że $f(x_1) \neq f(x_2)$ . Wtedy z definicji elementy te nie są w relacji $\sim_{f}$ . Z drugiej strony $x_1 \in \vec{f}^{-1}(\{f(x_1)\}$ oraz $x_2 \in \vec{f}^{-1}(\{f(x_2)\}$ . Skoro $f(x_1) \neq f(x_2)$ , to zbiory $\{f(x_1)\},\{f(x_2)\}$ są rozłączne, a więc ich przeciwobrazy również. Otrzymujemy stąd, że elementy $x_1,x_2$ należą do różnych zbiorów rodziny $F$ .

Przypuśćmy, że $f(x_1) = f(x_2)$ , oznaczmy tę wartość przez $y$ . Wtedy z definicji $(x_1,x_2) \in \sim_{f}$ . Z drugiej strony $x_1 \in \vec{f}^{-1}(\{f(x_1)\}=\vec{f}^{-1}(\{y\})=\vec{f}^{-1}(\{f(x_2)\}) \ni x_2$ , a więc elementy $x_1,x_2$ należą do tego samego zbioru rodziny $F$ .

Wynika stąd, że relacja $\sim_{f}$ jest dokładnie relacją wyznaczoną przez rodzinę zbiorów $F$ . Skoro rodzina ta jest podziałem zbioru $X$ , to relacja $\sim_{f}$ jest relacją równoważności.