Teoria kategorii dla informatyków/Wykład 6: Równoważność kategorii

Z Studia Informatyczne
Przejdź do nawigacjiPrzejdź do wyszukiwania

W trakcie naszych wykładów stało się jasne, że równość obiektów w danej kategorii jest własnością bez znaczenia - najważniejsze pojęcia zostały zdefiniowane z dokładnością do izomorfizmu. W szczególnym przypadku przypomnijmy, że dwie kategorie i są izomorficzne, jeśli istnieją funktory i takie, że i . Te dwie równości zgodnie z naszym dezyderatem: równość jest własnością bez znaczenia, po zastąpieniu przez izomorfizmy dają następującą ważną definicję:


Definicja równoważności i podstawowe własności

Definicja 6.1 [kategorie równoważne]

Mówimy, że dwie kategorie i są równoważne, jeśli istnieją funktory i takie, że i .


Równoważność i oznacza zatem, że istnieją dwie transformacje naturalne i , których komponentami są izomorfizmy.

Oto prosty przykład równoważności: niech będzie preporządkiem, zaś porządkiem ilorazowym utworzonym z przez podzielenie przez relację równoważności dla i niech będzie funkcją ilorazową. Wówczas jest funktorem ustanawiającym równoważność i , ale w ogólności nie jest to izomorfizm.


Definicja 6.2 [kategorie dualne]

Równoważność między kategoriami i (lub: i ) nazywamy dualnością.


Przykładem jest tutaj dualność Stone'a, której poświęcamy Ćwiczenia do tego wykładu.

Czasami sam funktor, który bierze udział w równoważności nazywamy równoważnością. Poczyńmy kilka prostych obserwacji: jeśli jest równoważnością, to istnieje taki, że i , a zatem jest również równoważnością. Równie łatwo pokazać, że złożenie dwóch równoważności jest równoważnością.

Poznajmy teraz podstawową własność równoważności:


Twierdzenie 6.3 [Własności równoważności]

Następujące dwa warunki są równoważne dla funktora :
  • jest równoważnością;
  • jest pełny i wierny oraz gęsty ze względu na izomorfizmy (tzn. dla dowolnego istnieje taki, że ).

Dowód

Załóżmy najpierw, że jest równoważnością. Istnieją zatem: funktor oraz naturalne izomorfizmy i wraz ze swoimi odwrotnościami i .

Pokażmy najpierw, że jest funktorem wiernym. Niech i . A zatem . Z naturalności wynika, że , a więc:

Symetryczny dowód pokazuje, że również jest funktorem wiernym - ten fakt przyda się nam za chwilę.

Pokażmy pełność . Niech będzie morfizmem w . Zdefiniujmy morfizm w jako: . Wtedy jest tego samego typu co oraz:

Ponieważ jest wierny, , co dowodzi pełności .

W końcu dla dowolnego izmorfizm daje natychmiast , gdzie , co dowodzi, że jest gęsty ze względu na izomorfizmy.

Odwrotnie, załóżmy, że pewien funktor posiada wszystkie cechy drugiego punktu twierdzenia. Wykażemy, że jest równoważnością. To zadanie polega na skonstruowaniu funktora i dwóch naturalnych izomorfizmów, tak jak wymaga tego od nas definicja równoważności. Skoro jest gęsty ze względu na izomorfizmy, dla każdego obiektu otrzymujemy taki, że . Ta informacja wystarcza, by skonstruować funktor na obiektach: . Izomorfizm oznaczymy jako . Strzałki tworzą komponenty pewnego izomorfizmu, który - jak zaraz wykażemy - jest naturalny. Mając dany morfizm w , rozważmy diagram:

Tk-6.1.png

Ale skoro jest pełny i wierny, możemy znaleźć dla dokładnie jedną strzałkę taką, że . Tak zdefiniowany na strzałkach jest funktorem, a jest naturalnym izomorfizmem.

