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

==Zadanie 9.1==

Znaleźć lewe sprzężenie dla funktora zapominania $U:\mathbf{𝐓}\mathbf{𝐨}\mathbf{𝐩}\to \mathbf{𝐒}\mathbf{𝐞}\mathbf{𝐭}$, 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 =\{\mathrm{\varnothing },X\}$, albo $\tau ={𝒫}(X)$. Nasz funktor $F:\mathbf{𝐒}\mathbf{𝐞}\mathbf{𝐭}\to \mathbf{𝐓}\mathbf{𝐨}\mathbf{𝐩}$ 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:X\to UF(X)$ jest identyczność $1_X$. Ta prosta postać jedności, w świetle Twierdzenia 9.5, pozwala nam na stwierdzenie, że $F⊣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 =\{\mathrm{\varnothing },X\}$ nie spełnia tego wymagania. Z pewnością również $\tau ={𝒫}(X)$ jest dobrym kandydatem - i jedynym możliwym (bo przecież moglibyśmy wziąć $(A,\gamma )=(X,{𝒫}(X))$ oraz $f=1_X$). Każda bowiem funkcja dziedzinie $(X,{𝒫}(X))$ jest ciągła. Podsumujmy: funktor zapominania $\mathbf{𝐓}\mathbf{𝐨}\mathbf{𝐩}\to \mathbf{𝐒}\mathbf{𝐞}\mathbf{𝐭}$ ma lewe sprzężenie $F:\mathbf{𝐒}\mathbf{𝐞}\mathbf{𝐭}\to \mathbf{𝐓}\mathbf{𝐨}\mathbf{𝐩}$ dany jako: $F(X):=(X,{𝒫}(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{𝐂}$. Przekątna to funktor $\mathrm{\Delta }:\mathbf{𝐂}\to \mathbf{𝐂}\times \mathbf{𝐂}$ definiowany na obiektach jako $\mathrm{\Delta }(X)=(X,X)$ i tak samo na strzałkach.

Rozwiązanie:

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

${\mathrm{H}\mathrm{o}\mathrm{m}}_{\mathbf{𝐂}}(A,F(X,Y))\cong {\mathrm{H}\mathrm{o}\mathrm{m}}_{\mathbf{𝐂}}(\mathrm{\Delta }(A),(X,Y))\cong {\mathrm{H}\mathrm{o}\mathrm{m}}_{\mathbf{𝐂}}(A,X)\times {\mathrm{H}\mathrm{o}\mathrm{m}}_{\mathbf{𝐂}}(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 :\mathbf{𝐂}\times \mathbf{𝐂}\to \mathbf{𝐂}$ (albo dowolny funktor izomorficzny do produktu) jest zatem prawym sprzężeniem: $\mathrm{\Delta }⊣\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:A\to X\times Y$ istnieje dokładnie jedna strzałka $(f_1,f_2):(A,A)\to (X,Y)$ tak, że $f=(f_1\times f_2)\circ {\eta }_A$. Ponieważ każda strzałka $f: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 $\mathrm{\Delta }$ ma prawe sprzężenie wtedy i tylko wtedy, gdy $\mathbf{𝐂}$ ma produkty. Rozważania dualne do powyższych wskazują, że $+⊣\mathrm{\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 $\mathrm{\Delta }$ typu $\mathbf{𝐂}\to \mathbf{𝟏}$, gdzie $\mathbf{𝐂}$ jest dowolną kategorią, zaś $\mathbf{𝟏}$ - dyskretną kategorią jednoobiektową.

Wskazówka:

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

Rozwiązanie:

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

Uwaga

Wykazaliśmy, że $\mathrm{\Delta }⊣\mathbf{𝟏}$ wtedy i tylko wtedy, gdy $\mathbf{𝐂}$ ma obiekt końcowy ($\mathbf{𝟎}⊣\mathrm{\Delta }$ wtedy i tylko wtedy, gdy $\mathbf{𝐂}$ 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{𝐢}\mathbf{𝐧}\mathbf{𝐭}$ jest prawym sprzężeniem do inkluzji zbiorów otwartych $X$ w podzbiory $X$.

Wskazówka:

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

Rozwiązanie:

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

$U\subseteq A⟺U\subseteq \mathbf{𝐢}\mathbf{𝐧}\mathbf{𝐭}(A)$ dla dowolnych $A\in {𝒫}(X)$ i $U\in \mathrm{\Omega }(X)$. Ale ta równoważność w tłumaczeniu na język polski mówi, że $\mathbf{𝐢}\mathbf{𝐧}\mathbf{𝐭}(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:A\to B$ są sprzężeniami na zbiorach potęgowych.

Rozwiązanie:

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

$im(f)(S)\subseteq T⟺S\subseteq f^{-1}(T)$ co dowodzi $im(f)⊣f^{-1}$.

==Zadanie 9.6==

Niech $L$ będzie językiem pierwszego rzędu. Dla listy różnych zmiennych $l:=\{x_1,\dots ,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 $\varphi \in L(l)$). Para $(L(l),⊢)$ jest preporządkiem względem syntaktycznej relacji dedukcji $⊢$. Niech $y\notin l$. Wówczas $*:L(l)\to L(l\cup \{y\})$, $*(\varphi ):=\varphi$ jest funktorem, ponieważ $\varphi ⊢\psi$ w $L(l)$ trywialnie implikuje $\varphi ⊢\psi$ w $L(l\cup \{y\})$. Udowodnić, że kwantyfikator ogólny $\mathrm{\forall }y:L(l\cup \{y\})\to L(l)$ jest prawym sprzężeniem do $*$, tj. $*⊣\mathrm{\forall }y$. Jakie jest twierdzenie dualne?

Rozwiązanie:

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

$\varphi (l)=*\varphi (l)⊢\psi (l,y)\mathrm{w}\mathrm{t}\mathrm{w},\mathrm{g}\mathrm{d}\mathrm{y}\varphi (l)⊢\mathrm{\forall }y.\psi (l,y)$

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

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

$\mathrm{\exists }y.\psi (l,y)⊢\varphi (l)\mathrm{w}\mathrm{t}\mathrm{w},\mathrm{g}\mathrm{d}\mathrm{y}\psi (l,y)⊢\varphi (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 $⊢$ wynika z tych dwóch sprzężeń powyżej, np. kojednością $\mathrm{\exists }⊢*$ jest prawo: $\psi (l,y)⊢\mathrm{\exists }y.\psi (l,y)$

==Zadanie 9.7==

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

Rozwiązanie:

Musimy udowodnić, że:

$\bigvee {}^{\downarrow }I\le x⟺I\subseteq \downarrow x$

dla dowolnego elementu $x\in P$ i ideału $I\in {ℐ}(P)$. Jeśli $\bigvee {}^{\downarrow }I\le x$, to oczywiście $i\le 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\le 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 :P\to {ℐ}(P)$ jest dobrze zdefiniowana (tj. ma odpowiedni typ). Musimy pokazać, że:

$\Downarrow x\subseteq I⟺x\le \bigvee {}^{\downarrow }I$ dla dowolnego ideału $I\in {ℐ}(P)$ oraz elementu $x\in P$. Załóżmy, że $\Downarrow x\subseteq I$. Wtedy $x=\bigvee {}^{\downarrow }x\le \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\le \bigvee {}^{\downarrow }I$, to ponieważ $I$ jest zbiorem skierowanym, dla dowolnego $y\ll x$ mamy $y\le i$ dla pewnego $i\in I$ (wprost z definicji relacji aproksymacji). A zatem $\Downarrow x\subseteq I$.