Iniekcja i suriekcja

Istotną własnością funkcji jest to, czy różnym elementom może ona przypisać tę samą wartość. Na przykład, w przypadku szyfrowania używamy takich funkcji, które dają się odszyfrować, a więc generują różne kody dla różnych wiadomości. Takie funkcje, których wartości są różne na różnych argumentach nazywamy iniekcjami. Ponieważ ta własność nie zależy od zbioru, na którym funkcja jest zdefiniowana, zdefiniujemy ją dla wszystkich funkcji częściowych.

Definicja 4.1.

Funkcję częściową \( f \) nazywamy iniekcją, jeśli różnym elementom przyporządkowuje różne wartości. Formalnie, jeśli spełnia następujący warunek:

\( \forall_{y \in f_P} \forall_{x_1,x_2 \in f_L} (f(x_1)=y \wedge f(x_2)=y) \Rightarrow x_1=x_2 \)

Powyższy warunek mówi dokładnie tyle, że jeśli elementom \( x_1,x_2 \) funkcja przypisuje tę samą wartość \( y \), to te elementy muszą być równe.

Przykład 4.2.

Następujące funkcje częściowe są iniekcjami:

1. \( \emptyset \),

2. \( \{(\emptyset,\emptyset)\} \),

3. \( \{ (0,1),(1,0)\} \),

4. funkcja, która każdej liczbie naturalnej przypisuje liczbę dwukrotnie większą.

Przykłady funkcji częściowych, które nie są iniekcjami:

1. \( \{ (\emptyset, \emptyset), (\{\emptyset\}, \emptyset)\} \),

2. \( \{ (0, 0), (1,0)\} \),

3. funkcja, która każdej liczbie naturalnej przypisuje największą

liczbę parzystą nie większą od niej.

W poniższym ćwiczeniu pokazujemy, że jeśli funkcja częściowa nie "zlepia" ze sobą dwóch różnych argumentów, to jest "odwracalna".

Ćwiczenie 4.1.

Udowodnij, że funkcja częściowa \( f \) jest iniekcją wtedy i tylko wtedy, gdy \( f^{-1} \) jest funkcją częściową.

Rozwiązanie

Dowiedziemy równoważne twierdzenie, które mówi, że funkcja częściowa \( f \) nie jest iniekcją wtedy i tylko wtedy, gdy \( f^{-1} \) nie jest funkcją częściową.
Przypuśćmy, że \( f:X \rightarrow Y \) nie jest iniekcją. Jest to równoważne temu, że istnieją różne elementy \( x_1,x_2 \in X \) takie, że istnieje \( y\in Y \), dla którego \( (x_1,y)\in f \) oraz \( (x_2,y)\in f \). Co jest z kolei równoważne temu, że \( (y,x_1)\in f^{-1} \) oraz \( (y,x_2)\in f^{-1} \), co wobec różności elementów \( x_1,x_2 \) jest równoważne z tym, że \( f^{-1} \) nie jest funkcją częściową.

Ćwiczenie 4.2.

Udowodnij, że funkcja \( f:X \rightarrow Y \) jest iniekcją wtedy i tylko wtedy, gdy istnieje funkcja częściowa \( g \) taka, że \( g \circ f=\mathbb{I}_{X} \).

Rozwiązanie

Zacznijmy od dowodu implikacji w prawo. W poprzednim ćwiczeniu pokazaliśmy, że jeśli \( f \) jest iniekcją to, \( f^{-1} \) jest funkcją. Załóżmy, że \( f \) jest iniekcją i niech \( g=f^{-1} \), pokażemy, że \( g\circ f=\mathbb{I}_{X} \). Weźmy dowolną parę \( (x_1,x_2) \in g\circ f \), wtedy musi istnieć element \( y\in Y \) taki, że \( (x_1,y)\in f \) oraz \( (y,x_2) \in g \). Skoro \( g \) jest odwrotnością \( f \), to \( (x_2,y)\in f \). Ponieważ \( f \) jest iniekcją to, \( x_1=x_2 \). Wynika stąd, że \( g \circ f \subset \mathbb{I}_{X} \). Weźmy dowolny element \( x\in X \), niech \( y\in Y \) będzie elementem takim, że \( (x,y)\in f \), wtedy \( (y,x) \in g \), a więc \( (x,x) \in g \circ f \). Otrzymujemy stąd, że \( g \circ f \supset \mathbb{I}_{X} \).

