Test Arka

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 $f:A\to B$ jest bijekcją jeśli jest różnowartościową surjekcją, tj. Parser nie mógł rozpoznać (błąd składni): {\displaystyle \forall x,y\in A\ f(x)=f(y)\Rightarrow x=y} oraz $\mathrm{\forall }z\in B\mathrm{\exists }x\in Af(x)=z.$

Zauważmy, że drugi warunek pozwala nam każdemu elementowi $z$ zbioru $B$ przyporządkować element $x$ zbioru $A$, zaś warunek pierwszy mówi, że to przekształcenie (nazwijmy je $g$) jest funkcją (śmiało napiszmy więc $g:B\to A$). W tym świetle z warunku drugiego wynika, że złożenie $f\circ g$ jest funkcją identycznościową na zbiorze $B$, a stąd wynika $f\circ g\circ f=f$, co w połączeniu z pierwszym warunkiem oznacza, że $g\circ f$ jest identycznością na zbiorze $A$. Idąc dalej tym tropem (patrz Zadanie Uzupelnic mod1:zad1|) jesteśmy w stanie bez trudu pokazać, że:

Fakt [Uzupelnij]

Funkcja $f:A\to B$ jest bijekcją wtedy i tylko wtedy, gdy istnieje funkcja

$g:B\to A$ taka, że $f\circ g=1_B$ oraz

$g\circ f=1_A$.

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 Parser nie mógł rozpoznać (błąd składni): {\displaystyle \mathrm\bf{nat}} . Teoria mnogości definiuje Parser nie mógł rozpoznać (błąd składni): {\displaystyle \mathrm\bf{nat}} jako najmniejszy zbiór zawierający liczbę zero $0$ i spełniający: Parser nie mógł rozpoznać (błąd składni): {\displaystyle n\in \mathrm\bf{nat} \Rightarrow \mathrm{succ}(n)\in \mathrm\bf{nat}} , gdzie Parser nie mógł rozpoznać (błąd składni): {\displaystyle \mathrm{succ}\colon \mathrm\bf{nat}\to \mathrm\bf{nat}} jest funkcją następnika (która jest injektywna i posiada tę właściwość, że $\mathrm{s}\mathrm{u}\mathrm{c}\mathrm{c}(n)\ne 0$ dla dowolnego Parser nie mógł rozpoznać (błąd składni): {\displaystyle n\in \mathrm\bf{nat}} ). Okazuje się, że zbiór liczb naturalnych można wyróżnić spośród innych zbiorów w ten sposób (Zadanie Uzupelnic mod1:zad2|):

Fakt [Uzupelnij]

Zbiór liczb

naturalnych Parser nie mógł rozpoznać (błąd składni): {\displaystyle \mathrm\bf{nat}} jest to zbiór zawierający liczbę zero oraz wyposażony w funkcję Parser nie mógł rozpoznać (błąd składni): {\displaystyle \mathrm{succ}\colon \mathrm\bf{nat}\to \mathrm\bf{nat}} taką, że: dla dowolnego zbioru

$X$ i elementu $e\in X$ oraz funkcji $g:X\to X$ istnieje dokładnie jedna funkcja Parser nie mógł rozpoznać (błąd składni): {\displaystyle f\colon \mathrm\bf{nat}\to X} spełniająca dwa warunki: $f(0)=e$ oraz $f\circ \mathrm{s}\mathrm{u}\mathrm{c}\mathrm{c}=g\circ f$.

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 $f$ działa na pewien jedyny obiekt, nazwijmy go dziedziną $f$ i oznaczmy Parser nie mógł rozpoznać (błąd składni): {\displaystyle \mathrm\it{dom}(f)} , i przekształca go w inny jedyny obiekt nazywany przeciwdziedziną $f$ i oznaczany jako Parser nie mógł rozpoznać (błąd składni): {\displaystyle \mathrm\it{cod}(f)} . Fakt, że morfizm $f$ ma dziedzinę $A$ i przeciwdziedzinę $B$ zapisujemy

{Tu wstawić brakujący rysunek o numerze 1.1}

lub po prostu $f:A\to B$. Nasza teoria nie może istnieć bez pojęcia złożenia przekształceń: zakładamy, że dwóm morfizmom $f,g$ takim, że $\mathrm{c}\mathrm{o}\mathrm{d}(g)=\mathrm{d}\mathrm{o}\mathrm{m}(f)$ (strzałki takie nazywamy składalnymi) przypisujemy morfizm $f\circ g$ zwany złożeniem, dla którego mamy $\mathrm{d}\mathrm{o}\mathrm{m}(f\circ g)=\mathrm{d}\mathrm{o}\mathrm{m}(g)$ i $\mathrm{c}\mathrm{o}\mathrm{d}(f\circ g)=\mathrm{c}\mathrm{o}\mathrm{d}(f)$. Przykłady wskazują na to, że kolejność złożenia składalnych przekształceń nie powinna grać roli, czyli dla:

{Tu wstawić brakujący rysunek o numerze 1.2}

morfizm:

{Tu wstawić brakujący rysunek o numerze 1.3}

może powstać albo z:

{Tu wstawić brakujący rysunek o numerze 1.4}

albo, równoważnie, z:

{Tu wstawić brakujący rysunek o numerze 1.5}

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:

{Tu wstawić brakujący rysunek o numerze 1.6}

To kończy nieformalny opis języka, w którym główną rolę grają przekształcenia. Zapiszmy to teraz formalnie.

Definicja kategorii

Definicja [Uzupelnij]

Kategoria

$\mathbf{𝐂}$ składa się z następujących danych:

• (D1): obiektów: $A,B,C,...$,

• (D2): morfizmów: $f,g,h,...$,

• (D3): dwóch operacji $\mathrm{d}\mathrm{o}\mathrm{m},\mathrm{c}\mathrm{o}\mathrm{d}$

