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

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

2. \( \vec{f} (\emptyset)= \emptyset \),

3. \( \vec{f} (\{1\})= \{2\} \),

4. \( \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

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

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

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

4. \( \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:

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

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

3. \( \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:

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

2. \( \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:

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

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

3. \( \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

1. \( 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.

2. \( \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:

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

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

3. \( \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:

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

2. \( \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.