Dla dowodu implikcaji w drugą stronę załóżmy, że istnieje funkcja częściowa \( g \) taka, że \( g \circ f=\mathbb{I}_{X} \). Weźmy dowolne dwa elementy \( x_1,x_2 \) takie, że \( f(x_1)=f(x_2) \). Wtedy \( g(f(x_1))=g(f(x_2)) \), ale skoro \( g \circ f = \mathbb{I}_{X} \), to \( g(f(x_1))=x_1 \) oraz \( g(f(x_2))=x_2 \). Wynika stąd, że \( x_1=x_2 \). A więc funkcja częściowa \( f \) jest iniekcją.

Ćwiczenie 4.3

Czy funkcja częściowa stała może być iniekcją? (funkcja częściowa jest stała, jeśli ma jednoelementowy zbiór wartości).

Rozwiązanie

Funkcja częściowa \( \{(\emptyset,\emptyset)\} \) jest stała i jest iniekcją.

Przypuśćmy, że \( f \) nie jest suriekcją na \( Y \), istnieje wtedy \( y\in Y \), dla którego \( \vec{f}^{-1}(\{y\}) = \emptyset \). Wobec tego dla dowolnego \( B\subset Y\setminus \{y\} \) mamy

\( \vec{f}^{-1}(B)= \vec{f}^{-1}(B) \cup \vec{f}^{-1}(\{y\})= \vec{f}^{-1}(B \cup \{y\}), \)

a więc funkcja \( \vec{f}^{-1} \) nie jest iniekcją.

Przypuśćmy teraz, że \( f \) jest suriekcją na \( Y \). Weźmy dwa różne zbiory \( A,B \subset Y \). Skoro są różne, to istnieje element \( y_1\in A \setminus B \) lub \( y_2 \in B \setminus A \). Zajmiemy się pierwszym przypadkiem, drugi jest symetryczny. Skoro \( y_1\notin B \), to \( \vec{f}^{-1}(\{y_1\}) \cap \vec{f}^{-1}(B) = \emptyset \). Ponieważ, \( f \) jest suriekcją, to \( \vec{f}^{-1}(\{y_1\}) \neq \emptyset \), więc istnieje element \( x\in \vec{f}^{-1}(\{y_1\}) \). Mamy więc element \( x \) taki, że \( x\in \vec{f}^{-1}(\{y_1\}) \subset \vec{f}^{-1}(A) \) oraz \( x\notin \vec{f}^{-1}(B) \), więc zbiory \( \vec{f}^{-1}(A) \) i \( \vec{f}^{-1}(B) \) są różne. Wobec tego funkcja \( \vec{f}^{-1} \) jest iniekcją.

Ćwiczenie 4.5

Udowodnij, że dla dowolnej funkcji \( f:X \rightarrow Y \), \( f \) jest iniekcją wtedy i tylko wtedy, gdy funkcja \( \vec{f}^{-1} \) jest suriekcją na \( \mathcal{P}(X) \).

Rozwiązanie

Zauważmy, że jeśli \( f \) jest iniekcją, to przeciwobrazy singletonów są singletonami lub są puste. Przypuśćmy, że \( f \) jest iniekcją, weźmy dowolny zbiór \( A \subset X \), pokażemy, że \( A=\vec{f}^{-1}(\vec{f}(A)) \).

\( \begin{array}{rll} A & = & \bigcup \{\{a\}:a\in A\} \\ \vec{f}(A) & = & \bigcup \{\vec{f}(\{a\}):a\in A\} \\ \vec{f}(A) & = & \bigcup \{\{f(a)\}:a\in A\} \\ \vec{f}^{-1}(\vec{f}(A)) & = & \vec{f}^{-1}(\bigcup \{\{f(a)\}:a\in A\}) \\ \vec{f}^{-1}(\vec{f}(A)) & = & (\bigcup \{\vec{f}^{-1}(\{f(a)\}):a\in A\}) \end{array} \)