przypisującej każdemu morfizmowi $f$ obiekty $\mathrm{d}\mathrm{o}\mathrm{m}(f)$i $\mathrm{c}\mathrm{o}\mathrm{d}(f)$,

• (D4): operacji $1$ przypisującej każdemu obiektowi

$A$ morfizm $1_A$ nazywany identycznością,

• (D5): operacji $\circ$ przypisującej każdej parze

morfizmów $f,g$ takich, że $\mathrm{c}\mathrm{o}\mathrm{d}(g)=\mathrm{d}\mathrm{o}\mathrm{m}(f)$ morfizm $f\circ g$ nazywany złożeniem,

spełniających następujące aksjomaty:

• (A1): $\mathrm{d}\mathrm{o}\mathrm{m}(1_A)=A=\mathrm{c}\mathrm{o}\mathrm{d}(1_A)$;

$\mathrm{d}\mathrm{o}\mathrm{m}(f\circ g)=\mathrm{d}\mathrm{o}\mathrm{m}(g)$; $\mathrm{c}\mathrm{o}\mathrm{d}(f\circ g)=\mathrm{c}\mathrm{o}\mathrm{d}(f)$,

• (A2): $f\circ 1_A=f=1_B\circ f$, gdzie

$A=\mathrm{d}\mathrm{o}\mathrm{m}(f)$ oraz $B=\mathrm{c}\mathrm{o}\mathrm{d}(f)$,

• (A3): jeśli $f,g$ są składalne oraz $g,h$

są składalne, to $(f\circ g)\circ h=f\circ (g\circ h)$.

Kolekcję obiektów kategorii $\mathbf{𝐂}$ będziemy w dalszym ciągu oznaczać jako ${\mathbf{𝐂}}_0$, zaś kolekcję jej morfizmów jako ${\mathbf{𝐂}}_1$.

{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 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 [Uzupelnij]

Grafem

skierowanym nazywamy kolekcję obiektów (wierzchołków) $O$, kolekcję strzałek (krawędzi) $A$ i dwie funkcje

{Tu wstawić brakujący rysunek o numerze 1.7}

W grafie, kolekcja składalnych par strzałek to zbiór $A{\times }_{O}A=\{(g,f)\mid g,f\in A\wedge \mathrm{d}\mathrm{o}\mathrm{m}(g)=\mathrm{c}\mathrm{o}\mathrm{d}(f)\}$ nazywany produktem nad $O$. O kategorii można myśleć jako o grafie skierowanym $\mathbf{𝐂}$, który posiada dwie dodatkowe funkcje $1:O\to A$, $C\mapsto 1_C$ oraz $\circ :A{\times }_{O}A\to A$, $(g,f)\mapsto g\circ f$ takie, że spełnione są warunki (A1)--(A3) Definicji

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 [Uzupelnij]

Kategoria

$\mathbf{𝐂}$ 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:

{Tu wstawić brakujący rysunek o numerze 1.8}

Operacje podlegają następującym aksjomatom:

• (b1): $xy$ jest zdefiniowane wtw, gdy $x◻=◻y$,

• (b2): $(◻x)◻=◻x$ oraz $◻(x◻)=x◻$,

• (b3): $(◻x)x=x$ oraz $x(x◻)=x$,

• (b4): $◻(xy)=◻(x(◻y))$ oraz $(xy)◻=((x◻)y)◻$

• (b5): $x(yz)=(xy)z$.

W tym wypadku równoważność definicji z dwiema pozostałymi (Definicje Uzupelnic mod1:def:kategria1| i 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 [Uzupelnij]

Dla

morfizmu $e$ następujące warunki są równoważne: istnieje $x$ taki, że $e=◻x$; istnieje $y$ taki, że $e=y◻$; $e=◻e$; $e=e◻$; dla każdego $x$, $ex\approx x$ (co oznacza, że jeśli złożenie $ex$ jest zdefiniowane, to jest równe $x$), dla każdego $x$, $xe\approx x$.

{Dowód} (1)$\to$(2) Dla $y=◻x$ mamy $y◻=(◻x)◻=◻x=e$. (2)$\to$(3) $◻e=◻(y◻)=y◻=e$. (3)$\to$(4) $e◻=(◻e)◻)=◻e=e$. (4)$\to$(5) Załóżmy, że $ex$ jest zdefiniowane dla każdego $x$; to oznacza, że $e◻=◻x$, czyli z (4), $e=◻x$ dla każdego $x$. A zatem $ex=(◻x)x=x$. (3)$\to$(1) Oczywiste. (4)$\to$(3) $◻e=◻(e◻)=e◻=e$. (5)$\to$(4) Połóżmy $x=e◻$. Mamy $◻x=◻(e◻)=e◻$, czyli $ex$ istnieje. Z (5) wynika, że $e(e◻)=e◻$. Ale (b3) implikuje, że $e(e◻)=e$, czyli $e=e◻$. Dowód

równoważności (6) z (3) jest podobny do równoważności (5) z (4).

Morfizm $e$ 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 Uzupelnic mod1:def:kategoria3| wystarczą do zrekonstruowania Definicji Uzupelnic mod1:def:kategria1|: Identyczność $1_x$ to zmienna $x$ taka, że $x=◻x=x◻$. Dziedziną $x$ jest $◻x$, przeciwdziedziną $x◻$. Złożenie $x\circ y$ to $yx$. Kolekcja obiektów Definicji Uzupelnic mod1:def:kategria1| pokrywa się z kolekcją morfizmów identycznościowych Definicji Uzupelnic mod1:def:kategoria3|. Zauważmy, że dla dowolnego $x$, zarówno $◻x$, jak i $x◻$ są obiektami (identycznościami), bo $◻(◻x)=◻x$, $(◻x)◻=◻x$, $(x◻)◻=(◻(x◻))◻=◻(x◻)=x◻$, $◻(x◻)=x◻$.

Sprawdźmy aksjomaty: $\mathrm{d}\mathrm{o}\mathrm{m}(1_x)=◻x=x=x◻=\mathrm{c}\mathrm{o}\mathrm{d}(1_x)$. Aby pokazać, że $f$ jest morfizmem, załóżmy, że $x=\mathrm{d}\mathrm{o}\mathrm{m}(f)$(czyli $1_x=◻f$) oraz $y=\mathrm{c}\mathrm{o}\mathrm{d}(f)$ (czyli $1_y=f◻$)). Wówczas $f\circ 1_x=1_{x}f=(◻f)f=f$, $1_y\circ f=f{1}_y=f(f◻)=f$.

