Teoria kategorii dla informatyków/Ćwiczenia 9: Sprzężenia I

==Zadanie 9.1==

Znaleźć lewe sprzężenie dla funktora zapominania $U\colon \mathbf {Top} \to \mathbf {Set}$, o ile istnieje.

Wskazówka:

To sprzężenie istnieje. Pytamy bowiem: jak stworzyć strukturę przestrzeni topologicznej na dowolnym zbiorze. Współczesna nauka zna odpowiedzi na takie pytania...

Rozwiązanie:

Na dowolnym zbiorze $X$ są dwa najprostsze sposoby zadania topologii $\tau$: albo bierzemy $\tau =\{\emptyset ,X\}$, albo $\tau ={\mathcal {P}}(X)$. Nasz funktor $F\colon \mathbf {Set} \to \mathbf {Top}$ na obiektach będzie zdefiniowany jako $F(X):=(X,\tau )$, zaś na strzałkach jako $f\mapsto f$. Dla zbioru $X$ naturalnym kandydatem na komponent jedności $\eta _{X}\colon X\to UF(X)$ jest identyczność $1_{X}$. Ta prosta postać jedności, w świetle Twierdzenia 9.5, pozwala nam na stwierdzenie, że $F\dashv U$ wtedy i tylko wtedy, gdy dla dowolnej przestrzeni topologicznej $(A,\gamma )$, dowolna funkcja $F(X)\to (A,\gamma )$ jest ciągła. To bardzo silne wymaganie! Mówiąc precyzyjniej: topologia na $F(X)$ musi być bardzo bogata, tak aby dla dowolnej funkcji $f$, jak wyżej, przeciwobraz dowolnego zbioru otwartego $U\in \gamma$ musi być otwarty w $F(X)$. Z pewnością $\tau =\{\emptyset ,X\}$ nie spełnia tego wymagania. Z pewnością również $\tau ={\mathcal {P}}(X)$ jest dobrym kandydatem - i jedynym możliwym (bo przecież moglibyśmy wziąć $(A,\gamma )=(X,{\mathcal {P}}(X))$ oraz $f=1_{X}$). Każda bowiem funkcja dziedzinie $(X,{\mathcal {P}}(X))$ jest ciągła. Podsumujmy: funktor zapominania $\mathbf {Top} \to \mathbf {Set}$ ma lewe sprzężenie $F\colon \mathbf {Set} \to \mathbf {Top}$ dany jako: $F(X):=(X,{\mathcal {P}}(X))$, $F(f):=f$.

==Zadanie 9.2==

Udowodnij, że produkt jest prawym sprzężeniem przekątnej, a koprodukt - lewym sprzężeniem.

Wskazówka:

Zakładamy, że pracujemy w kategorii $\mathbf {C}$. Przekątna to funktor $\Delta \colon \mathbf {C} \to \mathbf {C} \times \mathbf {C}$ definiowany na obiektach jako $\Delta (X)=(X,X)$ i tak samo na strzałkach.

Rozwiązanie:

Jeśli $\Delta \dashv F$ dla pewnego $F$, to po pierwsze, $F$ musi mieć typ $\mathbf {C} \times \mathbf {C} \to \mathbf {C}$. Po drugie, musimy mieć naturalny izomorfizm:

$\mathrm {Hom} _{\mathbf {C} }(A,F(X,Y))\cong \mathrm {Hom} _{\mathbf {C} }(\Delta (A),(X,Y))\cong \mathrm {Hom} _{\mathbf {C} }(A,X)\times \mathrm {Hom} _{\mathbf {C} }(A,Y),$

gdzie wykorzystaliśmy definicję produktu kategorii. Ale Zadanie 3.5 pokazuje nam, że w takim razie musi być $F(X,Y)\cong X\times Y$. Produkt $\times \colon \mathbf {C} \times \mathbf {C} \to \mathbf {C}$ (albo dowolny funktor izomorficzny do produktu) jest zatem prawym sprzężeniem: $\Delta \dashv \times$. Jedność tego sprzężenia, $\eta$, ma dla każdego komponentu $\eta _{A}$ typ $A\to A\times A$. Musimy tak dobrać jedność, aby spełniona była własność uniwersalna wyrażona w Twierdzeniu 9.5: dla każdej strzałki $f\colon A\to X\times Y$ istnieje dokładnie jedna strzałka $(f_{1},f_{2})\colon (A,A)\to (X,Y)$ tak, że $f=(f_{1}\times f_{2})\circ \eta _{A}$. Ponieważ każda strzałka $f\colon A\to (X,Y)$ jest postaci $f=(f_{1},f_{2})$, wystarczy wziąć $\eta _{A}:=(1_{A},1_{A})$, gdyż wtedy:

