Teoria kategorii dla informatyków/Wykład 9: Sprzężenia I

Z Studia Informatyczne
Przejdź do nawigacjiPrzejdź do wyszukiwania

Pojęcie sprzężenia jest jednym z najważniejszych w kursie teorii kategorii. Sprzężenie jest pewną prostą zależnością pomiędzy dwoma przeciwnie zwróconymi funktorami, która, jak się okazuje, występuje niezwykle często w matematyce.


Definicja 9.1 [sprzężenie I]

Dwa funktory i
Tk-9.1.png

tworzą sprzężenie, jeśli dla dowolnej pary obiektów istnieje naturalna bijekcja:

W takim wypadku nazywamy lewym sprzężeniem, nazywamy prawym sprzężeniem i całą sytuację opisujemy krótko jako:


Taka definicja wyjaśnia dobrze ideę sprzężenia, ale szczegóły trzeba rozszyfrować: naturalność bijekcji oznacza, że jest naturalnym izomorfizmem pomiędzy pewnymi funktorami (dociekliwym należy się wyjaśnienie, że oba te funktory są typu ), a naturalność , pomijając nieciekawe przekształcenia techniczne, sprowadza się ni mniej, ni więcej do faktu, że poniższe dwa diagramy komutują dla dowolnych morfizmów i :

Tk-9.2.png

Równoważnie do Definicji 9.1 powiemy więc, że:


Definicja 9.2

Dwa funktory i tworzą sprzężenie, jeśli dla dowolnej pary obiektów istnieje naturalna bijekcja (piszmy niepoprawnie zamiast uciążliwego ), która dowolnej strzałce przypisuje strzałkę tak, że oraz dla dowolnych strzałek i .


Wkrótce wykażemy, że jeśli funktor ma lewe sprzężenie (tzn. istnieje funktor taki, że ), to jest jedyny z dokładnością do izomorfizmu (tzn. ). Istnienie lewego lub prawego sprzężenia jest często ciekawym problemem matematycznym i jeśli da się udowodnić, sam dowód jest pożyteczną konstrukcją. Nie ma potrzeby dłużej strzępić języka, zobaczmy przykłady.


  • Wolne funktory są lewymi sprzężeniami do funktorów zapominania. Np. jeśli jest grupą, zaś jest zbiorem, to funkcje są w bijekcji z homomorfizmami typu , gdzie jest wolną grupą nad . A zatem , gdzie jest funktorem zapominania, zaś jest funktorem tworzącym wolną grupę nad . Inny przykład tego typu znajduje się w Zadaniu 9.1.


Uwaga
Problem istnienia lewego sprzężenia do funktora zapominania jest w zasadzie pytaniem o to, jak w sposób jednorodny zadać strukturę wymaganą przez na obiektach i strzałkach . Pytania o lewe sprzężenie są więc pytaniami typu: w jaki sposób na dowolnym zbiorze zadać topologię? Czy dla dowolnego zbioru da się znaleźć działanie grupowe tak, by elementy tego zbioru były elementami powstałej grupy? Czy każda przestrzeń metryczna da się rozszerzyć do przestrzeni zupełnej? I tak dalej. Niezwykle interesującą klasą kategorii, które posiadają lewe sprzężenie do funktora zapominania z kodziedziną w są tzw. kategorie algebraiczne. Mówimy o nich więcej w Wykładzie 15.


  • Przypuśćmy, że jest kategorią kartezjańsko zamkniętą. Niech . Wówczas funktor:

jest lewym sprzężeniem funktora (przypomnijmy sobie definicje pierwszego z tych funktorów podaną w Zadaniu 4.1 - definicja drugiego jest oczywista po przeczytaniu Zadania 3.6), co oznacza, że istnieje naturalna bijekcja pomiędzy morfizmami typu i morfizmami typu (dla ).

  • Jeśli są dowolnymi kategoriami, to funktor diagonalny jest lewym sprzężeniem do funktora . Rzeczywiście, wprost z Zadania 8.1, obiekt jest granicą diagramu wtedy i tylko wtedy, gdy istnieje naturalny izomorfizm:

A zatem . Szczególne przypadki tego sprzężenia omówimy w Zadaniach 9.2, 9.3.

  • Dla posetów para funkcji monotonicznych , jest sprzężeniem wtedy i tylko wtedy, gdy

Na przykład, inkluzja posiada lewe sprzężenie, które powszechnie nazywa się funkcją sufit }:

Parser nie mógł rozpoznać (błąd składni): {\displaystyle \lceil x\rceil := \mathrm{najmniejsza\ liczba\ całkowita} \geq x.}

Rzeczywiście, równoważność definiująca sprzężenie:

zachodzi wtedy i tylko wtedy, gdy jest najmniejszą liczbą całkowitą większą bądź równą .

  • Dualność Stone'a (patrz Ćwiczenia do Wykładu 6.). Twierdzenie Stone'a jest jednym z najważniejszych wyników matematyki XX wieku. W ograniczonym brzmieniu (tj. dualność między algebrami Boole'a a przestrzeniami Stone'a) udowodnione przez Marshalla Stone'a w 1939 roku, twierdzenie to po raz pierwszy jednoznacznie potwierdziło użyteczność metod topologii ogólnej w algebrze i dało początek topologii algebraicznej. Wspaniałe omówienie roli dualności Stone'a znajduje się w książce Stone Spaces P.T.Johnstone'a (Cambridge University Press, 1982).


