Test Arka: Różnice pomiędzy wersjami

Z Studia Informatyczne
Przejdź do nawigacjiPrzejdź do wyszukiwania
← poprzednia edycja
WizualnieWikikod
Arek (dyskusja | edycje)
687 edycji
m Zastępowanie tekstu – „\displaystyle ” na „”
 
(Nie pokazano 110 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
<quiz type="exclusive">
Samuela Eilenberga i Saundersa MacLane'a: pionierską pracą jest tu
When working with character arrays, always reserve enough array elements to hold the string AND its null-terminating character (\0).
''General 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
<quiz type="exclusive">
teorii 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
<quiz type="exclusive">
<math>z</math> zbioru <math>B</math> przyporządkować element
Variables that are declared, but not initialized, contain
<math>x</math> zbioru <math>A</math>, zaś warunek pierwszy mówi,
<wrongoption>blank spaces</wrongoption>
że to przekształcenie (nazwijmy je <math>g</math>) jest funkcją
<rightoption reply="Tak, pod warunkiem, że są globalne">zeros</rightoption>
(śmiało napiszmy więc <math>g\colon B\to A</math>). W tym świetle
<rightoption reply="Jeśli nie są globalne">"garbage" values</rightoption>
z warunku drugiego wynika, że złożenie <math>f\circ g</math>
<wrongoption reply="Dostajesz pałę!">nothing - they are empty</wrongoption>
jest funkcją identycznościową na zbiorze <math>B</math>, a stąd
</quiz>
wynika <math>f\circ g\circ f = f</math>, co w połączeniu z pierwszym
warunkiem oznacza, że <math>g\circ f</math> jest identycznością
na zbiorze <math>A</math>. Idąc dalej tym tropem (patrz Zadanie
[[#mod1:zad1|Uzupelnic mod1:zad1|]]) jesteśmy w stanie bez trudu
pokazać, że:


{{ fakt|[Uzupelnij]|| {{kotwica|mod1:fact:bij|}} Funkcja <math>f\colon
A\to B</math> jest bijekcją wtedy i tylko wtedy,  gdy  istnieje funkcja
<math>g\colon B\to A</math> taka, że <math>f\circ g = 1_B</math> oraz
<math>g\circ f = 1_A</math>.  }}


Sam wynik nie wygląda, być może, ekscytująco, ale w koniunkcji z
<div style="background-color: #bbbbbb; padding: 2em; border: 1px solid black">
kolejnymi przykładami pozwoli nam wyciągnąć ekscytujące wnioski.
Dlaczego suma <math>\sum_{i=1}^{10}i</math> jest źle wyświetlana w wykładniku potęgi?


Rozważmy zatem zbiór liczb naturalnych
<math>z^{\sum_{i=1}^{10}i}</math>
<math>\mathrm\bf{nat}</math>. Teoria mnogości definiuje
<math>\mathrm\bf{nat}</math> jako najmniejszy zbiór zawierający
liczbę zero <math>0</math> i spełniający: <math>n\in \mathrm\bf{nat}
\Rightarrow \mathrm{succ}(n)\in \mathrm\bf{nat}</math>, gdzie
<math>\mathrm{succ}\colon \mathrm\bf{nat}\to \mathrm\bf{nat}</math>
jest funkcją następnika (która jest injektywna i posiada tę
właściwość, że <math>\mathrm{succ}(n)\neq 0</math> dla dowolnego
<math>n\in \mathrm\bf{nat}</math>). Okazuje się, że zbiór liczb
naturalnych można wyróżnić spośród innych zbiorów w ten sposób
(Zadanie [[#mod1:zad2|Uzupelnic mod1:zad2|]]):


{{ fakt|[Uzupelnij]||{{kotwica|mod1:fact:naturalne|}} Zbiór liczb
naturalnych <math>\mathrm\bf{nat}</math> jest to zbiór zawierający
liczbę zero oraz wyposażony w funkcję <math>\mathrm{succ}\colon
\mathrm\bf{nat}\to \mathrm\bf{nat}</math> taką, że: dla dowolnego zbioru
<math>X</math> i elementu <math>e\in X</math> oraz funkcji <math>g\colon
X\to X</math> istnieje dokładnie jedna funkcja <math>f\colon
\mathrm\bf{nat}\to X</math> spełniająca dwa warunki: <math>f(0)=
e</math> oraz <math>f\circ \mathrm{succ} = g\circ f</math>.  }}


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


Odpowiedź brzmi: ''tak'' -- i ta właśnie twierdząca odpowiedź
powołuje do życia teorię kategorii. Teoria kategorii składa
się bowiem z twierdzeń dotyczących uniwersalnych własności
przekształceń, niezależnych od cech szczególnych danych teorii
matematycznych. Tak więc, teoria kategorii bada wspólne, uniwersalne
własnościami zbiorów, grup, przestrzeni topologicznych, przestrzeni
wektorowych, częściowych porządków, i tak dalej, wszystko w języku
przekształceń danej struktury.


Czy da się krótko, nieformalnie zebrać najważniejsze
<div id="content">
cechy przekształceń -- cechy niezależne od konkretnej teorii
<div id="navcontainer">
matematycznej? Spróbujmy!  Zaczynamy od nazwy: przekształcenie
<ul id="navlist">
nazywać będziemy również '''morfizmem''' (bo w przeróżnych teoriach
<div><a href="index.xml" class="withChild">Start</a></div>
matematycznych natykamy się na homomorfizmy, homeomorfizmy, endomorfizmy,
itd.) lub po prostu '''strzałką''' (bo tak zwykle graficznie
przedstawia się przekształcenia). Przekształcenie działa pomiędzy
'''obiektami''', np. funkcja to przekształcenie zbiorów, homomorfizm to
przekształcenie grupy w grupę, funkcja ciągła to przekształcenie
przestrzeni topologicznej w przestrzeń topologiczną, funkcja
monotoniczna to przekształcenie posetu w poset, itd. (Załóżmy na
początku dla prostoty, że w naszych przykładach nie bierzemy pod uwagę
przekształceń obiektów pewnej klasy w obiekty innej klasy, na przykład
wyznacznika, który przekształca macierz w liczbę. Takimi morfizmami
zajmiemy się poźniej.) Każde przekształcenie <math>f</math> działa
na pewien jedyny obiekt, nazwijmy go '''dziedziną'''  <math>f</math>
i oznaczmy <math>\mathrm\it{dom}(f)</math>, i przekształca go w inny
jedyny obiekt nazywany '''przeciwdziedziną'''  <math>f</math> i oznaczany
jako <math>\mathrm\it{cod}(f)</math>. Fakt, że morfizm <math>f</math>
ma dziedzinę <math>A</math> i przeciwdziedzinę <math>B</math> zapisujemy


{Tu wstawić brakujący rysunek o numerze 1.1}
<div id="active" class="withoutChild">Zadanie 1.</div>
<div><a href="zadanie_2.xml" class="withoutChild">Zadanie 2.</a></div>
<div><a href="zadanie_3.xml" class="withoutChild">Zadanie 3.</a></div>
<div><a href="zadanie_4.xml" class="withoutChild">Zadanie 4.</a></div>
<div><a href="zadanie_5.xml" class="withoutChild">Zadanie 5.</a></div>
<div><a href="zadanie_6.xml" class="withoutChild">Zadanie 6.</a></div>


lub po prostu <math>f\colon A\to B</math>. Nasza teoria nie
</ul>
może istnieć bez pojęcia '''złożenia'''  przekształceń:
</div>
zakładamy, że dwóm morfizmom <math>f,g</math> takim, że
<div id="main">
<math>\mathrm{cod}(g)=\mathrm{dom}(f)</math> (strzałki takie nazywamy
<div id="nodeDecoration">
'''składalnymi''') przypisujemy morfizm <math>f \circ g</math>
<p id="nodeTitle">Zadanie 1.</p>
zwany złożeniem, dla którego mamy <math>\mathrm{dom}(f\circ
</div>
g) = \mathrm{dom}(g)</math> i <math>\mathrm{cod}(f\circ
<script type="text/javascript" src="common.js"></script> <script
g)=\mathrm{cod}(f)</math>.  Przykłady wskazują na to, że kolejność
type="text/javascript" src="libot_drag.js"></script>
złożenia składalnych przekształceń nie powinna grać roli, czyli dla:
<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>


{Tu wstawić brakujący rysunek o numerze 1.2}
<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>


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


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


może powstać albo z:
<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>


{Tu wstawić brakujący rysunek o numerze 1.4}
</div>
 
</div>
albo, równoważnie, z:
<div class="noprt" align="right"><a href="index.xml">&laquo;
 
previous</a> | <a href="zadanie_2.xml">next &raquo;</a></div>
{Tu wstawić brakujący rysunek o numerze 1.5}
</div>
 
</div>
W końcu, w naszej nieformalnej teorii przekształceń postulujemy
istnienie przekształceń, które - jak to się potocznie mówi: nic
nie zmieniają, tak zwanych '''identyczności''':
 
{Tu wstawić brakujący rysunek o numerze 1.6}
 
To kończy nieformalny opis języka, w którym główną rolę grają
przekształcenia. Zapiszmy to teraz formalnie.
 
===Definicja kategorii===
 
{{ definicja|[Uzupelnij]|XXXX| {{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>.
 
{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|[Uzupelnij]|| {{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
 
{Tu wstawić brakujący rysunek o numerze 1.7}
 
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|[Uzupelnij]|| {{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:
 
{Tu wstawić brakujący rysunek o numerze 1.8}
 
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|[Uzupelnij]||{{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>.
 
{Dowód} (1)<math>\to</math>(2) Dla <math>y=\Box x</math> mamy <math>y\Box
= (\Box x)\Box = \Box x = e</math>. (2)<math>\to</math>(3) <math>\Box e
= \Box(y\Box) = y\Box = e</math>. (3)<math>\to</math>(4) <math>e\Box =
(\Box e)\Box)=\Box e = e</math>. (4)<math>\to</math>(5) Załóżmy,
że <math>ex</math> jest zdefiniowane dla każdego <math>x</math>; to
oznacza, że <math>e\Box = \Box x</math>, czyli z (4), <math>e=\Box
x</math> dla każdego <math>x</math>. A zatem <math>ex =(\Box x)x =
x</math>. (3)<math>\to</math>(1) Oczywiste. (4)<math>\to</math>(3)
<math>\Box e = \Box(e\Box) = e\Box = e</math>. (5)<math>\to</math>(4)
Połóżmy <math>x=e\Box</math>. Mamy <math>\Box x = \Box (e
\Box) = e\Box</math>, czyli <math>ex</math> istnieje. Z (5)
wynika, że <math>e(e\Box) = e\Box</math>. Ale (b3) implikuje,
że <math>e(e\Box)=e</math>, czyli <math>e=e\Box</math>. Dowód
równoważności (6) z (3) jest podobny do równoważności (5) z (4).  }}
 
Morfizm <math>e</math> spełniający dowolny z powyższych warunków
nazywamy '''identycznością'''.
 
A zatem równoważność trzeciej definicji kategorii z
pierwszą uzyskujemy następująco (tak naprawdę, to pokażemy
jedynie, że dane Definicji [[#mod1:def:kategoria3|Uzupelnic
mod1:def:kategoria3|]] wystarczą do zrekonstruowania Definicji
[[#mod1:def:kategria1|Uzupelnic mod1:def:kategria1|]]: Identyczność
<math>1_x</math> to zmienna <math>x</math> taka, że <math>x=\Box
x =x\Box</math>. Dziedziną <math>x</math> jest <math>\Box
x</math>, przeciwdziedziną <math>x\Box</math>. Złożenie
<math>x\circ y</math> to <math>yx</math>. Kolekcja obiektów
Definicji [[#mod1:def:kategria1|Uzupelnic mod1:def:kategria1|]]
pokrywa się z kolekcją morfizmów identycznościowych Definicji
[[#mod1:def:kategoria3|Uzupelnic mod1:def:kategoria3|]].  Zauważmy,
że dla dowolnego <math>x</math>, zarówno <math>\Box x</math>,
jak i <math>x\Box</math> są obiektami (identycznościami), bo
<math>\Box(\Box x) = \Box x</math>, <math>(\Box x)\Box = \Box x</math>,
<math>(x\Box)\Box =(\Box(x\Box))\Box = \Box(x\Box) = x\Box</math>,
<math>\Box(x\Box)=x\Box</math>.
 
Sprawdźmy aksjomaty: <math>\mathrm{dom}(1_x) = \Box x = x = x\Box
= \mathrm{cod}(1_x)</math>. Aby  pokazać, że <math>f</math> jest
morfizmem, załóżmy, że <math>x=\mathrm{dom}(f)</math>(czyli <math>1_x
= \Box f</math>) oraz <math>y=\mathrm{cod}(f)</math> (czyli <math>1_y =
f\Box</math>)). Wówczas <math>f\circ 1_x = 1_x f = (\Box f)f = f</math>,
<math>1_y \circ f = f 1_y =f(f\Box) = f</math>.
 
Załóżmy teraz, że
<math>\mathrm{dom}(f)=\mathrm{cod}(g)</math>. Wówczas
<math>\mathrm{dom}(f\circ g) = \Box(gf) = \Box(g\Box
f) = \mathrm{dom}(1_{\mathrm{dom}(f)}\circ g) =
\mathrm{dom}(1_{\mathrm{cod}(g)}\circ g) = \mathrm{dom}(g)</math>.
Ostatnia równość wynika z poprzedniego paragrafu. Podobnie,
<math>\mathrm{cod}(f\circ g) = (gf)\Box = ((g\Box)f)\Box =
\mathrm{cod}(f\circ 1_{\mathrm{cod}(g)}) = \mathrm{cod}(f\circ
1_{\mathrm{dom}(f)}) = \mathrm{cod}(f)</math>.
 
W końcu, <math>f\circ (g\circ h) = (hg)f = h(gf)=(f\circ g)\circ h</math>
przy odpowiednich założeniach.
 
===Przykłady kategorii===
 
* <math>\mathbf{Set}</math>: Obiektami są zbiory, morfizmami funkcje.
Uwaga! W teorii mnogości funkcja jest zdefiniowana jako zbiór par
uporządkowanych takich, że
 
<math>
 
((x,y)\in f\ \wedge \ (x,y')\in f)\ \Rightarrow \ y=y'.  </math>
 
Aby traktować funkcje jako morfizmy musimy precyzyjnie znać
<math>\mathrm{dom}(f)</math> i <math>\mathrm{cod}(f)</math>. Na przykład
funkcje <math>\sin\colon \mathbb{R}\to [-1,1]</math> oraz <math>\sin\colon
\mathbb{R}\to \mathbb{R},</math>, które mają takie samo działanie na
argumentach, będą traktowane jako dwa różne morfizmy. Formalnie, w
języku teorii mnogości morfizmem będzie trójka <math>(X,f,Y)</math>
taka, że <math>f\subseteq X\times Y</math> spełnia powyższe równanie
([[#eq:funkcja|Uzupelnic eq:funkcja|]]) wraz z poniższym:
 
<math> x\in X \Rightarrow  (\exists y\in Y\ (x,y)\in f).  </math>
 
Wtedy <math>\mathrm{dom}</math> jest projekcją na pierwszą
współrzędną <math>(X,f,Y)\mapsto X</math>, a <math>\mathrm{cod}</math>
projekcją na trzecią współrzędną.
 
* Kategoria zbiorów skończonych i funkcji <math> \mathbf{Set}_{fin}
</math>, jak również wiele innych kategorii, w których obiektami
i morfizmami są ograniczone klasy zbiorów i funkcji, np. kategoria
wszystkich zbiorów skończonych i injekcji.
 
* Kategorie, w których obiektami są zbiory z pewną dodatkową
stukturą algebraiczną, zaś morfizmami te funkcje, które tę strukturę
zachowują.
 
* <math>\mathbf{Vect}</math>: Przestrzenie wektorowe i odwzorowania
liniowe
 
* <math>\mathbf{Grp}</math>: Grupy i homomorfizmy grup
 
* <math>\mathbf{Ab}</math>: Grupy abelowe i homomorfizmy grup
 
* <math>\mathbf{Mon}</math>: Monoidy i homomorfizmy monoidów
 
* <math>\mathbf{Pos}</math>: Częściowe porządki i funkcje monotoniczne
 
* <math>\mathbf{Top}</math>: Przestrzenie topologiczne i funkcje ciągłe
 
* <math>\mathbf{Graph}</math>: Grafy i homomorfizmy grafów
 
* liczby naturalne <math>\mathrm\bf{nat}</math> i wszystkie funkcje
obliczalne
 
* Mając dowolny częściowy porządek (poset) <math>(P,\leq)</math>
definiujemy kategorię o tej samej nazwie <math>P</math> jak
następuje: jako obiekty bierzemy elementy <math> P</math>, zaś dla
dwóch obiektów <math> x,y\in P</math> przyjmujemy, że istnieje
morfizm z <math>x</math> do <math>y</math> wtedy i tylko wtedy, gdy
<math>x\leq y</math>. Zauważmy, że wystarczy tu, by <math>P</math>
był preporządkiem, tzn. aby relacja <math>\leq</math> była zaledwie
zwrotna i przechodnia.
 
* <math>\mathbf{Rel}</math>: Obiektami tej kategorii są zbiory, zaś
morfizmami relacje binarne, tzn. <math> f\colon A\to B</math> wtedy
i tylko wtedy, gdy <math> f\subseteq A\times B</math>. Wówczas rolę
identyczności spełniają relacje identycznościowe: <math> 1_A = \{
(a,a)\mid a\in A \}</math>, zaś złożeniem morfizmów jest po prostu
złożenie relacji znane z kursu teorii mnogości: mając dane <math>
R\subseteq A\times B</math> oraz <math> S \subseteq B\times C</math>
przyjmujemy: <math> (a,c)\in S\circ R \Leftrightarrow \exists b\in B\
((a,b)\in R\wedge (b,c)\in S)</math>
 
* Kategorie 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ść.
 
{Tu wstawić brakujący rysunek o numerze 1.9}
 
* <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).
 
{Tu wstawić brakujący rysunek o numerze 1.10}
 
* <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!)
 
{Tu wstawić brakujący rysunek o numerze 1.11}
 
* Inne kategorie skończone możemy tworzyć biorąc skończoną ilość
obiektów wraz z odpowiadającymi im identycznościami, a następnie
dodając dowolną skończoną ilość morfizmów. W tym wypadku musimy
jednak zadbać o to, aby - jeśli morfizmy będą tworzyły cykle -
zadeklarować złożenia wszystkich morfizmów w cyklu jako równe
odpowiednim identycznościom. W innym bowiem przypadku uzyskana kategoria
nie musi już być skończona (może mieć nieskończenie wiele morfizmów
odpowiadających wielokrotnościom cyklu).
 
* Kategorie dyskretne:  są to takie kategorie, w których nie ma innych
morfizmów niż identyczności. Łatwo uzmysłowić sobie, że kategorie
dyskretne możemy utożsamiać ze zbiorami, bo przecież obiekty możemy
interpretować jako elementy zbioru.
 
{Tu wstawić brakujący rysunek o numerze 1.12}
 
* Niech <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...)
 
{Tu wstawić brakujący rysunek o numerze 1.13}
 
* Dla danego rachunku logicznego możemy stworzyć kategorię w ten
sposób, że obiektami są formuły: <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|[Uzupelnij]||{{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|[Uzupelnij]||{{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|[Uzupelnij]||{{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===
 
{{ cwiczenie|| {{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ą.
 
[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ą.  }}
 
{{ cwiczenie|| {{kotwica|mod1:zad2|}} Udowodnij Fakt
[[#mod1:fact:naturalne|Uzupelnic mod1:fact:naturalne|]].
 
[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.
 
[Rozwiązanie:] Załóżmy zatem, że <math>N</math> jest pewnym zbiorem,
który posiada wyróżniony element <math>0\in N</math> i funkcję
<math>s\colon N\to N</math> spełniającą warunki zadania. Udowodnimy po
kolei następujące zdania (znane jako aksjomaty Peano), które -- zgodnie
z wykładnią teorii mnogości -- w sposób jednoznaczny determinują
liczby naturalne spośród innych zbiorów, a co za tym idzie,
potwierdzą, że zbiór <math>N</math> jest zbiorem liczb naturalnych:
 
* <math>\exists 0\in N</math>
 
To wiemy z założenia.
 
* <math>\forall n\in N \ s(n)\in N</math>
 
To wiemy z założenia.
 
* <math>\forall n\in N \ s(n)\neq 0</math>
 
Przypuśćmy przeciwnie, że dla pewnego <math>n\in N</math>
mamy <math>s(n)=0</math>. Wtedy kładąc <math>X=\{e, a\}</math>
oraz <math>g(e)=g(a)=a</math>, z założenia istnieje funkcja
<math>f\colon N\to X</math> taka, że <math>f(0)=e</math> oraz
<math>f(s(n))=g(f(n))</math>. A zatem <math>f(s(n))=f(0)=e\neq a =
g(f(n))</math>, sprzeczność.
 
* <math>s</math> jest injekcją.
 
Przypuśćmy, że <math>s(n) = s(m)</math> dla pewnych <math>n,m\in
N</math>. Kładąc <math>X := \{0,s(0),s(s(0)), ...\}</math> (jest to
podzbiór <math>N</math>) oraz <math>e:=0</math>, wiemy, że istnieje
funkcja <math>f\colon N\to X</math> taka, że <math>f(0)=0</math> oraz
<math>f(s(n))=s(f(n))</math>. Taka funkcja jest tylko jedna, więc jej
zawężenie do <math>X</math> musi być równe funkcji <math>h\colon
X\to X</math>, która spełnia warunki <math>h(0)=0</math> oraz
<math>h(s(n))=n</math> dla <math>n\neq 0</math>. Dlatego założenie
<math>s(n)=s(m)</math> implikuje <math>n=h(s(n))=h(s(m))=m</math>,
co należało pokazać.
 
* <math>\forall A\subseteq N\ ((0\in A\wedge (a\in A\Rightarrow s(a)\in
A))\Rightarrow A=N)</math>
 
W tym punkcie przedstawimy najpierw rozumowanie teoriomnogościowe,
a potem skorzystamy z okazji, aby ten sam dowód pokazać bardziej w
duchu teorii kategorii (stopniowo ten drugi rodzaj dowodów będzie
zastępował pierwszy).
 
Rozważmy zatem funkcję <math>s'\colon A\to A</math>, która --
będąc obcięciem <math>s</math> do <math>A</math> -- spełnia
warunek <math>s\circ i = i\circ s'</math>, gdzie <math>i\colon A\to
N</math> jest inkluzją <math>A</math> w <math>N</math>. Zgodnie z
założeniem zadania, dla funkcji <math>s'</math> istnieje dokładnie
jedna funkcja <math>f\colon N\to A</math> taka, że <math>f(0)=0</math>
oraz <math>s'\circ f = f\circ s</math>.  Łącząc tą równość
z poprzednią, dostajemy <math>s\circ i\circ f = i\circ f\circ
s</math>. Zwróćmy teraz uwagę na funkcję <math>i\circ f\colon N\to
N</math>. Oczywiste spostrzeżenie, że <math>i\circ f(0)=0</math> pozwala
nam stwierdzić, że <math>i\circ f</math> jest ''jedyną'' funkcją typu
<math>N\to N</math>, która spełnia ostatnią z równości. Skoro tak,
to musi być równa identyczności na <math>N</math>. Pokazaliśmy więc,
że <math>i\circ f = 1_N</math>, a stąd -- jak łatwo pokazać wynika,
że <math>f\colon N\to A</math> jest injekcją. A zatem <math>N\subseteq
A</math>, co należało wykazać.
 
Pokazaliśmy zatem, że aksjomaty Peano są spełnione dla zbioru
<math>N</math>, a zatem teoria mnogości uczy nas, że <math>N</math>
jest zbiorem liczb naturalnych <math>\mathrm\bf{nat}</math>.
 
Dowód ostatniego z aksjomatów Peano prowadzony w duchu teorii kategorii,
czyli teorii przekształceń, korzysta z dobrodziejstwa, jakim jest
możliwość przedstawiania funkcji i ich złożeń na diagramach.
 
Po pierwsze, spróbujmy przedstawić graficznie (na diagramach)
założenia, które mamy, tzn. zdanie: ''<math>N</math> jest zbiorem,
który posiada wyróżniony element <math>0</math> oraz funkcję
<math>s\colon N\to N</math> takie, że dla dowolnego innego zbioru
<math>X</math> i elementu <math>e\in X</math> oraz funkcji <math>g\colon
X\to X</math> istnieje dokładnie jedna funkcja <math>f\colon N\to
X</math> spełniająca warunki <math>f(0)=e</math> oraz <math>f\circ s =
g\circ f</math>.''
 
Zauważmy więc, że element <math>0\in N</math> może być
zawsze traktowany jako funkcja <math>0\colon \top \to N</math>,
gdzie <math>\top</math> jest dowolnym zbiorem jednoelementowym
(zwróćmy uwagę, że w tej interpretacji aplikacja funkcji staje
się złożeniem, np. <math>f(0)</math> staje się złożeniem
<math>f\circ 0</math>). Podobnie dla <math>e\in X</math>. Po drugie,
wszelkie równości pomiędzy funkcjami przedstawiamy jako komutowanie
odpowiedniego diagramu, np. równość <math>f\circ s = g\circ f</math>
zachodzi wtedy i tylko wtedy, gdy poniższy diagram komutuje:
 
{Tu wstawić brakujący rysunek o numerze 1.14}
 
Następnie umawiamy się, że jeśli funkcja w diagramie jest jedyną,
która może znajdować się pomiędzy dwoma danymi obiektami, to
zaznaczamy ją przerywaną linią, np. zdanie ''...<math>f\colon N\to
X</math> jest jedyną funkcją taką, że...'' odzwierciedla się
graficznie jako:
 
{Tu wstawić brakujący rysunek o numerze 1.15}
 
Jeśli diagram jest bardziej skomplikowany, to umawiamy się, że
odczytujemy '''wszystkie''' możliwe równania, przy czym umawiamy się,
że nie musimy rysować identyczności. A zatem diagram:
 
{Tu wstawić brakujący rysunek o numerze 1.16}
 
komutuje wtedy i tylko wtedy, gdy <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
 
{Tu wstawić brakujący rysunek o numerze 1.17}
 
komutuje, co możemy przedstawić również w skrócie jako:
 
{Tu wstawić brakujący rysunek o numerze 1.18}
 
jak również komutuje diagram:
 
{Tu wstawić brakujący rysunek o numerze 1.19}
 
to z warunku jednoznaczności istnienia funkcji dostajemy <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.
 
}}
 
{{ cwiczenie|| {{kotwica|mod1:zad3|}} Znajdź przykład na to, że
w kategorii <math>\mathrm\bf{Pos}</math> bijekcje nie zawsze są
izomorfizmami.
 
[Wskazówka:] Wystarczy rozważyć częściowe porządki dwuelementowe.
 
[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:
 
{Tu wstawić brakujący rysunek o numerze 1.20}
 
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.  }}
 
{{ cwiczenie|| {{kotwica|mod1:zad4|}} Pokaż, że każda grupa może być
traktowana jako kategoria, w której każdy morfizm jest izomorfizmem.
 
[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.  }}
 
{{ cwiczenie|| {{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>.
 
[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:
 
{Tu wstawić brakujący rysunek o numerze 1.21}
 
Teraz już łatwo dopowiedzieć szczegóły konstrukcji.
 
[Rozwiązanie:] Zaproponujemy najpierw złożenie: dwa morfizmy
<math>(a,b)</math> oraz <math>(c,d)</math> jak poniżej:
 
{Tu wstawić brakujący rysunek o numerze 1.22}
 
składają się tak:
 
{Tu wstawić brakujący rysunek o numerze 1.23}
 
albo formalnie: <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.  }}
 
{{ cwiczenie|| {{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>.
 
[Wskazówka:] Wykorzystaj Zadanie [[#mod1:zad5|Uzupelnic mod1:zad5|]].
 
[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:
 
{Tu wstawić brakujący rysunek o numerze 1.24}
 
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.  }}
 
{{ cwiczenie|| {{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.
 
[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:
 
{Tu wstawić brakujący rysunek o numerze 1.25}
 
(Przypomnijmy sobie umowę z Zadania [[#mod1:zad2|Uzupelnic mod1:zad2|]],
że nie rysujemy identyczności.)
 
Podobnie, diagram:
 
{Tu wstawić brakujący rysunek o numerze 1.26}
 
komutuje, a co za tym idzie, złożenie tych dwóch diagramów komutuje:
 
{Tu wstawić brakujący rysunek o numerze 1.27}
 
To zaś kończy dowód faktu, że <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.  }}
 
{{ cwiczenie|| {{kotwica|mod1:zad8|}} Znajdź kategorię, która ma tę
własność, że jeśli dwa obiekty są izomorficzne, to muszą być
sobie równe.
 
[Wskazówka:] Można wziąć pod uwagę te szczególne kategorie,
w których istnieje co najwyżej jedna strzałka pomiędzy dowolnymi
dwoma obiektami.
 
[Rozwiązanie:] Niech <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ć.  }}
 
{{ cwiczenie|| {{kotwica|mod1:zad9|}} Pokaż, że w kategorii
<math>\mathrm\bf{Mon}</math> izomorfizmy to dokładnie bijektywne
homomorfizmy monoidów.
 
[Wskazówka:] Jedna z implikacji jest bardzo łatwa: jeśli <math>f</math>
jest izomorfizmem w <math>\mathrm\bf{Mon}</math>, to w szczególności
jest morfizmem, czyli homomorfizmem monoidów. Równania dla
<math>f</math> jako izomorfizmu implikują, że <math>f</math> jest też
bijekcją, w dokładnie ten sam sposób, w jaki pokazaliśmy dla funkcji
między zbiorami (patrz dyskusja po Fakcie [[#mod1:fact:bij|Uzupelnic
mod1:fact:bij|]]). Wystarczy więc udowodnić implikację odwrotną.
 
[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ć.  }}
 
{{ cwiczenie|| {{kotwica|mod1:zad10|}} Przekonaj się, że
kategorie i funktory tworzą kategorię, którą oznaczamy
<math>\mathrm\bf{Cat}</math>.  [Wskazówka:] Przeczytaj najpierw
Definicję [[#mod5:def:funktor|Uzupelnic mod5:def:funktor|]], w której
mówimy czym są funktory.  [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.  }}
 
{{ cwiczenie|| {{kotwica|mod1:zad11|}} Podaj dwa dalsze przykłady
kategorii.  [Wskazówka:] Najprościej zdefiniować nowe kategorie poprzez
modyfikację istniejących przykładów (np. kategorię tworzą zbiory i
funkcje częściowe). Nasz drugi przykład jest tego typu: jako język
funkcyjny bierzemy <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.
 
[Rozwiązanie:]
 
* Automaty::  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ż?
 
* 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:
 
* typów: <math>A,B, A\times B,A\to B, ...</math>
 
* termów, w skład których wchodzą:
 
* dla każdego typu <math>A</math> zmienne tego typu:
<math>x:A,y:A,z:A,...</math>,
 
* stałe różnych typów: <math>a:A,b:B,...</math>,
 
* dla dowolnych <math>a:A, b:B</math>, para: <math>\langle
a,b\rangle:A\times B</math>,
 
* dla dowolnego <math>c:A\times, B</math>, projekcja
<math>\pi_1(c):A</math>,
 
* dla dowolnego <math>c:A\times B</math>, projekcja
<math>\pi_2(c):B</math>,
 
* dla dowolnych <math>c:A\times B, a:A</math>, aplikacja
<math>ca:B</math>,
 
* dla dowolnych <math>x:A, b:B</math>, abstrakcja <math>\lambda x.b:A\to
B</math>.
 
* równań:
 
* <math>\pi_1(\langle a,b\rangle)=a</math>,
 
* <math>\pi_2(\langle a,b\rangle)=b</math>,
 
* <math>\langle\pi_1(c),\pi_2(c)\rangle=c</math>,
 
* <math>(\lambda x.b)a = b[a/x]</math>,
 
* <math>\lambda x.cx = c</math>, o ile <math>x</math> nie występuje
w <math>c</math>.
 
Definiujemy też relację <math>a\approx b</math> na termach (nazywaną
zwyczajowo <math>\beta\eta</math>-równoważnością), jako relację
równoważności generowaną przez równania i zamianę nazwy zmiennych
związanych: o ile <math>y</math> nie występuje w <math>b</math>,
to <math>\lambda x.b = \lambda y.b[y/x].</math>
 
Kategorię <math>\mathbf{C}(\lambda)</math> definiujemy teraz jak
następuje:
 
* obiekty: typy <math>\lambda</math>-rachunku,
 
* morfizm z <math>A</math> do <math>B</math> to termy domknięte
<math>c\colon A\to B</math> (identyfikowane ze sobą, jeśli
<math>c\approx c'</math>),
 
* identyczności: <math>1_A = \lambda x.x</math> dla każdego
<math>x:A</math>,
 
* złożenie: <math>c\circ b = \lambda x.c(bx)</math>.
 
Sprawdźmy, że <math>\mathbf{C}(\lambda)</math> jest kategorią:
<math>c\circ 1_B = \lambda x.c((\lambda y.y)x)=\lambda x.c(y[x/y])=\lambda
x.cx=c,</math> <math>1_C \circ c= \lambda x.(\lambda y.y)(cx) = \lambda
x.y[cx/y]=\lambda x.cx = c,</math>
 
<math>\aligned c\circ (b\circ a) & = & \lambda x.c((b\circ a)x)\\ & =
& \lambda x.c((\lambda y.b(ay))x)\\ & = & \lambda x.c(b(ax))\\ & = &
\lambda x.\lambda y.c((by)(ax))\\ & = & \lambda x.(c\circ b)(ax)\\ & = &
(c\circ b)\circ a.
 
\endaligned</math>
 
Kategorii <math>\mathbf{C}(\lambda)</math> przyjrzymy się
jeszcze uważniej w wykładach [[#wyklad3|Uzupelnic wyklad3|]],
[[#wyklad4|Uzupelnic wyklad4|]].
 
}}

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”