1. Strona główna
  2. Wstęp do Matematyki
  3. 05. Produkt i suma

05. Produkt i suma

 

1. Obiekty i odwzorowania

Interesuje nas ujęcie w abstrakcyjnych terminach pojęć takich jak suma, produkt, przestrzeń funkcji z $A$ do $B$. W poprzednich wykładach za pojęcia atomowe uznaliśmy punkty, proste i okręgi w geometrii Euklidesowej, zbiory w teorii zbiorów i zdania w rachunku zdań. W poniższych konstrukcjach za atomy uznamy odwzorowania, obiekty oraz składanie odwzorowań. W przybliżeniu naśladujemy podejście z artykułu An elementary theory of the category of sets autorstwa F. Williama Lawvere. Jeśli ktoś z Państwa chciałby “wyklikać” te konstrukcje, to można to zrobić na stronie Jocelyn Ireson-Paine. Klikanie polega na podaniu konkretnych zbiorów skończonych jako obiektów, na których ma być wykonana dana konstrukcja, a komputer podaje żądane nowe zbiory i odwzorowania i weryfikuje je na przykładach.

Piszemy $A\stackrel{f}{\to} B$, jeśli $A,B$ są obiektami, a $f$ jest odwzorowaniem między $A$ i $B$. Obiekt $A$ nazwiemy dziedziną $f$, a obiekt $B$ przeciwdziedziną $g$. Jeśli $A\stackrel{f}{\to} B$ i $B\stackrel{g}{\to} C$, to zakładamy, że istnieje złożenie, oznaczane $fg$. Pisząc

(1)
\[A\stackrel{f}{\to} B\stackrel{g}{\to} C \]

mamy na myśli złożenie $A\stackrel{fg}{\to} C$.

2. Aksjomaty

  • Łączność: jeśli $A\stackrel{f}{\to}B$, $B\stackrel{g}{\to} C$, $C\stackrel{h}{\to} D$to
    (2)
    \[h(gf) = (hg)f. \]
  • Istnienie identyczności: dla każdego obiektu $A$ istnieje odwzorowanie $1_A$, którego dziedziną i przeciwdziedziną jest $A$ i takie, że każdego odwzorowania $g$, $B\stackrel{g}{\to} C$, zachodzi
    (3)
    \[1_Bg=g=g1_C. \]

3. Izomorfizmy

Odwzorowanie $A\stackrel{f}{\to}B$ jest izomorfizmem, jeśli istnieje odwzorowanie $B\stackrel{g}{\to}A$ o tej własności, że $fg = 1_B$ oraz $gf = 1_A$. Odwzorowanie $g$ nazywamy odwrotnością $f$.

Lemat 1. Dla każdego izomorfizmu $A\stackrel{f}{\to}B$ jego odwrotność jest jednoznacznie wyznaczona.

Dowód. Załóżmy, że $B\stackrel{g_1}{\to}A$, $B\stackrel{g_2}{\to}A$ są odwrotnościami $f$. Wtedy

(4)
\[(g_1f)g_2 = g_1(fg_2) \]

dzięki aksjomatowi łączności. Z definicji odwrotności i definicji identyczności dostajemy

(5)
\[g_2 = 1_Ag_2 = g_11_B = g_1 \]

To kończy dowód lematu Lematu 1. $\QEDA$

Zadanie 1. Mówimy, że $g$ jest lewą odwrotnością $A\stackrel{f}{\to}B$, jeśli $B\stackrel{g}{\to}A$ i $gf= 1_A$. Mówimy, że $g$ jest prawą odwrotnością $A\stackrel{f}{\to}B$, jeśli $B\stackrel{g}{\to}A$ i $fg= 1_B$. Udowodnij, że jeśli $g_1$ jest lewą odwrotnością, a $g_2$ prawą odwrotnością, to $g_1=g_2$.

4. Obiekt końcowy i początkowy, pojęcie elementu

Obiekt końcowy $1$ definiujemy jako obiekt o tej własności, że dla każdego obiektu $A$ istnieje dokładnie jedno odwzorowania $A\to 1$. Obiek początkowy $0$ definiujemy jako obiekt o tej własności, a dla każdego obiektu $A$ istnieje dokładnie jedno odwzorowania $0\to A$.

5. Produkt dwóch obiektów

Dla danych dwóch obiektów $A$, $B$ przez produkt $A$ i $B$ rozumiemy obiekt $A\times B$ raz dwa odwzorowania $p_A$, $p_B$ takie, że

\[\xymatrix @-0.5em{ & A \\ A\times B \ar[ru]^{p_A} \ar[rd]_{p_B} & \\ & B } \]

dla dowolnego obiektu $X$ oraz dwóch odwzorowań $f_A,f_B$

\[\xymatrix @-0.5em{ & A \\ X \ar[ru]^{f_A} \ar[rd]_{f_B} & \\ & B } \]

istniej dokładnie jedno odwzorowanie $X\stackrel{h}{\to}A\times B$ takie, że $hp_A = f_A$ oraz $hp_B=f_B$, co równoważnie można wysłowić przy pomocy diagramu

