Test Arka: Różnice pomiędzy wersjami

Z Studia Informatyczne
Przejdź do nawigacjiPrzejdź do wyszukiwania
WizualnieWikikod
Arek (dyskusja | edycje)
687 edycji
Nie podano opisu zmian
 
m Zastępowanie tekstu – „\displaystyle ” na „”
 
(Nie pokazano 118 wersji utworzonych przez 4 użytkowników)
Linia 1: Linia 1:
\newtheorem{definition}[subsection]{Definicja}
<quiz type="exclusive">
\newtheorem{theorem}[subsection]{Twierdzenie}
When working with character arrays, always reserve enough array elements to hold the string AND its null-terminating character (\0).
\newtheorem{lemma}[subsection]{Lemat}
<rightoption>True</rightoption>
\newtheorem{corollary}[subsection]{Wniosek}
<wrongoption>False</wrongoption>
\newtheorem{remark}[subsection]{Uwaga}
</quiz>
\newtheorem{question}[subsection]{Pytanie}
==Testy==
\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
<quiz type="exclusive">
When working with character arrays, always reserve enough array elements to hold the string AND its null-terminating character (\0).
<rightoption>True</rightoption>
<wrongoption>False</wrongoption>
</quiz>


==Moduł: Teoria kategorii jako abstrakcyjna teoria funkcji==
<quiz>
When working with character arrays, always reserve enough array elements to hold the string AND its null-terminating character (\0).
<rightoption>True</rightoption>
<wrongoption>False</wrongoption>
</quiz>


Teoria
<quiz type="exclusive">
kategorii jako ogólny dział algebry wyrosła z prac Samuela
In C++, 14 % 4 =
Eilenberga i Saundersa MacLane'a: pionierską pracą jest tu {\it
<option reply="Za mało">1</option>
General theory of natural equivalences}, Transactions of the
<option>2</option>
American Mathematical Society 58 (1945), pp. 231-294 -- autorzy
<option reply="Za dużo">3</option>
wprowadzili tam pojęcie kategorii, funktora i naturalnej
<wrongoption reply="O wiele za dużo">4</wrongoption>
transformacji funktorów. Teoria kategorii szybko przekroczyła
</quiz>
granice algebry i jej język okazał się uniwersalnym sposobem
mówienia o innych teoriach matematycznych: logice, teorii zbiorów,
<quiz>
topologii, teorii porządku, geometrii, analizie itd. Jak to
In C++, 14 % 4 =
możliwe? Treść tych wykładów stanowi jedną z odpowiedzi na to
<option reply="Za mało">1</option>
pytanie.
<option>2</option>
<option reply="Za dużo">3</option>
<wrongoption reply="O wiele za dużo">4</wrongoption>
</quiz>


===Przekształcenia i ich algebra===
<quiz>
Variables that are declared, but not initialized, contain
<wrongoption>blank spaces</wrongoption>
<rightoption reply="Tak, pod warunkiem, że są globalne">zeros</rightoption>
<rightoption reply="Jeśli nie są globalne">"garbage" values</rightoption>
<wrongoption reply="Dostajesz pałę!">nothing - they are empty</wrongoption>
</quiz>


Zacznijmy od niegroźnego przeformułowania dwóch znanych pojęć z
<quiz type="exclusive">
teorii mnogości.
Variables that are declared, but not initialized, contain
<wrongoption>blank spaces</wrongoption>
<rightoption reply="Tak, pod warunkiem, że są globalne">zeros</rightoption>
<rightoption reply="Jeśli nie są globalne">"garbage" values</rightoption>
<wrongoption reply="Dostajesz pałę!">nothing - they are empty</wrongoption>
</quiz>


