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

==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:

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

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

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

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_{P}e=(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.