Teoria kategorii dla informatyków/Wykład 10: Sprzężenia II

Z Studia Informatyczne
Przejdź do nawigacjiPrzejdź do wyszukiwania


Wstęp

Ten wykład poświęcamy związkom między sprzężeniami a równoważnością kategorii oraz problemowi istnienia sprzężeń, która wiąże się z ich najważniejszą własnością: zachowywaniem odpowiednich granic.

Sprzężenia a równoważność

W świetle Twierdzenia 9.3 i definicji równoważności widzimy, że jeśli jedność i kojedność sprzężenia są izomorfizmami, to tworzą równoważność. Z drugiej strony, jeśli i są równoważnością, to naturalny izomorfizm daje dla każdej strzałki przemienny diagram:

Tk-10.1.png

co oznacza . Dla dowolnych mamy:


a zatem jest funktorem wiernym. Z symetrii założeń wynika, że jest również wierny. Aby pokazać, że jest pełny, weźmy dowolną strzałkę . Połóżmy , co oznacza, że:

Tk-10.2K.png

komutuje. A zatem:

Skoro jest wierny, , co dowodzi, że jest pełny. Pokazaliśmy, że jest pełny i wierny, a zatem morfizmy typu w są w bijekcji z morfizmami typu w , czyli po złożeniu z izomorfizmem , w odpowiedniości 1-1 z morfizmami typu . To znaczy, że . Z symetrii założeń wynika . Udowodniliśmy następujące:


Twierdzenie 10.1 [Sprzężenia a równoważność]

Jeśli są równoważnością, to i .


Z dowodu powyższego twierdzenia wynika wniosek, że funktory pełne i wierne (na przykład te pochodzące z równoważności kategorii) są ze sobą sprzężone. Poniżej scharakteryzujemy prawe sprzężenia ze względu na pełność i wierność.


Twierdzenie 10.2 [wierność i pełność prawego sprzężenia]

Załóżmy, że dla i . Wówczas:
  • jest wierny wtedy i tylko wtedy, gdy dla dowolnego komponent kojedności jest epimorfizmem w .
  • jest pełny i wierny wtedy i tylko wtedy, gdy kojedność jest izomorfizmem.

Dowód

Zauważmy najpierw, że dowolny morfizm w dowolnej kategorii lokalnie małej jest epimorfizmem (izomorfizmem) wtedy i tylko wtedy, gdy dla dowolnego funkcja jest injekcją (bijekcją) w .

Przechodząc do właściwego dowodu, dla , mamy złożenie:

A zatem jest wierny (wierny i pełny) wtedy i tylko wtedy, gdy jest injekcją (bijekcją), co zachodzi dokładnie wtedy, gdy jest injekcją (bijekcją), co zgodnie z uwagą na początku dowodu jest równoważne warunkowi, że dla dowolnego jest epimorfizmem (izomorfizmem). To kończy dowód (prowadzony równolegle dla obu własności). End of proof.gif

Istnienie sprzężeń

Spróbujemy teraz odpowiedzieć sobie na ważne pytanie: kiedy dany funktor ma sprzężenie. Warunkiem koniecznym okazuje się następująca własność, którą można rozumieć tak, że prawych sprzężeń należy poszukiwać wśród funktorów zachowujących granice (dualnie: lewe funktory znajdują się wśród funktorów zachowujących kogranice).


Twierdzenie 10.3 [PZG, LZK]

Prawe sprzężenia zachowują granice (PZG). Dualnie: lewe sprzężenia zachowują kogranice (LZK).

Dowód

Niech będzie sprzężeniem między i . Niech będzie diagramem, który posiada w granicę . Wówczas dla dowolnego obiektu mamy:
(Wykorzystaliśmy fakt, że hom-funktory zachowują granice, patrz Zadanie 8.4.) Wszystkie powyższe izomorfizmy są naturalne, a zatem lemat Yonedy implikuje, że . Dualnie, . End of proof.gif

Powyższy dowód również bardzo łatwo wyrazić elementarnie w języku stożków i granic, bez użycia lematu Yonedy, patrz Zadanie 10.3.

