Teoria kategorii dla informatyków/Ćwiczenia 10: Sprzężenia II

From Studia Informatyczne

==Zadanie 10.1==

Udowodnić, że F\dashv G, F'\dashv G' oraz G\cong G' implikują F\cong F'.

Wskazówka:

Użyć wniosku z lematu Yonedy.

Rozwiązanie:

Z założeń wynika istnienie następującego ciągu naturalnych izomorfizmów, dla dowolnych A,B:

\mathrm{Hom}(FA,B)\cong \mathrm{Hom}(A,GB)\cong  \mathrm{Hom}(A,G'B)\cong \mathrm{Hom}(F'A,B)

(po kolei wykorzystaliśmy: sprzężenie F\dashv G, zachowywanie izomorfizmu przez funktor Yonedy, sprzężenie F'\dashv G'). Z wniosku z lematu Yonedy, udowodnionego w Zadaniu 7.2, wynika, że F\cong F'.


==Zadanie 10.2==

Udowodnić, że jeśli F\dashv G oraz H\dashv K, to H\circ F\dashv G\circ K.

Rozwiązanie:

Następujący ciąg naturalnych izomorfizmów, prawdziwy dla dowolnych A,B, dowodzi tezy zadania:

\mathrm{Hom}(HFA,B)\cong\mathrm{Hom}(FA,KB)\cong\mathrm{Hom}(A,GKB).


==Zadanie 10.3==

Udowodnij Twierdzenie 10.3 bez użycia lematu Yonedy.

Rozwiązanie:

Załóżmy, że G\colon \mathbf{D}\to \mathbf{C} ma lewe sprzężenie F. Niech D\colon \mathbf{J}\to\mathbf{D} będzie diagramem, który ma granicę:

\{c_j\colon Y\to D(j)\mid j\in \mathbf{J}_0\}.

Musimy pokazać, że:

\{Gc_j\colon GY\to GD(j)\mid j\in \mathbf{J}_0\}

jest granicą diagramu G\circ D\colon \mathbf{J}\to \mathbf{C}. Dla dowolnego stożka

\{d_j\colon X\to GD(j)\mid j\in\mathbf{J}_0\}

nad G\circ D, używając sprzężenia, dostajemy stożek:

\{\hat{d_j}\colon FX\to D(j)\mid j\in \mathbf{J}_0\}.

Z definicji granicy, diagram:

Grafika:tk-10.3.png

komutuje, czyli, używając sprzężenia,

Grafika:tk-10.4.png

komutuje. To kończy dowód.

==Zadanie 10.4==

Udowodnij, że funkcja monotoniczna pomiędzy dwoma kratami zupełnymi posiada lewe sprzężenie wtedy i tylko wtedy, gdy zachowuje wszystkie infima. Jakie jest twierdzenie dualne?

Wskazówka:

Oczywiście, twierdzenie dualne brzmi: funkcja monotoniczna f\colon L\to K ma prawe sprzężenie wtedy i tylko wtedy, gdy zachowuje wszelkie suprema, tzn. f(\bigvee_i x_i)=\bigvee_i f(x_i) dla dowolnej rodziny elementów \{x_i\}\subseteq L.

Zauważmy też, że w świetle Twierdzenia 10.3, aby rozwiązać oryginalne zadanie, wystarczy połowa pracy.

Rozwiązanie:

Niech f\colon L\to K będzie monotoniczna i niech zachowuje wszystkie infima. Zdefiniujmy funkcję g\colon K\to L jako:

g(y):= \bigwedge\{ z\in L\mid y\leq f(z)\}.

Wtedy g jest monotoniczna: załóżmy, że x\leq y. Wtedy dla każdego z\in L, jeśli y\leq f(z), to x\leq f(z), co świadczy już o tym, że g(x)\leq g(y). Pokażmy teraz, że g ma lewe sprzężenie. Z definicji g wprost wynika, że jeśli f(a)\leq b, to g(f(a))=\bigwedge\{z\mid f(z)\leq f(a)\}=f(a)\leq g(B). Z drugiej strony, jeśli a\leq g(b), to f(a)\leq f(g(b))=\bigwedge_{b\leq f(z)}f(z)=b. To kończy dowód.


==Zadanie 10.5==

Udowodnić, że kategoria lokalnie mała i zupełna \mathbf{C} posiada obiekt początkowy wtedy i tylko wtedy, gdy spełniony jest następujący warunek itnienia zbioru rozwiązań: istnieje zbiór obiektów C_i taki, że dla dowolnego obiektu C\in \mathbf{C}_0 istnieje strzałka C_i\to C dla pewnego i\in I.

Wskazówka:

Jeśli \mathbf{C} ma obiekt początkowy \mathbf{0}, to singleton \{\mathbf{0}\} jest zbiorem rozwiązań. Odwrotnie, jeśli istnieje zbiór rozwiązań \{C_i\mid i\in I\}, rozważamy produkt W :=\Pi_i C_i. Tenże produkt jest słabo początkowy, w tym sensie, że dla dowolnego obiektu C\in \mathbf{C}_0 istnieje (niekoniecznie jedyna!) strzałka typu W\to C, a mianowicie złożenie:

\Pi_i C_i\stackrel{p_i}{\to} C_i\to C

(dla każdego i\in I mamy bowiem projekcję p_i\colon \Pi_i C_i\to C_i). Ponieważ \mathrm{Hom}_{\mathbf{C}}(W,W) jest zbiorem, bo \mathbf{C} jest lokalnie mała, możemy rozważać granicę diagramu