\[\xymatrix @-0.5em{ & & & A \\ X \ar[rrru]^{f_A} \ar[rrrd]_{f_B} \ar@{-->}[rr]^h & & A\times B \ar[ru]_{p_A} \ar[rd]^{p_B} & \\ & & & B } \]

Zadanie 2. Wykaż, że $(A\times B)\times (C\times D) \cong (A\times C)\times (B\times D)$.

Zadanie 3. Wykaż, że $A\times 1\cong A\cong 1\times A$.

W odniesieniu do zbiorów, produkt można zaimplementować na przykład przy pomocy pary Kuratowskiego. Mianowicie, dla zbiorów $a,b$ definiujemy parę Kuratowskiego jako $\{\{a\},\{a,b\}\}$. W istocie dowolna inna konstrukcja pary $(a,b)$ byłaby dobra, jeśli spełnione byłyby warunek, że $(a,b)=(x,y)$ wtedy i tylko wtedy, gdy $a=x$ i $b=y$.

Lemat 2. Niech $A$, $B$ będą zbiorami. Wtedy zbiór $A\times B = \{ (a,b) : a\in A, b\in B\}$ wraz z odwzorowaniami $p_A(a,b)=a$, $p_B(a,b)=b$, jest produktem zbiorów $A$ i $B$.

Dowód. Rozważmy obiekt $X$ oraz dwa odwzorowania $f_A,f_B$

\[\xymatrix @-0.5em{ & A \\ X \ar[ru]^{f_A} \ar[rd]_{f_B} & \\ & B } \]

Naszym zadaniem jest skonstruować $h$ takie, żeby diagram okazał się przemienny.

\[\xymatrix @-0.5em{ & & & A \\ X \ar[rrru]^{f_A} \ar[rrrd]_{f_B} \ar@{-->}[rr]^h & & A\times B \ar[ru]_{p_A} \ar[rd]^{p_B} & \\ & & & B } \]

Niech $h(x) = (f_A(x),f_B(x))$. Wtedy $\pi_A(h(x))=f_A(x)$ oraz $\pi_B(h(x)) = f_B(x)$. Należy jeszcze zauważyć, że $h$ jest jednoznacznie wyznaczone, gdyż z warunków $\pi_A(h(x))=f_A(x)$ oraz $\pi_B(h(x)) = f_B(x)$ można już stwierdzić, że $h(x) = (f_A(x),f_B(x))$. $\QEDA$.

Zadanie 4. Sprawdż, że w przypadku definicji pary uporządkowanej w wersji Kuratowskiego, możemy zdediniować $\pi_A(x) = \bigcup\bigcap x$. Podaj wzór na $\pi_B$ i sprawdź jego poprawność.

Zadanie 5. Sprawdż, że para $(a,b)'$ zdefiniowana wzorem $\{ a, \{a,b\} \}$ spełnia warunek, że $(a,b)=(x,y)$ wtedy i tylko wtedy, gdy $a=x$ i $b=y$. Znajdź odwzorowania $\pi_A$ i $\pi_B$ dla tej pary.

6. Implementacja funkcji jako relacji binarnych

Wszystkie podane w tym wykładzie definicje odnoszą się do ogólnych obiektów, ale na naszym wykładzie jesteśmy szczególnie zainteresowani zbiorami. Jest to szczególny rodzaj obiektów, dla których odwzorowania $A\stackrel{f}{\to}B$ możemy zdefiniować jako podzbiory $A\times B$ o tej własności, że dla każdego $x\in A$ istnieje dokładnie jeden $y\in B$ taki, że $(x,y)\in f$. Zatem każdemu elementowi w dziedzinie $f$ odpowiada dokładnie jeden element w przeciwdziedzinie $f$. Taką implementację pojęcia funkcji będziemy nazywać implementacją funkcji jako relacji binarnej.

Zadanie 6. Przy implementacji funkcji jako relacji binarnych sprawdź, że obiektem początkowym jest zbiór pusty, a obiektem końcowym jest każdy singleton.

W terminach obiektów i odwzorowań możemy zdefiniować także pojęcie elementu. Mówimy, że odwzorowanie $x$ jest elementem obiektu $A$, jeśli $1\stackrel{x}{\to}A$ (ozn. $x\epsilon A$). W poniższym zadaniu sprawdzamy, że w odniesieniu do zbiorów i funkcji jako relacji binarnych, pojęcia $\epsilon$ i $\in$ działają  tak samo.

Zadanie 7. Niech $A\stackrel{f}{\to}B$ będzie funkcją i niech $A$, $B$ będą zbiorami. Przy implementacji funkcji jako relacji binarnych sprawdź, że

(6)
\[ \forall_x (x\epsilon A\Rightarrow \exists^!_y (y\epsilon B\text{ i } f(x)=y)) \]

7. Suma dwóch obiektów

