Test Arka

\newtheorem{definition}[subsection]{Definicja} \newtheorem{theorem}[subsection]{Twierdzenie} \newtheorem{lemma}[subsection]{Lemat} \newtheorem{corollary}[subsection]{Wniosek} \newtheorem{remark}[subsection]{Uwaga} \newtheorem{question}[subsection]{Pytanie} \newtheorem{problem}[subsection]{Problem} \newtheorem{proposition}[subsection]{Stwierdzenie} \newtheorem{example}[subsection]{Przykład} \newtheorem{fact}[subsection]{Fakt} \newtheorem{zadanie}[subsection]{Zadanie} \newtheorem{obserwacja}[subsection]{Obserwacja} \newtheorem{counterexample}[subsection]{Kontrprzykład}

\begin_document

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 {\it 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 {\bf bijekcją} jeśli jest różnowartościową surjekcją, tj. $\mathrm{\forall }x,y\in Af(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 \ref{mod1:zad1}) jesteśmy w stanie bez trudu pokazać, że:

\begin_fact \label{mod1:fact:bij} 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$. \end_fact

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 $\mathbf{𝐧}\mathbf{𝐚}\mathbf{𝐭}$. Teoria mnogości definiuje $\mathbf{𝐧}\mathbf{𝐚}\mathbf{𝐭}$ jako najmniejszy zbiór zawierający liczbę zero $0$ i spełniający: $n\in \mathbf{𝐧}\mathbf{𝐚}\mathbf{𝐭}\Rightarrow \mathrm{s}\mathrm{u}\mathrm{c}\mathrm{c}(n)\in \mathbf{𝐧}\mathbf{𝐚}\mathbf{𝐭}$, gdzie $\mathrm{s}\mathrm{u}\mathrm{c}\mathrm{c}:\mathbf{𝐧}\mathbf{𝐚}\mathbf{𝐭}\to \mathbf{𝐧}\mathbf{𝐚}\mathbf{𝐭}$ 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 $n\in \mathbf{𝐧}\mathbf{𝐚}\mathbf{𝐭}$). Okazuje się, że zbiór liczb naturalnych można wyróżnić spośród innych zbiorów w ten sposób (Zadanie \ref{mod1:zad2}):

