Twierdzenie o faktoryzacji
W tym rozdziale udowodnimy ważne twierdzenie dobrze ilustrujące rolę, którą spełniają iniekcje i suriekcje wśród wszystkich funkcji.
Twierdzenie 5.1.
Dla każdej funkcji \( f:X \rightarrow Y \) istnieje zbiór \( Z \) oraz funkcje \( g:X \rightarrow Z ,h:Z \rightarrow Y \) takie, że \( f= h \circ g \), \( g \) jest suriekcją i \( h \) jest iniekcją.
Dowód
Niech \( Z \) będzie zbiorem klas abstrakcji relacji \( \sim_{f} \). Wtedy definujemy \( g \) jako funkcję, która każdemu elementowi zbioru \( x \) przypisuje jego klasę abstrakcji względem relacji \( \sim_{f} \), czyli
\( g= \{(x,k)\in X\times \mathcal{P}(X):x\in X \wedge k=[x]_{\sim_{f}} \}. \)
Zauważmy, że tak zdefiniowana funkcja \( g \) jest suriekcją na zbiór \( Z \), gdyż klasy abstrakcji nie mogą być puste. Funkcję \( h \) defniujemy jako funkcję przypisującą klasom abstrakcji relacji \( \sim_{f} \) wartość funkcji na dowolnym elemencie tej klasy, czyli
\( h= \{(k,y)\in \mathcal{P}(X)\times Y: \exists_{x\in X} k=[x]_{\sim_{f}} \wedge f(x)=y\}. \)
Zauważmy, że \( h \) rzeczywiście jest funkcją, gdyż, zgodnie z definicją relacji \( \sim_{f} \), funkcja \( f \) przypisuje wszystkim elementom danej klasy te same wartości.
Pokażemy teraz, że \( h \) jest iniekcją. Weźmy dowolne dwie klasy \( k_1,k_2 \in Z \) i przypuśćmy, że \( h(k_1)=h(k_2) \). Niech \( x_1,x_2 \in X \) będą takimi elementami, że \( [x_1]_{\sim_{f}}=k_1 \) oraz \( [x_2]_{\sim_{f}}=k_2 \). Zgodnie z definicją \( h \) mamy \( h(k_1)= f(x_1) \) oraz \( h(k_2)=f(x_2) \). Założyliśmy, że \( h(k_1)=h(k_2) \), więc również \( f(x_1)=f(x_2) \). Wynika stąd, że \( x_1 \sim_{f} x_2 \), a więc \( [x_1]_{\sim_{f}}=[x_2]_{\sim_{f}} \), co oznacza dokładnie, że \( k_1 = k_2 \). Pokazaliśmy więc, że \( h \) jest iniekcją.
Pozostaje pokazać, że \( f= h \circ g \). Dla dowolnego elementu \( x\in X \) mamy
\( g(x)=[x]_{\sim_{f}} \)
oraz
\( h([x]_{\sim_{f}})= f(x). \)
Wobec czego otrzymujemy \( h(g(x))=f(x). \)
Skoro własność ta zachodzi dla każdego \( x\in X \), otrzymujemy \( f= h\circ g \).
Ćwiczenie 5.1
Dla poniższych funkcji podaj przykład funkcji \( g,h \) oraz zbioru \( Z \) z twierdzenia 5.1 o faktoryzacji (patrz twierdzenie 5.1.)
1. Niech \( K \) będzie zbiorem okręgów na płaszczyźnie, funkcja \( f:K \rightarrow R \) niech przypisuje okręgom długości ich średnic,
2. \( f:N^2 \rightarrow R \) w taki sposób, że \( f(x,y)=\frac{x}{y} \).