Informatyka MIMUW

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