Okazuje się, że w wielu przypadkach warunek konieczny: zachowywanie granic przez funktor, wystarczy do tego, by istniało sprzężenie. Dobrym przykładem są tutaj kraty zupełne (kategoryjnie: częściowe porządki, w których istnieją wszystkie suprema, a co za tym idzie - wszystkie infima) - patrz Zadanie 10.4. W związku z tym, należy przypuszczać, że zachowywanie granic jest istotnym elementem warunku wystarczającego do istnienia sprzężenia. Tak jest w istocie. Poniższe twierdzenie pochodzi od prof. Petera Freyda.


Twierdzenie 10.4 [twierdzenie Freyda]

Niech będzie kategorią zupełną i lokalnie małą. Dla dowolnej kategorii i funktora następujące warunki są równoważne:
  • ma lewe sprzężenie;
  • zachowuje granice oraz dla każdego obiektu funktor spełnia następujący warunek: (Istnienie zbioru rozwiązań) Istnieje zbiór obiektów w kategorii taki, że dla dowolnego obiektu oraz strzałki istnieje oraz strzałki , takie, że .


Uwaga
  • warunek istnienia zbioru rozwiązań mówi po prostu, że każda strzałka faktoryzuje się przez jakiś obiekt ze zbioru rozwiązań, jak na diagramie:
Tk-10.5.png
  • Jeśli jest kategorią małą i zupełną, to jest preporządkiem - patrz Zadanie 8.2, a więc warunek istnienia zbioru rozwiązań można całkiem pominąć - Zadanie 10.4.
  • Jeśli nie jest lokalnie mała, to twierdzenie Freyda nic nam nie mówi o istnieniu sprzężeń.

Dowód

Krok : Szczególnie prostą postać warunku istnienia zbioru rozwiązań dla lokalnie małej i zupełnej kategorii można wyrazić następująco: istnieje zbiór obiektów taki, że dla dowolnego obiektu istnieje strzałka dla pewnego . Ten warunek jest równoważny istnieniu obiektu początkowego w kategorii , co udowodnimy w Zadaniu 10.5. Krok : Zaczynamy właściwy dowód twierdzenia: jeśli ma lewe sprzężenie , to oczywiście jest zbiorem rozwiązań dla , ponieważ zawsze mamy:
Tk-10.8.png

dla jedności sprzężenia i obrazu strzałki przez sprzężenie.

Odwrotnie, aby dla stworzyć lewe sprzężenie, rozważmy następującą kategorię , której obiektami są pary , gdzie , zaś strzałkami są strzałki takie, że :

Tk-10.9.png

Wtedy ma lewe sprzężenie wtedy i tylko wtedy, gdy dla każdego kategoria ma obiekt początkowy . Pozostaje zatem: Krok : sprawdzimy, czy spełnia warunek zbioru rozwiązań Kroku . Założenia twierdzenia implikują, że istnieje zbiór par taki, że dla dowolnego istnieje strzałka tak, że:

Tk-10.5.png
Ponieważ jest zarówno lokalnie mała (bo jest) i zupełna (z tego samego powodu), więc założenia Kroku implikują, że ma obiekt początkowy. To kończy dowód twierdzenia. End of proof.gif


Problemem, który pozostaje do wyjaśnienia, jest jeszcze pytanie o to, w jakich okolicznościach istnienie zbioru rozwiązań jest automatycznie spełnione. Widzieliśmy bowiem, że w przypadku (pre)porządków zachowywanie granic było dla funktora równoważne istnieniu lewego sprzężenia. O tej szczególnej sytuacji mówi drugie twierdzenie Freyda, którego nie będziemy dowodzić. Drugie twierdzenie Freyda mówi pokrótce tyle, że warunek istnienia zbioru rozwiązań jest automatycznie spełniony, gdy (lokalnie mała i zupełna):

  • posiada wystarczająco dużo obiektów potęgowych (ang. is well-powered) (nie wchodząc w szczegóły znaczy to, że dla każdego obiektu kolekcja podobiektów jest zbiorem;
  • posiada zbiór kogeneratorów, tzn. zbiór obiektów , które separują uogólnione elementy, tzn. dla każdych dwóch równoległych strzałek w , jeśli , to istnieje tak, że .

W takiej kategorii - podkreślmy to raz jeszcze - funktor zachowuje granicę wtedy i tylko wtedy, gdy posiada lewe sprzężenie .

Oto zaawansowany przykład sytuacji, gdy działa drugie twierdzenie Freyda: funktor zapominania z kategorii zwartych przestrzeni Hausdorffa do kategorii przestrzeni topologicznych posiada lewe sprzężenie . Dla przestrzeni , obiekt jest znany jako uzwarcenie Cecha - Stone'a. Jednym ze sposobów tworzenia jest podążanie krok w krok za dowodem twierdzenia Freyda, gdyż przestrzeń zanurza się najpierw w odpowiedni produkt kopii , a potem bierze domknięcie obrazu zanurzenia, które jest szukanym uzwarceniem .

I na koniec ciekawy kontrprzykład: niech oznacza kategorię zupełnych algebr Boole'a (tj. takich algebr Boole'a, które są kratami zupełnymi). Funktor zapominania zachowuje wszystkie granice. Jednakże warunek istnienia zbioru rozwiązań nie jest spełniony ze względu na następujące twierdzenie:


Twierdzenie 10.5

Istnieje przeliczalnie generowana zupełna algebra Boole'a o dowolnie dużej mocy.


Wniosek: nie posiada lewego sprzężenia, co oznacza w szczególności, że nie istnieje wolna algebra Boole'a posiadająca generatorów.

Sprzężenia między częściowymi porządkami

Sprzężenia między częściowymi porządkami, których liczne przykłady poznaliśmy w Ćwiczeniach do Wykładu 9., mają bardzo przyjemne własności. Warto przyjrzeć się tej sytuacji lepiej i nieco na przekór trendowi naszego wykładu: chcemy bowiem zbadać, jak własności kategoryjne porządków przekładają się na język teorii mnogości, a nie odwrotnie. Powtórzmy konieczne definicje tak, aby ten rozdział można było czytać niezależnie od pozostałych. Zwróćmy też uwagę, że pary e-p, o których mówiliśmy w Wykładzie 2. są szczególnym przypadkiem sprzężeń między posetami.


Definicja 10.6 [sprzężenia na częściowych porządkach]

Niech będą częściowymi porządkami. Powiemy, że para funkcji i jest sprzężeniem, jeśli: obie funkcje są monotoniczne oraz dla każdej pary elementów mamy:
Funkcję nazywamy lewym sprzężeniem, zaś funkcję - prawym sprzężeniem.


Fakt 10.7

Niech i będą funkcjami między częściowymi porządkami. Wówczas następujące warunki są równoważne:
  • ;
  • jest monotoniczna oraz dla każdego ;
  • jest monotoniczna oraz dla każdego .
W konsekwencji, każda z funkcji biorących udział w sprzężeniu determinuje drugą.


Z twierdzenia Freyda i Zadania 10.4 wynika natychmiast:


Fakt 10.8

  • Niech będzie funkcją między posetami, z których jest kratą zupełną. Wtedy zachowuje infima wtedy i tylko wtedy, gdy ma lewe sprzężenie.
  • Niech będzie funkcją między posetami, z których jest kratą zupełną. Wtedy zachowuje suprema wtedy i tylko wtedy, gdy ma prawe sprzężenie.


Zaobserwujmy doskonałą dualność powyższego sformułowania.


Twierdzenie 9.3 tłumaczy się na język częściowych porządków następująco (nieco je tu wzbogacamy); dowód znajdziemy w Zadaniu 10.7.


Fakt 10.9

Następujące warunki są równoważne:
  • ;
  • oraz .

Każdy z tych warunków implikuje, że:

  • oraz ;
  • i są idempotentne (funkcja jest idempotentna jeśli ).


Na samym końcu scharakteryzujemy te sprzężenia, które są sekcjami (retrakcjami), by w ten sposób nawiązać do samych początków naszego spotkania z teorią kategorii, do Wykładu 2.


Fakt 10.10

Dla sprzężenia następujące warunki są równoważne:
  • jest surjekcją;
  • dla każdego ;
  • ;
  • jest injekcją.

Dualnie, mamy następujące warunki równoważne:

  • jest injekcją;
  • dla każdego ;
  • ;
  • jest surjekcją.