Skorzystamy teraz z faktu, że przeciwobrazy singletonów są puste lub są sigletonami. Wiemy, że \( a \in \vec{f}^{-1}(\{f(a)\}) \), wobec czego zbiór \( \vec{f}^{-1}(\{f(a)\}) \) jest niepusty, a więc jest singletonem. W takim wypadku jego jedynym elementem może być \( a \). Otrzymujemy więc \( \vec{f}^{-1}(\{f(a)\})=\{a\} \). Wtedy

\( \begin{array}{rll}\vec{f}^{-1}(\vec{f}(A)) & = & (\bigcup \{\{a\}:a\in A\}) \\ \vec{f}^{-1}(\vec{f}(A)) & = & A \end{array} \).

Wobec tego dowolny zbiór \( A \subset X \) jest przeciwobrazem zbioru \( \vec{f}(A) \) przez funkcję \( f \), a więc funkcja \( \vec{f}^{-1} \) jest suriekcją.

Przypuśćmy teraz, że funkcja \( f \) nie jest iniekcją. Istnieją wtedy różne elementy \( x_1,x_2\in X \) oraz element \( y\in Y \) takie, że \( (x_1,y),(x_2,y)\in f \). Pokażemy, że zbiór \( \{x_1\} \) nie należy do obrazu zbioru \( \mathcal{P}(Y) \) przez funkcję \( \vec{f}^{-1} \). Dla dowodu nie wprost przypuśćmy, że istnieje zbiór \( B \subset Y \) taki, że \( \vec{f}^{-1}(B)=\{x_1\} \). Rozważmy zbiór \( \vec{f}^{-1}(\{y\}) \), oznaczmy go przez \( A \). Z całą pewnością \( x_1,x_2 \in A \). Ponieważ przeciwobrazy zbiorów rozłącznych są rozłączne, a \( x_1 \) należy zarówno do zbioru \( A \), jak i do zbioru \( \vec{f}^{-1}(B) \), to zbiory \( \{y\} \) oraz \( B \) nie mogą być rozłączne. Oznacza to, że \( y\in B \). Ale w takim wypadku \( \{y\} \subset B \) i w konsekwencji

\( \{x_1,x_2\} \subset \vec{f}^{-1}(\{y\}) \subset \vec{f}^{-1}(B). \)

Ponieważ \( x_1\neq x_2 \), to zbiór \( \vec{f}^{-1}(B) \) nie może być singletonem. Wobec tego nie istnieje zbiór \( B \), dla którego \( \vec{f}^{-1}(B)=\{x_1\} \). W efekcie czego funkcja \( \vec{f}^{-1} \) nie jest suriekcją.

Funkcję nazywamy bijekcją pomiędzy zbiorami \( X \) i \( Y \), jeśli każdemu elementowi zbioru \( X \) przypisuje dokładnie jeden element zbioru \( Y \), i w dodatku każdy element zbioru \( Y \) występuje w jakimś przypisaniu. Oznacza to dokładnie, że funkcja ta jest zarówno iniekcją jak i suriekcją na zbiór \( Y \).

Definicja 4.5.

Funkcję częściową \( f \) nazywamy bijekcją ze zbioru \( X \) w zbiór \( Y \), jeśli są spełnione poniższe warunki:

1. \( f:X \rightarrow Y \),

2. \( f \) jest iniekcją,

3. \( f \) jest suriekcją na \( Y \).

Każda funkcja bijektywna pomiędzy zbiorem \( X \) a \( Y \) dobiera elementy tych zbiorów w pary.

Twierdzenie 4.6.

Funkcja \( f \) jest bijekcją ze zbioru \( X \) w zbiór \( Y \) wtedy i tylko wtedy, gdy \( f^{-1} \) jest bijekcją (a więc także funkcją) ze zbioru \( Y \) w zbiór \( X \).

Dowód