$(f_{1}\times f_{2})\circ \eta _{A}=(f_{1}p_{1}\eta _{A},f_{2},p_{2}\eta _{A})=(f_{1}1_{A},f_{2}1_{A})=(f_{1},f_{2})=f.$ Uwaga: Dowiedliśmy, że $\Delta$ ma prawe sprzężenie wtedy i tylko wtedy, gdy $\mathbf {C}$ ma produkty. Rozważania dualne do powyższych wskazują, że $+\dashv \Delta$ - cały dowód dostajemy za darmo zgodnie z zasadą dualności.

==Zadanie 9.3==

Znaleźć lewe i prawe sprzężenie do funktora diagonalnego $\Delta$ typu $\mathbf {C} \to \mathbf {1}$, gdzie $\mathbf {C}$ jest dowolną kategorią, zaś $\mathbf {1}$ - dyskretną kategorią jednoobiektową.

Wskazówka:

Funktor o kodziedzinie $\mathbf {1}$ jest tylko jeden - nie mamy wyboru - musimy bowiem zdefiniować go jako $\Delta (X)=*$ i $\Delta (f)=1_{*}$ dla $X\in \mathbf {C} _{0}$, $f\in \mathbf {C} _{1}$ i $\mathbf {1} _{0}=\{*\}$.

Rozwiązanie:

Prawe sprzężenie do $\Delta$, o ile istnieje, musi z definicji być elementem $A\colon \mathbf {1} \to \mathbf {C}$, czyli obiektem $A\in \mathbf {C} _{0}$, takim że dla dowolnego obiektu $C\in \mathbf {C} _{0}$ istnieje strzałka typu $C\to \Delta (*)=A$. Co więcej, ta strzałka może być tylko jedna, bo $\mathrm {Hom} (\Delta (A),*)$ jest singletonem (zawiera tylko $1_{*}$). Taki obiekt $A$, o ile istnieje, jest obiektem końcowym w $\mathbf {C}$. Pokazaliśmy zatem, że $\Delta \dashv \mathbf {1}$ (gdzie tym razem $\mathbf {1}$ oznacza obiekt końcowy w $\mathbf {C}$). Dualnie, lewym sprzężeniem $\Delta$ jest obiekt początkowy: $\mathbf {0} \dashv \Delta$, o ile istnieje.

Uwaga

Wykazaliśmy, że $\Delta \dashv \mathbf {1}$ wtedy i tylko wtedy, gdy $\mathbf {C}$ ma obiekt końcowy ($\mathbf {0} \dashv \Delta$ wtedy i tylko wtedy, gdy $\mathbf {C}$ ma obiekt początkowy).

Szereg kolejnych zadań dotyczy sprzężeń między częściowymi porządkami.

==Zadanie 9.4==

Wykaż, że topologiczna operacja wnętrza $\mathbf {int}$ jest prawym sprzężeniem do inkluzji zbiorów otwartych $X$ w podzbiory $X$.

Wskazówka:

Niech $X$ będzie przestrzenią topologiczną, $\Omega (X)$ - kolekcją zbiorów otwartych. Wówczas wnętrze $\mathbf {int}$ jest operacją typu ${\mathcal {P}}(X)\to \Omega (X)$, zaś inkluzja ma typ odwrotny: $i\colon \Omega (X)\to {\mathcal {P}}(X)$.

Rozwiązanie:

Aby pokazać sprzężenie, musimy udowodnić, że:

$U\subseteq A\iff U\subseteq \mathbf {int} (A)$ dla dowolnych $A\in {\mathcal {P}}(X)$ i $U\in \Omega (X)$. Ale ta równoważność w tłumaczeniu na język polski mówi, że $\mathbf {int} (A)$ jest największym zbiorem otwartym zawartym w $A$. A to jest właśnie definicja wnętrza!

==Zadanie 9.5==

Udowodnij, że operacje obrazu i przeciwobrazu funkcji $f\colon A\to B$ są sprzężeniami na zbiorach potęgowych.

Rozwiązanie:

Operację przeciwobrazu oznaczmy $f^{-1}\colon {\mathcal {P}}(B)\to {\mathcal {P}}(A)$, zaś obraz jako $im(f)\colon {\mathcal {P}}(A)\to {\mathcal {P}}(B)$. Wtedy widać, że:

$im(f)(S)\subseteq T\iff S\subseteq f^{-1}(T),$ co dowodzi $im(f)\dashv f^{-1}$.

==Zadanie 9.6==