Wracając do głównego wątku wykładu, zanalizujmy głębiej strukturę sprzężenia. Przy ustalonych oznaczeniach z Definicji 9.2 (pominiemy też wszelkie zbędne nawiasy) zauważmy, że jeśli przyjmiemy , to . Możemy więc położyć dla każdego morfizm typu :

Sama operacja , która obiektowi przypisuje strzałkę jest transformacją naturalną typu , ponieważ każdy diagram:

Tk-9.3.png

komutuje. Rzeczywiście,

gdzie dwukrotnie wykorzystaliśmy naturalność . Transformację nazywamy jednością sprzężenia .

Pokażemy teraz, że bijekcja może być całkowicie odtworzona za pomocą , to znaczy, że kolekcja komponentów wystarcza do zrekonstruowania bijekcji . Niech . Wówczas . Warto zapamiętać:

     (9.1)


Dualnie, jeśli przyjmiemy w Definicji 9.2, że , to możemy zdefiniować dla każdego strzałkę :

Transformację naturalną nazywamy kojednością sprzężenia . Mając na uwadze, że oraz dla dowolnej mamy:

     (9.2)

co oznacza, że kojedność wystarcza do odtworzenia , a co za tym idzie, .

W końcu, zauważmy, że:

i podobnie:

Pokazaliśmy najważniejsze kroki następującego twierdzenia:


Twierdzenie 9.3

Następujące warunki są równoważne:
  • ,
  • Istnieją dwie transformacje naturalne i takie, że następujące diagramy trójkątne komutują:
Tk-9.4.png


Uwaga
aby w pełni zrozumieć treść powyższego twierdzenia, należy zauważyć, że transformacje naturalne można złożyć z funktorami (i to na dwa sposoby). Na przykład, jest transformacją naturalną będącą złożeniem transformacji i funktora . To złożenie definiujemy przez komponenty jako ; podobnie jest transformacją naturalną daną przez komponenty . I tak dalej. Uważny czytelnik powinien udowodnić, że złożenia, które tu opisujemy są rzeczywiście transformacjami naturalnymi.

Przejdźmy do ostatniej charakteryzacji sprzężenia, które uwypukla uniwersalny charakter jedności sprzężenia. Przypomnijmy sobie definicję elementu uniwersalnego dla funktora reprezentowalnego (Definicja 7.4): element jest uniwersalny jeśli dla każdego obiektu i elementu istnieje dokładnie jedna funkcja taka, że . Ale może być traktowany jako strzałka w ( jest dowolnym singletonem - obiektem końcowym ), Definicja elementu uniwersalnego może być więc uogólniona i postawiona dla funktorów dowolnego typu:


Definicja 9.4

Niech będzie funktorem i niech . Strzałką uniwersalną z do jest para składająca się z obiektu i strzałki taka, że dla dowolnego obiektu i strzałki istnieje dokładnie jedna strzałka spełniająca .
Tk-9.5.png

Innymi słowy: każda strzałka faktoryzuje się przez .

Jak się okazuje, sprzężenie jest w pełni scharakteryzowane przez fakt, że jedność jest strzałką uniwersalną z do (przy oznaczeniach Definicji 9.2).


Twierdzenie 9.5

Następujące warunki są równoważne:
  • jest transformacją naturalną taką, że dla każdego , jest strzałką uniwersalną z do .

Dowód

Strzałka jest uniwersalna wtedy i tylko wtedy, gdy dla dowolnego morfizmu istnieje dokładnie jeden morfizm tak, że następujący diagram komutuje:
Tk-9.6.png
Ale to oznacza, że jest bijekcją pomiędzy i . Ta bijekcja jest naturalna względem , bo jest naturalna; jest naturalna względem , bo jest funktorem. To dowodzi . End of proof.gif

Uwaga: Powyższe twierdzenie jest jednym z najpopularniejszych sposobów prezentowania sprzężenia. Śmiało możemy więc ująć je jako definicję:


Definicja 9.6 [Sprzężenie II]

Dla i mamy wtedy tylko wtedy, gdy dla każdego istnieje strzałka taka, że: dla dowolnego morfizmu istnieje dokładnie jeden morfizm tak, że następujący diagram komutuje:
Tk-9.6.png

Oto dalsze przykłady sprzężeń:

  • Funktor (patrz Przykład 5.3) jest lewym sprzężeniem do funktora zapominania (bo jest funktorem wolnym). Dla zbioru jedność sprzężenia jest funkcją , czyli przekształca elementy na listy jednoelementowe. W tym przykładzie, dla funkcji , jedyną funkcją (oznaczoną ), która sprawia, że diagram:
Tk-9.7.png

komutuje, jest funkcja przypisująca liście jej długość.

  • Niech oznacza kategorię przestrzeni metrycznych i funkcji niepowiększających odległości, zaś - kategorię przestrzeni metrycznych zupełnych, z takimi samymi morfizmami. Wówczas dla funktora zapominania istnieje lewe sprzężenie, które każdej przestrzeni metrycznej przypisuje jej uzupełnienie. Jednością tego sprzężenia jest rodzina odwzorowań, które elementowi przestrzeni metrycznej przypisują stały ciąg Cauchy'ego .


W Ćwiczeniach do tego wykładu omówimy szczegółowo zarówno przykłady, które już się pojawiły, jak i całkiem nowe, często być może zaskakujące Czytelnika sytuacje, których ukrytym mechanizmem jest sprzężenie.