Załóżmy teraz, że $\mathrm{d}\mathrm{o}\mathrm{m}(f)=\mathrm{c}\mathrm{o}\mathrm{d}(g)$. Wówczas $\mathrm{d}\mathrm{o}\mathrm{m}(f\circ g)=◻(gf)=◻(g◻f)=\mathrm{d}\mathrm{o}\mathrm{m}(1_{\mathrm{d}\mathrm{o}\mathrm{m}(f)}\circ g)=\mathrm{d}\mathrm{o}\mathrm{m}(1_{\mathrm{c}\mathrm{o}\mathrm{d}(g)}\circ g)=\mathrm{d}\mathrm{o}\mathrm{m}(g)$. Ostatnia równość wynika z poprzedniego paragrafu. Podobnie, $\mathrm{c}\mathrm{o}\mathrm{d}(f\circ g)=(gf)◻=((g◻)f)◻=\mathrm{c}\mathrm{o}\mathrm{d}(f\circ 1_{\mathrm{c}\mathrm{o}\mathrm{d}(g)})=\mathrm{c}\mathrm{o}\mathrm{d}(f\circ 1_{\mathrm{d}\mathrm{o}\mathrm{m}(f)})=\mathrm{c}\mathrm{o}\mathrm{d}(f)$.

W końcu, $f\circ (g\circ h)=(hg)f=h(gf)=(f\circ g)\circ h$ przy odpowiednich założeniach.

Przykłady kategorii

• $\mathbf{𝐒}\mathbf{𝐞}\mathbf{𝐭}$: Obiektami są zbiory, morfizmami funkcje.

Uwaga! W teorii mnogości funkcja jest zdefiniowana jako zbiór par uporządkowanych takich, że

$((x,y)\in f\wedge (x,y^{\prime })\in f)\Rightarrow y=y^{\prime }.$

Aby traktować funkcje jako morfizmy musimy precyzyjnie znać $\mathrm{d}\mathrm{o}\mathrm{m}(f)$ i $\mathrm{c}\mathrm{o}\mathrm{d}(f)$. Na przykład funkcje $\sin :\mathbb{ℝ}\to [-1,1]$ oraz $\sin :\mathbb{ℝ}\to \mathbb{ℝ},$, 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 $(X,f,Y)$ taka, że $f\subseteq X\times Y$ spełnia powyższe równanie (Uzupelnic eq:funkcja|) wraz z poniższym:

$x\in X\Rightarrow (\mathrm{\exists }y\in Y(x,y)\in f).$

Wtedy $\mathrm{d}\mathrm{o}\mathrm{m}$ jest projekcją na pierwszą współrzędną $(X,f,Y)\mapsto X$, a $\mathrm{c}\mathrm{o}\mathrm{d}$ projekcją na trzecią współrzędną.

• Kategoria zbiorów skończonych i funkcji ${\mathbf{𝐒}\mathbf{𝐞}\mathbf{𝐭}}_{fin}$, 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ą.

• $\mathbf{𝐕}\mathbf{𝐞}\mathbf{𝐜}\mathbf{𝐭}$: Przestrzenie wektorowe i odwzorowania

liniowe

• $\mathbf{𝐆}\mathbf{𝐫}\mathbf{𝐩}$: Grupy i homomorfizmy grup

• $\mathbf{𝐀}\mathbf{𝐛}$: Grupy abelowe i homomorfizmy grup

• $\mathbf{𝐌}\mathbf{𝐨}\mathbf{𝐧}$: Monoidy i homomorfizmy monoidów

• $\mathbf{𝐏}\mathbf{𝐨}\mathbf{𝐬}$: Częściowe porządki i funkcje monotoniczne

• $\mathbf{𝐓}\mathbf{𝐨}\mathbf{𝐩}$: Przestrzenie topologiczne i funkcje ciągłe

• $\mathbf{𝐆}\mathbf{𝐫}\mathbf{𝐚}\mathbf{𝐩}\mathbf{𝐡}$: Grafy i homomorfizmy grafów

• liczby naturalne Parser nie mógł rozpoznać (błąd składni): {\displaystyle \mathrm\bf{nat}} i wszystkie funkcje

obliczalne

• Mając dowolny częściowy porządek (poset) $(P,\le )$

definiujemy kategorię o tej samej nazwie $P$ jak następuje: jako obiekty bierzemy elementy $P$, zaś dla dwóch obiektów $x,y\in P$ przyjmujemy, że istnieje morfizm z $x$ do $y$ wtedy i tylko wtedy, gdy $x\le y$. Zauważmy, że wystarczy tu, by $P$ był preporządkiem, tzn. aby relacja $\le$ była zaledwie zwrotna i przechodnia.

• $\mathbf{𝐑}\mathbf{𝐞}\mathbf{𝐥}$: Obiektami tej kategorii są zbiory, zaś