Z ćwiczenia 4 wynika, że relacja \( f^{-1} \) jest iniekcją (bo \( f \) jest iniekcją). Z własności przeciwobrazów wynika, że \( \vec{f}^{-1}(Y)=X \). Pozostaje pokazać, że funkcja częściowa \( f^{-1} \) jest określona na całym \( Y \). Weźmy dowolny element \( y\in Y \). Ponieważ \( f \) jest suriekcją, to istnieje \( x\in X \), dla którego \( (x,y)\in f \). Wtedy \( (y,x)\in f^{y} \), a więc \( y \) należy do dziedziny \( f^{-1} \). Wobec dowolności wyboru \( y \) dziedziną \( f^{-1} \) jest cały zbiór \( Y \). Podsumowując, \( f^{-1}:Y \rightarrow Y \) jest iniekcją oraz \( \vec{f}^{-1}(Y)=X \), a więc \( f^{-1} \) jest bijekcją ze zbioru \( Y \) w zbiór \( X \). Implikacja w drugą stronę wynika z faktu, że \( f=(f^{-1})^{-1} \).

Twierdzenie 4.7.

Jeśli funkcje częściowe \( f,g \) są iniekcjami, to ich złożenie jest iniekcją.

Dowód

Jeśli funkcja częściowa \( g\circ f \) jest pusta to jest iniekcją. W przeciwnym razie weźmy dwie dowolne (niekoniecznie różne) pary należące do niej, które mają taką samą drugą współrzędną \( (x_1,y), (x_2,y) \in g\circ f \). Skoro należą one do złożenia \( f \) z \( g \), to istnieją elementy \( z_1,z_2 \) w dziedzinie relacji \( f \) takie, że \( (x_1,z_1), (x_2,z_2) \in f \) oraz \( (z_1,y), (z_2,y) \in g \). Z iniektywności funkcji częściowej \( g \) otrzymujemy, że \( z_1=z_2 \), oznaczmy ten element przez \( z \). Mamy więc \( (x_1,z), (x_2,z) \in f \). Z iniektywności funkcji częściowej \( f \) dostajemy \( x_1=x_2 \), co dowodzi, że funkcja częściowa \( g \circ f \) jest iniekcją.

Ćwiczenie 4.6

Udowodnij że w twierdzeniu 4.7. (patrz twierdzenie 4.7.) implikacja w przeciwną stronę nie jest prawdziwa.

Rozwiązanie

Rozważmy funkcje częściowe \( f=\{(0,0)\} \) oraz \( g=\{(0,1),(1,1)\} \). Wtedy \( g \circ f=\{(0,1)\} \), a więc jest iniekcją, podczas gdy funkcja \( g \) iniekcją nie jest.

Twierdzenie 4.8.

Dla dowolnych funkcji \( f:X \rightarrow Y ,g:Y \rightarrow Z \), jeśli \( f \) jest suriekcją na \( Y \) i \( g \) jest suriekcją na \( Z \), to \( g\circ f \) jest suriekcją na \( Z \).

Dowód

Weźmy dowolny \( z \in Z \). Ponieważ funkcja \( g \) jest suriekcją na \( Z \), to istnieje element \( y\in Y \) taki, że \( (y,z) \in g \). Skoro funkcja \( f \) jest suriekcją na \( Y \), to istnieje \( x\in X \) taki, że \( (x,y) \in f \). Z faktów \( (x,y) \in f \) oraz \( (y,z) \in g \) otrzymujemy \( (x,z) \in g \circ f \). Dobraliśmy więc do \( z \) element \( x\in X \), z którym jest on w relacji \( g \circ f \). Wobec dowolności wyboru \( z \) funkcja \( g \circ f \) jest suriekcją.

Ćwiczenie 4.7

Udowodnij, że w twierdzeniu 4.8. implikacja w przeciwną stronę nie jest prawdziwa.

Rozwiązanie

Weźmy \( X=Z=\{0\} \), \( Y=\{0,1\} \) oraz \( f=\{(0,1)\}, g=\{(0,0),(1,0)\} \). Wtedy \( f \) jest funkcją ze zbioru \( X \) w zbiór \( Y \), \( g \) jest funkcją ze zbioru \( Y \) w zbiór \( Z \) oraz \( g \circ f =\{(0,0)\} \) jest suriekcją na \( \{0\} \), podczas gdy \( f \) nie jest suriekcją na \( \{0,1\} \).

