Test Arka: Różnice pomiędzy wersjami

Z Studia Informatyczne
Przejdź do nawigacjiPrzejdź do wyszukiwania
← poprzednia edycja
WizualnieWikikod
Arek (dyskusja | edycje)
687 edycji
Nie podano opisu zmian
m Zastępowanie tekstu – „\displaystyle ” na „”
 
(Nie pokazano 116 wersji utworzonych przez 4 użytkowników)
Linia 1: Linia 1:
==Moduł: Teoria kategorii jako abstrakcyjna teoria funkcji==
<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>
==Testy==


Teoria kategorii jako ogólny dział algebry wyrosła z prac Samuela
<quiz type="exclusive">
Eilenberga i Saundersa MacLane'a: pionierską pracą jest tu ''General
When working with character arrays, always reserve enough array elements to hold the string AND its null-terminating character (\0).
theory of natural equivalences'', Transactions of the American
<rightoption>True</rightoption>
Mathematical Society 58 (1945), pp. 231-294 -- autorzy wprowadzili tam
<wrongoption>False</wrongoption>
pojęcie kategorii, funktora i naturalnej transformacji funktorów. Teoria
</quiz>
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===
<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>


Zacznijmy od niegroźnego przeformułowania dwóch znanych pojęć z teorii
<quiz type="exclusive">
mnogości.
In C++, 14 % 4 =
<option reply="Za mało">1</option>
<option>2</option>
<option reply="Za dużo">3</option>
<wrongoption reply="O wiele za dużo">4</wrongoption>
</quiz>
<quiz>
In C++, 14 % 4 =
<option reply="Za mało">1</option>
<option>2</option>
<option reply="Za dużo">3</option>
<wrongoption reply="O wiele za dużo">4</wrongoption>
</quiz>


Jak pamiętamy, funkcja <math>f\colon A\to B</math> jest '''bijekcją'''
<quiz>
jeśli jest różnowartościową surjekcją, tj.  <math>\forall x,y\in A\
Variables that are declared, but not initialized, contain
f(x)=f(y)\Rightarrow x=y</math> oraz <math>\forall z\in B\ \exists x\in
<wrongoption>blank spaces</wrongoption>
A\ f(x)=z.</math>
<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>