\begin_fact\label{mod1:fact:naturalne} Zbiór liczb naturalnych $\mathbf{𝐧}\mathbf{𝐚}\mathbf{𝐭}$ jest to zbiór zawierający liczbę zero oraz wyposażony w funkcję $\mathrm{s}\mathrm{u}\mathrm{c}\mathrm{c}:\mathbf{𝐧}\mathbf{𝐚}\mathbf{𝐭}\to \mathbf{𝐧}\mathbf{𝐚}\mathbf{𝐭}$ taką, że: dla dowolnego zbioru $X$ i elementu $e\in X$ oraz funkcji $g:X\to X$ istnieje dokładnie jedna funkcja $f:\mathbf{𝐧}\mathbf{𝐚}\mathbf{𝐭}\to X$ spełniająca dwa warunki: $f(0)=e$ oraz $f\circ \mathrm{s}\mathrm{u}\mathrm{c}\mathrm{c}=g\circ f$. \end_fact

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: {\it 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ż {\bf morfizmem} (bo w przeróżnych teoriach matematycznych natykamy się na homomorfizmy, homeomorfizmy, endomorfizmy, itd.) lub po prostu {\bf strzałką} (bo tak zwykle graficznie przedstawia się przekształcenia). Przekształcenie działa pomiędzy {\bf 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 {\bf dziedziną} $f$ i oznaczmy ${d}{o}{m}(f)$, i przekształca go w inny jedyny obiekt nazywany {\bf przeciwdziedziną} $f$ i oznaczany jako ${c}{o}{d}(f)$. Fakt, że morfizm $f$ ma dziedzinę $A$ i przeciwdziedzinę $B$ zapisujemy

\begin_quote{\tt Tu wstawić brakujący rysunek o numerze 1.1}\end_quote

lub po prostu $f:A\to B$. Nasza teoria nie może istnieć bez pojęcia {\bf 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 {\bf 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:

\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 {\bf 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

\label{mod1:def:kategria1} Kategoria $\mathbf{𝐂}$ składa się z następujących danych: \begin_enumerate \item[(D1)] {\bf obiektów}: $A,B,C,...$, \item[(D2)] {\bf morfizmów}: $f,g,h,...$, \item[(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)$, \item[(D4)] operacji $1$ przypisującej każdemu obiektowi $A$ morfizm $1_A$ nazywany identycznością, \item[(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, \end_enumerate spełniających następujące aksjomaty: \begin_enumerate \item[(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)$, \item[(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)$, \item[(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)$. \end_enumerate

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

{\tiny Tylko dla dociekliwych: Wiemy więc z czego {\it składa się} kategoria. Nie znamy jednak odpowiedzi na -- być może -- równie ważne pytanie: czym {\it jest} kategoria? W naszym wykładzie przyjmiemy po prostu, że kategorią będzie każda interpretacja aksjomatów przedstawionych w Definicji \ref{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

\label{mod1:def:kategoria2} Grafem skierowanym nazywamy kolekcję obiektów (wierzchołków) $O$, kolekcję strzałek (krawędzi) $A$ 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 $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 {\bf 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 \ref{mod1:def:kategria1}.

Poniżej pokażemy trzecią, równoważną, algebraiczną definicję kategorii (na podstawie książki: Peter J. Freyd, Andre Scedrov, {\it Categories, Allegories}, North Holland, 1989).

Definicja

\label{mod1:def:kategoria3} 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 {\bf morfizmami} ({\bf 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: \begin_enumerate \item[(b1)] $xy$ jest zdefiniowane wtw, gdy $x◻=◻y$, \item[(b2)] $(◻x)◻=◻x$ oraz $◻(x◻)=x◻$, \item[(b3)] $(◻x)x=x$ oraz $x(x◻)=x$, \item[(b4)] $◻(xy)=◻(x(◻y))$ oraz $(xy)◻=((x◻)y)◻$ \item[(b5)] $x(yz)=(xy)z$. \end_enumerate

W tym wypadku równoważność definicji z dwiema pozostałymi (Definicje \ref{mod1:def:kategria1} i \ref{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.

\begin_lemma\label{mod1:lemma:freyd1} 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$.

\proof{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). \end_lemma

Morfizm $e$ spełniający dowolny z powyższych warunków nazywamy {\bf 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 \ref{mod1:def:kategoria3} wystarczą do zrekonstruowania Definicji \ref{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 \ref{mod1:def:kategria1} pokrywa się z kolekcją morfizmów identycznościowych Definicji \ref{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

\begin_itemize \item $\mathbf{𝐒}\mathbf{𝐞}\mathbf{𝐭}$: Obiektami są zbiory, morfizmami funkcje. Uwaga! W teorii mnogości funkcja jest zdefiniowana jako zbiór par uporządkowanych takich, że \begin_equation \label{eq:funkcja} ((x,y)\in f\ \wedge \ (x,y')\in f)\ \Rightarrow \ y=y'. \end_equation

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 (\ref{eq:funkcja}) wraz z poniższym: \begin_equation x\in X \Rightarrow (\exists y\in Y\ (x,y)\in f). \end_equation 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ą. \item 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. \item Kategorie, w których obiektami są zbiory z pewną dodatkową stukturą algebraiczną, zaś morfizmami te funkcje, które tę strukturę zachowują. \begin_itemize \item $\mathbf{𝐕}\mathbf{𝐞}\mathbf{𝐜}\mathbf{𝐭}$: Przestrzenie wektorowe i odwzorowania liniowe \item $\mathbf{𝐆}\mathbf{𝐫}\mathbf{𝐩}$: Grupy i homomorfizmy grup \item $\mathbf{𝐀}\mathbf{𝐛}$: Grupy abelowe i homomorfizmy grup \item $\mathbf{𝐌}\mathbf{𝐨}\mathbf{𝐧}$: Monoidy i homomorfizmy monoidów \item $\mathbf{𝐏}\mathbf{𝐨}\mathbf{𝐬}$: Częściowe porządki i funkcje monotoniczne \item $\mathbf{𝐓}\mathbf{𝐨}\mathbf{𝐩}$: Przestrzenie topologiczne i funkcje ciągłe \item $\mathbf{𝐆}\mathbf{𝐫}\mathbf{𝐚}\mathbf{𝐩}\mathbf{𝐡}$: Grafy i homomorfizmy grafów \item liczby naturalne $\mathbf{𝐧}\mathbf{𝐚}\mathbf{𝐭}$ i wszystkie funkcje obliczalne \end_itemize \item 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. \item $\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: $(a,c)\in S\circ R\iff \mathrm{\exists }b\in B((a,b)\in R\wedge (b,c)\in S)$ \item {\bf Kategorie skończone} (skończoność dotyczy ilości istniejących {\it morfizmów}, choć nazwy tych kategorii odnoszą się do ilości {\it obiektów}): \begin_itemize \item $\mathbf{𝟏}$: Ta kategoria ma jeden obiekt i jedną strzałkę: identyczność.

\begin_quote{\tt Tu wstawić brakujący rysunek o numerze 1.9}\end_quote

\item $\mathbf{𝟎}$: Ta kategoria nie ma obiektów i nie ma strzałek. \item $\mathbf{𝟐}$: 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

\item $\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!)

\begin_quote{\tt Tu wstawić brakujący rysunek o numerze 1.11}\end_quote

\item 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). \end_itemize \item {\bf 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.

\begin_quote{\tt Tu wstawić brakujący rysunek o numerze 1.12}\end_quote

\item 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...)

\begin_quote{\tt Tu wstawić brakujący rysunek o numerze 1.13}\end_quote

\item 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$. \item 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 {\it nic nie robi}. \end_itemize

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

\label{mod1:def:iso} Niech $\mathbf{𝐂}$ będzie dowolną kategorią. Morfizm $f:A\to B$ jest {\bf 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ę {\bf 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 \ref{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 \ref{mod5:def:konkret}, bijekcje {\it nie zawsze} są izomorfizmami. Prosty kontrprzykład stanowi tutaj kategoria $\mathbf{𝐏}\mathbf{𝐨}\mathbf{𝐬}$ (Zadanie \ref{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

\label{mod1:def:size} Kategorię $\mathbf{𝐂}$ nazywamy {\bf małą}, jeśli kolekcja wszystkich obiektów ${\mathbf{𝐂}}_0$ i morfizmów ${\mathbf{𝐂}}_1$ kategorii $\mathbf{𝐂}$ są zbiorami. W przeciwnym wypadku $\mathbf{𝐂}$ jest {\bf 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

\label{mod1:def:localsize} Kategorię $\mathbf{𝐂}$ nazywamy {\bf 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 {\bf 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 {\it 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: {\it 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

\begin_zadanie \label{mod1:zad1} 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ą.

\proof[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ą. \end_zadanie

\begin_zadanie \label{mod1:zad2} Udowodnij Fakt \ref{mod1:fact:naturalne}.

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

\proof[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: \begin_itemize \item $\mathrm{\exists }0\in N$

To wiemy z założenia.

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

To wiemy z założenia.

\item $\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ść.

\item $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ć.

\item $\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 {\it 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 $\mathbf{𝐧}\mathbf{𝐚}\mathbf{𝐭}$.

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: {\it $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:

\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 {\it ...$f:N\to X$ 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 {\bf 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 $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

\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 $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. \end_itemize

\end_zadanie

\begin_zadanie \label{mod1:zad3} Znajdź przykład na to, że w kategorii $\mathbf{𝐏}\mathbf{𝐨}\mathbf{𝐬}$ bijekcje nie zawsze są izomorfizmami.

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

\proof[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:

\begin_quote{\tt Tu wstawić brakujący rysunek o numerze 1.20}\end_quote

Funkcja $g$ jest oczywiście bijekcją, ale funkcja do niej odwrotna nie jest monotoniczna, a zatem nie jest morfizmem w $\mathbf{𝐏}\mathbf{𝐨}\mathbf{𝐬}$. To oznacza, że $g$ nie może być izomorfizmem. \end_zadanie

\begin_zadanie \label{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 $(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. \end_zadanie

\begin_zadanie \label{mod1:zad5} Dla dowolnej kategorii $\mathbf{𝐂}$ zaproponuj konstrukcję nowej kategorii, w której -- żądamy -- obiektami są morfizmy z $\mathbf{𝐂}$.

\proof[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 {\it para morfizmów} $(a:A\to C,b:B\to D)$ z kategorii $\mathbf{𝐂}$ 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 $(a,b)$ oraz $(c,d)$ 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: $(a,b)\circ (c,d)=(a\circ c,b\circ d)$. Oczywiście ${d}{o}{m}((a\circ c,b\circ d))=h$ oraz ${c}{o}{d}((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. \end_zadanie

\begin_zadanie \label{mod1:zad6} 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$.

\proof[Wskazówka:] Wykorzystaj Zadanie \ref{mod1:zad5}.

\proof[Rozwiązanie:] Tak jak w Zadaniu \ref{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:

\begin_quote{\tt Tu wstawić brakujący rysunek o numerze 1.24}\end_quote

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. \end_zadanie

\begin_zadanie \label{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 $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:

\begin_quote{\tt Tu wstawić brakujący rysunek o numerze 1.25}\end_quote

(Przypomnijmy sobie umowę z Zadania \ref{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 $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. \end_zadanie

\begin_zadanie \label{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 $(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ć. \end_zadanie

\begin_zadanie \label{mod1:zad9} Pokaż, że w kategorii $\mathbf{𝐌}\mathbf{𝐨}\mathbf{𝐧}$ izomorfizmy to dokładnie bijektywne homomorfizmy monoidów.

\proof[Wskazówka:] Jedna z implikacji jest bardzo łatwa: jeśli $f$ jest izomorfizmem w $\mathbf{𝐌}\mathbf{𝐨}\mathbf{𝐧}$, 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 \ref{mod1:fact:bij}). Wystarczy więc udowodnić implikację odwrotną.

\proof[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ć. \end_zadanie

\begin_zadanie \label{mod1:zad10} Przekonaj się, że kategorie i funktory tworzą kategorię, którą oznaczamy $\mathbf{𝐂}\mathbf{𝐚}\mathbf{𝐭}$. \proof[Wskazówka:] Przeczytaj najpierw Definicję \ref{mod5:def:funktor}, w której mówimy czym są funktory. \proof[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 $\mathbf{𝐒}\mathbf{𝐞}\mathbf{𝐭}$. 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. \end_zadanie

\begin_zadanie \label{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 $\lambda$-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:]\begin_enumerate \item {\bf Automaty:} Niech $M=(M,*,e)$ będzie monoidem. Definiujemy {\bf $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ż? \item {\bf 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: \begin_enumerate \item typów: $A,B,A\times B,A\to B,...$ \item termów, w skład których wchodzą: \begin_enumerate \item dla każdego typu $A$ zmienne tego typu: $x:A,y:A,z:A,...$, \item stałe różnych typów: $a:A,b:B,...$, \item dla dowolnych $a:A,b:B$, para: $⟨a,b⟩:A\times B$, \item dla dowolnego $c:A\times ,B$, projekcja ${\pi }_1(c):A$, \item dla dowolnego $c:A\times B$, projekcja ${\pi }_2(c):B$, \item dla dowolnych $c:A\times B,a:A$, aplikacja $ca:B$, \item dla dowolnych $x:A,b:B$, abstrakcja $\lambda x.b:A\to B$. \end_enumerate \item równań: \begin_enumerate \item ${\pi }_1(⟨a,b⟩)=a$, \item ${\pi }_2(⟨a,b⟩)=b$, \item $⟨{\pi }_1(c),{\pi }_2(c)⟩=c$, \item $(\lambda x.b)a=b[a/x]$, \item $\lambda x.cx=c$, o ile $x$ nie występuje w $c$. \end_enumerate \end_enumerate 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: \begin_itemize \item obiekty: typy $\lambda$-rachunku, \item morfizm z $A$ do $B$ to termy domknięte $c:A\to B$ (identyfikowane ze sobą, jeśli $c\approx c^{\prime }$), \item identyczności: $1_A=\lambda x.x$ dla każdego $x:A$, \item złożenie: $c\circ b=\lambda x.c(bx)$. \end_itemize 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,$ \begin_eqnarray* 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. \end_eqnarray* Kategorii $\mathbf{𝐂}(\lambda )$ przyjrzymy się jeszcze uważniej w wykładach \ref{wyklad3}, \ref{wyklad4}. \end_enumerate \end_zadanie

\end_document