|
|
| Linia 1: |
Linia 1: |
| ==Moduł: Teoria kategorii jako abstrakcyjna teoria funkcji==
| |
|
| |
|
| Teoria kategorii jako ogólny dział algebry wyrosła z prac Samuela
| |
| Eilenberga i Saundersa MacLane'a: pionierską pracą jest tu ''General
| |
| theory of natural equivalences'', Transactions of the American
| |
| Mathematical Society 58 (1945), pp. 231-294 -- autorzy wprowadzili tam
| |
| pojęcie kategorii, funktora i naturalnej transformacji funktorów. Teoria
| |
| kategorii szybko przekroczyła granice algebry i jej język okazał się
| |
| uniwersalnym sposobem mówienia o innych teoriach matematycznych: logice,
| |
| teorii zbiorów, topologii, teorii porządku, geometrii, analizie itd. Jak
| |
| to możliwe? Treść tych wykładów stanowi jedną z odpowiedzi na to pytanie.
| |
|
| |
| ===Przekształcenia i ich algebra===
| |
|
| |
| Zacznijmy od niegroźnego przeformułowania dwóch znanych pojęć z teorii
| |
| mnogości.
| |
|
| |
| Jak pamiętamy, funkcja <math>f\colon A\to B</math> jest '''bijekcją'''
| |
| jeśli jest różnowartościową surjekcją, tj. <math>\forall x,y\in A\
| |
| f(x)=f(y)\Rightarrow x=y</math> oraz <math>\forall z\in B\ \exists x\in
| |
| A\ f(x)=z.</math>
| |
|
| |
| Zauważmy, że drugi warunek pozwala nam każdemu elementowi <math>z</math>
| |
| zbioru <math>B</math> przyporządkować element <math>x</math> zbioru
| |
| <math>A</math>, zaś warunek pierwszy mówi, że to przekształcenie
| |
| (nazwijmy je <math>g</math>) jest funkcją (śmiało napiszmy więc
| |
| <math>g\colon B\to A</math>). W tym świetle z warunku drugiego wynika,
| |
| że złożenie <math>f\circ g</math> jest funkcją identycznościową na
| |
| zbiorze <math>B</math>, a stąd wynika <math>f\circ g\circ f = f</math>,
| |
| co w połączeniu z pierwszym warunkiem oznacza, że <math>g\circ f</math>
| |
| jest identycznością na zbiorze <math>A</math>. Idąc dalej tym tropem
| |
| (patrz Zadanie [[#mod1:zad1|Uzupelnic mod1:zad1|]]) jesteśmy w stanie
| |
| bez trudu pokazać, że:
| |
|
| |
| {{ Fakt||uzupelnic|
| |
|
| |
| {{kotwica|mod1:fact:bij|}} Funkcja <math>f\colon A\to B</math> jest
| |
| bijekcją wtedy i tylko wtedy, gdy istnieje funkcja <math>g\colon B\to
| |
| A</math> taka, że <math>f\circ g = 1_B</math> oraz <math>g\circ f =
| |
| 1_A</math>. }}
| |
|
| |
| Sam wynik nie wygląda, być może, ekscytująco, ale w koniunkcji z kolejnymi
| |
| przykładami pozwoli nam wyciągnąć ekscytujące wnioski.
| |
|
| |
| Rozważmy zatem zbiór liczb naturalnych
| |
| <math>\mathrm\bf{nat}</math>. Teoria mnogości definiuje
| |
| <math>\mathrm\bf{nat}</math> jako najmniejszy zbiór zawierający
| |
| liczbę zero <math>0</math> i spełniający: <math>n\in \mathrm\bf{nat}
| |
| \Rightarrow \mathrm{succ}(n)\in \mathrm\bf{nat}</math>, gdzie
| |
| <math>\mathrm{succ}\colon \mathrm\bf{nat}\to \mathrm\bf{nat}</math>
| |
| jest funkcją następnika (która jest injektywna i posiada tę właściwość,
| |
| że <math>\mathrm{succ}(n)\neq 0</math> dla dowolnego <math>n\in
| |
| \mathrm\bf{nat}</math>). Okazuje się, że zbiór liczb naturalnych
| |
| można wyróżnić spośród innych zbiorów w ten sposób (Zadanie
| |
| [[#mod1:zad2|Uzupelnic mod1:zad2|]]):
| |
|
| |
| {{ Fakt||uzupelnic| {{kotwica|mod1:fact:naturalne|}} Zbiór liczb
| |
| naturalnych <math>\mathrm\bf{nat}</math> jest to zbiór zawierający
| |
| liczbę zero oraz wyposażony w funkcję <math>\mathrm{succ}\colon
| |
| \mathrm\bf{nat}\to \mathrm\bf{nat}</math> taką, że: dla dowolnego
| |
| zbioru <math>X</math> i elementu <math>e\in X</math> oraz funkcji
| |
| <math>g\colon X\to X</math> istnieje dokładnie jedna funkcja <math>f\colon
| |
| \mathrm\bf{nat}\to X</math> spełniająca dwa warunki: <math>f(0)= e</math>
| |
| oraz <math>f\circ \mathrm{succ} = g\circ f</math>. }}
| |
|
| |
| Dwa powyższe przykłady wskazują na to, że definicje teorii mnogości można
| |
| wyrażać operując jedynie pojęciem funkcji i złożenia funkcji (zauważmy,
| |
| że elementy zbiorów można traktować jako funkcje, których dziedziną
| |
| jest singleton). Postawmy więc śmiałe pytanie: czy można prezentować
| |
| różnorodne teorie matematyczne badając jedynie własności przekształceń
| |
| obiektów matematycznych będących przedmiotem zainteresowania danej teorii?
| |
| A zatem pytamy czy: można prezentować teorię mnogości badając własności
| |
| funkcji między zbiorami, teorię grup badając własności homomorfizmów grup,
| |
| topologię badając własności funkcji ciągłych pomiędzy przestrzeniami
| |
| topologicznymi? W ogólności zapytajmy więc jeszcze raz: czy można badać
| |
| dowolne obiekty matematyczne z określoną strukturą za pomocą własności
| |
| przekształceń, które tę strukturę zachowują?
| |
|
| |
| Odpowiedź brzmi: ''tak'' -- i ta właśnie twierdząca odpowiedź powołuje do
| |
| życia teorię kategorii. Teoria kategorii składa się bowiem z twierdzeń
| |
| dotyczących uniwersalnych własności przekształceń, niezależnych od cech
| |
| szczególnych danych teorii matematycznych. Tak więc, teoria kategorii
| |
| bada wspólne, uniwersalne własnościami zbiorów, grup, przestrzeni
| |
| topologicznych, przestrzeni wektorowych, częściowych porządków, i tak
| |
| dalej, wszystko w języku przekształceń danej struktury.
| |
|
| |
| Czy da się krótko, nieformalnie zebrać najważniejsze cechy przekształceń
| |
| -- cechy niezależne od konkretnej teorii matematycznej? Spróbujmy!
| |
| Zaczynamy od nazwy: przekształcenie nazywać będziemy również
| |
| '''morfizmem''' (bo w przeróżnych teoriach matematycznych natykamy
| |
| się na homomorfizmy, homeomorfizmy, endomorfizmy, itd.) lub po
| |
| prostu '''strzałką''' (bo tak zwykle graficznie przedstawia się
| |
| przekształcenia). Przekształcenie działa pomiędzy '''obiektami''',
| |
| np. funkcja to przekształcenie zbiorów, homomorfizm to przekształcenie
| |
| grupy w grupę, funkcja ciągła to przekształcenie przestrzeni topologicznej
| |
| w przestrzeń topologiczną, funkcja monotoniczna to przekształcenie
| |
| posetu w poset, itd. (Załóżmy na początku dla prostoty, że w naszych
| |
| przykładach nie bierzemy pod uwagę przekształceń obiektów pewnej klasy w
| |
| obiekty innej klasy, na przykład wyznacznika, który przekształca macierz
| |
| w liczbę. Takimi morfizmami zajmiemy się poźniej.) Każde przekształcenie
| |
| <math>f</math> działa na pewien jedyny obiekt, nazwijmy go '''dziedziną'''
| |
| <math>f</math> i oznaczmy <math>\mathrm\it{dom}(f)</math>, i przekształca
| |
| go w inny jedyny obiekt nazywany '''przeciwdziedziną''' <math>f</math>
| |
| i oznaczany jako <math>\mathrm\it{cod}(f)</math>. Fakt, że morfizm
| |
| <math>f</math> ma dziedzinę <math>A</math> i przeciwdziedzinę
| |
| <math>B</math> zapisujemy
| |
|
| |
| \begin_quote\tt{Tu wstawić brakujący rysunek o numerze 1.1}\end_quote
| |
|
| |
| lub po prostu <math>f\colon A\to B</math>. Nasza teoria nie może istnieć
| |
| bez pojęcia '''złożenia''' przekształceń: zakładamy, że dwóm morfizmom
| |
| <math>f,g</math> takim, że <math>\mathrm{cod}(g)=\mathrm{dom}(f)</math>
| |
| (strzałki takie nazywamy '''składalnymi''') przypisujemy morfizm <math>f
| |
| \circ g</math> zwany złożeniem, dla którego mamy <math>\mathrm{dom}(f\circ
| |
| g) = \mathrm{dom}(g)</math> i <math>\mathrm{cod}(f\circ
| |
| g)=\mathrm{cod}(f)</math>. Przykłady wskazują na to, że kolejność
| |
| złożenia składalnych przekształceń nie powinna grać roli, czyli dla:
| |
|
| |
| \begin_quote\tt{Tu wstawić brakujący rysunek o numerze 1.2}\end_quote
| |
|
| |
| morfizm:
| |
|
| |
| \begin_quote\tt{Tu wstawić brakujący rysunek o numerze 1.3}\end_quote
| |
|
| |
| może powstać albo z:
| |
|
| |
| \begin_quote\tt{Tu wstawić brakujący rysunek o numerze 1.4}\end_quote
| |
|
| |
| albo, równoważnie, z:
| |
|
| |
| \begin_quote\tt{Tu wstawić brakujący rysunek o numerze 1.5}\end_quote
| |
|
| |
| W końcu, w naszej nieformalnej teorii przekształceń postulujemy istnienie
| |
| przekształceń, które - jak to się potocznie mówi: nic nie zmieniają,
| |
| tak zwanych '''identyczności''':
| |
|
| |
| \begin_quote\tt{Tu wstawić brakujący rysunek o numerze 1.6}\end_quote
| |
|
| |
| To kończy nieformalny opis języka, w którym główną rolę grają
| |
| przekształcenia. Zapiszmy to teraz formalnie.
| |
|
| |
| ===Definicja kategorii===
| |
|
| |
| {{ Definicja||uzupelnic|
| |
|
| |
| {{kotwica|mod1:def:kategria1|}} Kategoria <math>\mathbf{C}</math> składa
| |
| się z następujących danych:
| |
|
| |
| * (D1): '''obiektów''': <math>A,B,C,...</math>, * (D2): '''morfizmów''':
| |
| <math>f,g,h,...</math>, * (D3): dwóch operacji <math>\mathrm{dom},
| |
| \mathrm{cod}</math> przypisującej każdemu morfizmowi <math>f</math>
| |
| obiekty <math>\mathrm{dom}(f)</math>i <math>\mathrm{cod}(f)</math>,
| |
| * (D4): operacji <math>1</math> przypisującej każdemu obiektowi
| |
| <math>A</math> morfizm <math>1_A</math> nazywany identycznością, *
| |
| (D5): operacji <math>\circ</math> przypisującej każdej parze morfizmów
| |
| <math>f,g</math> takich, że <math>\mathrm{cod}(g) = \mathrm{dom}(f)</math>
| |
| morfizm <math>f\circ g</math> nazywany złożeniem,
| |
|
| |
| spełniających następujące aksjomaty:
| |
|
| |
| * (A1): <math>\mathrm{dom}(1_A) = A = \mathrm{cod}(1_A)</math>;
| |
| <math>\mathrm{dom}(f\circ g) = \mathrm{dom}(g)</math>;
| |
| <math>\mathrm{cod}(f\circ g)=\mathrm{cod}(f)</math>, * (A2): <math>f\circ
| |
| 1_A = f = 1_B \circ f</math>, gdzie <math>A=\mathrm{dom}(f)</math>
| |
| oraz <math>B=\mathrm{cod}(f)</math>, * (A3): jeśli <math>f,g</math>
| |
| są składalne oraz <math>g,h</math> są składalne, to <math>(f\circ g)
| |
| \circ h = f\circ(g\circ h)</math>.
| |
|
| |
| }}
| |
|
| |
| Kolekcję obiektów kategorii <math>\mathbf{C}</math> będziemy w dalszym
| |
| ciągu oznaczać jako <math>\mathbf{C}_0</math>, zaś kolekcję jej morfizmów
| |
| jako <math>\mathbf{C}_1</math>.
| |
|
| |
| {{ uwaga||uwaga_uzupelnic| Tylko dla dociekliwych: Wiemy więc z
| |
| czego ''składa się'' kategoria. Nie znamy jednak odpowiedzi na --
| |
| być może -- równie ważne pytanie: czym ''jest'' kategoria? W naszym
| |
| wykładzie przyjmiemy po prostu, że kategorią będzie każda interpretacja
| |
| aksjomatów przedstawionych w Definicji [[#mod1:def:kategria1|Uzupelnic
| |
| mod1:def:kategria1|]] na gruncie teorii mnogości. }}
| |
|
| |
| Pokażmy, że o kategorii można też myśleć jako o specjalnym grafie
| |
| skierowanym. Oto druga, równie dobra dla naszych potrzeb, definicja
| |
| kategorii:
| |
|
| |
| {{ Definicja||uzupelnic|
| |
|
| |
| {{kotwica|mod1:def:kategoria2|}} Grafem skierowanym nazywamy kolekcję
| |
| obiektów (wierzchołków) <math>O</math>, kolekcję strzałek (krawędzi)
| |
| <math>A</math> i dwie funkcje
| |
|
| |
| \begin_quote\tt{Tu wstawić brakujący rysunek o numerze 1.7}\end_quote
| |
|
| |
| W grafie, kolekcja składalnych par strzałek to zbiór <math>A\times_O A =\{
| |
| (g,f)\mid g,f\in A \wedge \mathrm{dom}(g) = \mathrm{cod}(f)\}</math>
| |
| nazywany '''produktem nad <math>O</math>'''. O kategorii można myśleć
| |
| jako o grafie skierowanym <math>\mathbf{C}</math>, który posiada dwie
| |
| dodatkowe funkcje <math>1\colon O\to A</math>, <math>C\mapsto 1_C</math>
| |
| oraz <math>\circ\colon A\times_O A\to A</math>, <math>(g,f)\mapsto
| |
| g\circ f</math> takie, że spełnione są warunki (A1)--(A3) Definicji
| |
| [[#mod1:def:kategria1|Uzupelnic mod1:def:kategria1|]]. }}
| |
|
| |
| Poniżej pokażemy trzecią, równoważną, algebraiczną definicję kategorii
| |
| (na podstawie książki: Peter J. Freyd, Andre Scedrov, ''Categories,
| |
| Allegories'', North Holland, 1989).
| |
|
| |
| {{ Definicja||uzupelnic|
| |
|
| |
| {{kotwica|mod1:def:kategoria3|}} Kategoria <math>\mathbf{C}</math> składa
| |
| się z dwóch operacji unarnych i jednej częściowej operacji binarnej.
| |
| Zmienne, na które działają te operacje nazywamy '''morfizmami'''
| |
| ('''strzałkami'''). Wartości tych operacji są zapisywane i czytane jako:
| |
|
| |
| \begin_quote\tt{Tu wstawić brakujący rysunek o numerze 1.8}\end_quote
| |
|
| |
| Operacje podlegają następującym aksjomatom:
| |
|
| |
| * (b1): <math>xy</math> jest zdefiniowane wtw, gdy <math>x\Box =
| |
| \Box y</math>, * (b2): <math>(\Box x )\Box = \Box x</math> oraz
| |
| <math>\Box (x\Box) = x\Box</math>, * (b3): <math>(\Box x)x = x</math>
| |
| oraz <math>x(x\Box)=x</math>, * (b4): <math>\Box(xy) = \Box(x(\Box
| |
| y))</math> oraz <math>(xy)\Box = ((x\Box)y)\Box</math> * (b5):
| |
| <math>x(yz)=(xy)z</math>.
| |
|
| |
| }}
| |
|
| |
| W tym wypadku równoważność definicji z dwiema pozostałymi
| |
| (Definicje [[#mod1:def:kategria1|Uzupelnic mod1:def:kategria1|]] i
| |
| [[#mod1:def:kategoria2|Uzupelnic mod1:def:kategoria2|]]) nie jest
| |
| oczywista. Aby ją wykazać, rozpocznijmy od lematu, który rzuci trochę
| |
| światła na strukturę algebraiczną, którą przed chwilą opisaliśmy.
| |
|
| |
| {{ Lemat||uzupelnic| {{kotwica|mod1:lemma:freyd1|}} Dla morfizmu
| |
| <math>e</math> następujące warunki są równoważne: istnieje <math>x</math>
| |
| taki, że <math>e=\Box x</math>; istnieje <math>y</math> taki, że
| |
| <math>e=y\Box</math>; <math>e=\Box e</math>; <math>e=e\Box</math>; dla
| |
| każdego <math>x</math>, <math>ex\approx x</math> (co oznacza, że jeśli
| |
| złożenie <math>ex</math> jest zdefiniowane, to jest równe <math>x</math>),
| |
| dla każdego <math>x</math>, <math>xe\approx x</math>.
| |
|
| |
| \proof{Dowód} (1)<math>\to</math>(2) Dla <math>y=\Box x</math> mamy
| |
| <math>y\Box = (\Box x)\Box = \Box x = e</math>. (2)<math>\to</math>(3)
| |
| <math>\Box e = \Box(y\Box) = y\Box = e</math>. (3)<math>\to</math>(4)
| |
| <math>e\Box = (\Box e)\Box)=\Box e = e</math>. (4)<math>\to</math>(5)
| |
| Załóżmy, że <math>ex</math> jest zdefiniowane dla każdego <math>x</math>;
| |
| to oznacza, że <math>e\Box = \Box x</math>, czyli z (4), <math>e=\Box
| |
| x</math> dla każdego <math>x</math>. A zatem <math>ex =(\Box x)x =
| |
| x</math>. (3)<math>\to</math>(1) Oczywiste. (4)<math>\to</math>(3)
| |
| <math>\Box e = \Box(e\Box) = e\Box = e</math>. (5)<math>\to</math>(4)
| |
| Połóżmy <math>x=e\Box</math>. Mamy <math>\Box x = \Box (e
| |
| \Box) = e\Box</math>, czyli <math>ex</math> istnieje. Z (5)
| |
| wynika, że <math>e(e\Box) = e\Box</math>. Ale (b3) implikuje, że
| |
| <math>e(e\Box)=e</math>, czyli <math>e=e\Box</math>. Dowód równoważności
| |
| (6) z (3) jest podobny do równoważności (5) z (4). }}
| |
|
| |
| Morfizm <math>e</math> spełniający dowolny z powyższych warunków nazywamy
| |
| '''identycznością'''.
| |
|
| |
| A zatem równoważność trzeciej definicji kategorii z
| |
| pierwszą uzyskujemy następująco (tak naprawdę, to pokażemy
| |
| jedynie, że dane Definicji [[#mod1:def:kategoria3|Uzupelnic
| |
| mod1:def:kategoria3|]] wystarczą do zrekonstruowania Definicji
| |
| [[#mod1:def:kategria1|Uzupelnic mod1:def:kategria1|]]:
| |
| Identyczność <math>1_x</math> to zmienna <math>x</math> taka,
| |
| że <math>x=\Box x =x\Box</math>. Dziedziną <math>x</math> jest
| |
| <math>\Box x</math>, przeciwdziedziną <math>x\Box</math>. Złożenie
| |
| <math>x\circ y</math> to <math>yx</math>. Kolekcja obiektów
| |
| Definicji [[#mod1:def:kategria1|Uzupelnic mod1:def:kategria1|]]
| |
| pokrywa się z kolekcją morfizmów identycznościowych Definicji
| |
| [[#mod1:def:kategoria3|Uzupelnic mod1:def:kategoria3|]]. Zauważmy,
| |
| że dla dowolnego <math>x</math>, zarówno <math>\Box x</math>,
| |
| jak i <math>x\Box</math> są obiektami (identycznościami), bo
| |
| <math>\Box(\Box x) = \Box x</math>, <math>(\Box x)\Box = \Box x</math>,
| |
| <math>(x\Box)\Box =(\Box(x\Box))\Box = \Box(x\Box) = x\Box</math>,
| |
| <math>\Box(x\Box)=x\Box</math>.
| |
|
| |
| Sprawdźmy aksjomaty: <math>\mathrm{dom}(1_x) = \Box x = x = x\Box
| |
| = \mathrm{cod}(1_x)</math>. Aby pokazać, że <math>f</math> jest
| |
| morfizmem, załóżmy, że <math>x=\mathrm{dom}(f)</math>(czyli <math>1_x =
| |
| \Box f</math>) oraz <math>y=\mathrm{cod}(f)</math> (czyli <math>1_y =
| |
| f\Box</math>)). Wówczas <math>f\circ 1_x = 1_x f = (\Box f)f = f</math>,
| |
| <math>1_y \circ f = f 1_y =f(f\Box) = f</math>.
| |
|
| |
| Załóżmy teraz, że <math>\mathrm{dom}(f)=\mathrm{cod}(g)</math>. Wówczas
| |
| <math>\mathrm{dom}(f\circ g) = \Box(gf) = \Box(g\Box
| |
| f) = \mathrm{dom}(1_{\mathrm{dom}(f)}\circ g) =
| |
| \mathrm{dom}(1_{\mathrm{cod}(g)}\circ g) = \mathrm{dom}(g)</math>.
| |
| Ostatnia równość wynika z poprzedniego paragrafu. Podobnie,
| |
| <math>\mathrm{cod}(f\circ g) = (gf)\Box = ((g\Box)f)\Box =
| |
| \mathrm{cod}(f\circ 1_{\mathrm{cod}(g)}) = \mathrm{cod}(f\circ
| |
| 1_{\mathrm{dom}(f)}) = \mathrm{cod}(f)</math>.
| |
|
| |
| W końcu, <math>f\circ (g\circ h) = (hg)f = h(gf)=(f\circ g)\circ h</math>
| |
| przy odpowiednich założeniach.
| |
|
| |
| ===Przykłady kategorii===
| |
|
| |
| * <math>\mathbf{Set}</math>: Obiektami są zbiory, morfizmami funkcje.
| |
| Uwaga! W teorii mnogości funkcja jest zdefiniowana jako zbiór par
| |
| uporządkowanych takich, że
| |
|
| |
| <math>
| |
|
| |
| ((x,y)\in f\ \wedge \ (x,y')\in f)\ \Rightarrow \ y=y'. </math>
| |
|
| |
| Aby traktować funkcje jako morfizmy musimy precyzyjnie znać
| |
| <math>\mathrm{dom}(f)</math> i <math>\mathrm{cod}(f)</math>. Na przykład
| |
| funkcje <math>\sin\colon \mathbb{R}\to [-1,1]</math> oraz <math>\sin\colon
| |
| \mathbb{R}\to \mathbb{R},</math>, które mają takie samo działanie
| |
| na argumentach, będą traktowane jako dwa różne morfizmy. Formalnie,
| |
| w języku teorii mnogości morfizmem będzie trójka <math>(X,f,Y)</math>
| |
| taka, że <math>f\subseteq X\times Y</math> spełnia powyższe równanie
| |
| ([[#eq:funkcja|Uzupelnic eq:funkcja|]]) wraz z poniższym:
| |
|
| |
| <math> x\in X \Rightarrow (\exists y\in Y\ (x,y)\in f). </math>
| |
|
| |
| Wtedy <math>\mathrm{dom}</math> jest projekcją na pierwszą współrzędną
| |
| <math>(X,f,Y)\mapsto X</math>, a <math>\mathrm{cod}</math> projekcją
| |
| na trzecią współrzędną. * Kategoria zbiorów skończonych i funkcji
| |
| <math> \mathbf{Set}_{fin} </math>, jak również wiele innych kategorii,
| |
| w których obiektami i morfizmami są ograniczone klasy zbiorów i funkcji,
| |
| np. kategoria wszystkich zbiorów skończonych i injekcji. * Kategorie,
| |
| w których obiektami są zbiory z pewną dodatkową stukturą algebraiczną,
| |
| zaś morfizmami te funkcje, które tę strukturę zachowują.
| |
|
| |
| * <math>\mathbf{Vect}</math>: Przestrzenie wektorowe i odwzorowania
| |
| liniowe * <math>\mathbf{Grp}</math>: Grupy i homomorfizmy grup *
| |
| <math>\mathbf{Ab}</math>: Grupy abelowe i homomorfizmy grup *
| |
| <math>\mathbf{Mon}</math>: Monoidy i homomorfizmy monoidów *
| |
| <math>\mathbf{Pos}</math>: Częściowe porządki i funkcje monotoniczne *
| |
| <math>\mathbf{Top}</math>: Przestrzenie topologiczne i funkcje ciągłe
| |
| * <math>\mathbf{Graph}</math>: Grafy i homomorfizmy grafów * liczby
| |
| naturalne <math>\mathrm\bf{nat}</math> i wszystkie funkcje obliczalne
| |
|
| |
| * Mając dowolny częściowy porządek (poset) <math>(P,\leq)</math>
| |
| definiujemy kategorię o tej samej nazwie <math>P</math> jak następuje:
| |
| jako obiekty bierzemy elementy <math> P</math>, zaś dla dwóch
| |
| obiektów <math> x,y\in P</math> przyjmujemy, że istnieje morfizm z
| |
| <math>x</math> do <math>y</math> wtedy i tylko wtedy, gdy <math>x\leq
| |
| y</math>. Zauważmy, że wystarczy tu, by <math>P</math> był preporządkiem,
| |
| tzn. aby relacja <math>\leq</math> była zaledwie zwrotna i przechodnia.
| |
| * <math>\mathbf{Rel}</math>: Obiektami tej kategorii są zbiory, zaś
| |
| morfizmami relacje binarne, tzn. <math> f\colon A\to B</math> wtedy
| |
| i tylko wtedy, gdy <math> f\subseteq A\times B</math>. Wówczas rolę
| |
| identyczności spełniają relacje identycznościowe: <math> 1_A = \{
| |
| (a,a)\mid a\in A \}</math>, zaś złożeniem morfizmów jest po prostu
| |
| złożenie relacji znane z kursu teorii mnogości: mając dane <math>
| |
| R\subseteq A\times B</math> oraz <math> S \subseteq B\times C</math>
| |
| przyjmujemy: <math> (a,c)\in S\circ R \Leftrightarrow \exists b\in
| |
| B\ ((a,b)\in R\wedge (b,c)\in S)</math> * \bfKategorie skończone:
| |
| (skończoność dotyczy ilości istniejących ''morfizmów'', choć nazwy tych
| |
| kategorii odnoszą się do ilości ''obiektów''):
| |
|
| |
| * <math>\mathbf{1}</math>: Ta kategoria ma jeden obiekt i jedną strzałkę:
| |
| identyczność.
| |
|
| |
| \begin_quote\tt{Tu wstawić brakujący rysunek o numerze 1.9}\end_quote
| |
|
| |
| * <math>\mathbf{0}</math>: Ta kategoria nie ma obiektów i nie ma strzałek.
| |
| * <math>\mathbf{2}</math>: Kategoria ta ma dwa obiekty i jedną strzałkę
| |
| pomiędzy nimi (a także oczywiście dwie wymagane identyczności).
| |
|
| |
| \begin_quote\tt{Tu wstawić brakujący rysunek o numerze 1.10}\end_quote
| |
|
| |
| * <math>\mathbf{3}</math>: Kategoria ma trzy obiekty, trzy identyczności,
| |
| dokładnie jedną strzałkę z obiektu pierwszego do drugiego, dokładnie
| |
| jedną strzałkę z obiektu drugiego do trzeciego i dokładnie jedną strzałkę
| |
| z obiektu pierwszego do trzeciego (co oznacza, że ta ostatnia musi być
| |
| złożeniem dwóch pozostałych nieidentycznościowych strzałek!)
| |
|
| |
| \begin_quote\tt{Tu wstawić brakujący rysunek o numerze 1.11}\end_quote
| |
|
| |
| * Inne kategorie skończone możemy tworzyć biorąc skończoną ilość obiektów
| |
| wraz z odpowiadającymi im identycznościami, a następnie dodając dowolną
| |
| skończoną ilość morfizmów. W tym wypadku musimy jednak zadbać o to, aby
| |
| - jeśli morfizmy będą tworzyły cykle - zadeklarować złożenia wszystkich
| |
| morfizmów w cyklu jako równe odpowiednim identycznościom. W innym bowiem
| |
| przypadku uzyskana kategoria nie musi już być skończona (może mieć
| |
| nieskończenie wiele morfizmów odpowiadających wielokrotnościom cyklu).
| |
|
| |
| * \bfKategorie dyskretne: są to takie kategorie, w których nie ma
| |
| innych morfizmów niż identyczności. Łatwo uzmysłowić sobie, że kategorie
| |
| dyskretne możemy utożsamiać ze zbiorami, bo przecież obiekty możemy
| |
| interpretować jako elementy zbioru.
| |
|
| |
| \begin_quote\tt{Tu wstawić brakujący rysunek o numerze 1.12}\end_quote
| |
|
| |
| * Niech <math>(M, *, e)</math> będzie monoidem (<math>e</math> jest
| |
| jego jedynką). Wówczas biorąc <math>M</math> jako jedyny obiekt,
| |
| zaś elementy <math>M</math> jako morfizmy (z dziedziną i kodziedziną
| |
| <math>M</math>), a działanie <math>*</math> jako złożenie morfizmów,
| |
| otrzymujemy kategorię. Można łatwo pokazać również konstrukcję odwrotną,
| |
| tj. przekonać się, że każda kategoria z jednym obiektem może być
| |
| traktowana jako monoid. Mówiąc krótko: kategorie z jednym obiektem to
| |
| monoidy. (Jak w takim razie traktować grupy? Odpowiedź znajdziemy jeszcze
| |
| przed końcem wykładu...)
| |
|
| |
| \begin_quote\tt{Tu wstawić brakujący rysunek o numerze 1.13}\end_quote
| |
|
| |
| * Dla danego rachunku logicznego możemy stworzyć kategorię w ten
| |
| sposób, że obiektami są formuły: <math>\phi, \psi, ...</math> zaś
| |
| morfizmem z <math>\phi</math> do <math>\psi</math> jest każda dedukcja
| |
| (dowód) <math>\psi</math> z założenia <math>\phi</math>. Złożeniem
| |
| morfizmów jest wtedy połączenie dowodów, które jest oczywiście
| |
| łączne. Identyczność <math>1_\phi{}</math> to dowód pusty, bowiem
| |
| z aksjomatów logicznych zawsze wynika <math>\phi\vdash\phi</math>.
| |
| * Dla danego typowanego języka funkcyjnego <math>L</math> tworzymy
| |
| kategorię w ten sposób, że obiektami są typy danych, zaś strzałkami są
| |
| programy (procedury) języka <math>L</math>. Złożenie dwóch programów
| |
| <math>X\stackrel{f}\to{}Y\stackrel{g}\to{}Z</math> jest program dany
| |
| poprzez zaaplikowanie wyjścia programu <math>f</math> na wejściu programu
| |
| <math>g</math>. Identycznością jest procedura, która ''nic nie robi''.
| |
|
| |
| Inne przykłady kategorii zamieścimy w Ćwiczeniach do tego wykładu.
| |
|
| |
| ===Izomorfizmy===
| |
|
| |
| Definicja izomorfizmu jest pierwszą definicją teorii kategorii,
| |
| definicją abstrakcyjną, niezależną od specyficznych wymagań konkretnej
| |
| teorii matematycznej, definicją wyrażoną tylko w języku strzałek (czyli
| |
| w języku teorii kategorii).
| |
|
| |
| {{ Definicja||uzupelnic| {{kotwica|mod1:def:iso|}} Niech
| |
| <math>\mathbf{C}</math> będzie dowolną kategorią. Morfizm <math>
| |
| f\colon A\to B</math> jest '''izomorfizmem''' jeśli istnieje morfizm
| |
| <math> g\colon B\to A</math> taki, że <math> f\circ g = 1_B </math>
| |
| oraz <math> g\circ f = 1_A</math>. Morfizm <math> g</math> nazywa się
| |
| '''morfizmem odwrotnym do <math> f</math>''' . Jeśli dla obiektów <math>
| |
| A,B</math> kategorii <math> \mathbf{C}</math> istnieje izomorfizm <math>
| |
| f\colon A\to B</math>, to obiekty <math> A</math> i <math> B</math>
| |
| nazywamy izomorficznymi, co zapisujemy jako <math>A\cong B</math>. }}
| |
|
| |
| Ponieważ dowolny morfizm <math> f</math> posiada dokładnie jeden
| |
| morfizm odwrotny (dowód?), będziemy go oznaczać jako <math> f^{-1}
| |
| </math>. Można łatwo pokazać (dowód?), że morfizm odwrotny do izomorfizmu
| |
| jest izomorfizmem.
| |
|
| |
| Fakt [[#mod1:fact:bij|Uzupelnic mod1:fact:bij|]] wyraża zatem
| |
| myśl, że izomorfizmami w <math>\mathbf{Set}</math> są dokładnie
| |
| bijekcje. Ale uwaga: w kategoriach, których obiektami są zbiory
| |
| z pewną strukturą, a morfizmami funkcje zachowujące tę strukturę
| |
| (kategorie o takich własnościach nazywamy konkretnymi, patrz Definicja
| |
| [[#mod5:def:konkret|Uzupelnic mod5:def:konkret|]], bijekcje ''nie zawsze''
| |
| są izomorfizmami. Prosty kontrprzykład stanowi tutaj kategoria <math>
| |
| \mathbf{Pos}</math> (Zadanie [[#mod1:zad3|Uzupelnic mod1:zad3|]]).
| |
|
| |
| ===Podstawy teoriomnogościowe===
| |
|
| |
| Teoria mnogości uczy nas, że nie istnieje zbiór wszystkich zbiorów. Jeśli
| |
| więc rozważamy kategorię <math> \mathbf{Set} </math>, której obiektami
| |
| są zbiory, to widzimy, że kolekcja wszystkich obiektów <math>
| |
| \mathbf{Set}</math> nie tworzy zbioru (jest zbyt duża!). Podobnie,
| |
| kolekcja wszystkich morfizmów <math> \mathbf{Set}</math> jest zbyt wielka,
| |
| aby być zbiorem (zauważmy, że samych identyczności jest już tyle, ile
| |
| obiektów). Kategoria <math> \mathbf{Set}</math> nie jest taką jedyną. W
| |
| związku z tym definiujemy:
| |
|
| |
| {{ Definicja||uzupelnic| {{kotwica|mod1:def:size|}} Kategorię
| |
| <math>\mathbf{C}</math> nazywamy '''małą''', jeśli kolekcja wszystkich
| |
| obiektów <math> \mathbf{C}_0 </math> i morfizmów <math> \mathbf{C}_1
| |
| </math> kategorii <math>\mathbf{C}</math> są zbiorami. W przeciwnym
| |
| wypadku <math>\mathbf{C}</math> jest '''duża'''. }}
| |
|
| |
| A zatem <math> \mathbf{Pos}</math>, <math> \mathbf{Grp}</math>, <math>
| |
| \mathbf{Vec}</math> są duże, zaś kategorie skończone są małe. Kategorie
| |
| duże wyglądają na pierwszy rzut oka bardzo nieprzyjaźnie, część z nich
| |
| posiada jednak bardzo często następującą cechę:
| |
|
| |
| {{ Definicja||uzupelnic| {{kotwica|mod1:def:localsize|}} Kategorię <math>
| |
| \mathbf{C} </math> nazywamy '''lokalnie małą''' jeśli dla każdej pary
| |
| obiektów <math> A,B</math> z <math> \mathbf{C} </math> kolekcja <math>
| |
| \mathrm{Hom}_{\mathbf{C}}(A,B) = \{ f\in \mathbf{C}_1\mid f\colon A\to B
| |
| \} </math> jest zbiorem (o takim zbiorze mówimy w skrócie '''homset''',
| |
| podobnie jak o zbiorze częściowo uporządkowanym przyjęło się mówić:
| |
| poset). }}
| |
|
| |
| Większa część teorii kategorii, którą zaprezentujemy
| |
| w dalszym toku wykładu dotyczy kategorii lokalnie małych
| |
| (takich jak <math>\mathbf{Pos}</math>, <math>\mathbf{Grp}</math>,
| |
| <math>\mathbf{Vec}</math> itd. czy wszystkie kategorie małe). Po dalsze
| |
| wiadomości dotyczące podstaw teoriomnogościowych teorii kategorii
| |
| odsyłamy do dyskusji tego tematu w podręczniku ''Categories for the
| |
| Working Mathematician'', Springer, 1997, Saundersa Mac Lane'a. Bardzo
| |
| ciekawą dyskusję roli teorii kategorii w badaniach nad podstawami
| |
| matematyki zaproponował Steven Awodey w artykule: ''An answer to
| |
| Hellman's question: ``Does category theory provide a framework for
| |
| mathematical structuralism?'''', Philosophia Mathematics (3) vol. 12
| |
| (2004), dostępnym również na stronie domowej autora pracy.
| |
|
| |
| ===Ćwiczenia do Modułu 1===
| |
|
| |
| {{ Zadanie||uzupelnic|
| |
|
| |
| {{kotwica|mod1:zad1|}} Udowodnij, że dla dwóch funkcji <math>f\colon
| |
| A\to B</math> oraz <math>g\colon B\to A</math> jeśli <math>f\circ g =
| |
| 1_B</math> oraz <math>g\circ f = 1_A</math>, to funkcja <math>f</math>
| |
| jest bijekcją.
| |
|
| |
| \proof[Rozwiązanie:] Pokażemy najpierw, że <math>f</math> jest funkcją
| |
| różnowartościową. Przypuśćmy, że <math>f(x)= f(y)</math> dla pewnych
| |
| elementów <math>x,y\in A</math>. Wówczas <math>x = 1_A(x) = (g\circ
| |
| f)(x) = g(f(x)) = g(f(y)) = (g\circ f)(y) = 1_A(y) = y</math>. Ponadto,
| |
| dla dowolnego <math>z\in B</math> element <math>g(z)</math> jest jedynym
| |
| takim elementem, że <math>f(g(z)) = z</math>, co w szczególności oznacza,
| |
| że <math>f</math> jest surjekcją. Wnioskujemy więc, że <math>f</math>
| |
| jest różnowartościową surjekcją, czyli bijekcją. }}
| |
|
| |
| {{ Zadanie||uzupelnic|
| |
|
| |
| {{kotwica|mod1:zad2|}} Udowodnij Fakt [[#mod1:fact:naturalne|Uzupelnic
| |
| mod1:fact:naturalne|]].
| |
|
| |
| \proof[Wskazówka:] Fakt, że liczby naturalne posiadają wspomnianą w
| |
| Fakcie [[#mod1:fact:naturalne|Uzupelnic mod1:fact:naturalne|]] jest
| |
| dokładnie twierdzeniem o rekursji. Pozostaje nam zatem udowodnienie
| |
| implikacji przeciwnej.
| |
|
| |
| \proof[Rozwiązanie:] Załóżmy zatem, że <math>N</math> jest pewnym
| |
| zbiorem, który posiada wyróżniony element <math>0\in N</math> i funkcję
| |
| <math>s\colon N\to N</math> spełniającą warunki zadania. Udowodnimy
| |
| po kolei następujące zdania (znane jako aksjomaty Peano), które --
| |
| zgodnie z wykładnią teorii mnogości -- w sposób jednoznaczny determinują
| |
| liczby naturalne spośród innych zbiorów, a co za tym idzie, potwierdzą,
| |
| że zbiór <math>N</math> jest zbiorem liczb naturalnych:
| |
|
| |
| * <math>\exists 0\in N</math>
| |
|
| |
| To wiemy z założenia.
| |
|
| |
| * <math>\forall n\in N \ s(n)\in N</math>
| |
|
| |
| To wiemy z założenia.
| |
|
| |
| * <math>\forall n\in N \ s(n)\neq 0</math>
| |
|
| |
| Przypuśćmy przeciwnie, że dla pewnego <math>n\in N</math> mamy
| |
| <math>s(n)=0</math>. Wtedy kładąc <math>X=\{e, a\}</math> oraz
| |
| <math>g(e)=g(a)=a</math>, z założenia istnieje funkcja <math>f\colon N\to
| |
| X</math> taka, że <math>f(0)=e</math> oraz <math>f(s(n))=g(f(n))</math>. A
| |
| zatem <math>f(s(n))=f(0)=e\neq a = g(f(n))</math>, sprzeczność.
| |
|
| |
| * <math>s</math> jest injekcją.
| |
|
| |
| Przypuśćmy, że <math>s(n) = s(m)</math> dla pewnych <math>n,m\in
| |
| N</math>. Kładąc <math>X := \{0,s(0),s(s(0)), ...\}</math> (jest to
| |
| podzbiór <math>N</math>) oraz <math>e:=0</math>, wiemy, że istnieje
| |
| funkcja <math>f\colon N\to X</math> taka, że <math>f(0)=0</math> oraz
| |
| <math>f(s(n))=s(f(n))</math>. Taka funkcja jest tylko jedna, więc jej
| |
| zawężenie do <math>X</math> musi być równe funkcji <math>h\colon
| |
| X\to X</math>, która spełnia warunki <math>h(0)=0</math> oraz
| |
| <math>h(s(n))=n</math> dla <math>n\neq 0</math>. Dlatego założenie
| |
| <math>s(n)=s(m)</math> implikuje <math>n=h(s(n))=h(s(m))=m</math>,
| |
| co należało pokazać.
| |
|
| |
| * <math>\forall A\subseteq N\ ((0\in A\wedge (a\in A\Rightarrow s(a)\in
| |
| A))\Rightarrow A=N)</math>
| |
|
| |
| W tym punkcie przedstawimy najpierw rozumowanie teoriomnogościowe, a potem
| |
| skorzystamy z okazji, aby ten sam dowód pokazać bardziej w duchu teorii
| |
| kategorii (stopniowo ten drugi rodzaj dowodów będzie zastępował pierwszy).
| |
|
| |
| Rozważmy zatem funkcję <math>s'\colon A\to A</math>, która -- będąc
| |
| obcięciem <math>s</math> do <math>A</math> -- spełnia warunek <math>s\circ
| |
| i = i\circ s'</math>, gdzie <math>i\colon A\to N</math> jest inkluzją
| |
| <math>A</math> w <math>N</math>. Zgodnie z założeniem zadania, dla
| |
| funkcji <math>s'</math> istnieje dokładnie jedna funkcja <math>f\colon
| |
| N\to A</math> taka, że <math>f(0)=0</math> oraz <math>s'\circ
| |
| f = f\circ s</math>. Łącząc tą równość z poprzednią, dostajemy
| |
| <math>s\circ i\circ f = i\circ f\circ s</math>. Zwróćmy teraz uwagę na
| |
| funkcję <math>i\circ f\colon N\to N</math>. Oczywiste spostrzeżenie,
| |
| że <math>i\circ f(0)=0</math> pozwala nam stwierdzić, że <math>i\circ
| |
| f</math> jest ''jedyną'' funkcją typu <math>N\to N</math>, która spełnia
| |
| ostatnią z równości. Skoro tak, to musi być równa identyczności na
| |
| <math>N</math>. Pokazaliśmy więc, że <math>i\circ f = 1_N</math>,
| |
| a stąd -- jak łatwo pokazać wynika, że <math>f\colon N\to A</math>
| |
| jest injekcją. A zatem <math>N\subseteq A</math>, co należało wykazać.
| |
|
| |
| Pokazaliśmy zatem, że aksjomaty Peano są spełnione dla zbioru
| |
| <math>N</math>, a zatem teoria mnogości uczy nas, że <math>N</math>
| |
| jest zbiorem liczb naturalnych <math>\mathrm\bf{nat}</math>.
| |
|
| |
| Dowód ostatniego z aksjomatów Peano prowadzony w duchu teorii kategorii,
| |
| czyli teorii przekształceń, korzysta z dobrodziejstwa, jakim jest
| |
| możliwość przedstawiania funkcji i ich złożeń na diagramach.
| |
|
| |
| Po pierwsze, spróbujmy przedstawić graficznie (na diagramach) założenia,
| |
| które mamy, tzn. zdanie: ''<math>N</math> jest zbiorem, który posiada
| |
| wyróżniony element <math>0</math> oraz funkcję <math>s\colon N\to
| |
| N</math> takie, że dla dowolnego innego zbioru <math>X</math> i elementu
| |
| <math>e\in X</math> oraz funkcji <math>g\colon X\to X</math> istnieje
| |
| dokładnie jedna funkcja <math>f\colon N\to X</math> spełniająca warunki
| |
| <math>f(0)=e</math> oraz <math>f\circ s = g\circ f</math>.''
| |
|
| |
| Zauważmy więc, że element <math>0\in N</math> może być zawsze traktowany
| |
| jako funkcja <math>0\colon \top \to N</math>, gdzie <math>\top</math> jest
| |
| dowolnym zbiorem jednoelementowym (zwróćmy uwagę, że w tej interpretacji
| |
| aplikacja funkcji staje się złożeniem, np. <math>f(0)</math> staje się
| |
| złożeniem <math>f\circ 0</math>). Podobnie dla <math>e\in X</math>. Po
| |
| drugie, wszelkie równości pomiędzy funkcjami przedstawiamy jako
| |
| komutowanie odpowiedniego diagramu, np. równość <math>f\circ s = g\circ
| |
| f</math> zachodzi wtedy i tylko wtedy, gdy poniższy diagram komutuje:
| |
|
| |
| \begin_quote\tt{Tu wstawić brakujący rysunek o numerze 1.14}\end_quote
| |
|
| |
| Następnie umawiamy się, że jeśli funkcja w diagramie jest jedyną,
| |
| która może znajdować się pomiędzy dwoma danymi obiektami, to zaznaczamy
| |
| ją przerywaną linią, np. zdanie ''...<math>f\colon N\to X</math> jest
| |
| jedyną funkcją taką, że...'' odzwierciedla się graficznie jako:
| |
|
| |
| \begin_quote\tt{Tu wstawić brakujący rysunek o numerze 1.15}\end_quote
| |
|
| |
| Jeśli diagram jest bardziej skomplikowany, to umawiamy się, że odczytujemy
| |
| '''wszystkie''' możliwe równania, przy czym umawiamy się, że nie musimy
| |
| rysować identyczności. A zatem diagram:
| |
|
| |
| \begin_quote\tt{Tu wstawić brakujący rysunek o numerze 1.16}\end_quote
| |
|
| |
| komutuje wtedy i tylko wtedy, gdy <math>0\in N</math>, <math>e\in
| |
| X</math>, <math>f(0)=e</math>, <math>f\circ s = g\circ f</math>,
| |
| <math>(f\circ s)(0) = g(e)</math> (ten wniosek wynika z czterech
| |
| pozostałych!) i <math>f</math> jest jedyną taką funkcją, która spełnia
| |
| wszystkie wymienione zależności. Tak więc powyższy diagram zawiera całą
| |
| informację dostępną w założeniach zadania.
| |
|
| |
| Przystąpmy więc do kategoryjnego dowodu ostatniego aksjomatu Peano. Oto
| |
| on: skoro diagram
| |
|
| |
| \begin_quote\tt{Tu wstawić brakujący rysunek o numerze 1.17}\end_quote
| |
|
| |
| komutuje, co możemy przedstawić również w skrócie jako:
| |
|
| |
| \begin_quote\tt{Tu wstawić brakujący rysunek o numerze 1.18}\end_quote
| |
|
| |
| jak również komutuje diagram:
| |
|
| |
| \begin_quote\tt{Tu wstawić brakujący rysunek o numerze 1.19}\end_quote
| |
|
| |
| to z warunku jednoznaczności istnienia funkcji dostajemy <math>i\circ
| |
| f = 1_N</math>. To jednak implikuje, że <math>f</math> jest injekcją,
| |
| czyli <math>N\subseteq A</math>, co należało pokazać.
| |
|
| |
| Jak zobaczymy w toku wykładu, dowody poprzez pokazanie komutujących
| |
| diagramów (czyli de facto wyeksplikowanie pewnych równości między
| |
| funkcjami -- czy też ogólniej: morfizmami) są bardzo często spotykane
| |
| w teorii kategorii, a nawet zastępują wszelkie inne dowody.
| |
|
| |
| }}
| |
|
| |
| {{ Zadanie||uzupelnic|
| |
|
| |
| {{kotwica|mod1:zad3|}} Znajdź przykład na to, że w kategorii
| |
| <math>\mathrm\bf{Pos}</math> bijekcje nie zawsze są izomorfizmami.
| |
|
| |
| \proof[Wskazówka:] Wystarczy rozważyć częściowe porządki dwuelementowe.
| |
|
| |
| \proof[Rozwiązanie:] Rozważmy dwa posety dwuelementowe
| |
| <math>P=\{x,y\}</math>, <math>Q=\{z,w\}</math> i funkcję <math>g\colon
| |
| Q\to P</math>, <math>g(z)=x, g(w)=y</math>, jak na rysunku:
| |
|
| |
| \begin_quote\tt{Tu wstawić brakujący rysunek o numerze 1.20}\end_quote
| |
|
| |
| Funkcja <math>g</math> jest oczywiście bijekcją, ale funkcja do
| |
| niej odwrotna nie jest monotoniczna, a zatem nie jest morfizmem w
| |
| <math>\mathrm\bf{Pos}</math>. To oznacza, że <math>g</math> nie może
| |
| być izomorfizmem. }}
| |
|
| |
| {{ Zadanie||uzupelnic|
| |
|
| |
| {{kotwica|mod1:zad4|}} Pokaż, że każda grupa może być traktowana jako
| |
| kategoria, w której każdy morfizm jest izomorfizmem.
| |
|
| |
| \proof[Rozwiązanie:] Niech <math>(G,\circ, e)</math> będzie
| |
| grupą. Podobnie jak w przypadku monoidów, deklarujemy <math>G</math>
| |
| jako jedyny obiekt pewnej kategorii, zaś elementy zbioru <math>G</math>
| |
| jako morfizmy tejże kategorii, działanie <math>\circ</math> jako złożenie
| |
| morfizmów, element <math>e</math> traktując jako identyczność na obiekcie
| |
| <math>G</math>. Zauważmy, że każdy element posiada element odwrotny,
| |
| czyli dla każdego <math>g\in G</math> istnieje <math>g^{-1}\in G</math>
| |
| tak, że <math>g\circ g^{-1} = e = g^{-1}\circ g</math>. Te równania
| |
| interpretowane w naszej kategorii czynią tenże dowolnie wybrany element
| |
| <math>g</math> izomorfizmem. }}
| |
|
| |
| {{ Zadanie||uzupelnic|
| |
|
| |
| {{kotwica|mod1:zad5|}} Dla dowolnej kategorii <math>\mathbf{C}</math>
| |
| zaproponuj konstrukcję nowej kategorii, w której -- żądamy -- obiektami
| |
| są morfizmy z <math>\mathbf{C}</math>.
| |
|
| |
| \proof[Wskazówka:] Niech <math>\mathbf{C}</math> będzie dowolną
| |
| kategorią; dla dwóch jej dowolnych morfizmów <math>f\colon A\to
| |
| B</math> oraz <math>g\colon C\to D</math>, musimy zaproponować taką
| |
| operację, dla której <math>f</math> jest dziedziną i <math>g</math>
| |
| jest kodziedziną. Gdyby przedstawić to graficznie, w postaci diagramu,
| |
| łatwo przyjdzie nam na myśl definicja takiej operacji: będzie to ''para
| |
| morfizmów'' <math>(a\colon A\to C, b\colon B\to D)</math> z kategorii
| |
| <math>\mathbf{C}</math> taka, że poniższy diagram komutuje:
| |
|
| |
| \begin_quote\tt{Tu wstawić brakujący rysunek o numerze 1.21}\end_quote
| |
|
| |
| Teraz już łatwo dopowiedzieć szczegóły konstrukcji.
| |
|
| |
| \proof[Rozwiązanie:] Zaproponujemy najpierw złożenie: dwa morfizmy
| |
| <math>(a,b)</math> oraz <math>(c,d)</math> jak poniżej:
| |
|
| |
| \begin_quote\tt{Tu wstawić brakujący rysunek o numerze 1.22}\end_quote
| |
|
| |
| składają się tak:
| |
|
| |
| \begin_quote\tt{Tu wstawić brakujący rysunek o numerze 1.23}\end_quote
| |
|
| |
| albo formalnie: <math>(a,b)\circ (c,d) = (a\circ c, b\circ
| |
| d)</math>. Oczywiście <math>\mathrm\it{dom}((a\circ c, b\circ d)) =
| |
| h</math> oraz <math>\mathrm\it{cod}((a\circ c, b\circ d)) = g</math>.
| |
| W końcu, identycznościami w nowej kategorii, która często oznacza się
| |
| jako <math>\mathbf{C}^\to{}</math> są pary identyczności z kategorii
| |
| <math>\mathbf{C}</math>. Wszelkie pozostałe czynności, które musimy
| |
| wykonać, by sprawdzić, że <math>\mathbf{C}</math> jest kategorią,
| |
| są trywialne. }}
| |
|
| |
| {{ Zadanie||uzupelnic|
| |
|
| |
| {{kotwica|mod1:zad6|}} Niech <math>\mathbf{C}</math> będzie kategorią,
| |
| zaś <math>A\in \CC_0</math> jej ustalonym obiektem. Zaproponuj
| |
| konstrukcję nowej kategorii, której obiektami są wszystkie morfizmy z
| |
| <math>\mathbf{C}</math> o kodziedzinie <math>A</math>.
| |
|
| |
| \proof[Wskazówka:] Wykorzystaj Zadanie [[#mod1:zad5|Uzupelnic
| |
| mod1:zad5|]].
| |
|
| |
| \proof[Rozwiązanie:] Tak jak w Zadaniu [[#mod1:zad5|Uzupelnic mod1:zad5|]]
| |
| morfizmami nowej kategorii, oznaczanej często <math>\mathbf{C} /
| |
| A</math> i nazywanej <math>A</math>-warstwą <math>\mathbf{C}</math>
| |
| są komutujące diagramy: ponieważ wszystkie obiekty <math>\mathbf{C} /
| |
| A</math> jako morfizmy <math>\mathbf{C}</math> mają wspólną kodziedzinę,
| |
| więc możemy przyjąć, że morfizmami są komutujące trójkąty:
| |
|
| |
| \begin_quote\tt{Tu wstawić brakujący rysunek o numerze 1.24}\end_quote
| |
|
| |
| albo formalnie: jeśli <math>f\colon B\to A</math> oraz <math>g\colon
| |
| C\to A</math> są obiektami <math>\mathbf{C} / A</math>, to morfizmem
| |
| o dziedzinie <math>f</math> i kodziedzinie <math>g</math> jest morfizm
| |
| <math>h\colon B\to C</math> z <math>\mathbf{C}</math> taki, że powyższy
| |
| diagram komutuje. Sprawdzenie, że <math>\mathbf{C} / A</math> jest
| |
| kategorią jest już trywialne. }}
| |
|
| |
| {{ Zadanie||uzupelnic|
| |
|
| |
| {{kotwica|mod1:zad7|}} Udowodnij, że złożenie izomorfizmów jest
| |
| izomorfizmem, że morfizm odwrotny do izomorfizmu jest tylko jeden,
| |
| a także, że identyczności w dowolnej kategorii są izomorfizmami.
| |
|
| |
| \proof[Rozwiązanie:] Pokażmy najpierw, że złożenie izomorfizmów jest
| |
| izomorfizmem. Załóżmy, że <math>f\colon A\to B</math> oraz <math>g\colon
| |
| B\to C</math> są izmorfizmami. Wówczas ich złożenie <math>g\circ
| |
| f\colon A\to C</math> posiada morfizm odwrotny <math>f^{-1}\circ
| |
| g^{-1}</math>. Rzeczywiście, <math>(g\circ f)\circ (f^{-1}\circ g^{-1})
| |
| = g\circ )f\circ f^{-1})\circ g^{-1} = g\circ 1_B \circ g^{-1} = g\circ
| |
| g^{-1} = 1_C</math> i podobnie pokazujemy drugie z równań dla izomorfizmu.
| |
|
| |
| Rozwiążemy to samo zadanie graficznie: zauważmy, że fakt, że
| |
| <math>f</math> jest izomorfizmem z odwrotnością <math>f^{-1}</math>
| |
| jest wyrażony przez fakt, że poniższy diagram komutuje:
| |
|
| |
| \begin_quote\tt{Tu wstawić brakujący rysunek o numerze 1.25}\end_quote
| |
|
| |
| (Przypomnijmy sobie umowę z Zadania [[#mod1:zad2|Uzupelnic mod1:zad2|]],
| |
| że nie rysujemy identyczności.)
| |
|
| |
| Podobnie, diagram:
| |
|
| |
| \begin_quote\tt{Tu wstawić brakujący rysunek o numerze 1.26}\end_quote
| |
|
| |
| komutuje, a co za tym idzie, złożenie tych dwóch diagramów komutuje:
| |
|
| |
| \begin_quote\tt{Tu wstawić brakujący rysunek o numerze 1.27}\end_quote
| |
|
| |
| To zaś kończy dowód faktu, że <math>f^{-1}\circ g^{-1}</math> jest
| |
| odwrotnością <math>g\circ f</math>.
| |
|
| |
| Po drugie, pokażmy, że morfizm odwrotny do izmorfizmu jest tylko jeden:
| |
| załóżmy przeciwnie, że dla pewnego izomorfizmu <math>f\colon A\to B</math>
| |
| istnieją dwie odwrotności <math>g,h\colon B\to A</math>. Wówczas <math>g
| |
| = g\circ 1_B = g \circ (f\circ h) = (g\circ f)\circ h = 1_A\circ h =
| |
| h</math>, co należało pokazać.
| |
|
| |
| Po trzecie, niech <math>A</math> będzie dowolnym obiektem dowolnej
| |
| kategorii. Identyczność <math>1_A</math> spełnia oczywiście (z definicji
| |
| kategorii) równanie <math>1_A = 1_A\circ 1_A</math>, co świadczy o tym,
| |
| że jest izomorfizmem. }}
| |
|
| |
| {{ Zadanie||uzupelnic|
| |
|
| |
| {{kotwica|mod1:zad8|}} Znajdź kategorię, która ma tę własność, że jeśli
| |
| dwa obiekty są izomorficzne, to muszą być sobie równe.
| |
|
| |
| \proof[Wskazówka:] Można wziąć pod uwagę te szczególne kategorie, w
| |
| których istnieje co najwyżej jedna strzałka pomiędzy dowolnymi dwoma
| |
| obiektami.
| |
|
| |
| \proof[Rozwiązanie:] Niech <math>(P,\sqsubseteq)</math> będzie
| |
| częściowym porządkiem. Traktowany jako kategoria, posiada tę własność,
| |
| że pomiędzy dwoma jego obiektami (elementami) istnieje co najwyżej jeden
| |
| morfizm (w przypadku, gdy elementy te są w częściowym porządku). Niech
| |
| <math>p,q</math> będą obiektami izomorficznymi. W języku częściowych
| |
| porządków oznacza to, że <math>p\sqsubseteq q</math> i <math>q\sqsubseteq
| |
| p</math>. Antysymetria relacji porządkującej daje nam <math>p=q</math>,
| |
| co należało pokazać. }}
| |
|
| |
| {{ Zadanie||uzupelnic|
| |
|
| |
| {{kotwica|mod1:zad9|}} Pokaż, że w kategorii <math>\mathrm\bf{Mon}</math>
| |
| izomorfizmy to dokładnie bijektywne homomorfizmy monoidów.
| |
|
| |
| \proof[Wskazówka:] Jedna z implikacji jest bardzo łatwa: jeśli
| |
| <math>f</math> jest izomorfizmem w <math>\mathrm\bf{Mon}</math>, to w
| |
| szczególności jest morfizmem, czyli homomorfizmem monoidów. Równania dla
| |
| <math>f</math> jako izomorfizmu implikują, że <math>f</math> jest też
| |
| bijekcją, w dokładnie ten sam sposób, w jaki pokazaliśmy dla funkcji
| |
| między zbiorami (patrz dyskusja po Fakcie [[#mod1:fact:bij|Uzupelnic
| |
| mod1:fact:bij|]]). Wystarczy więc udowodnić implikację odwrotną.
| |
|
| |
| \proof[Rozwiązanie:] Załóżmy, że <math>f\colon M\to N</math>
| |
| jest bijektywnym homomorfizmem z odwrotnością <math>g\colon N\to
| |
| M</math>. Wystarczy pokazać, że <math>g</math> jest homomorfizmem, tzn.,
| |
| że <math>g(e_N)=e_M</math> oraz <math>g(n_1\circ_N n_2) = g(n_1)\circ_M
| |
| g(n_2)</math> dla dowolnych <math>n_1, n_2\in N</math>. Wykorzystując
| |
| fakt, że <math>f</math> -- jako homomorfizm -- zachowuje jedynkę,
| |
| mamy: <math>e_M = g(f(e_M)) = g(e_N)</math>, czyli pierwszą z
| |
| szukanych równości. Znów opierając się na własnościach <math>f</math>
| |
| mamy: <math>g(n_1)\circ_M g(n_2) = g(f(g(n_1)\circ_M g(n_2))) =
| |
| g(f(g(n_1))\circ_N f(g(n_2))) = g(n_1\circ_N n_2)</math>, co należało
| |
| pokazać. }}
| |
|
| |
| {{ Zadanie||uzupelnic|
| |
|
| |
| {{kotwica|mod1:zad10|}} Przekonaj się, że kategorie i funktory
| |
| tworzą kategorię, którą oznaczamy <math>\mathrm\bf{Cat}</math>.
| |
| \proof[Wskazówka:] Przeczytaj najpierw Definicję
| |
| [[#mod5:def:funktor|Uzupelnic mod5:def:funktor|]], w której mówimy czym
| |
| są funktory. \proof[Rozwiązanie:] Najpierw definiujemy identyczności:
| |
| dla dowolnej kategorii <math>\mathbf{C}</math> proponujemy przekształcenie
| |
| <math>1_\mathbf{C}{}</math> jako <math>1_\mathbf{C}{}(A) := A</math>
| |
| <math>1_\mathbf{C}{}(f\colon A\to B) := f</math> dla dowolnych <math>A\in
| |
| \CC_0, f\in \CC_1</math>. Wtedy oczywiście <math>1_\mathbf{C}{}</math>
| |
| jest funktorem. Złożenie funktorów definiujemy w sposób naturalny,
| |
| tak jak złożenie funkcji w <math>\mathrm\bf{Set}</math>. Niech
| |
| <math>F\colon \mathbf{C}\to \mathbf{D}</math>, <math>G\colon \mathbf{D}\to
| |
| \mathbf{A}</math>, <math>H\colon \mathbf{A}\to\mathbf{B}</math> będą
| |
| funktorami. <math>(1_\mathbf{D}{}\circ F)(A) = 1_\mathbf{D}{}(F(A))=F(A)=
| |
| F(1_\mathbf{C}{})(A)=(F\circ 1_\mathbf{C}{})(A)</math> dla <math>A\in
| |
| \CC_0</math> i taki sam dowód działa dla morfizmów. Wnioskujemy więc,
| |
| że <math>1_\mathbf{D}{}\circ F = F= F\circ 1_\mathbf{C}{}.</math> Ponadto:
| |
| <math>H\circ (G\circ F)(-) = H((G\circ F)(-))=H(G(F(-)))=(H\circ G)(F(-))
| |
| = ((H\circ G)\circ F)(-),</math> gdzie <math>(-)</math> oznacza miejsce,
| |
| w które można wstawić obiekt lub morfizm z <math>\mathbf{C}</math> --
| |
| taka konwencja notacyjna będzie często używana w przyszłości. A zatem
| |
| wnioskujemy, że złożenie funktorów jest łączne. }}
| |
|
| |
| {{ Zadanie||uzupelnic|
| |
|
| |
| {{kotwica|mod1:zad11|}} Podaj dwa dalsze przykłady kategorii.
| |
| \proof[Wskazówka:] Najprościej zdefiniować nowe kategorie poprzez
| |
| modyfikację istniejących przykładów (np. kategorię tworzą zbiory i funkcje
| |
| częściowe). Nasz drugi przykład jest tego typu: jako język funkcyjny
| |
| bierzemy <math>\lambda</math>-rachunek i tworzymy dla niego kategorię,
| |
| tak jak opisaliśmy to w jednym z ostatnich przykładów podanych podczas
| |
| wykładu.
| |
|
| |
| \proof[Rozwiązanie:]
| |
|
| |
| * \bfAutomaty:: Niech <math>M=(M,*, e)</math> będzie
| |
| monoidem. Definiujemy '''<math>M</math>-automat''' jako parę
| |
| <math>(S,\delta)</math> składającą się ze zbioru stanów <math>S</math>
| |
| i funkcji przejścia <math>\delta\colon M\times S\to S</math>
| |
| tak, że: <math>\delta(x*y,s) := \delta(x,\delta(y,s)),</math>
| |
| <math>\delta(e,s)=s,</math> dla dowolnych <math>x,y\in M</math>,
| |
| <math>s\in S</math>. Morfizmem <math>M</math>-automatów
| |
| <math>(S,\delta)</math>, <math>(Z,\eta)</math> jest funkcja
| |
| <math>f\colon S\to Z</math> taka, że <math>f(\delta(x,s)) =
| |
| \eta(x,f(s))</math>. Sprawdzenie, że taka struktura jest kategorią jest
| |
| oczywiste, nieprawdaż? * \bfRachunek lambda:: rozważamy prosty rachunek
| |
| <math>\lambda</math> z typami. (<math>\lambda</math>-rachunek jest
| |
| formalizmem pozwalającym na wygodną manipulację funkcjami. Umożliwia opis
| |
| funkcji bez podawania jej nazwy, np: funkcja <math>x\mapsto x^2</math>
| |
| jest w rachunku lambda zapisywana jako <math>\lambda x.x^2</math>,
| |
| zaś funkcja, której wartością jest również funkcja: <math>y\mapsto
| |
| (x\mapsto x^2+2y)</math> zapisuje się jako <math>\lambda y.\lambda
| |
| x.x^2+2y</math>.) Formalnie, <math>\lambda</math>-rachunek składa się z:
| |
|
| |
| * typów: <math>A,B, A\times B,A\to B, ...</math> * termów, w skład
| |
| których wchodzą:
| |
|
| |
| * dla każdego typu <math>A</math> zmienne tego typu:
| |
| <math>x:A,y:A,z:A,...</math>, * stałe różnych typów:
| |
| <math>a:A,b:B,...</math>, * dla dowolnych <math>a:A, b:B</math>,
| |
| para: <math>\langle a,b\rangle:A\times B</math>, * dla dowolnego
| |
| <math>c:A\times, B</math>, projekcja <math>\pi_1(c):A</math>, * dla
| |
| dowolnego <math>c:A\times B</math>, projekcja <math>\pi_2(c):B</math>, *
| |
| dla dowolnych <math>c:A\times B, a:A</math>, aplikacja <math>ca:B</math>,
| |
| * dla dowolnych <math>x:A, b:B</math>, abstrakcja <math>\lambda x.b:A\to
| |
| B</math>.
| |
|
| |
| * równań:
| |
|
| |
| * <math>\pi_1(\langle a,b\rangle)=a</math>, * <math>\pi_2(\langle
| |
| a,b\rangle)=b</math>, * <math>\langle\pi_1(c),\pi_2(c)\rangle=c</math>,
| |
| * <math>(\lambda x.b)a = b[a/x]</math>, * <math>\lambda x.cx = c</math>,
| |
| o ile <math>x</math> nie występuje w <math>c</math>.
| |
|
| |
| Definiujemy też relację <math>a\approx b</math> na termach (nazywaną
| |
| zwyczajowo <math>\beta\eta</math>-równoważnością), jako relację
| |
| równoważności generowaną przez równania i zamianę nazwy zmiennych
| |
| związanych: o ile <math>y</math> nie występuje w <math>b</math>, to
| |
| <math>\lambda x.b = \lambda y.b[y/x].</math>
| |
|
| |
| Kategorię <math>\mathbf{C}(\lambda)</math> definiujemy teraz jak
| |
| następuje:
| |
|
| |
| * obiekty: typy <math>\lambda</math>-rachunku, * morfizm z <math>A</math>
| |
| do <math>B</math> to termy domknięte <math>c\colon A\to B</math>
| |
| (identyfikowane ze sobą, jeśli <math>c\approx c'</math>), * identyczności:
| |
| <math>1_A = \lambda x.x</math> dla każdego <math>x:A</math>, * złożenie:
| |
| <math>c\circ b = \lambda x.c(bx)</math>.
| |
|
| |
| Sprawdźmy, że <math>\mathbf{C}(\lambda)</math> jest kategorią:
| |
| <math>c\circ 1_B = \lambda x.c((\lambda y.y)x)=\lambda x.c(y[x/y])=\lambda
| |
| x.cx=c,</math> <math>1_C \circ c= \lambda x.(\lambda y.y)(cx) = \lambda
| |
| x.y[cx/y]=\lambda x.cx = c,</math>
| |
|
| |
| <math>\aligned c\circ (b\circ a) & = & \lambda x.c((b\circ a)x)\\ & =
| |
| & \lambda x.c((\lambda y.b(ay))x)\\ & = & \lambda x.c(b(ax))\\ & = &
| |
| \lambda x.\lambda y.c((by)(ax))\\ & = & \lambda x.(c\circ b)(ax)\\ & = &
| |
| (c\circ b)\circ a.
| |
|
| |
| \endaligned</math>
| |
|
| |
| Kategorii <math>\mathbf{C}(\lambda)</math> przyjrzymy się jeszcze
| |
| uważniej w wykładach [[#wyklad3|Uzupelnic wyklad3|]], [[#wyklad4|Uzupelnic
| |
| wyklad4|]].
| |
|
| |
| }}
| |
