1. Obiekty i odwzorowania
Interesuje nas ujęcie w abstrakcyjnych terminach pojęć takich jak suma, produkt, przestrzeń funkcji z do
. W poprzednich wykładach za pojęcia atomowe uznaliśmy punkty, proste i okręgi w geometrii Euklidesowej, zbiory w teorii zbiorów i zdania w rachunku zdań. W poniższych konstrukcjach za atomy uznamy odwzorowania, obiekty oraz składanie odwzorowań. W przybliżeniu naśladujemy podejście z artykułu An elementary theory of the category of sets autorstwa F. Williama Lawvere. Jeśli ktoś z Państwa chciałby “wyklikać” te konstrukcje, to można to zrobić na stronie Jocelyn Ireson-Paine. Klikanie polega na podaniu konkretnych zbiorów skończonych jako obiektów, na których ma być wykonana dana konstrukcja, a komputer podaje żądane nowe zbiory i odwzorowania i weryfikuje je na przykładach.
Piszemy , jeśli
są obiektami, a
jest odwzorowaniem między
i
. Obiekt
nazwiemy dziedziną
, a obiekt
przeciwdziedziną
. Jeśli
i
, to zakładamy, że istnieje złożenie, oznaczane
. Pisząc
mamy na myśli złożenie .
2. Aksjomaty
- Łączność: jeśli
,
,
to
(2) - Istnienie identyczności: dla każdego obiektu
istnieje odwzorowanie
, którego dziedziną i przeciwdziedziną jest
i takie, że każdego odwzorowania
,
, zachodzi
(3)
3. Izomorfizmy
Odwzorowanie jest izomorfizmem, jeśli istnieje odwzorowanie
o tej własności, że
oraz
. Odwzorowanie
nazywamy odwrotnością
.
Lemat 1. Dla każdego izomorfizmu jego odwrotność jest jednoznacznie wyznaczona.
Dowód. Załóżmy, że ,
są odwrotnościami
. Wtedy
dzięki aksjomatowi łączności. Z definicji odwrotności i definicji identyczności dostajemy
To kończy dowód lematu Lematu 1.
Zadanie 1. Mówimy, że jest lewą odwrotnością
, jeśli
i
. Mówimy, że
jest prawą odwrotnością
, jeśli
i
. Udowodnij, że jeśli
jest lewą odwrotnością, a
prawą odwrotnością, to
.
4. Obiekt końcowy i początkowy, pojęcie elementu
Obiekt końcowy definiujemy jako obiekt o tej własności, że dla każdego obiektu
istnieje dokładnie jedno odwzorowania
. Obiek początkowy
definiujemy jako obiekt o tej własności, a dla każdego obiektu
istnieje dokładnie jedno odwzorowania
.
5. Produkt dwóch obiektów
Dla danych dwóch obiektów ,
przez produkt
i
rozumiemy obiekt
raz dwa odwzorowania
,
takie, że
dla dowolnego obiektu oraz dwóch odwzorowań
istniej dokładnie jedno odwzorowanie takie, że
oraz
, co równoważnie można wysłowić przy pomocy diagramu
Zadanie 2. Wykaż, że .
Zadanie 3. Wykaż, że .
W odniesieniu do zbiorów, produkt można zaimplementować na przykład przy pomocy pary Kuratowskiego. Mianowicie, dla zbiorów definiujemy parę Kuratowskiego jako
. W istocie dowolna inna konstrukcja pary
byłaby dobra, jeśli spełnione byłyby warunek, że
wtedy i tylko wtedy, gdy
i
.
Lemat 2. Niech ,
będą zbiorami. Wtedy zbiór
wraz z odwzorowaniami
,
, jest produktem zbiorów
i
.
Dowód. Rozważmy obiekt oraz dwa odwzorowania
Naszym zadaniem jest skonstruować takie, żeby diagram okazał się przemienny.
Niech . Wtedy
oraz
. Należy jeszcze zauważyć, że
jest jednoznacznie wyznaczone, gdyż z warunków
oraz
można już stwierdzić, że
.
.
Zadanie 4. Sprawdż, że w przypadku definicji pary uporządkowanej w wersji Kuratowskiego, możemy zdediniować . Podaj wzór na
i sprawdź jego poprawność.
Zadanie 5. Sprawdż, że para zdefiniowana wzorem
spełnia warunek, że
wtedy i tylko wtedy, gdy
i
. Znajdź odwzorowania
i
dla tej pary.
6. Implementacja funkcji jako relacji binarnych
Wszystkie podane w tym wykładzie definicje odnoszą się do ogólnych obiektów, ale na naszym wykładzie jesteśmy szczególnie zainteresowani zbiorami. Jest to szczególny rodzaj obiektów, dla których odwzorowania możemy zdefiniować jako podzbiory
o tej własności, że dla każdego
istnieje dokładnie jeden
taki, że
. Zatem każdemu elementowi w dziedzinie
odpowiada dokładnie jeden element w przeciwdziedzinie
. Taką implementację pojęcia funkcji będziemy nazywać implementacją funkcji jako relacji binarnej.
Zadanie 6. Przy implementacji funkcji jako relacji binarnych sprawdź, że obiektem początkowym jest zbiór pusty, a obiektem końcowym jest każdy singleton.
W terminach obiektów i odwzorowań możemy zdefiniować także pojęcie elementu. Mówimy, że odwzorowanie jest elementem obiektu
, jeśli
(ozn.
). W poniższym zadaniu sprawdzamy, że w odniesieniu do zbiorów i funkcji jako relacji binarnych, pojęcia
i
działają tak samo.
Zadanie 7. Niech będzie funkcją i niech
,
będą zbiorami. Przy implementacji funkcji jako relacji binarnych sprawdź, że
7. Suma dwóch obiektów
Sumą obiektów jest obiekt
oraz odwzorowania
takie, że następujący diagram
jest przemienny. Oznacza to, że dla dowolnych odwzorowań ,
ma istnieć dokładnie jedno odwzorowanie
takie, że
Lemat 3. Niech ,
będą zbiorami. Wtedy
wraz z odwzorowaniami
oraz
spełnia warunki definicji sumy.
Dowód. Ustalmy dowolne oraz odwzorowania
,
. Dla
definiujemy
Jeśli , to wtedy
i podobnie, jeśli
, to wtedy
. Ponadto wzory
(
),
(
) jednoznacznie określają
na całym zbiorze
.
8. Epimorfizm`
Poniższy diagram czytamy następujaco: jest epimorfizmem, jeśli z warunku, że
wynika, że
.
Zadanie 8. Sprawdź, że złożenie dwóch epimorfizmów jest epimorfizmem.
Zadanie 9. Sprawdź, że jeśli jest odwzorowaniem z
do
zakodwanym jako relacja binarna i dla każdego
istnieje
takie, że
, to
jest epimorfizmem.
9. Monomofizm
Poniższy diagram czytamy następujaco: jest monomorfizmem, jeśli z warunku, że
wynika, że
.
Zadanie 10. Sprawdź, że złożenie dwóch monomorfizmów jest monomorfizmem.
Zadanie 11. Sprawdź, że jeśli jest odwzorowaniem z
do
zakodwanym jako relacja binarna i dla każdych
,
zachodzi
, to
jest monomorfizmem.
10. Ekwaliztor
Zadanie 12. Implementacja jako podzbioru, na którym się zgadzają.
11. Koekwaliztor
Zadanie 13. Implementacja jako relacji na .
12. Obiekt wykładniczy
Dla obiektów znajdziemy ogólną definicję “przestrzeni funkcji” z
do
.
Obiekt nazywamy obiektem wykładniczym, jeśli dla dowolnego obiektu
i odwzorowania
istnieje dokładnie jedno odwzorowanie
takie, że powyższy diagram jest przemienny.
Zadanie 14. Implementacja jako przestrzeni wszystkich funkcji z do
.