Niech $L$ będzie językiem pierwszego rzędu. Dla listy różnych zmiennych $l:=\{x_{1},...,x_{n}\}$ definiujemy jako $L(l)$ zbiór tych formuł języka $L$, których wszystkie zmienne wolne znajdują się na liście $l$ (oczywiście nie wszystkie zmienne $l$ muszą występować w formule $\phi \in L(l)$). Para $(L(l),\vdash )$ jest preporządkiem względem syntaktycznej relacji dedukcji $\vdash$. Niech $y\notin l$. Wówczas $*\colon L(l)\to L(l\cup \{y\})$, $*(\phi ):=\phi$ jest funktorem, ponieważ $\phi \vdash \psi$ w $L(l)$ trywialnie implikuje $\phi \vdash \psi$ w $L(l\cup \{y\})$. Udowodnić, że kwantyfikator ogólny $\forall y\colon L(l\cup \{y\})\to L(l)$ jest prawym sprzężeniem do $*$, tj. $*\dashv \forall y$. Jakie jest twierdzenie dualne?

Rozwiązanie:

Dowód stanowi równoważność:

$\phi (l)=*\phi (l)\vdash \psi (l,y)\ \mathrm {wtw,\ gdy} \ \phi (l)\vdash \forall y.\psi (l,y),$

która wyraża dwie reguły: wprowadzenia i eliminacji kwantyfikatora ogólnego.

Dualnie $\exists y\dashv *$, co objawia się regułą wprowadzenia i eliminacji kwantyfikatora szczegółowego:

$\exists y.\psi (l,y)\vdash \phi (l)\ \mathrm {wtw,\ gdy} \ \psi (l,y)\vdash \phi (l).$

Uwaga

Badając jedności i kojedności tych sprzężeń, dostajemy zupełny system dedukcyjny języka $L$, tzn. każde z praw logicznych dla $\vdash$ wynika z tych dwóch sprzężeń powyżej, np. kojednością $\exists \vdash *$ jest prawo: $\psi (l,y)\vdash \exists y.\psi (l,y).$

==Zadanie 9.7==

Niech $(P,\leq )$ będzie dcpo, jak definiujemy to w Wykładzie 12. Wykazać, że domknięcie dolne $\downarrow \colon (P,\leq )\to ({\mathcal {I}}(P),\subseteq )$ jest prawym sprzężeniem do operacji supremum skierowanego $\bigvee {}^{\downarrow }\colon ({\mathcal {I}}(P),\subseteq )\to (P,\leq )$.

Rozwiązanie:

Musimy udowodnić, że:

$\bigvee {}^{\downarrow }I\leq x\iff I\subseteq \downarrow x$

dla dowolnego elementu $x\in P$ i ideału $I\in {\mathcal {I}}(P)$. Jeśli $\bigvee {}^{\downarrow }I\leq x$, to oczywiście $i\leq x$ dla każdego $i\in I$, a co za tym idzie, $i\in \downarrow x$. To dowodzi $I\subseteq \downarrow x$. Odwrotnie, jeśli ta ostatnia inkluzja zachodzi, to $x$ jest ograniczeniem górnym $I$, więc jest powyżej jego supremum, tj. $\bigvee {}^{\downarrow }I\leq x$ (zwróćmy uwagę, że to supremum istnieje, bo $P$ jest dcpo).

==Zadanie 9.8==

Czy operacja $\bigvee {}^{\downarrow }$, jak zdefiniowana w Zadaniu 9.7 ma lewe sprzężenie?

Wskazówka:

Tak, ale wtedy i tylko wtedy, kiedy $P$ jest posetem ciągłym (definicji ciągłości szukaj Wykładzie 12.).

Rozwiązanie:

Niech $P$ będzie posetem ciągłym i dcpo. Wtedy relacja aproksymacji $\ll \colon P\to {\mathcal {I}}(P)$ jest dobrze zdefiniowana (tj. ma odpowiedni typ). Musimy pokazać, że:

$\Downarrow x\subseteq I\iff x\leq \bigvee {}^{\downarrow }I$ dla dowolnego ideału $I\in {\mathcal {I}}(P)$ oraz elementu $x\in P$. Załóżmy, że $\Downarrow x\subseteq I$. Wtedy $x=\bigvee {}^{\downarrow }x\leq \bigvee {}^{\downarrow }I$, co wynika z ciągłości $P$ i faktu, że $I$ jest większym zbiorem niż $\ll x$. Odwrotnie, jeśli $x\leq \bigvee {}^{\downarrow }I$, to ponieważ $I$ jest zbiorem skierowanym, dla dowolnego $y\ll x$ mamy $y\leq i$ dla pewnego $i\in I$ (wprost z definicji relacji aproksymacji). A zatem $\Downarrow x\subseteq I$.