Sumą obiektów $A,B$ jest obiekt $A+B$ oraz odwzorowania $i_A,i_B$ takie, że następujący diagram

\[\xymatrix @-0.5em{ A \ar[rd]_{i_A} \ar[rrrd]^{f_A} & & & \\ & A + B \ar@{-->}[rr]^h & & X \\ B \ar[ru]^{i_B} \ar[rrru]_{f_B} & & & } \]

jest przemienny. Oznacza to, że dla dowolnych odwzorowań $A\stackrel{f_A}{\to}X$, $B\stackrel{f_B}{\to}X$ ma istnieć dokładnie jedno odwzorowanie $A+B\stackrel{h}{\to}X$ takie, że

\[hi_A = f_A\ \text{oraz}\ hi_B = f_B \]

Lemat 3. Niech $A$, $B$ będą zbiorami. Wtedy $\{ A \}\times\{0\}\cup \{ B\}\times \{1\}$ wraz z odwzorowaniami $i_A(x) = (x,0)$ oraz $i_B(x) = (x,1)$ spełnia warunki definicji sumy.

Dowód. Ustalmy dowolne $X$ oraz odwzorowania $A\stackrel{f_A}{\to}X$, $B\stackrel{f_B}{\to}X$. Dla $x\in A+B$ definiujemy

\[h(x) = \begin{cases} f_A(a), & \text{ jeśli } x = (a,0),\\ f_B(b), & \text{ jeśli } x = (b,1). \end{cases} \]

Jeśli $a\in A$, to wtedy $hi_A(a) = f_A(a)$ i podobnie, jeśli $b\in B$, to wtedy $hi_B(b) = f_B(a)$. Ponadto wzory $hi_A(a) = f_A(a)$ ($a\in A$), $hi_B(b) = f_B(a)$ ($b\in B$) jednoznacznie określają $h$ na całym zbiorze $A+B$.

8. Epimorfizm`

Poniższy diagram czytamy następujaco: $e$ jest epimorfizmem, jeśli z warunku, że $g_1e = g_2e$ wynika, że $g_1 = g_2$.

\[\xymatrix @-0.5em{ E \ar[r]^{e} & A \ar@<-.5ex>[r]_{g_2} \ar@<.5ex>[r]^{g_1} & B } \]

Zadanie 8. Sprawdź, że złożenie dwóch epimorfizmów jest epimorfizmem.

Zadanie 9. Sprawdź, że jeśli $e$ jest odwzorowaniem z $A$ do $B$ zakodwanym jako relacja binarna i dla każdego $b\in B$ istnieje $a\in A$ takie, że $e(a) = b$, to $f$ jest epimorfizmem.

9. Monomofizm

Poniższy diagram czytamy następujaco: $m$ jest monomorfizmem, jeśli z warunku, że $mg_1 = mg_2$ wynika, że $g_1 = g_2$.

\[\xymatrix @-0.5em{ A \ar@<-.5ex>[r]_{g_2} \ar@<.5ex>[r]^{g_1} & B \ar[r]^m & E^* } \]

Zadanie 10. Sprawdź, że złożenie dwóch monomorfizmów jest monomorfizmem.

Zadanie 11. Sprawdź, że jeśli $e$ jest odwzorowaniem z $A$ do $B$ zakodwanym jako relacja binarna i dla każdych $a_1,a_2\in A$, $a_1\neq a_2$ zachodzi $m(a_1)\neq m(a_2)$, to $m$ jest monomorfizmem.

10. Ekwaliztor

\[\xymatrix @-0.5em{ E \ar[r]^{k} & A \ar@<-.5ex>[r] \ar@<.5ex>[r] & B \\ & & & \\ & X \ar[uu]_u \ar@{-->}[uul]_u & } \]

Zadanie 12. Implementacja jako podzbioru, na którym $f,g$ się zgadzają.

11. Koekwaliztor

\[\xymatrix @-0.5em{ A \ar@<-.5ex>[r] \ar@<.5ex>[r] & B \ar[dd]_u \ar[r]^q & E^* \ar@{-->}[ddl]_z \\ & & & \\ & X & } \]

Zadanie 13. Implementacja jako relacji na $B\times B$.

12. Obiekt wykładniczy

Dla obiektów $A,B$ znajdziemy ogólną definicję “przestrzeni funkcji” z $A$ do $B$.

\[\xymatrix @-0.5em{ X\times Y \ar[dd]_{\lambda g\times i_Y} \ar@{-->}[rrdd]^{g} & & \\ & & \\ Z^Y\times Y \ar[rr]_{\text{eval}} & & Z } \]

Obiekt $Z^Y$ nazywamy obiektem wykładniczym, jeśli dla dowolnego obiektu $X$ i odwzorowania $g:X\times Y\to Z$ istnieje dokładnie jedno odwzorowanie $\lambda g:X\to Z^Y$ takie, że powyższy diagram jest przemienny.

Zadanie 14. Implementacja jako przestrzeni wszystkich funkcji z $Y$ do $Z$.

Created with Madoko.net.