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

From Studia Informatyczne

==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_1p_1\eta_A,f_2,p_2\eta_A)=(f_11_A,f_21_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.