Ćwiczenie 4.8

W ćwiczeniu 3 pokazaliśmy, że poniższe równości nie są prawdziwe dla wszystkich funkcji. Udowodnij, że:

1.dla funkcji \( f:X \rightarrow Y \) równość \( \vec{f}(A_1 \cap A_2) = \vec{f}(A_1) \cap \vec{f}(A_2) \) jest prawdą dla dowolnych zbiorów \( A_1,A_2 \) wtedy i tylko wtedy, gdy \( f \) jest iniekcją,

2. dla funkcji \( f:X \rightarrow Y \) równość \( \vec{f}(X \setminus A_1) = \vec{f}(X) \setminus \vec{f}(A_1) \) jest prawdą dla dowolnego zbioru \( A_1 \) wtedy i tylko wtedy, gdy \( f \) jest iniekcją,

3. dla funkcji \( f:X \rightarrow Y \) równość \( \vec{f}(X \setminus A_1) = Y \setminus \vec{f}(A_1) \) jest prawdą dla dowolnego zbioru \( A_1 \) wtedy i tylko wtedy, gdy \( f \) jest bijekcją.

Rozwiązanie 1

Implikacja w lewo. Przypuśćmy że zbiory te są różne. Wobec tego musi zachodzić

\( \vec{f}(A_1 \cap A_2) ⊊ \vec{f}(A_1) \cap \vec{f}(A_2), \)

to znaczy, że istnieje element \( y\in Y \) taki, że \( y\in \vec{f}(A_1) \cap \vec{f}(A_2) \) oraz \( y\notin \vec{f}(A_1 \cap A_2) \). Czyli istnieją \( x_1\in A_1 \setminus A_2 \) oraz \( x_2 \in A_2\setminus A_1 \) takie, że \( f(x_1)=f(x_2)=y \). Ponieważ \( x_1,x_2 \) należą do rozłącznych zbiorów, to muszą być różne, więc funkcja \( f \) nie jest iniekcją.

Implikacja w prawo. Jeśli równość zachodzi dla wszystkich zbiorów, to dla dowolnych różnych elementów \( x_1,x_2 \in X \) mamy

\( \{f(x_1)\} \cap \{f(x_2)\} = \vec{f}(\{x_1\}) \cap \vec{f}(\{x_2\}) = \vec{f}(\{x_1\} \cap \{x_2\}) = \vec{f}(\emptyset)=\emptyset, \)

skąd otrzymujemy \( f(x_1)\neq f(x_2) \), a więc funkcja \( f \) jest iniekcją.

Rozwiązanie 2

Implikacja w prawo. Przypuśćmy, że \( f \) nie jest iniekcją. Weźmy \( x_1,x_2\in X \) oraz \( y\in Y \) takie, że \( y=f(x_1)=f(x_2) \) oraz \( x_1\neq x_2 \). Niech \( A_1= X \setminus \{x_1\} \). Wtedy

\( \{y\}= \vec{f}(X \setminus A_1), \)

a więc \( y\in \vec{f}(X \setminus A_1) \). Równocześnie, ponieważ \( x_2\in A_1 \), to \( y\in\vec{f}( A_1) \), a więc \( y\notin \vec{f}(X) \setminus \vec{f}(A_1) \). Wynika stąd, że zbiory \( y\notin \vec{f}(X) \setminus \vec{f}(A_1) \) i \( \vec{f}(X \setminus A_1) \) są różne.

Implikacja w lewo. Przypuśćmy teraz, że \( f \) jest iniekcją. Wtedy z punktu pierwszego otrzymamy, że obrazy rozłącznych zbiorów są rozłączne. Weźmy dowolny zbiór \( A_1\subset X \). Niech \( A_2=X \setminus A_1 \). Wtedy

\( \vec{f}(X)=\vec{f}(A_1 \cup A_2)= \vec{f}(A_1) \cup \vec{f}(A_2). \) Ponieważ \( \vec{f}(A_1) \cap \vec{f}(A_2)= \emptyset \), to