Grafika:tk-10.6.png

wszystkich strzałek typu W\to W. Ta granica, niech nazywa się (E,e),

Grafika:tk-10.7.png

istnieje, bo \mathbf{C} jest kategorią zupełną. Teraz wystarczy udowodnić, że E jest obiektem początkowym w \mathbf{C}.

Rozwiązanie:

Granica (E,e), jak zdefiniowana powyżej, posiada następujące własności:

  • dla dowolnych endostrzałek f,g\in \mathrm{Hom}_{\mathbf{C}}(W,W) mamy fe=ge;
  • jeśli h\colon A\to W jest strzałką taką, że dla każdej pary strzałek f,g\in \mathrm{Hom}_{\mathbf{C}}(W,W) takich, że fh=gh, istnieje dokładnie jedna strzałka k\colon A\to E z ek=h.

Innymi słowy, E jest pewnym uogólnionym ekwalizatorem. Pokażemy, że E jest początkowy w \mathbf{C}. Niech A\in\mathbf{C}_0 będzie dowolnym obiektem. Skoro W jest obiektem słabo początkowym, istnieje strzałka

E\stackrel{e}{\to}W\stackrel{p_i}{\to}C_i\to A.

Czy jest to jedyna strzałka tego typu? Tak, bo jeśli mamy dwie równoległe strzałki f,g\colon E\to A, to niech (B,h) będzie ich ekwalizatorem. Ponieważ W jest słabo początkowy, znów znajdziemy strzałkę k\colon W\to B. Wtedy ehk jest typu W\to W. Skoro E jest ekwalizatorem, to 1_Pe = (ehk)e, a zatem e1_E=e(hke). Drugi warunek na E implikuje, że e jest mono, więc 1_E=hke. I w końcu f=f1_E=fhke=ghke=g1_E=g. To kończy dowód.

==Zadanie 10.6==

Udowodnić Fakt 10.7.

Rozwiązanie:

Załóżmy d\dashv g. Skoro t\leq g(s) wtedy i tylko wtedy, gdy d(t)\leq s, to oczywiście d(t) jest ograniczeniem dolnym g^{-1}(\uparrow t). Ale d(t)\leq d(t) implikuje t\leq g(d(t)), więc d(t)\in g^{-1}(\uparrow t), co świadczy o tym, że d(t) = \mathrm{min}\{ g^{-1}(\uparrow  t)\} dla każdego t\in T. Odwrotnie, załóżmy, że d jest scharakteryzowana przez g jak wyżej. Niech t\leq g(s). Wtedy s\in  g^{-1}(\uparrow t), co daje s\geq \mathrm{min}  g^{-1}(\uparrow t) = d(t). Z drugiej strony, niech m=\mathrm{min} g^{-1}(\uparrow t), czyli m\in  g^{-1}(\uparrow t), a więc g(m)\geq t. Jeśli zatem zachodzi s\geq d(t)=m, to g(s)\geq  g(m)\geq t, gdyż g jest monotoniczna. To kończy dowód.


==Zadanie 10.7==

Udowodnij Fakt 10.9.

Rozwiązanie:

Niech d\dashv g. Wówczas z g(s)\leq g(s) wynika dg(s)\leq s. Dualnie t\geq gd(t). Odwrotnie, załóżmy te nierówności. Niech t\leq g(s). Wtedy d(t)\leq dg(s), bo d monotoniczna. Z założenia dg(s)\leq s, więc d(t)\leq s. Podobnie, jeśli s\geq d(t), to g(s)\geq gd(t)\geq t.

Zauważmy teraz, że dg\leq 1 implikuje gdg\leq g z monotoniczności. Ale dla t=g(s) z założenia 1\leq gd, mamy że g(s)\leq gdg(s), czyli g\leq gdg. Pokazaliśmy, że g=gdg. Podobnie dowodzi się d=dgd. Idempotentność: g=gdg implikuje dg=dgdg, zaś d=dgd implikuje gd=gdgd, co należało pokazać.


==Zadanie==

Udowodnij Fakt Fakt 10.10.

Rozwiązanie:

Udowodnimy równoważność pierwszych czterech warunków:

  1. g jest surjekcją;
  2. d(t)=\mathrm{min} g^{-1}(t) dla każdego t\in T;
  3. gd=1_T;
  4. d jest injekcją.

w przypadku, gdy d\dashv g.

Załóżmy (1). Z Zadania 10.6 wynika, że d(t)=\mathrm{min} g^{-1}(\uparrow t). Skoro g jest surjekcją, g(g^{-1}(\uparrow t))=\uparrow t. Z monotoniczności, g(d(t))=\mathrm{min} g(g^{-1}(\uparrow t))=\mathrm{min}\uparrow t = t. A zatem d(t)\in g^{-1}(t), czyli \mathrm{min} g^{-1}(t)=d(t), co jest (2). Załóżmy (2). Mamy d(t)\in g^{-1}(t), tzn. g(d(t))=t, czyli (3). Załóżmy (3). Wtedy d jest sekcją, a zatem jest injekcją. Załóżmy (4). Skoro d=dgd i d jest injekcją, to jest monomorfizmem, więc 1_T=gd, a zatem g jest retrakcją, czyli surjekcją. To pokazuje (1) i kończy dowód.