Jak pamiętamy, funkcja <math>f\colon A\to B</math> jest {\bf 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>
<div style="background-color: #bbbbbb; padding: 2em; border: 1px solid black">
zbioru <math>B</math> przyporządkować element <math>x</math> zbioru <math>A</math>, zaś warunek
Dlaczego suma <math>\sum_{i=1}^{10}i</math> jest źle wyświetlana w wykładniku potęgi?
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 \ref{mod1:zad1}) jesteśmy w stanie bez trudu pokazać, że:


\begin_fact
<math>z^{\sum_{i=1}^{10}i}</math>
\label{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>.
\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 <math>\mathrm{\bf nat}</math>. Teoria mnogości
</div>
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
\ref{mod1:zad2}):


\begin_fact\label{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>.
\end_fact


Dwa powyższe przykłady wskazują na to, że definicje teorii
<div id="content">
mnogości można wyrażać operując jedynie pojęciem funkcji i
<div id="navcontainer">
złożenia funkcji (zauważmy, że elementy zbiorów można traktować
<ul id="navlist">
jako funkcje, których dziedziną jest singleton). Postawmy więc
<div><a href="index.xml" class="withChild">Start</a></div>
ś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ź
<div id="active" class="withoutChild">Zadanie 1.</div>
powołuje do życia teorię kategorii. Teoria kategorii składa się
<div><a href="zadanie_2.xml" class="withoutChild">Zadanie 2.</a></div>
bowiem z twierdzeń dotyczących uniwersalnych własności
<div><a href="zadanie_3.xml" class="withoutChild">Zadanie 3.</a></div>
przekształceń, niezależnych od cech szczególnych danych teorii
<div><a href="zadanie_4.xml" class="withoutChild">Zadanie 4.</a></div>
matematycznych. Tak więc, teoria kategorii bada wspólne,
<div><a href="zadanie_5.xml" class="withoutChild">Zadanie 5.</a></div>
uniwersalne własnościami zbiorów, grup, przestrzeni
<div><a href="zadanie_6.xml" class="withoutChild">Zadanie 6.</a></div>
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!
</ul>
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 <math>f</math> działa na pewien jedyny obiekt, nazwijmy go {\bf dziedziną}  <math>f</math> i
</div>
oznaczmy <math>\mathrm{\it dom}(f)</math>, i przekształca go w inny jedyny obiekt
<div id="main">
nazywany {\bf przeciwdziedziną}  <math>f</math> i oznaczany jako <math>\mathrm{\it cod}(f)</math>.
<div id="nodeDecoration">
Fakt, że morfizm <math>f</math> ma dziedzinę <math>A</math> i przeciwdziedzinę <math>B</math>
<p id="nodeTitle">Zadanie 1.</p>
zapisujemy
</div>
<script type="text/javascript" src="common.js"></script> <script
type="text/javascript" src="libot_drag.js"></script>
<div class="iDevice emphasis1"><img alt="Ikona obiektu Pytanie"
class="iDevice_icon" src="icon_question.gif" /> <span
class="iDeviceTitle">Zadanie 1,</span><br />
<div class="iDevice_inner">
Liczba <math><msqrt><mrow><mn>3</mn>


\begin_quote{\tt Tu wstawić brakujący rysunek o numerze 1.1}\end_quote
<mo class="MathClass-bin">+</mo> <mn>2</mn><msqrt><mrow>
<mn>2</mn></mrow></msqrt></mrow></msqrt> <mo class="MathClass-bin">&minus;</mo><msqrt><mrow><mn>3</mn>
<mo class="MathClass-bin">&minus;</mo> <mn>2</mn><msqrt><mrow>
<mn>2</mn></mrow></msqrt></mrow></msqrt></math> &nbsp;&nbsp;
<table>
<tbody>


lub po prostu <math>f\colon A\to B</math>. Nasza teoria nie może istnieć bez
<tr>
pojęcia {\bf złożenia}  przekształceń: zakładamy, że dwóm
<td><input type="checkbox" name="option9" id="ia0b9"
morfizmom <math>f,g</math> takim, że <math>\mathrm{cod}(g)=\mathrm{dom}(f)</math>
value="vTrue"
(strzałki takie nazywamy {\bf składalnymi}) przypisujemy morfizm
onclick="document.getElementById('sa0b9').style.display = this.checked ? 'block' : 'none';" /></td>
<math>f \circ g</math> zwany złożeniem, dla którego mamy <math>\mathrm{dom}(f\circ
<td>jest dodatnia</td>
g) = \mathrm{dom}(g)</math> i <math>\mathrm{cod}(f\circ g)=\mathrm{cod}(f)</math>.
<td>
Przykłady wskazują na to, że kolejność złożenia składalnych
<div id="sa0b9" style="color: rgb(0, 51, 204);display: none;">Poprawnie</div>
przekształceń nie powinna grać roli, czyli dla:
</td>
</tr>
<tr>


\begin_quote{\tt Tu wstawić brakujący rysunek o numerze 1.2}\end_quote
<td><input type="checkbox" name="option9" id="ia1b9"
value="vTrue"
onclick="document.getElementById('sa1b9').style.display = this.checked ? 'block' : 'none';" /></td>
<td>jest wymierna</td>
<td>
<div id="sa1b9" style="color: rgb(0, 51, 204);display: none;">Poprawnie</div>
</td>
</tr>
<tr>
<td><input type="checkbox" name="option9" id="ia2b9"
value="vFalse"
onclick="document.getElementById('sa2b9').style.display = this.checked ? 'block' : 'none';" /></td>


morfizm:
<td>nale&raquo;y do tr&oacute;jkowego zbioru Cantora.</td>
<td>
<div id="sa2b9" style="color: rgb(0, 51, 204);display: none;">Źle</div>
</td>
</tr>
</tbody>
</table>


\begin_quote{\tt Tu wstawić brakujący rysunek o numerze 1.3}\end_quote
</div>
 
</div>
może powstać albo z:
<div class="noprt" align="right"><a href="index.xml">&laquo;
 
previous</a> | <a href="zadanie_2.xml">next &raquo;</a></div>
\begin_quote{\tt Tu wstawić brakujący rysunek o numerze 1.4}\end_quote
</div>
 
</div>
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||uzupelnic|
 
\label{mod1:def:kategria1} Kategoria <math>\mathbf{C}</math> składa się z
następujących danych:
\begin_enumerate
\item[(D1)] {\bf obiektów}: <math>A,B,C,...</math>,
\item[(D2)] {\bf morfizmów}: <math>f,g,h,...</math>,
\item[(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>,
\item[(D4)] operacji <math>1</math> przypisującej każdemu
obiektowi <math>A</math> morfizm <math>1_A</math> nazywany identycznością,
\item[(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,
\end_enumerate
spełniających następujące aksjomaty:
\begin_enumerate
\item[(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>,
\item[(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>,
\item[(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>.
\end_enumerate
}}
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>.
 
{\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||uzupelnic|
 
\label{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 {\bf 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
\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||uzupelnic|
 
\label{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 {\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)] <math>xy</math> jest zdefiniowane wtw, gdy <math>x\Box = \Box y</math>,
\item[(b2)] <math>(\Box x )\Box = \Box x</math> oraz <math>\Box (x\Box) = x\Box</math>,
\item[(b3)] <math>(\Box x)x = x</math> oraz <math>x(x\Box)=x</math>,
\item[(b4)] <math>\Box(xy) = \Box(x(\Box y))</math> oraz <math>(xy)\Box = ((x\Box)y)\Box</math>
\item[(b5)] <math>x(yz)=(xy)z</math>.
\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 <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).
\end_lemma
 
Morfizm <math>e</math> 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ść <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 \ref{mod1:def:kategria1} pokrywa się z kolekcją
morfizmów identycznościowych Definicji \ref{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===
 
\begin_itemize
\item <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
\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ć
<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 (\ref{eq:funkcja}) wraz z poniższym:
\begin_equation
x\in X \Rightarrow  (\exists y\in Y\ (x,y)\in f).
\end_equation
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ą.
\item 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.
\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 <math>\mathbf{Vect}</math>: Przestrzenie wektorowe i odwzorowania liniowe
\item <math>\mathbf{Grp}</math>: Grupy i homomorfizmy grup
\item <math>\mathbf{Ab}</math>: Grupy abelowe i homomorfizmy grup
\item <math>\mathbf{Mon}</math>: Monoidy i homomorfizmy monoidów
\item <math>\mathbf{Pos}</math>: Częściowe porządki i funkcje monotoniczne
\item <math>\mathbf{Top}</math>: Przestrzenie topologiczne i funkcje ciągłe
\item <math>\mathbf{Graph}</math>: Grafy i homomorfizmy grafów
\item liczby naturalne <math>\mathrm{\bf nat}</math> i wszystkie funkcje obliczalne
\end_itemize
\item 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.
\item <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>
\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 <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
 
\item <math>\mathbf{0}</math>: Ta kategoria nie ma obiektów i
nie ma strzałek.
\item <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
 
\item <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
 
\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 <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
 
\item 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>.
\item 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 {\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||uzupelnic|
\label{mod1:def:iso}  Niech <math>\mathbf{C}</math> będzie dowolną
kategorią. Morfizm <math> f\colon A\to B</math> jest {\bf 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ę {\bf 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 \ref{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 \ref{mod5:def:konkret}, bijekcje {\it nie zawsze} są izomorfizmami. Prosty kontrprzykład stanowi tutaj
kategoria <math> \mathbf{Pos}</math> (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ę <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|
\label{mod1:def:size}  Kategorię <math>\mathbf{C}</math> nazywamy {\bf 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 {\bf 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|
\label{mod1:def:localsize} Kategorię <math> \mathbf{C} </math> nazywamy {\bf 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 {\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
<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 {\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 <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ą.
\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 <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:
\begin_itemize
\item <math>\exists 0\in N</math>
 
To wiemy z założenia.
 
\item <math>\forall n\in N \ s(n)\in N</math>
 
To wiemy z założenia.
 
\item <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ść.
 
\item <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ć.
 
\item <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 {\it 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: {\it <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 {\it ...<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 {\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 <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.
\end_itemize
 
\end_zadanie
 
\begin_zadanie
\label{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.
\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 <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.
\end_zadanie
 
\begin_zadanie
\label{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 {\it 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.
\end_zadanie
 
\begin_zadanie
\label{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 \ref{mod1:zad5}.
 
\proof[Rozwiązanie:] Tak jak w Zadaniu \ref{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.
\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 <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 \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 <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.
\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 <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ć.
\end_zadanie
 
\begin_zadanie
\label{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 \ref{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ć.
\end_zadanie
 
\begin_zadanie
\label{mod1:zad10} Przekonaj się, że kategorie i funktory tworzą kategorię, którą oznaczamy <math>\mathrm{\bf Cat}</math>.
\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 <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.
\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 <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:]\begin_enumerate
\item {\bf Automaty:} Niech <math>M=(M,*, e)</math> będzie monoidem. Definiujemy {\bf <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ż?
\item {\bf Rachunek 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:
\begin_enumerate
\item typów: <math>A,B, A\times B,A\to B, ...</math>
\item termów, w skład których wchodzą:
\begin_enumerate
\item dla każdego typu <math>A</math> zmienne tego typu: <math>x:A,y:A,z:A,...</math>,
\item stałe różnych typów: <math>a:A,b:B,...</math>,
\item dla dowolnych <math>a:A, b:B</math>, para: <math>\langle a,b\rangle:A\times B</math>,
\item dla dowolnego <math>c:A\times, B</math>, projekcja <math>\pi_1(c):A</math>,
\item dla dowolnego <math>c:A\times B</math>, projekcja <math>\pi_2(c):B</math>,
\item dla dowolnych <math>c:A\times B, a:A</math>, aplikacja <math>ca:B</math>,
\item dla dowolnych <math>x:A, b:B</math>, abstrakcja <math>\lambda x.b:A\to B</math>.
\end_enumerate
\item równań:
\begin_enumerate
\item <math>\pi_1(\langle a,b\rangle)=a</math>,
\item <math>\pi_2(\langle a,b\rangle)=b</math>,
\item <math>\langle\pi_1(c),\pi_2(c)\rangle=c</math>,
\item <math>(\lambda x.b)a = b[a/x]</math>,
\item <math>\lambda x.cx = c</math>, o ile <math>x</math> nie występuje w <math>c</math>.
\end_enumerate
\end_enumerate
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:
\begin_itemize
\item obiekty: typy <math>\lambda</math>-rachunku,
\item 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>),
\item identyczności: <math>1_A = \lambda x.x</math> dla każdego <math>x:A</math>,
\item złożenie: <math>c\circ b = \lambda x.c(bx)</math>.
\end_itemize
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>
\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 <math>\mathbf{C}(\lambda)</math> przyjrzymy się jeszcze uważniej w wykładach \ref{wyklad3}, \ref{wyklad4}.
\end_enumerate
\end_zadanie
 
\end_document

Aktualna wersja na dzień 08:57, 28 sie 2023

When working with character arrays, always reserve enough array elements to hold the string AND its null-terminating character (\0).

True

False

Testy

When working with character arrays, always reserve enough array elements to hold the string AND its null-terminating character (\0).

True

False

When working with character arrays, always reserve enough array elements to hold the string AND its null-terminating character (\0).

True

False

In C++, 14 % 4 =

1

2

3

4

In C++, 14 % 4 =

1

2

3

4

Variables that are declared, but not initialized, contain

blank spaces

zeros

"garbage" values

nothing - they are empty

Variables that are declared, but not initialized, contain

blank spaces

zeros

"garbage" values

nothing - they are empty


Dlaczego suma ∑i=110i jest źle wyświetlana w wykładniku potęgi?

z∑i=110i



Zadanie 1.

<script type="text/javascript" src="common.js"></script> <script type="text/javascript" src="libot_drag.js"></script>

<img alt="Ikona obiektu Pytanie"

class="iDevice_icon" src="icon_question.gif" /> Zadanie 1,

Liczba Parser nie mógł rozpoznać (błąd składni): {\displaystyle <msqrt><mrow><mn>3</mn> <mo class="MathClass-bin">+</mo> <mn>2</mn><msqrt><mrow> <mn>2</mn></mrow></msqrt></mrow></msqrt> <mo class="MathClass-bin">&minus;</mo><msqrt><mrow><mn>3</mn> <mo class="MathClass-bin">&minus;</mo> <mn>2</mn><msqrt><mrow> <mn>2</mn></mrow></msqrt></mrow></msqrt>}   

<tbody> </tbody>
<input type="checkbox" name="option9" id="ia0b9"

value="vTrue"

onclick="document.getElementById('sa0b9').style.display = this.checked ? 'block' : 'none';" />		 jest dodatnia
<input type="checkbox" name="option9" id="ia1b9"

value="vTrue"

onclick="document.getElementById('sa1b9').style.display = this.checked ? 'block' : 'none';" />		 jest wymierna
<input type="checkbox" name="option9" id="ia2b9"

value="vFalse"

onclick="document.getElementById('sa2b9').style.display = this.checked ? 'block' : 'none';" />		 nale»y do trójkowego zbioru Cantora.
<a href="index.xml">« previous</a> | <a href="zadanie_2.xml">next »</a>
Źródło: „https://wazniak.mimuw.edu.pl/index.php?title=Test_Arka&oldid=79852”