\( \vec{f}(X ) \setminus \vec{f}(A_1) = \vec{f}(A_2)= \vec{f}(X\setminus A_1), \)

a więc postulowana równość jest prawdziwa.

Rozwiązanie 3

Implikacja w lewo. Jeśli funkcja jest bijekcją, to \( \vec{f}(X)=Y \) i jest iniekcją, więc z poprzedniego punktu wynika, że badana równość jest prawdziwa.

Implikacja w prawo. Przypuśćmy teraz, że badana równość jest prawdziwa. Pokażemy, że \( f \) jest suriekcją na \( Y \). Weźmy dowolny element \( y\in Y \). Jeśli \( y\in \vec{f}(A_1) \), to tym bardziej \( y\in \vec{f}(X) \). W przeciwnym przypadku z założonej równości wynika, że to

\( y\in \vec{f}(X \setminus A_1) \), więc również \( y\in \vec{f}(X) \). Wobec tego każdy \( y\in Y \) należy do obrazu zbioru \( X \) przez funkcję \( f \), a więc \( f \) jest suriekcją. Skoro tak, to \( \vec{f}(X)=Y \) i z założonej równości oraz poprzedniego punktu otrzymujemy, że \( f \) jest iniekcją.

Ćwiczenie 4.9

Udowodnij, że funkcja \( f:N^2 \rightarrow N \) określona w następujący sposób

\( f(x,y)= \frac{(x+y+1)\cdot(x+y)}{2}+x \)

jest iniekcją.

Rozwiązanie

Weźmy dowolne \( (x_1,y_1), (x_2,y_2) \in N^2 \). Rozważymy dwa przypadki.
1. Przypuśćmy, że \( x_1+y_1=x_2+y_2 \). Wtedy niech \( z=x_1+y_1 \). Jeśli \( f(x_1,y_1)=f(x_2,y_2) \), to

\( \frac{(x_1+y_1+1) \cdot (x_1+y_1)}{2} + x_1= \frac{(x_2+y_2+1) \cdot (x_2+y_2)}{2} + x_2, \) ponieważ jednak

\( \frac{(x_1+y_1+1) \cdot (x_1+y_1)}{2} = \frac{(z+1) \cdot (z)}{2} = \frac{(x_2+y_2+1) \cdot (x_2+y_2)}{2}, \) to \( x_1=x_2 \) i skoro \( x_1+y_1=x_2+y_2 \), to również \( y_1=y_2 \).

2. W pozostałym przypadku mamy \( x_1+y_1\neq x_2+y_2 \). Możemy, bez straty ogólności założyć, że \( x_1+y_1 < x_2+y_2 \). Niech \( z=x_1+y_1 \) oraz \( c \) niech będzie takie, że \( z+c=x_2+y_2 \). Wtedy

\( f(x_1,y_1)= \frac{(x_1+y_1+1) \cdot (x_1+y_1)}{2} + x_1 \leq \frac{(z+1) \cdot (z)}{2} + z \)

oraz

\( f(x_2,y_2)= \frac{(x_2+y_2+1) \cdot (x_2+y_2)}{2} + x_2 \geq \frac{(z+c+1) \cdot (z+c)}{2} \geq \frac{(z+2) \cdot (z+1)}{2}. \)

Ostatnia nierówność wynika z faktu, że \( c\geq 1 \). Łatwo zauważyć, że

\( \frac{(z+1) \cdot (z)}{2} + z = \frac{z^2+3\cdot z}{2} < \frac{z^2+3\cdot z +1}{2} = \frac{(z+2) \cdot (z+1)}{2}, \)

co dowodzi, że \( f(x_1,y_1) < f(x_2,y_2) \).

Przypuśćmy teraz, że \( f(x_1,y_1)= f(x_2,y_2) \), wtedy przypadek drugi nie może się zdarzyć, gdyż doszlibyśmy do sprzeczności. W pozostałym (pierwszym) przypadku równość ta implikuje \( x_1=x_2 \) oraz \( y_1=y_2 \). A więc funkcja \( f \) jest iniekcją.