morfizmami relacje binarne, tzn. $f:A\to B$ wtedy i tylko wtedy, gdy $f\subseteq A\times B$. Wówczas rolę identyczności spełniają relacje identycznościowe: $1_A=\{(a,a)\mid a\in A\}$, zaś złożeniem morfizmów jest po prostu złożenie relacji znane z kursu teorii mnogości: mając dane $R\subseteq A\times B$ oraz $S\subseteq B\times C$ przyjmujemy: Parser nie mógł rozpoznać (błąd składni): {\displaystyle (a,c)\in S\circ R \Leftrightarrow \exists b\in B\ ((a,b)\in R\wedge (b,c)\in S)}

• Kategorie skończone: (skończoność dotyczy ilości istniejących

morfizmów, choć nazwy tych kategorii odnoszą się do ilości obiektów):

• $\mathbf{𝟏}$: Ta kategoria ma jeden obiekt i jedną

strzałkę: identyczność.

{Tu wstawić brakujący rysunek o numerze 1.9}

• $\mathbf{𝟎}$: Ta kategoria nie ma obiektów i nie ma

strzałek.

• $\mathbf{𝟐}$: Kategoria ta ma dwa obiekty i jedną strzałkę

pomiędzy nimi (a także oczywiście dwie wymagane identyczności).

{Tu wstawić brakujący rysunek o numerze 1.10}

• $\mathbf{𝟑}$: 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!)

{Tu wstawić brakujący rysunek o numerze 1.11}

• 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).

• Kategorie 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.

{Tu wstawić brakujący rysunek o numerze 1.12}

• Niech $(M,*,e)$ będzie monoidem ($e$ jest

jego jedynką). Wówczas biorąc $M$ jako jedyny obiekt, zaś elementy $M$ jako morfizmy (z dziedziną i kodziedziną $M$), a działanie $*$ 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...)

{Tu wstawić brakujący rysunek o numerze 1.13}

• Dla danego rachunku logicznego możemy stworzyć kategorię w ten

sposób, że obiektami są formuły: $\varphi ,\psi ,...$ zaś morfizmem z $\varphi$ do $\psi$ jest każda dedukcja (dowód) $\psi$ z założenia $\varphi$. Złożeniem morfizmów jest wtedy połączenie dowodów, które jest oczywiście łączne. Identyczność $1_{\varphi }$ to dowód pusty, bowiem z aksjomatów logicznych zawsze wynika $\varphi ⊢\varphi$.

• Dla danego typowanego języka funkcyjnego $L$ tworzymy

kategorię w ten sposób, że obiektami są typy danych, zaś strzałkami są programy (procedury) języka $L$. Złożenie dwóch programów $X\stackrel{f}{\to }Y\stackrel{g}{\to }Z$ jest program dany poprzez zaaplikowanie wyjścia programu $f$ na wejściu programu $g$. 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 [Uzupelnij]

Niech

$\mathbf{𝐂}$ będzie dowolną kategorią. Morfizm $f:A\to B$ jest izomorfizmem jeśli istnieje morfizm $g:B\to A$ taki, że $f\circ g=1_B$ oraz $g\circ f=1_A$. Morfizm $g$ nazywa się morfizmem odwrotnym do $f$ . Jeśli dla obiektów $A,B$ kategorii $\mathbf{𝐂}$ istnieje izomorfizm $f:A\to B$, to obiekty $A$ i $B$

nazywamy izomorficznymi, co zapisujemy jako $A\cong B$.

Ponieważ dowolny morfizm $f$ posiada dokładnie jeden morfizm odwrotny (dowód?), będziemy go oznaczać jako $f^{-1}$. Można łatwo pokazać (dowód?), że morfizm odwrotny do izomorfizmu jest izomorfizmem.

