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

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 $\mathbf{𝐂}$ i $\mathbf{𝐃}$ są izomorficzne, jeśli istnieją funktory $F:\mathbf{𝐂}\to \mathbf{𝐃}$ i $G:\mathbf{𝐃}\to \mathbf{𝐂}$ takie, że $F\circ G=1_{\mathbf{𝐃}}$ i $G\circ F=1_{\mathbf{𝐂}}$. 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 $\mathbf{𝐂}$ i $\mathbf{𝐃}$ są równoważne, jeśli istnieją funktory $F:\mathbf{𝐂}\to \mathbf{𝐃}$ i $G:\mathbf{𝐃}\to \mathbf{𝐂}$ takie, że $F\circ G\cong 1_{\mathbf{𝐃}}$ i $G\circ F\cong 1_{\mathbf{𝐂}}$.

Równoważność $\mathbf{𝐂}$ i $\mathbf{𝐃}$ oznacza zatem, że istnieją dwie transformacje naturalne $\mu :1_{\mathbf{𝐂}}\to G\circ F$ i $\nu :1_{\mathbf{𝐃}}\to F\circ G$, których komponentami są izomorfizmy.

Oto prosty przykład równoważności: niech $(P,⪯)$ będzie preporządkiem, zaś $Q=P/\equiv$ porządkiem ilorazowym utworzonym z $P$ przez podzielenie przez relację równoważności $x\equiv y⟺(x⪯y\wedge y⪯x)$ dla $x,y\in P$ i $\pi :P\to Q$ niech będzie funkcją ilorazową. Wówczas $\pi$ jest funktorem ustanawiającym równoważność $P$ i $Q$, ale w ogólności nie jest to izomorfizm.

Definicja 6.2 [kategorie dualne]

Równoważność między kategoriami ${\mathbf{𝐂}}^{op}$ i $\mathbf{𝐃}$ (lub: $\mathbf{𝐂}$ i ${\mathbf{𝐃}}^{op}$) 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 $F:\mathbf{𝐂}\to \mathbf{𝐃}$ jest równoważnością, to istnieje $G:\mathbf{𝐃}\to \mathbf{𝐂}$ taki, że $F\circ G\cong 1_{\mathbf{𝐃}}$ i $G\circ F\cong 1_{\mathbf{𝐂}}$, a zatem $G$ 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 $F:\mathbf{𝐂}\to \mathbf{𝐃}$:

• $F$ jest równoważnością;
• $F$ jest pełny i wierny oraz gęsty ze względu na izomorfizmy (tzn. dla dowolnego $D\in {\mathbf{𝐃}}_0$ istnieje $C\in {\mathbf{𝐂}}_0$ taki, że $FC\cong D$).

Dowód

Załóżmy najpierw, że $F$ jest równoważnością. Istnieją zatem: funktor $G:\mathbf{𝐃}\to \mathbf{𝐂}$ oraz naturalne izomorfizmy $\mu :1_{\mathbf{𝐂}}\to GF$ i $\nu :1_{\mathbf{𝐃}}\to FG$ wraz ze swoimi odwrotnościami ${\mu }^{-1}:GF\to 1_{\mathbf{𝐂}}$ i ${\nu }^{-1}:FG\to 1_{\mathbf{𝐃}}$.

Pokażmy najpierw, że $F$ jest funktorem wiernym. Niech $f,g\in {\mathbf{𝐂}}_1$ i $Ff=Fg$. A zatem $GFf=GFg$. Z naturalności $\mu$ wynika, że $f={\mu }_{cod(f)}^{-1}\circ GFf\circ {\mu }_{dom(f)}$, a więc:

$f={\mu }_{cod(f)}^{-1}\circ GFf\circ {\mu }_{dom(f)}={\mu }_{cod(g)}^{-1}\circ GFg\circ {\mu }_{dom(g)}=g$

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

Pokażmy pełność $F$. Niech $h:F(C)\to F(C^{\prime })$ będzie morfizmem w $\mathbf{𝐃}$. Zdefiniujmy morfizm $f:C\to C^{\prime }$ w $\mathbf{𝐂}$ jako: $f:={\mu }_{C^{\prime }}^{-1}\circ Gh\circ {\mu }_C$. Wtedy $Ff$ jest tego samego typu co $h$ oraz:

$GFf={\mu }_{C^{\prime }}\circ f\circ {\mu }_C^{-1}={\mu }_{C^{\prime }}\circ ({\mu }_{C^{\prime }}^{-1}\circ Gh\circ {\mu }_C)\circ {\mu }_C^{-1}=Gh$

Ponieważ $G$ jest wierny, $Ff=h$, co dowodzi pełności $F$.

W końcu dla dowolnego $D\in {\mathbf{𝐃}}_0$ izmorfizm $\nu$ daje natychmiast $D\cong GFD$, gdzie $FD\in {\mathbf{𝐂}}_0$, co dowodzi, że $F$ jest gęsty ze względu na izomorfizmy.

Odwrotnie, załóżmy, że pewien funktor $F:\mathbf{𝐂}\to \mathbf{𝐃}$ posiada wszystkie cechy drugiego punktu twierdzenia. Wykażemy, że jest równoważnością. To zadanie polega na skonstruowaniu funktora $G:\mathbf{𝐃}\to \mathbf{𝐂}$ i dwóch naturalnych izomorfizmów, tak jak wymaga tego od nas definicja równoważności. Skoro $F$ jest gęsty ze względu na izomorfizmy, dla każdego obiektu $D\in {\mathbf{𝐃}}_0$ otrzymujemy $C_D\in {\mathbf{𝐂}}_0$ taki, że $FC\cong D$. Ta informacja wystarcza, by skonstruować funktor $G:\mathbf{𝐃}\to \mathbf{𝐂}$ na obiektach: $G(D):=C_D$. Izomorfizm $FC\stackrel{\cong }{to}D$ oznaczymy jako ${\nu }_D$. Strzałki ${\nu }_D$ tworzą komponenty pewnego izomorfizmu, który - jak zaraz wykażemy - jest naturalny. Mając dany morfizm $h:D\to D^{\prime }$ w $\mathbf{𝐃}$, rozważmy diagram:

Ale skoro $F$ jest pełny i wierny, możemy znaleźć dla $h$ dokładnie jedną strzałkę $G(h):GD\to G{D}^{\prime }$ taką, że $FGh={\nu }_{D^{\prime }}\circ h\circ {\nu }_D^{-1}$. Tak zdefiniowany $G$ na strzałkach jest funktorem, a $\nu$ jest naturalnym izomorfizmem.