Pozostaje nam znalezienie , najłatwiej przez zaproponowanie komponentów dla . Przyjmiemy jako jedyną strzałkę, która jest w przeciwobrazie przez (możemy mówić o przeciwobrazie, bo jest pełny i wierny) strzałki . Oczywiście jest izomorfizmem, bo pełne i wierne funktory odzwierciedlają izomorfizmy. Naturalność wynika wprost z naturalności .

End of proof.gif


Przykłady równoważności

  • Każdy izomorfizm między kategoriami jest równoważnością, tzn. kategorie izomorficzne są równoważne.
  • Częściowe porządki są równoważne wtedy i tylko wtedy, gdy są izomorficzne (bo izomorfizmy na przestrzeni funkcji monotonicznych redukują się do równości). Z drugiej strony, preporządki, jak już widzieliśmy powyżej mogą być równoważne i nie być izomorficzne.
  • Wiemy z teorii mnogości, że każdy zbiór skończony jest izomorficzny ze swoją liczbą kardynalną, , która jest liczbą jego elementów. Oznaczmy ten izomorfizm jako . Mając dwa dowolne zbiory skończone i funkcję , definiujemy jako . Oczywiście wtedy jest funktorem. Z drugiej strony niech oznacza naturalną inkluzję skończonych liczb kardynalnych w skończone zbiory (istnienie wyraża fakt, że każda liczba kardynalna sama jest zbiorem). Złożenie jest funktorem na . Jest on izomorficzny z identycznością , ponieważ istnieje naturalny izomorfizm dany przez komponenty jako . Z drugiej strony, , a zatem kategorie i są równoważne. Oczywiście nie są izomorficzne, bo istnienie takiego izomorfizmu pociągnęłoby za sobą istnienie bijekcji pomiędzy zbiorami skończonymi i liczbami naturalnymi, a ta - jak wiemy - nie istnieje.
  • Niech będzie kategorią częściowych porządków i częściowych funkcji monotonicznych. Przypomnijmy, że funkcja jest częściowa, jeśli jest określona tylko na (być może właściwym) podzbiorze swojej dziedziny, . Na zbiorze funkcja pozostaje nieokreślona. Funkcję częściową z do będziemy dalej oznaczać jako . Te spośród funkcji częściowych, które są określone na całej swojej dziedzinie nazywamy funkcjami totalnymi. Oczywiście jest kategorią, w której złożenie i definiujemy jako funkcję częściową oznaczaną zdefiniowaną na . Czytelnik zechce sprawdzić, że to złożenie jest łączne i że identyczności spełniają względem złożenia swoje aksjomaty.

Drugą kategorią w tym przykładzie jest , czyli kategoria częściowych porządków posiadających elementy najmniejsze wraz z funkcjami monotonicznymi zachowującymi elementy najmniejsze. Udowodnimy, że i są kategoriami równoważnymi.

Funktor definiujemy na obiektach jako dodatnie do posetu nowego elementu najmniejszego:

Dla prostoty oznaczymy jako , tzn. . Na strzałkach ten funktor działa jako:

gdzie:

Oczywiście , więc definicja funktora jest poprawnie postawiona.

Funktor przeciwnie zwrócony definiujemy na obiektach odejmując element najmniejszy:

zaś na strzałkach: dla

jest funkcją częściową zdefiniowaną na podzbiorze zbioru


Przy tych definicjach jest identycznością na . Tymczasem jest jedynie naturalnie izomorficzny z , gdyż:

(w ogólności ). Sprawdzenie faktu, że ten izomorfizm jest naturalny i , są funktorami jest łatwym ćwiczeniem dla Czytelnika, które polecamy wykonać w pamięci.

  • Kategoria przestrzeni metrycznych i funkcji ciągłych jest równoważna kategorii przestrzeni topologicznych metryzowalnych i funkcji ciągłych. Te dwie kategorie nie są jednak izmomorficzne (nieformalnie wynika to z faktu, że dana topologia na zbiorze może pochodzić od wielu różnych metryk równoważnych).
  • jest równoważna z kategorią zupełnych atomowych algebr Boole'a (dla dociekliwych: i zupełne algebry Boole'a są zaledwie sprzężone: ). Ten przykład i następny podrozdział są szczególnymi przypadkami całej serii tzw. dualności Stone'a, które określają równoważność pomiędzy kratami i topologiami odpowiednich typów. W Ćwiczeniach do tego wykładu poznamy najogólniejszą z dualności Stone'a, czyli dualność pomiędzy przestrzennymi ramami(ang. spatial frames) i przestrzeniami realnymi (ang. sober spaces).


Dualność zbiorów skończonych i skończonych algebr Boole'a

Oznaczmy kategorię skończonych algebr Boole'a (o algebrach Boole'a mówiliśmy już w Wykładzie 4. w tym podrozdziale) i homomorfizmów tych algebr (homomorfizmy to te funkcje na zbiorach podkładowych, które zachowują operacje algebry) przez . Takie algebry są zawsze atomowe, tzn. generowane za pomocą operacji algebry ze zbioru atomów. Jeśli , to jej zbiór atomów definiujemy jako:


Rozpocznijmy konstrukcję od przypomnienia podstawowych definicji teorii porządku (które są rozszerzone i uzupełnione w Wykładzie 12. Odsyłamy tam Czytelnika w przypadku, gdyby spotkał nieznane sobie oznaczenia).


Definicja 6.4 [filtr, ultrafiltr]

Filtrem w kracie nazywamy podzbiór taki, że:

  • implikuje
  • , co oznacza dokładnie tyle, że i razem implikują .

Filtr, który jest właściwym podzbiorem kraty nazywamy filtrem właściwym. Filtr właściwy, który jest maksymalny w sensie inkluzji w kracie nazywamy ultrafiltrem. Można łatwo przekonać się, że filtr jest ultrafiltrem wtedy i tylko wtedy, gdy dla dowolnego albo , albo .


Zaobserwujmy, że jeśli posiada element najmniejszy , to każdy filtr, który go zawiera jest całym zbiorem i w związku z tym jest filtrem niewłaściwym. Zauważmy też, że każdy filtr w algebrze Boole'a zawiera element największy .

Ideałem w kracie nazywamy każdy filtr w . Czy dopełnienie filtru w może być ideałem? Tak. Ten szczególny przypadek da się przyjemnie opisać:


Stwierdzenie 6.5 [Filtr pierwszy]

W dowolnej kracie dla następujące warunki są równoważne:
  1. jest filtrem i jest ideałem;
  2. jest filtrem właściwym i jeśli , to lub ;
  3. dla pewnego homomorfizmu krat .


Filtr spełniający dowolny z powyższych warunków nazywamy filtrem pierwszym.

Uwaga
jest kratą dwuelementową . Warunek trzeci oznacza dokładnie tyle, że zachowuje dowolne suprema i dowolne infima w kracie .

Dowód

Załóżmy, jest ideałem. Wówczas jest zbiorem dolnym, co pociąga . Dlatego też . Jeśli i , to skoro jest ideałem, dostajemy , czyli .

Załóżmy teraz warunek (2). Zdefiniujmy jako

Wtedy oraz zachowuje i , bo jest filtrem i zachowuje i ze względu na założenia z (2).

W końcu, niech będzie homomorfizmem. Wówczas jest filtrem, a odwzorowuje filtry w filtry. Podobnie, jest ideałem, zaś posyła ideały w ideały.

End of proof.gif


W kratach zupełnych istnieją ciekawe odpowiedniki filtrów pierwszych, tak zwane filtry zupełnie pierwsze.


Definicja 6.6 [filtr zupełnie pierwszy]

Niech będzie kratą zupełną. Filtr jest zupełnie pierwszy, jeśli dla dowolnego podzbioru , z faktu, że wynika .


Jeśli jest przestrzenią topologiczną, zaś jest kratą zupełną zbiorów otwartych z uporządkowanych względem inkluzji, to dla dowolnego zbiór otoczeń otwartych :