Fakt Uzupelnic mod1:fact:bij| wyraża zatem myśl, że izomorfizmami w $\mathbf{𝐒}\mathbf{𝐞}\mathbf{𝐭}$ 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 Uzupelnic mod5:def:konkret|, bijekcje nie zawsze są izomorfizmami. Prosty kontrprzykład stanowi tutaj kategoria $\mathbf{𝐏}\mathbf{𝐨}\mathbf{𝐬}$ (Zadanie 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ę $\mathbf{𝐒}\mathbf{𝐞}\mathbf{𝐭}$, której obiektami są zbiory, to widzimy, że kolekcja wszystkich obiektów $\mathbf{𝐒}\mathbf{𝐞}\mathbf{𝐭}$ nie tworzy zbioru (jest zbyt duża!). Podobnie, kolekcja wszystkich morfizmów $\mathbf{𝐒}\mathbf{𝐞}\mathbf{𝐭}$ jest zbyt wielka, aby być zbiorem (zauważmy, że samych identyczności jest już tyle, ile obiektów). Kategoria $\mathbf{𝐒}\mathbf{𝐞}\mathbf{𝐭}$ nie jest taką jedyną. W związku z tym definiujemy:

Definicja [Uzupelnij]

Kategorię

$\mathbf{𝐂}$ nazywamy małą, jeśli kolekcja wszystkich obiektów ${\mathbf{𝐂}}_0$ i morfizmów ${\mathbf{𝐂}}_1$ kategorii $\mathbf{𝐂}$ są zbiorami. W przeciwnym

wypadku $\mathbf{𝐂}$ jest duża.

A zatem $\mathbf{𝐏}\mathbf{𝐨}\mathbf{𝐬}$, $\mathbf{𝐆}\mathbf{𝐫}\mathbf{𝐩}$, $\mathbf{𝐕}\mathbf{𝐞}\mathbf{𝐜}$ 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 [Uzupelnij]

Kategorię

$\mathbf{𝐂}$ nazywamy lokalnie małą jeśli dla każdej pary obiektów $A,B$ z $\mathbf{𝐂}$ kolekcja ${\mathrm{H}\mathrm{o}\mathrm{m}}_{\mathbf{𝐂}}(A,B)=\{f\in {\mathbf{𝐂}}_1\mid f:A\to B\}$ 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 $\mathbf{𝐏}\mathbf{𝐨}\mathbf{𝐬}$, $\mathbf{𝐆}\mathbf{𝐫}\mathbf{𝐩}$, $\mathbf{𝐕}\mathbf{𝐞}\mathbf{𝐜}$ 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

<span id=" Udowodnij, że dla dwóch funkcji $f:A\to B$ oraz $g:B\to A$ jeśli $f\circ g=1_B$ oraz $g\circ f=1_A$, to funkcja $f$ jest bijekcją.

[Rozwiązanie:] Pokażemy najpierw, że $f$ jest funkcją różnowartościową. Przypuśćmy, że $f(x)=f(y)$ dla pewnych elementów $x,y\in A$. Wówczas $x=1_A(x)=(g\circ f)(x)=g(f(x))=g(f(y))=(g\circ f)(y)=1_A(y)=y$. Ponadto, dla dowolnego $z\in B$ element $g(z)$ jest jedynym takim elementem, że $f(g(z))=z$, co w szczególności oznacza, że $f$ jest surjekcją. Wnioskujemy więc, że $f$ jest różnowartościową surjekcją, czyli bijekcją. " style="font-variant:small-caps; color: #1A6ABF;">Ćwiczenie

{{{3}}}

<span id=" Udowodnij Fakt Uzupelnic mod1:fact:naturalne|.

[Wskazówka:] Fakt, że liczby naturalne posiadają wspomnianą w Fakcie Uzupelnic mod1:fact:naturalne| jest dokładnie twierdzeniem o rekursji. Pozostaje nam zatem udowodnienie implikacji przeciwnej.

[Rozwiązanie:] Załóżmy zatem, że $N$ jest pewnym zbiorem, który posiada wyróżniony element $0\in N$ i funkcję $s:N\to N$ 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 $N$ jest zbiorem liczb naturalnych:

• $\mathrm{\exists }0\in N$

To wiemy z założenia.

• $\mathrm{\forall }n\in Ns(n)\in N$

To wiemy z założenia.

• $\mathrm{\forall }n\in Ns(n)\ne 0$

Przypuśćmy przeciwnie, że dla pewnego $n\in N$ mamy $s(n)=0$. Wtedy kładąc $X=\{e,a\}$ oraz $g(e)=g(a)=a$, z założenia istnieje funkcja $f:N\to X$ taka, że $f(0)=e$ oraz $f(s(n))=g(f(n))$. A zatem $f(s(n))=f(0)=e\ne a=g(f(n))$, sprzeczność.

• $s$ jest injekcją.

Przypuśćmy, że $s(n)=s(m)$ dla pewnych $n,m\in N$. Kładąc $X:=\{0,s(0),s(s(0)),...\}$ (jest to podzbiór $N$) oraz $e:=0$, wiemy, że istnieje funkcja $f:N\to X$ taka, że $f(0)=0$ oraz $f(s(n))=s(f(n))$. Taka funkcja jest tylko jedna, więc jej zawężenie do $X$ musi być równe funkcji $h:X\to X$, która spełnia warunki $h(0)=0$ oraz $h(s(n))=n$ dla $n\ne 0$. Dlatego założenie $s(n)=s(m)$ implikuje $n=h(s(n))=h(s(m))=m$, co należało pokazać.

• $\mathrm{\forall }A\subseteq N((0\in A\wedge (a\in A\Rightarrow s(a)\in A))\Rightarrow A=N)$

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ę $s^{\prime }:A\to A$, która -- będąc obcięciem $s$ do $A$ -- spełnia warunek $s\circ i=i\circ s^{\prime }$, gdzie $i:A\to N$ jest inkluzją $A$ w $N$. Zgodnie z założeniem zadania, dla funkcji $s^{\prime }$ istnieje dokładnie jedna funkcja $f:N\to A$ taka, że $f(0)=0$ oraz $s^{\prime }\circ f=f\circ s$. Łącząc tą równość z poprzednią, dostajemy $s\circ i\circ f=i\circ f\circ s$. Zwróćmy teraz uwagę na funkcję $i\circ f:N\to N$. Oczywiste spostrzeżenie, że $i\circ f(0)=0$ pozwala nam stwierdzić, że $i\circ f$ jest jedyną funkcją typu $N\to N$, która spełnia ostatnią z równości. Skoro tak, to musi być równa identyczności na $N$. Pokazaliśmy więc, że $i\circ f=1_N$, a stąd -- jak łatwo pokazać wynika, że $f:N\to A$ jest injekcją. A zatem $N\subseteq A$, co należało wykazać.

Pokazaliśmy zatem, że aksjomaty Peano są spełnione dla zbioru $N$, a zatem teoria mnogości uczy nas, że $N$ jest zbiorem liczb naturalnych Parser nie mógł rozpoznać (błąd składni): {\displaystyle \mathrm\bf{nat}} .

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: $N$ jest zbiorem, który posiada wyróżniony element $0$ oraz funkcję $s:N\to N$ takie, że dla dowolnego innego zbioru $X$ i elementu $e\in X$ oraz funkcji $g:X\to X$ istnieje dokładnie jedna funkcja $f:N\to X$ spełniająca warunki $f(0)=e$ oraz $f\circ s=g\circ f$.

Zauważmy więc, że element $0\in N$ może być zawsze traktowany jako funkcja $0:\mathrm{\top }\to N$, gdzie $\mathrm{\top }$ jest dowolnym zbiorem jednoelementowym (zwróćmy uwagę, że w tej interpretacji aplikacja funkcji staje się złożeniem, np. $f(0)$ staje się złożeniem $f\circ 0$). Podobnie dla $e\in X$. Po drugie, wszelkie równości pomiędzy funkcjami przedstawiamy jako komutowanie odpowiedniego diagramu, np. równość $f\circ s=g\circ f$ zachodzi wtedy i tylko wtedy, gdy poniższy diagram komutuje:

{Tu wstawić brakujący rysunek o numerze 1.14}

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 ...$f:N\to X$ jest jedyną funkcją taką, że... odzwierciedla się graficznie jako:

{Tu wstawić brakujący rysunek o numerze 1.15}

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:

{Tu wstawić brakujący rysunek o numerze 1.16}

komutuje wtedy i tylko wtedy, gdy $0\in N$, $e\in X$, $f(0)=e$, $f\circ s=g\circ f$, $(f\circ s)(0)=g(e)$ (ten wniosek wynika z czterech pozostałych!) i $f$ 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

{Tu wstawić brakujący rysunek o numerze 1.17}

komutuje, co możemy przedstawić również w skrócie jako:

{Tu wstawić brakujący rysunek o numerze 1.18}

jak również komutuje diagram:

{Tu wstawić brakujący rysunek o numerze 1.19}

to z warunku jednoznaczności istnienia funkcji dostajemy $i\circ f=1_N$. To jednak implikuje, że $f$ jest injekcją, czyli $N\subseteq A$, 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.

" style="font-variant:small-caps; color: #1A6ABF;">Ćwiczenie

{{{3}}}

<span id=" Znajdź przykład na to, że w kategorii Parser nie mógł rozpoznać (błąd składni): {\displaystyle \mathrm\bf{Pos}} bijekcje nie zawsze są izomorfizmami.

[Wskazówka:] Wystarczy rozważyć częściowe porządki dwuelementowe.

[Rozwiązanie:] Rozważmy dwa posety dwuelementowe $P=\{x,y\}$, $Q=\{z,w\}$ i funkcję $g:Q\to P$, $g(z)=x,g(w)=y$, jak na rysunku:

{Tu wstawić brakujący rysunek o numerze 1.20}

Funkcja $g$ jest oczywiście bijekcją, ale funkcja do niej odwrotna nie jest monotoniczna, a zatem nie jest morfizmem w Parser nie mógł rozpoznać (błąd składni): {\displaystyle \mathrm\bf{Pos}} . To oznacza, że $g$ nie może być izomorfizmem. " style="font-variant:small-caps; color: #1A6ABF;">Ćwiczenie

{{{3}}}

<span id=" Pokaż, że każda grupa może być traktowana jako kategoria, w której każdy morfizm jest izomorfizmem.

[Rozwiązanie:] Niech $(G,\circ ,e)$ będzie grupą. Podobnie jak w przypadku monoidów, deklarujemy $G$ jako jedyny obiekt pewnej kategorii, zaś elementy zbioru $G$ jako morfizmy tejże kategorii, działanie $\circ$ jako złożenie morfizmów, element $e$ traktując jako identyczność na obiekcie $G$. Zauważmy, że każdy element posiada element odwrotny, czyli dla każdego $g\in G$ istnieje $g^{-1}\in G$ tak, że $g\circ g^{-1}=e=g^{-1}\circ g$. Te równania interpretowane w naszej kategorii czynią tenże dowolnie wybrany element $g$ izomorfizmem. " style="font-variant:small-caps; color: #1A6ABF;">Ćwiczenie

{{{3}}}

<span id=" Dla dowolnej kategorii $\mathbf{𝐂}$ zaproponuj konstrukcję nowej kategorii, w której -- żądamy -- obiektami są morfizmy z $\mathbf{𝐂}$.

[Wskazówka:] Niech $\mathbf{𝐂}$ będzie dowolną kategorią; dla dwóch jej dowolnych morfizmów $f:A\to B$ oraz $g:C\to D$, musimy zaproponować taką operację, dla której $f$ jest dziedziną i $g$ jest kodziedziną. Gdyby przedstawić to graficznie, w postaci diagramu, łatwo przyjdzie nam na myśl definicja takiej operacji: będzie to para morfizmów $(a:A\to C,b:B\to D)$ z kategorii $\mathbf{𝐂}$ taka, że poniższy diagram komutuje:

{Tu wstawić brakujący rysunek o numerze 1.21}

Teraz już łatwo dopowiedzieć szczegóły konstrukcji.

[Rozwiązanie:] Zaproponujemy najpierw złożenie: dwa morfizmy $(a,b)$ oraz $(c,d)$ jak poniżej:

{Tu wstawić brakujący rysunek o numerze 1.22}

składają się tak:

{Tu wstawić brakujący rysunek o numerze 1.23}

albo formalnie: $(a,b)\circ (c,d)=(a\circ c,b\circ d)$. Oczywiście Parser nie mógł rozpoznać (błąd składni): {\displaystyle \mathrm\it{dom}((a\circ c, b\circ d)) = h} oraz Parser nie mógł rozpoznać (błąd składni): {\displaystyle \mathrm\it{cod}((a\circ c, b\circ d)) = g} . W końcu, identycznościami w nowej kategorii, która często oznacza się jako ${\mathbf{𝐂}}^{\to }$ są pary identyczności z kategorii $\mathbf{𝐂}$. Wszelkie pozostałe czynności, które musimy wykonać, by sprawdzić, że $\mathbf{𝐂}$ jest kategorią, są trywialne. " style="font-variant:small-caps; color: #1A6ABF;">Ćwiczenie

{{{3}}}

<span id=" Niech $\mathbf{𝐂}$ będzie kategorią, zaś Parser nie mógł rozpoznać (nieznana funkcja „\CC”): {\displaystyle A\in \CC_0} jej ustalonym obiektem. Zaproponuj konstrukcję nowej kategorii, której obiektami są wszystkie morfizmy z $\mathbf{𝐂}$ o kodziedzinie $A$.

[Wskazówka:] Wykorzystaj Zadanie Uzupelnic mod1:zad5|.

[Rozwiązanie:] Tak jak w Zadaniu Uzupelnic mod1:zad5| morfizmami nowej kategorii, oznaczanej często $\mathbf{𝐂}/A$ i nazywanej $A$-warstwą $\mathbf{𝐂}$ są komutujące diagramy: ponieważ wszystkie obiekty $\mathbf{𝐂}/A$ jako morfizmy $\mathbf{𝐂}$ mają wspólną kodziedzinę, więc możemy przyjąć, że morfizmami są komutujące trójkąty:

{Tu wstawić brakujący rysunek o numerze 1.24}

albo formalnie: jeśli $f:B\to A$ oraz $g:C\to A$ są obiektami $\mathbf{𝐂}/A$, to morfizmem o dziedzinie $f$ i kodziedzinie $g$ jest morfizm $h:B\to C$ z $\mathbf{𝐂}$ taki, że powyższy diagram komutuje. Sprawdzenie, że $\mathbf{𝐂}/A$ jest kategorią jest już trywialne. " style="font-variant:small-caps; color: #1A6ABF;">Ćwiczenie

{{{3}}}

<span id=" 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.

[Rozwiązanie:] Pokażmy najpierw, że złożenie izomorfizmów jest izomorfizmem. Załóżmy, że $f:A\to B$ oraz $g:B\to C$ są izmorfizmami. Wówczas ich złożenie $g\circ f:A\to C$ posiada morfizm odwrotny $f^{-1}\circ g^{-1}$. Rzeczywiście, $(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$ i podobnie pokazujemy drugie z równań dla izomorfizmu.

Rozwiążemy to samo zadanie graficznie: zauważmy, że fakt, że $f$ jest izomorfizmem z odwrotnością $f^{-1}$ jest wyrażony przez fakt, że poniższy diagram komutuje:

{Tu wstawić brakujący rysunek o numerze 1.25}

(Przypomnijmy sobie umowę z Zadania Uzupelnic mod1:zad2|, że nie rysujemy identyczności.)

Podobnie, diagram:

{Tu wstawić brakujący rysunek o numerze 1.26}

komutuje, a co za tym idzie, złożenie tych dwóch diagramów komutuje:

{Tu wstawić brakujący rysunek o numerze 1.27}

To zaś kończy dowód faktu, że $f^{-1}\circ g^{-1}$ jest odwrotnością $g\circ f$.

Po drugie, pokażmy, że morfizm odwrotny do izmorfizmu jest tylko jeden: załóżmy przeciwnie, że dla pewnego izomorfizmu $f:A\to B$ istnieją dwie odwrotności $g,h:B\to A$. Wówczas $g=g\circ 1_B=g\circ (f\circ h)=(g\circ f)\circ h=1_A\circ h=h$, co należało pokazać.

Po trzecie, niech $A$ będzie dowolnym obiektem dowolnej kategorii. Identyczność $1_A$ spełnia oczywiście (z definicji kategorii) równanie $1_A=1_A\circ 1_A$, co świadczy o tym, że jest izomorfizmem. " style="font-variant:small-caps; color: #1A6ABF;">Ćwiczenie

{{{3}}}

<span id=" Znajdź kategorię, która ma tę własność, że jeśli dwa obiekty są izomorficzne, to muszą być sobie równe.

[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.

[Rozwiązanie:] Niech $(P,⊑)$ 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 $p,q$ będą obiektami izomorficznymi. W języku częściowych porządków oznacza to, że $p⊑q$ i $q⊑p$. Antysymetria relacji porządkującej daje nam $p=q$, co należało pokazać. " style="font-variant:small-caps; color: #1A6ABF;">Ćwiczenie

{{{3}}}

<span id=" Pokaż, że w kategorii Parser nie mógł rozpoznać (błąd składni): {\displaystyle \mathrm\bf{Mon}} izomorfizmy to dokładnie bijektywne homomorfizmy monoidów.

[Wskazówka:] Jedna z implikacji jest bardzo łatwa: jeśli $f$ jest izomorfizmem w Parser nie mógł rozpoznać (błąd składni): {\displaystyle \mathrm\bf{Mon}} , to w szczególności jest morfizmem, czyli homomorfizmem monoidów. Równania dla $f$ jako izomorfizmu implikują, że $f$ jest też bijekcją, w dokładnie ten sam sposób, w jaki pokazaliśmy dla funkcji między zbiorami (patrz dyskusja po Fakcie Uzupelnic mod1:fact:bij|). Wystarczy więc udowodnić implikację odwrotną.

[Rozwiązanie:] Załóżmy, że $f:M\to N$ jest bijektywnym homomorfizmem z odwrotnością $g:N\to M$. Wystarczy pokazać, że $g$ jest homomorfizmem, tzn., że $g(e_N)=e_M$ oraz $g(n_1{\circ }_N{n}_2)=g(n_1){\circ }_{M}g(n_2)$ dla dowolnych $n_1,n_2\in N$. Wykorzystując fakt, że $f$ -- jako homomorfizm -- zachowuje jedynkę, mamy: $e_M=g(f(e_M))=g(e_N)$, czyli pierwszą z szukanych równości. Znów opierając się na własnościach $f$ mamy: $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)$, co należało pokazać. " style="font-variant:small-caps; color: #1A6ABF;">Ćwiczenie

{{{3}}}

<span id=" Przekonaj się, że kategorie i funktory tworzą kategorię, którą oznaczamy Parser nie mógł rozpoznać (błąd składni): {\displaystyle \mathrm\bf{Cat}} . [Wskazówka:] Przeczytaj najpierw Definicję Uzupelnic mod5:def:funktor|, w której mówimy czym są funktory. [Rozwiązanie:] Najpierw definiujemy identyczności: dla dowolnej kategorii $\mathbf{𝐂}$ proponujemy przekształcenie $1_{\mathbf{𝐂}}$ jako $1_{\mathbf{𝐂}}(A):=A$ $1_{\mathbf{𝐂}}(f:A\to B):=f$ dla dowolnych Parser nie mógł rozpoznać (nieznana funkcja „\CC”): {\displaystyle A\in \CC_0, f\in \CC_1} . Wtedy oczywiście $1_{\mathbf{𝐂}}$ jest funktorem. Złożenie funktorów definiujemy w sposób naturalny, tak jak złożenie funkcji w Parser nie mógł rozpoznać (błąd składni): {\displaystyle \mathrm\bf{Set}} . Niech $F:\mathbf{𝐂}\to \mathbf{𝐃}$, $G:\mathbf{𝐃}\to \mathbf{𝐀}$, $H:\mathbf{𝐀}\to \mathbf{𝐁}$ będą funktorami. $(1_{\mathbf{𝐃}}\circ F)(A)=1_{\mathbf{𝐃}}(F(A))=F(A)=F(1_{\mathbf{𝐂}})(A)=(F\circ 1_{\mathbf{𝐂}})(A)$ dla Parser nie mógł rozpoznać (nieznana funkcja „\CC”): {\displaystyle A\in \CC_0} i taki sam dowód działa dla morfizmów. Wnioskujemy więc, że $1_{\mathbf{𝐃}}\circ F=F=F\circ 1_{\mathbf{𝐂}}.$ Ponadto: $H\circ (G\circ F)(-)=H((G\circ F)(-))=H(G(F(-)))=(H\circ G)(F(-))=((H\circ G)\circ F)(-),$ gdzie $(-)$ oznacza miejsce, w które można wstawić obiekt lub morfizm z $\mathbf{𝐂}$ -- taka konwencja notacyjna będzie często używana w przyszłości. A zatem wnioskujemy, że złożenie funktorów jest łączne. " style="font-variant:small-caps; color: #1A6ABF;">Ćwiczenie

{{{3}}}

<span id=" Podaj dwa dalsze przykłady kategorii. [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 $\lambda$-rachunek i tworzymy dla niego kategorię, tak jak opisaliśmy to w jednym z ostatnich przykładów podanych podczas wykładu.

[Rozwiązanie:]

• Automaty:: Niech $M=(M,*,e)$ będzie monoidem. Definiujemy

$M$-automat jako parę $(S,\delta )$ składającą się ze zbioru stanów $S$ i funkcji przejścia $\delta :M\times S\to S$ tak, że: $\delta (x*y,s):=\delta (x,\delta (y,s)),$ $\delta (e,s)=s,$ dla dowolnych $x,y\in M$, $s\in S$. Morfizmem $M$-automatów $(S,\delta )$, $(Z,\eta )$ jest funkcja $f:S\to Z$ taka, że $f(\delta (x,s))=\eta (x,f(s))$. Sprawdzenie, że taka struktura jest kategorią jest oczywiste, nieprawdaż?

• Rachunek lambda:: rozważamy prosty rachunek $\lambda$ z

typami. ($\lambda$-rachunek jest formalizmem pozwalającym na wygodną manipulację funkcjami. Umożliwia opis funkcji bez podawania jej nazwy, np: funkcja $x\mapsto x^2$ jest w rachunku lambda zapisywana jako $\lambda x.x^2$, zaś funkcja, której wartością jest również funkcja: $y\mapsto (x\mapsto x^2+2y)$ zapisuje się jako $\lambda y.\lambda x.x^2+2y$.) Formalnie, $\lambda$-rachunek składa się z:

• typów: $A,B,A\times B,A\to B,...$

• termów, w skład których wchodzą:

• dla każdego typu $A$ zmienne tego typu:

$x:A,y:A,z:A,...$,

• stałe różnych typów: $a:A,b:B,...$,

• dla dowolnych $a:A,b:B$, para: $⟨a,b⟩:A\times B$,

• dla dowolnego $c:A\times ,B$, projekcja

${\pi }_1(c):A$,

• dla dowolnego $c:A\times B$, projekcja

${\pi }_2(c):B$,

• dla dowolnych $c:A\times B,a:A$, aplikacja

$ca:B$,

• dla dowolnych $x:A,b:B$, abstrakcja $\lambda x.b:A\to B$.

• równań:

• ${\pi }_1(⟨a,b⟩)=a$,

• ${\pi }_2(⟨a,b⟩)=b$,

• $⟨{\pi }_1(c),{\pi }_2(c)⟩=c$,

• $(\lambda x.b)a=b[a/x]$,

• $\lambda x.cx=c$, o ile $x$ nie występuje

w $c$.

Definiujemy też relację $a\approx b$ na termach (nazywaną zwyczajowo $\beta \eta$-równoważnością), jako relację równoważności generowaną przez równania i zamianę nazwy zmiennych związanych: o ile $y$ nie występuje w $b$, to $\lambda x.b=\lambda y.b[y/x].$

Kategorię $\mathbf{𝐂}(\lambda )$ definiujemy teraz jak następuje:

• obiekty: typy $\lambda$-rachunku,

• morfizm z $A$ do $B$ to termy domknięte

$c:A\to B$ (identyfikowane ze sobą, jeśli $c\approx c^{\prime }$),

• identyczności: $1_A=\lambda x.x$ dla każdego

$x:A$,

• złożenie: $c\circ b=\lambda x.c(bx)$.

Sprawdźmy, że $\mathbf{𝐂}(\lambda )$ jest kategorią: $c\circ 1_B=\lambda x.c((\lambda y.y)x)=\lambda x.c(y[x/y])=\lambda x.cx=c,$ $1_C\circ c=\lambda x.(\lambda y.y)(cx)=\lambda x.y[cx/y]=\lambda x.cx=c,$

Parser nie mógł rozpoznać (nieznana funkcja „\aligned”): {\displaystyle \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}

Kategorii $\mathbf{𝐂}(\lambda )$ przyjrzymy się jeszcze uważniej w wykładach Uzupelnic wyklad3|, Uzupelnic wyklad4|.

" style="font-variant:small-caps; color: #1A6ABF;">Ćwiczenie

{{{3}}}