Pozostaje nam znalezienie $\mu$, najłatwiej przez zaproponowanie komponentów ${\mu }_C$ dla $C\in {\mathbf{𝐂}}_0$. Przyjmiemy jako ${\mu }_C$ jedyną strzałkę, która jest w przeciwobrazie przez $F$ (możemy mówić o przeciwobrazie, bo $F$ jest pełny i wierny) strzałki ${\nu }_{FC}:FC\to FGFC$. Oczywiście ${\mu }_C$ jest izomorfizmem, bo pełne i wierne funktory odzwierciedlają izomorfizmy. Naturalność $\mu$ wynika wprost z naturalności $\nu$.

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 $X$ jest izomorficzny ze swoją liczbą kardynalną, $|X|$, która jest liczbą jego elementów. Oznaczmy ten izomorfizm jako ${\alpha }_X$. Mając dwa dowolne zbiory skończone i funkcję $f:X\to Y$, definiujemy $|f|:|X|\to |Y|$ jako $|f|:={\alpha }_Y\circ f\circ {\alpha }_X^{-1}$. Oczywiście wtedy $|\cdot |:{\mathbf{𝐒}\mathbf{𝐞}\mathbf{𝐭}}_{fin}\to {\mathbf{𝐂}\mathbf{𝐚}\mathbf{𝐫}\mathbf{𝐝}}_{fin}$ jest funktorem. Z drugiej strony niech $I:{\mathbf{𝐂}\mathbf{𝐚}\mathbf{𝐫}\mathbf{𝐝}}_{fin}\to {\mathbf{𝐒}\mathbf{𝐞}\mathbf{𝐭}}_{fin}$ oznacza naturalną inkluzję skończonych liczb kardynalnych w skończone zbiory (istnienie $I$ wyraża fakt, że każda liczba kardynalna sama jest zbiorem). Złożenie $I\circ |\cdot |$ jest funktorem na ${\mathbf{𝐒}\mathbf{𝐞}\mathbf{𝐭}}_{fin}$. Jest on izomorficzny z identycznością $1_{{\mathbf{𝐒}\mathbf{𝐞}\mathbf{𝐭}}_{fin}}$, ponieważ istnieje naturalny izomorfizm $\beta :1_{{\mathbf{𝐒}\mathbf{𝐞}\mathbf{𝐭}}_{fin}}\to I\circ |\cdot |$ dany przez komponenty jako ${\beta }_Z(z\in Z):={\alpha }_Z(z)$. Z drugiej strony, $|I(-)|=1_{{\mathbf{𝐂}\mathbf{𝐚}\mathbf{𝐫}\mathbf{𝐝}}_{fin}}$, a zatem kategorie ${\mathbf{𝐒}\mathbf{𝐞}\mathbf{𝐭}}_{fin}$ i ${\mathbf{𝐂}\mathbf{𝐚}\mathbf{𝐫}\mathbf{𝐝}}_{fin}$ 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 $\mathbf{𝐏}\mathbf{𝐏}\mathbf{𝐨}\mathbf{𝐬}$ będzie kategorią częściowych porządków i częściowych funkcji monotonicznych. Przypomnijmy, że funkcja $f:P\to Q$ jest częściowa, jeśli jest określona tylko na (być może właściwym) podzbiorze swojej dziedziny, $D_f\subseteq P$. Na zbiorze $P\setminus D_f$ funkcja $f$ pozostaje nieokreślona. Funkcję częściową $f$ z $P$ do $Q$ będziemy dalej oznaczać jako $f\subseteq :P\to Q$. Te spośród funkcji częściowych, które są określone na całej swojej dziedzinie nazywamy funkcjami totalnymi. Oczywiście $\mathbf{𝐏}\mathbf{𝐏}\mathbf{𝐨}\mathbf{𝐬}$ jest kategorią, w której złożenie $f\subseteq :P\to Q$ i $g\subseteq :Q\to R$ definiujemy jako funkcję częściową oznaczaną $g\circ f\subseteq :P\to R$ zdefiniowaną na $D_{g\circ f}:=f^{-1}[D_g]$. 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 ${\mathbf{𝐏}\mathbf{𝐨}\mathbf{𝐬}}_{\mathrm{\perp }}$, czyli kategoria częściowych porządków posiadających elementy najmniejsze wraz z funkcjami monotonicznymi zachowującymi elementy najmniejsze. Udowodnimy, że $\mathbf{𝐏}\mathbf{𝐏}\mathbf{𝐨}\mathbf{𝐬}$ i ${\mathbf{𝐏}\mathbf{𝐨}\mathbf{𝐬}}_{\mathrm{\perp }}$ są kategoriami równoważnymi.

Funktor $F:\mathbf{𝐏}\mathbf{𝐏}\mathbf{𝐨}\mathbf{𝐬}\to {\mathbf{𝐏}\mathbf{𝐨}\mathbf{𝐬}}_{\mathrm{\perp }}$ definiujemy na obiektach jako dodatnie do posetu nowego elementu najmniejszego:

$F((P,\le )):=(P\cup \{{\mathrm{\perp }}_P\},\le \cup \{({\mathrm{\perp }}_P,x)\mid x\in P\})$

Dla prostoty oznaczymy $F$ jako $(-{)}_{\mathrm{\perp }}$, tzn. $F(P)=P_{\mathrm{\perp }}$. Na strzałkach ten funktor działa jako:

$f\subseteq :P\to Q\mapsto f_{\mathrm{\perp }}:P_{\mathrm{\perp }}\to Q_{\mathrm{\perp }}$

gdzie:

$f_{\mathrm{\perp }}(x):=\{\begin{array}{ll}f(x),& x\in D_f\\ \mathrm{\perp },& \text{wpp}\end{array}$

Oczywiście $f_{\mathrm{\perp }}({\mathrm{\perp }}_P)={\mathrm{\perp }}_Q$, więc definicja funktora jest poprawnie postawiona.

Funktor przeciwnie zwrócony $G:{\mathbf{𝐏}\mathbf{𝐨}\mathbf{𝐬}}_{\mathrm{\perp }}\to \mathbf{𝐏}\mathbf{𝐏}\mathbf{𝐨}\mathbf{𝐬}$ definiujemy na obiektach odejmując element najmniejszy:

$G(P_{\mathrm{\perp }}):=P_{\mathrm{\perp }}\setminus \{{\mathrm{\perp }}_P\}$

zaś na strzałkach: dla $f:P_{\mathrm{\perp }}\to Q_{\mathrm{\perp }}$

$G(f)\subseteq P\setminus \{{\mathrm{\perp }}_P\}\to Q\setminus \{{\mathrm{\perp }}_Q\}$

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

$D_{G(f)}:=P\setminus f^{-1}[\{{\mathrm{\perp }}_Q\}]$

Przy tych definicjach $F\circ G$ jest identycznością na $\mathbf{𝐏}\mathbf{𝐏}\mathbf{𝐨}\mathbf{𝐬}$. Tymczasem $G\circ F$ jest jedynie naturalnie izomorficzny z $1_{{\mathbf{𝐏}\mathbf{𝐨}\mathbf{𝐬}}_{\mathrm{\perp }}}$, gdyż:

$P_{\mathrm{\perp }}\cong (P_{\mathrm{\perp }}\setminus \{{\mathrm{\perp }}_P\})\cup \{\mathrm{\perp }{\text{'}}_P\}$

(w ogólności ${\mathrm{\perp }}_P\ne \mathrm{\perp }{\text{'}}_P$). Sprawdzenie faktu, że ten izomorfizm jest naturalny i $F$, $G$ 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).
• ${\mathbf{𝐒}\mathbf{𝐞}\mathbf{𝐭}}^{op}$ jest równoważna z kategorią zupełnych atomowych algebr Boole'a (dla dociekliwych: ${\mathbf{𝐒}\mathbf{𝐞}\mathbf{𝐭}}^{op}$ i zupełne algebry Boole'a są zaledwie sprzężone: ${\mathbf{𝐒}\mathbf{𝐞}\mathbf{𝐭}}^{op}⊣\mathbf{𝐜}\mathbf{𝐁}\mathbf{𝐀}$). 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 ${\mathbf{𝐁}\mathbf{𝐀}}_{fin}$ . Takie algebry są zawsze atomowe, tzn. generowane za pomocą operacji algebry ze zbioru atomów. Jeśli $B\in {\mathbf{𝐁}\mathbf{𝐀}}_{fin}$, to jej zbiór atomów definiujemy jako:

${𝒜}(B):=\{a\in B\mid (\mathbf{𝟎}<a)\wedge (b<a\Rightarrow b=\mathbf{𝟎}\}$

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 $L$ nazywamy podzbiór $U\subseteq B$ taki, że:

• $x,y\in U$ implikuje $x\wedge y\in U$
• $U=\uparrow U$, co oznacza dokładnie tyle, że $x\le y$ i $x\in L$ razem implikują $y\in L$.

Filtr, który jest właściwym podzbiorem kraty $L$ nazywamy filtrem właściwym. Filtr właściwy, który jest maksymalny w sensie inkluzji w kracie $L$ nazywamy ultrafiltrem. Można łatwo przekonać się, że filtr $F\subseteq L$ jest ultrafiltrem wtedy i tylko wtedy, gdy dla dowolnego $x\in L$ albo $x\in F$, albo $\mathrm{\neg }x\in F$.

Zaobserwujmy, że jeśli $L$ posiada element najmniejszy $\mathbf{𝟎}$, to każdy filtr, który go zawiera jest całym zbiorem $L$ 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 $\mathbf{𝟏}$.

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

Stwierdzenie 6.5 [Filtr pierwszy]

W dowolnej kracie $L$ dla $F\subseteq L$ następujące warunki są równoważne:

1. $F$ jest filtrem i $L\setminus F$ jest ideałem;
2. $F$ jest filtrem właściwym i jeśli $a\vee b\in F$, to $a\in F$ lub $b\in F$;
3. $F=h^{-1}[\{1\}]$ dla pewnego homomorfizmu krat $h:L\to \mathbf{𝟐}$.

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

Uwaga

$\mathbf{𝟐}$ jest kratą dwuelementową $\{0\le 1\}$. Warunek trzeci oznacza dokładnie tyle, że $h$ zachowuje dowolne suprema i dowolne infima w kracie $L$.

Dowód

Załóżmy, $L\setminus F$ jest ideałem. Wówczas $L\setminus F$ jest zbiorem dolnym, co pociąga $\mathbf{𝟎}\in L\setminus F$. Dlatego też $\mathbf{𝟎}\notin F$. Jeśli $a\notin F$ i $b\notin F$, to skoro $L\setminus F$ jest ideałem, dostajemy $a\vee b\in L\setminus F$, czyli $a\vee b\notin F$.

Załóżmy teraz warunek (2). Zdefiniujmy $h:L\to \mathbf{𝟐}$ jako

$h(x):=\{\begin{array}{ll}1,& x\in F\\ 0,& x\notin F\end{array}$

Wtedy $h^{-1}[\{1\}]=F$ oraz $h$ zachowuje $\mathbf{𝟏}$ i $\wedge$, bo $F$ jest filtrem i $h$ zachowuje $\mathbf{𝟎}$ i $\vee$ ze względu na założenia z (2).

W końcu, niech $h:L\to \mathbf{𝟐}$ będzie homomorfizmem. Wówczas $\{1\}\subseteq \mathbf{𝟐}$ jest filtrem, a $h^{-1}$ odwzorowuje filtry w filtry. Podobnie, $\{0\}\in \mathbf{𝟐}$ jest ideałem, zaś $h^{-1}$ posyła ideały w ideały.

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

Definicja 6.6 [filtr zupełnie pierwszy]

Niech $L$ będzie kratą zupełną. Filtr $F$ jest zupełnie pierwszy, jeśli dla dowolnego podzbioru $A\subseteq L$, z faktu, że $\bigvee A\in F$ wynika $A\cap F\ne \mathrm{\varnothing }$.

Jeśli $(X,\tau )$ jest przestrzenią topologiczną, zaś $\mathrm{\Omega }(X)$ jest kratą zupełną zbiorów otwartych z $X$ uporządkowanych względem inkluzji, to dla dowolnego $x\in X$ zbiór otoczeń otwartych $x$:

${{𝒩}}^{\circ }(x):=\{U\in \tau \mid x\in U\}$

jest filtrem zupełnie pierwszym w $\mathrm{\Omega }(X)$.

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

Stwierdzenie 6.7 [filtry pierwsze w kracie dystrybutywnej]

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

Dowód

Ponieważ $\mathbf{𝟎}\in I$, to $F$ jest właściwy. Niech $a\notin F$ i $b\notin F$. Zbiory: $F_a:=\{(f\wedge a)\vee z\mid f\in F,z\in L\}$ $F_b:=\{(f\wedge b)\vee z\mid f\in F,z\in L\}$

są filtrami zawierającymi w sposób właściwy $F$, które - ze względu na maksymalność $F$ - muszą przecinać się z $I$. Wybierzmy zatem $c\in F_a\cap I$ i $d\in F_b\cap I$. skoro $I$ jest ideałem $c\vee d\in I$. Dystrybutywność daje nam po kilku przekształceniach: $c\vee d=f\wedge (a\vee b)$ dla pewnego $f\in F$. Ponieważ $F$ i $I$ są rozłączne, $a\vee b\in F$ implikowałoby $f\wedge (a\vee b)\in F$, czyli $c\vee d\in F\cap I$, sprzeczność. A zatem: $a\vee b\notin F$. To kończy dowód.

Warto też dodać, że lemat Zorna implikuje, że w dowolnej kracie, jeśli mamy filtr $F$ i ideał $I$ takie, że $F\cap I\ne \mathrm{\varnothing }$, to istnieje maksymalny filtr $F^{\prime }\supseteq F$ rozłączny z $I$. Oczywiście na mocy poprzedniego Stwierdzenia, tenże $F^{\prime }$ 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 $F$ w algebrze Boole'a $B$ następujące warunki są równoważne:

1. $F$ jest ultrafiltrem;
2. $F$ jest pierwszy;
3. Dla dowolnego $a\in B$, $a\in F$ wtedy i tylko wtedy, gdy dla dowolnego $b\in B$ $a\wedge b\ne \mathbf{𝟎}$;
4. Dla dowolnego $a\in B$ albo $a\in F$, albo $a\notin F$.

Dowód

Załóżmy (1). Ponieważ $\{\mathbf{𝟎}\}$ jest ideałem, (2) wynika ze Stwierdzenia 6.7. Załóżmy (2). Niech $a\in B$ i załóżmy, że $a\notin F$. Wtedy najmniejszy filtr zawierający $\uparrow a$ i $F$ musi być całą kratą $B$. To znaczy, że $a\wedge b=\mathbf{𝟎}$ dla pewnego $b\in F$. Odwrotnie, przypuśćmy że $a\in F$. Ponieważ $F$ jest właściwy, $a\wedge b\ne \mathbf{𝟎}$ dla każdego $b\in F$. Załóżmy teraz (3). Ponieważ każdy ultrafiltr jest pierwszy i dla dowolnego $a\in B$, $\mathbf{𝟏}=a\vee \mathrm{\neg }a\in F$, dostajemy (4). W końcu, zakładając (4), jeśli $a\notin F$, to $\mathrm{\neg }a\in F$, więc nie istnieje filtr właściwy zawierający $a$ i $F$. A zatem $F$ jest maksymalnym filtrem właściwym w kracie $B$.

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 $B$ istnieje izomorfizm między atomami ${𝒜}(B)$ i ultrafiltrami $\mathrm{U}\mathrm{l}\mathrm{t}(B)$ na $B$.

Dowód

jeśli $a$ jest atomem, to $\uparrow a$ jest ultrafiltrem, bo dla dowolnego $b\in B$ albo $a\wedge b=a$ i wtedy $b\in \uparrow a$, albo $a\wedge b\ne a$, czyli $a\wedge b=\mathbf{𝟎}$, więc $\mathrm{\neg }b\in \uparrow a$. Odwrotnie, jeśli $F$ jest ultrafiltrem na $B$, to $\bigwedge F$ jest atomem. Łatwo przekonać się, że $\uparrow \bigwedge F=F$ oraz jest trywialne, że $\bigwedge \uparrow a=a$.

Aby pokazać teraz równoważność ${\mathbf{𝐒}\mathbf{𝐞}\mathbf{𝐭}}_{fin}^{op}$ i ${\mathbf{𝐁}\mathbf{𝐀}}_{fin}$, zdefiniujemy odpowiednie funktory. Z jednej strony, mamy kontrawariantny funktor potęgowy ${𝒫}:{\mathbf{𝐒}\mathbf{𝐞}\mathbf{𝐭}}_{fin}^{op}\to {\mathbf{𝐁}\mathbf{𝐀}}_{fin}$. Z drugiej strony, pokażemy, że operacja ${𝒜}:{\mathbf{𝐁}\mathbf{𝐀}}_{fin}^{op}\to {\mathbf{𝐒}\mathbf{𝐞}\mathbf{𝐭}}_{fin}$, której działanie znamy na obiektach, da się rozszerzyć do funktora. Ale tak jest dzięki Lematowi 6.9. Jeśli $h:B\to C$ jest homomorfizmem algebr Boole'a, to dla $c\in C$ zbiór $h^{-1}[\uparrow c]$ jest ultrafiltrem na $B$. Definiujemy zatem:

${𝒜}(h:B\to C)(c):=\bigwedge h^{-1}[\uparrow c]$

Uważny Czytelnik zwrócił uwagę, że typ ${𝒜}$, którym jest ${\mathbf{𝐁}\mathbf{𝐀}}_{fin}^{op}\to {\mathbf{𝐒}\mathbf{𝐞}\mathbf{𝐭}}_{fin}$, jest tym samym co typ ${\mathbf{𝐁}\mathbf{𝐀}}_{fin}\to {\mathbf{𝐒}\mathbf{𝐞}\mathbf{𝐭}}_{fin}^{op}$.

Wraz z funktorami ${𝒫}$ i ${𝒜}$ dostajemy też dwie transformacje naturalne. Pierwsza, $\alpha :1\to {𝒜}{𝒫}$ jest dana na komponentach jak następuje: niech $X$ będzie zbiorem skończonym. Atomami ${𝒫}(X)$ są singletony, więc ${\alpha }_X(x):=\{x\}$ jest izomorfizmem. Drugą transformację $\beta :1\to {𝒫}{𝒜}$ określamy na komponencie $B$ jako:

${\beta }_B(b):=\{a\in {𝒜}(B)\mid a\le b\}$

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