jest filtrem zupełnie pierwszym w .

W kratach dystrybutywnych (np. w algebrach Boole'a) zachodzi:


Stwierdzenie 6.7 [filtry pierwsze w kracie dystrybutywnej]

Niech będzie ideałem w kracie dystrybutywnej . Jeśli jest maksymalnym filtrem, który jest rozłączny z , to jest pierwszy.

Dowód

Ponieważ , to jest właściwy. Niech i . Zbiory:

są filtrami zawierającymi w sposób właściwy , które - ze względu na maksymalność - muszą przecinać się z . Wybierzmy zatem i . skoro jest ideałem . Dystrybutywność daje nam po kilku przekształceniach: dla pewnego . Ponieważ i są rozłączne, implikowałoby , czyli , sprzeczność. A zatem: . To kończy dowód.

End of proof.gif


Warto też dodać, że lemat Zorna implikuje, że w dowolnej kracie, jeśli mamy filtr i ideał takie, że , to istnieje maksymalny filtr rozłączny z . Oczywiście na mocy poprzedniego Stwierdzenia, tenże jest filtrem pierwszym.

Cała nasza dyskusja pierwszości zmierzała do tego, by scharakteryzować ultrafiltry w algebrach Boole'a. Oto ten wynik:


Twierdzenie 6.8 [ultrafiltry w algebrach Boole'a]

Dla filtra w algebrze Boole'a następujące warunki są równoważne:
  1. jest ultrafiltrem;
  2. jest pierwszy;
  3. Dla dowolnego , wtedy i tylko wtedy, gdy dla dowolnego ;
  4. Dla dowolnego albo , albo .

Dowód

Załóżmy (1). Ponieważ jest ideałem, (2) wynika ze Stwierdzenia 6.7. Załóżmy (2). Niech i załóżmy, że . Wtedy najmniejszy filtr zawierający i musi być całą kratą . To znaczy, że dla pewnego . Odwrotnie, przypuśćmy że . Ponieważ jest właściwy, dla każdego . Załóżmy teraz (3). Ponieważ każdy ultrafiltr jest pierwszy i dla dowolnego , , dostajemy (4). W końcu, zakładając (4), jeśli , to , więc nie istnieje filtr właściwy zawierający i . A zatem jest maksymalnym filtrem właściwym w kracie . End of proof.gif


W przypadku skończonej algebry Boole'a, łatwo pokazać, że zbiór jej atomów jest w bijekcji z ultrafiltrami.


Lemat 6.9 [atomy w skończonej algebrze Boole'a]

W dowolnej skończonej algebrze Boole'a istnieje izomorfizm między atomami i ultrafiltrami na .

Dowód

jeśli jest atomem, to jest ultrafiltrem, bo dla dowolnego albo i wtedy , albo , czyli , więc . Odwrotnie, jeśli jest ultrafiltrem na , to jest atomem. Łatwo przekonać się, że oraz jest trywialne, że . End of proof.gif


Aby pokazać teraz równoważność i , zdefiniujemy odpowiednie funktory. Z jednej strony, mamy kontrawariantny funktor potęgowy . Z drugiej strony, pokażemy, że operacja , której działanie znamy na obiektach, da się rozszerzyć do funktora. Ale tak jest dzięki Lematowi 6.9. Jeśli jest homomorfizmem algebr Boole'a, to dla zbiór jest ultrafiltrem na . Definiujemy zatem:

Uważny Czytelnik zwrócił uwagę, że typ , którym jest , jest tym samym co typ .

Wraz z funktorami i dostajemy też dwie transformacje naturalne. Pierwsza, jest dana na komponentach jak następuje: niech będzie zbiorem skończonym. Atomami są singletony, więc jest izomorfizmem. Drugą transformację określamy na komponencie jako:

i również jest izomorfizmem (dowód jest łatwy i pozostawiamy go do zrobienia w pamięci).