Zauważmy, że drugi warunek pozwala nam każdemu elementowi <math>z</math>
<quiz type="exclusive">
zbioru <math>B</math> przyporządkować element <math>x</math> zbioru
Variables that are declared, but not initialized, contain
<math>A</math>, zaś warunek pierwszy mówi, że to przekształcenie
<wrongoption>blank spaces</wrongoption>
(nazwijmy je <math>g</math>) jest funkcją (śmiało napiszmy więc
<rightoption reply="Tak, pod warunkiem, że są globalne">zeros</rightoption>
<math>g\colon B\to A</math>). W tym świetle z warunku drugiego wynika,
<rightoption reply="Jeśli nie są globalne">"garbage" values</rightoption>
że złożenie <math>f\circ g</math> jest funkcją identycznościową na
<wrongoption reply="Dostajesz pałę!">nothing - they are empty</wrongoption>
zbiorze <math>B</math>, a stąd wynika <math>f\circ g\circ f = f</math>,
</quiz>
co w połączeniu z pierwszym warunkiem oznacza, że <math>g\circ f</math>
jest identycznością na zbiorze <math>A</math>. Idąc dalej tym tropem
(patrz Zadanie [[#mod1:zad1|Uzupelnic mod1:zad1|]]) jesteśmy w stanie
bez trudu pokazać, że:


{{ Fakt||uzupelnic|


{{kotwica|mod1:fact:bij|}} Funkcja <math>f\colon A\to B</math> jest
<div style="background-color: #bbbbbb; padding: 2em; border: 1px solid black">
bijekcją wtedy i tylko wtedy,  gdy  istnieje funkcja <math>g\colon B\to
Dlaczego suma <math>\sum_{i=1}^{10}i</math> jest źle wyświetlana w wykładniku potęgi?
A</math> taka, że <math>f\circ g = 1_B</math> oraz <math>g\circ f =
1_A</math>.  }}


Sam wynik nie wygląda, być może, ekscytująco, ale w koniunkcji z kolejnymi
<math>z^{\sum_{i=1}^{10}i}</math>
przykładami pozwoli nam wyciągnąć ekscytujące wnioski.


Rozważmy zatem zbiór liczb naturalnych
<math>\mathrm'''nat'''</math>. Teoria mnogości definiuje
<math>\mathrm'''nat'''</math> jako najmniejszy zbiór zawierający
liczbę zero <math>0</math> i spełniający: <math>n\in \mathrm'''nat'''
\Rightarrow \mathrm{succ}(n)\in \mathrm'''nat'''</math>, gdzie
<math>\mathrm{succ}\colon \mathrm'''nat'''\to \mathrm'''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'''nat'''</math>). Okazuje się, że zbiór liczb
naturalnych można wyróżnić spośród innych zbiorów w ten sposób (Zadanie
[[#mod1:zad2|Uzupelnic mod1:zad2|]]):


{{ Fakt||uzupelnic| {{kotwica|mod1:fact:naturalne|}} Zbiór liczb
</div>
naturalnych <math>\mathrm'''nat'''</math> jest to zbiór zawierający
liczbę zero oraz wyposażony w funkcję <math>\mathrm{succ}\colon
\mathrm'''nat'''\to \mathrm'''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'''nat'''\to X</math> spełniająca dwa warunki: <math>f(0)= e</math>
oraz <math>f\circ \mathrm{succ} = g\circ f</math>.  }}


Dwa powyższe przykłady wskazują na to, że definicje teorii mnogości można
wyrażać operując jedynie pojęciem funkcji i złożenia funkcji (zauważmy,
że elementy zbiorów można traktować jako funkcje, których dziedziną
jest singleton). Postawmy więc śmiałe pytanie: czy można prezentować
różnorodne teorie matematyczne badając jedynie własności przekształceń
obiektów matematycznych będących przedmiotem zainteresowania danej teorii?
A zatem pytamy czy: można prezentować teorię mnogości badając własności
funkcji między zbiorami, teorię grup badając własności homomorfizmów grup,
topologię badając własności funkcji ciągłych pomiędzy przestrzeniami
topologicznymi? W ogólności zapytajmy więc jeszcze raz: czy można badać
dowolne obiekty matematyczne z określoną strukturą za pomocą własności
przekształceń, które tę strukturę zachowują?


Odpowiedź brzmi: ''tak'' -- i ta właśnie twierdząca odpowiedź powołuje do
<div id="content">
życia teorię kategorii. Teoria kategorii składa się bowiem z twierdzeń
<div id="navcontainer">
dotyczących uniwersalnych własności przekształceń, niezależnych od cech
<ul id="navlist">
szczególnych danych teorii matematycznych. Tak więc, teoria kategorii
<div><a href="index.xml" class="withChild">Start</a></div>
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ń
<div id="active" class="withoutChild">Zadanie 1.</div>
-- cechy niezależne od konkretnej teorii matematycznej? Spróbujmy!
<div><a href="zadanie_2.xml" class="withoutChild">Zadanie 2.</a></div>
Zaczynamy od nazwy: przekształcenie nazywać będziemy również
<div><a href="zadanie_3.xml" class="withoutChild">Zadanie 3.</a></div>
'''morfizmem''' (bo w przeróżnych teoriach matematycznych natykamy
<div><a href="zadanie_4.xml" class="withoutChild">Zadanie 4.</a></div>
się na homomorfizmy, homeomorfizmy, endomorfizmy, itd.) lub po
<div><a href="zadanie_5.xml" class="withoutChild">Zadanie 5.</a></div>
prostu '''strzałką''' (bo tak zwykle graficznie przedstawia się
<div><a href="zadanie_6.xml" class="withoutChild">Zadanie 6.</a></div>
przekształcenia). Przekształcenie działa pomiędzy '''obiektami''',
np. funkcja to przekształcenie zbiorów, homomorfizm to przekształcenie
grupy w grupę, funkcja ciągła to przekształcenie przestrzeni topologicznej
w przestrzeń topologiczną, funkcja monotoniczna to przekształcenie
posetu w poset, itd. (Załóżmy na początku dla prostoty, że w naszych
przykładach nie bierzemy pod uwagę przekształceń obiektów pewnej klasy
w obiekty innej klasy, na przykład wyznacznika, który przekształca
macierz w liczbę. Takimi morfizmami zajmiemy się poźniej.) Każde
przekształcenie <math>f</math> działa na pewien jedyny obiekt, nazwijmy go
'''dziedziną'''  <math>f</math> i oznaczmy <math>\mathrm''dom''(f)</math>,
i przekształca go w inny jedyny obiekt nazywany '''przeciwdziedziną'''
<math>f</math> i oznaczany jako <math>\mathrm''cod''(f)</math>.  Fakt,
że morfizm <math>f</math> ma dziedzinę <math>A</math> i przeciwdziedzinę
<math>B</math> zapisujemy


\begin_quote\tt{Tu wstawić brakujący rysunek o numerze 1.1}\end_quote
</ul>
</div>
<div id="main">
<div id="nodeDecoration">
<p id="nodeTitle">Zadanie 1.</p>
</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>


lub po prostu <math>f\colon A\to B</math>. Nasza teoria nie może istnieć
<mo class="MathClass-bin">+</mo> <mn>2</mn><msqrt><mrow>
bez pojęcia '''złożenia'''  przekształceń: zakładamy, że dwóm morfizmom
<mn>2</mn></mrow></msqrt></mrow></msqrt> <mo class="MathClass-bin">&minus;</mo><msqrt><mrow><mn>3</mn>
<math>f,g</math> takim, że <math>\mathrm{cod}(g)=\mathrm{dom}(f)</math>
<mo class="MathClass-bin">&minus;</mo> <mn>2</mn><msqrt><mrow>
(strzałki takie nazywamy '''składalnymi''') przypisujemy morfizm <math>f
<mn>2</mn></mrow></msqrt></mrow></msqrt></math> &nbsp;&nbsp;
\circ g</math> zwany złożeniem, dla którego mamy <math>\mathrm{dom}(f\circ
<table>
g) = \mathrm{dom}(g)</math> i <math>\mathrm{cod}(f\circ
<tbody>
g)=\mathrm{cod}(f)</math>.  Przykłady wskazują na to, że kolejność
złożenia składalnych przekształceń nie powinna grać roli, czyli dla:


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


morfizm:
<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>


\begin_quote\tt{Tu wstawić brakujący rysunek o numerze 1.3}\end_quote
<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>


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

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”