Teoria kategorii dla informatyków/Ćwiczenia 4: Zaawansowane konstrukcje uniwersalne

==Zadanie 4.1==

Udowodnić, że w kategorii kartezjańsko zamkniętej $\mathbf {C}$ podnoszenie do potęgi $A\in \mathbf {C} _{0}$:

$[A,-]\colon \mathbf {C} \to \mathbf {C}$

$[A,-](B):=[A,B]$

$[A,-](f\colon X\to Y):=[A,f]\colon [A,X]\to [A,Y]$

$[A,f]:=\mathrm {curry} (f\circ \mathrm {ev} ),$

gdzie $B,X,Y\in \mathbf {C} _{0}$, jest funktorem.

Wskazówka:

Należy najpierw przeczytać Wykład 5. dotyczący funktorów.

Rozwiązanie:

Ustalmy $A\in \mathbf {C} _{0}$. Pokażmy, że operacja $[A,-]$ zachowuje identyczności: ponieważ komutuje diagram

mamy $[A,1_{X}]=\mathrm {curry} (1_{X}\circ \mathrm {ev} )=1_{[A,X]}$, co należało pokazać. Aby pokazać, że $[A,-]$ zachowuje złożenia, rozważmy:

$X{\stackrel {f}{\to }}Y{\stackrel {g}{\to }}Z.$

Wówczas diagram

komutuje, mamy - używając Zadania 3.6:

$([A,g]\times 1_{A})\circ ([A,f]\times 1_{A})=([A,g]\circ [A,f])\times 1_{A}.$

Ale ponieważ strzałka $([A,g]\circ [A,f])\times 1_{A}$ jest jedyną, która sprawia, że zewnętrzny prostokąt komutuje, musi być:

$[A,g]\circ [A,f]=[A,g\circ f],$

co należało pokazać.

==Zadanie 4.2==

Pokazać, że kategoria $\mathbf {Cat}$ jest kartezjańsko zamknięta.

Wskazówka:

Przypomnijmy, że obiektami $\mathbf {Cat}$ są wszystkie małe kategorie, zaś morfizmami - funktory. Należy więc najpierw przeczytać Wykład 5. dotyczący funktorów, w szczególności Zadanie 5.3.

Rozwiązanie:

Wiemy już z Wykładu 3. dotyczącego m.in. produktów, że $\mathbf {Cat}$ ma produkty. Posada też obiekt końcowy, którym jest kategoria $\mathbf {1}$ z jednym obiektem i jedną strzałką. Rzeczywiście, dla dowolnej kategorii $\mathbf {C}$ funktor stały typu $\mathbf {C} \to \mathbf {1}$ da się zdefiniować tylko w jeden sposób (jaki?). Dowód jest trywialny, więc go pomijamy. Aby zakończyć dowód kartezjańskiej zamkniętości $\mathbf {Cat}$, wykażemy, że dla dowolnych dwóch kategorii $\mathbf {A} ,\mathbf {B}$, kategoria funktorów typu $\mathbf {A} \to \mathbf {B}$ (z transformacjami naturalnymi jako strzałkami) jest eksponentem. Oznaczmy tę kategorię tymczasowo jako $Fun(\mathbf {A} ,\mathbf {B} )$, gdyż po zakończeniu dowodu będziemy mogli o niej pisać $[\mathbf {A} ,\mathbf {B} ]$. Musimy zatem wykazać, że odpowiednio zdefiniowana ewaluacja jest morfizmem oraz zagwarantować istnienie bijekcji opisującej własność uniwersalną eksponentu. Oto cztery wymagane kroki:

• Pokażemy, że $\mathrm {ev} \colon Fun(\mathbf {A} ,\mathbf {B} )\times \mathbf {A} \to \mathbf {B}$ jest funktorem. W tym celu skorzystamy z Zadania 5.3 i pokażemy, że $\mathrm {ev}$ jest funktorem ze względu na każdą ze współrzędnych. Niech $F\colon \mathbf {A} \to \mathbf {B}$ będzie ustalonym funktorem. Rozważmy $\mathrm {ev} (F,-)$. Z definicji ewaluacji dostajemy natychmiast, że $ev(F,-)=F$, czyli jest to funktor. Jeśli $A\in \mathbf {A} _{0}$, to operacja $\mathrm {ev} (-,A)\colon Fun(\mathbf {A} ,\mathbf {B} )\to \mathbf {B}$ jest na strzałkach zdefiniowana następująco:

$\eta \colon F\to G\ \mapsto \ \eta _{A}\colon F(A)\to G(A).$

To przypisanie jest również funktorem. W końcu, prawo przemienności wymagane do założeń Zadania 4.3 jest dokładnie stwierdzeniem naturalności transformacji $\eta$, a zatem zachodzi.

• Niech $\mathbf {X}$ będzie dowolną kategorią, zaś $F\colon \mathbf {X} \times \mathbf {A} \to \mathbf {B}$ funktorem. Wówczas $\mathrm {curry} (F)\colon \mathbf {X} \to Fun(\mathbf {A} ,\mathbf {B} )$ definiujemy jako $\mathrm {curry} (F)(X)(A):=F(X,A)$, gdzie $X$ może oznaczać zarówno obiekt, jak i strzałkę w $\mathbf {X}$. Dowód, że jest to funktor, wynika wprost z definicji i faktu, że $F$ jest funktorem.
• Następnie dla każdego funktora $G\colon \mathbf {X} \to Fun(\mathbf {A} ,\mathbf {B} )$ definiujemy $\mathrm {uncurry} (G)\colon \mathbf {X} \times \mathbf {A} \to \mathbf {B}$ jako

$\mathrm {uncurry} (G):=\mathrm {ev} \circ (G\times 1_{\mathbf {A} })$

i pokazujemy, że jest to funktor (bo $G$ jest funktorem, identyczność $1_{\mathbf {A} }\colon \mathbf {A} \to \mathbf {A}$ jest funktorem, produkt funktorów jest funktorem, złożenie tego z funktorem ewaluacji $\mathrm {ev}$ też jest funktorem).

• W końcu mamy $\mathrm {curry} (\mathrm {ev} \circ (G\times 1_{\mathbf {A} }))(X)(A)=(\mathrm {ev} \circ (G\times 1_{\mathbf {A} }))(X,A)=\mathrm {ev} (G(X),A)=G(X)(A),$

dla $X\in \mathbf {X} _{0}$, $A\in \mathbf {A} _{0}$ i dokładnie te same równości będą zachodzić na strzałkach. Dlatego

$\mathrm {curry} (\mathrm {ev} \circ (G\times 1_{\mathbf {A} }))=G,$

co daje szukaną bijekcję i kończy dowód.

==Zadanie 4.3==

Sprawdzić, że w dowolnej kategorii kartezjańsko zamkniętej $\mathbf {C}$ zachodzą następujące związki (gdzie trzeba, należy założyć też istnienie obiektu początkowego $\mathbf {0}$ w kategorii $\mathbf {C}$).

• $\mathbf {0} \cong \mathbf {0} \times A$,
• jeśli istnieje strzałka $A\to \mathbf {0}$, to $A\cong \mathbf {0}$ dla dowolnego $A\in \mathbf {C} _{0}$,
• jeśli $\mathbf {0} \cong \mathbf {1}$, to wszystkie obiekty $\mathbf {C}$ są izomorficzne,
• dowolna strzałka $A\to \mathbf {0}$ jest mono,
• $[A,\mathbf {1} ]\cong \mathbf {1}$,
• $[1,A]\cong A$,
• $[A\times B,C]\cong [A,[B,C]]$,
• $[A,B]\times [A,C]\cong [A,B\times C]$,

Rozwiązanie:

• Pokazujemy $\mathbf {0} \cong \mathbf {0} \times A$. Rozważmy komutujący diagram:

z którego odczytamy - po pierwsze - że $p_{\mathbf {0} }\circ !_{\mathbf {0} \times A}=1_{\mathbf {0} }$. Po drugie, widzimy, że strzałka $!_{\mathbf {0} \times A}\circ p_{\mathbf {0} }$ sprawia, iż zewnętrzne strzałki na diagramie komutują. Ale tę samą rolę spełniłaby tu $1_{\mathbf {0} \times A}$. A zatem uniwersalność produktu daje nam $!_{\mathbf {0} \times A}\circ p_{\mathbf {0} }=1_{\mathbf {0} \times A}$. Wykazaliśmy więc, że $!_{\mathbf {0} \times A}$ oraz $p_{\mathbf {0} }$ są wzajemnie odwrotnymi izomorfizmami między $\mathbf {0}$ i $\mathbf {0} \times A$.

• Załóżmy, że istnieje strzałka $A\to \mathbf {0}$. Technką z punktu powyżej pokazujemy, że $A\cong \mathbf {0} \times A$ dla dowolnego $A\in \mathbf {C} _{0}$.

A zatem złożenie $A\cong \mathbf {0} \times A\cong \mathbf {0}$ jest szukanym izomorfizmem.

• Wykażemy, że jeśli $\mathbf {0} \cong \mathbf {1}$, to wszystkie obiekty $\mathbf {C}$ są izomorficzne. Wystarczy pokazać, że przy założeniu $\mathbf {0} \cong \mathbf {1}$ dowolny obiekt $A$ jest izomorficzny z obiektem końcowym, gdyż wtedy złożenie $A\cong \mathbf {1} \cong B$ da izomorfizm między dowolnymi obiektami $A,B$. Niech $f\colon \mathbf {1} \to \mathbf {0}$ będzie zadanym izomorfizmem. Poniższy diagram (cykl):

komutuje, więc mamy natychmiast $1_{A}=(!_{A}\circ f)\circ A$ oraz $1_{\mathbf {1} }=A\circ (!_{A}\circ f)$, co ustanawia żądany izomorfizm $\mathbf {1} \cong A$.

• Dowodzimy, że dowolna strzałka $f\colon A\to \mathbf {0}$ jest mono. To bardzo proste zadanie: ponieważ strzałka typu $\mathbf {0} \to \mathbf {0}$ jest tylko jedna, więc musi być $!_{A}\circ f=1_{\mathbf {0} }$. To równanie mówi, że $f$ jest sekcją, czyli w szczególności jest monomorfizmem.
• Aby dowieść $[A,\mathbf {1} ]\cong \mathbf {1}$, rozważmy diagram:

z którego wynika, że

$(\mathrm {curry} (\mathbf {1} \times A)\times 1_{A})\circ ([A,\mathbf {1} ]\times 1_{A})=(\mathrm {curry} (\mathbf {1} \times A)\circ [A,\mathbf {1} ])\times 1_{A}$

jest jedyną strzałką, która sprawia, że zewnętrzna część diagramu komutuje. Zgodnie z definicją eksponentu musi zatem być:

$\mathrm {curry} (\mathbf {1} \times A)\circ [A,\mathbf {1} ]=1_{[A,\mathbf {1} ]}.$

Drugi komutujący diagram

daje natychmiast:

Parser nie mógł rozpoznać (błąd składni): {\displaystyle 1_{\mathbf{1}}\times 1_A &=& 1_{\mathbf{1}\times A}=([A,\mathbf{1}]\times 1_A)\circ (\mathrm{curry}(\mathbf{1}\times A)\times 1_A)=([A,\mathbf{1}]\circ \mathrm{curry}(\mathbf{1}\times A))\times 1_A,}

skąd łatwo już wynika:

$1_{\mathbf {1} }=[A,\mathbf {1} ]\circ \mathrm {curry} (\mathbf {1} \times A).$

• Pokazujemy $[1,A]\cong A$, korzystając z wniosku z lematu Yonedy, który znajdziemy w Zadaniu 7.2. Niech $Z$ będzie dowolnym obiektem $\mathbf {C}$. Wtedy

$\mathrm {Hom} _{\mathbf {C} }(Z,[\mathbf {1} ,A])\cong \mathrm {Hom} _{\mathbf {C} }(Z\times \mathbf {1} ,A)\cong \mathrm {Hom} _{\mathbf {C} }(Z,A),$

gdzie wykorzystaliśmy łatwy fakt, że $Z\times \mathbf {1} \cong Z$ i każdy funktor, w szczególności $\mathrm {Hom} (-,A)$, zachowuje izomorfizmy. Obydwa izomorfizmy powyżej są naturalne (dowód tego faktu jest łatwy lecz uciążliwy i będziemy go konsekwentnie pomijać), a zatem założenia Zadania 7.2 są spełnione. Wyciągamy wniosek, że $[\mathbf {1} ,A]\cong A$.

• Aby pokazać $[A\times B,C]\cong [A,[B,C]]$, niech $Z$ będzie dowolnym obiektem $\mathbf {C}$. Wtedy

$\mathrm {Hom} _{\mathbf {C} }(Z,[A\times B,C])\cong \mathrm {Hom} _{\mathbf {C} }(Z\times A\times B,C)\cong \mathrm {Hom} _{\mathbf {C} }(Z\times A,[B,C])\cong \mathrm {Hom} _{\mathbf {C} }(Z,[A,[B,C]]),$

skąd wyciągamy wniosek, że $[A\times B,C]\cong [A,[B,C]]$. (To równanie dla liczb naturalnych sprowadza się do prawa potęgowania $c^{a\cdot b}=(c^{b})^{a}$).

• Pokazujemy, że $[A,B]\times [A,C]\cong [A,B\times C]$: dla dowolnego $Z\in \mathbf {C} _{0}$ mamy

$\mathrm {Hom} _{\mathbf {C} }(Z,[A,B]\times [A,C])\cong \mathrm {Hom} _{\mathbf {C} }(Z,[A,B])\times \mathrm {Hom} _{\mathbf {C} }(Z,[A,C])\cong \mathrm {Hom} _{\mathbf {C} }(Z\times A,B)\times \mathrm {Hom} _{\mathbf {C} }(Z\times A,C)\cong \mathrm {Hom} _{\mathbf {C} }(Z\times A,B\times C)\cong \mathrm {Hom} _{\mathbf {C} }(Z,[A,B\times C]).$

Oprócz metody rozwiązania zaczerpniętej z Zadania 7.2, użyliśmy również dwukrotnie faktu, że hom-funktor zachowuje produkty, który wykazaliśmy w Zadaniu 3.5.

==Zadanie 4.4==

Udowodnij Fakt 4.5.

Rozwiązanie:

Pokażemy, że w kracie dystrybutywnej zachodzi prawo:

$x\vee (y\wedge z)=(x\vee y)\wedge (x\vee z).$

Rzeczywiście,

$(x\vee y)\wedge (x\vee z)=((x\vee y)\wedge x)\vee ((x\vee y)\wedge z)=x\vee ((x\vee y)\wedge z)=x\vee ((x\wedge z)\vee (y\wedge z))=(x\vee (x\wedge z))\vee (y\wedge z)=x\vee (y\wedge z).$

==Zadanie 4.5==

Udowodnij Fakt 4.7.

Rozwiązanie:

Pokażemy, że w kracie dystrybutywnej element przeciwny do $x$ jest jedyny. Przypuśćmy, że $a,a'$ są przeciwne do $x$. Wówczas

$a=a\vee \mathbf {0} =a\vee (x\wedge a')=(a\vee x)\wedge (a\vee a')=\mathbf {1} \wedge (a\vee a')=a\vee a'.$

W ten sam sposób otrzymamy równość $a'=a'\vee a$, co oznacza

$a=a\vee a'=a'\vee a=a'.$

==Zadanie 4.6==

Udowodnij Fakt 4.9.

Rozwiązanie:

Niech $L$ będzie dowolną algebrą Boole'a i niech $x,y,z\in L$.

• Aby pokazać $\neg (x\vee y)=\neg x\wedge \neg y,$ zauważmy najpierw, że $\mathbf {0} =(\mathbf {0} \wedge z)\vee \mathbf {0}$, więc $(\mathbf {0} \wedge z)\leq \mathbf {0}$, co daje $(\mathbf {0} \wedge z)=\mathbf {0}$, bo $\mathbf {0}$ jest elementem najmniejszym. Dualnie dostajemy dowód $(\mathbf {1} \vee z)=\mathbf {1}$. Mając dane te dwie równości, obliczamy - po pierwsze:

$(x\vee y)\wedge (\neg x\wedge \neg y)=(x\wedge \neg x\wedge \neg y)\vee (y\wedge \neg x\wedge \neg y)=(\mathbf {0} \wedge \neg y)\vee (\mathbf {0} \wedge \neg x)=\mathbf {0} \vee \mathbf {0} =\mathbf {0} .$

Po drugie:

$(x\vee y)\vee (\neg x\wedge \neg y)=(x\vee \neg x\vee \neg y)\wedge (y\vee \neg x\vee \neg y)=(\mathbf {1} \vee \neg y)\wedge (\mathbf {1} \vee \neg x)=\mathbf {1} \wedge \mathbf {1} =\mathbf {1} .$

To świadczy o tym, że $\neg x\wedge \neg y$ jest elementem odwrotnym do $x\vee y$, co należało pokazać.

• Dowód równości $\neg (x\wedge y)=\neg x\vee \neg y$ jest dualny do poprzedniego, tzn. wystarczy zaaplikować dowód poprzedni do kraty $L^{op}$.
• Równość $\neg \neg x=x$ - proszę to zauważyć! - jest innym sformułowaniem definicji elementu przeciwnego.

==Zadanie 4.7==

Udowodnij Fakt 4.11.

Rozwiązanie:

Aby pokazać, że w dowolnej algebrze Boole'a mamy:

$z\leq (\neg x\vee y)\iff z\wedge x\leq y,$

wykażemy zdanie równoważne, a mianowicie, że $\neg x\vee y=\bigvee A$, gdzie $A=\{z\in L\mid z\wedge x\leq y\}$. Po pierwsze:

$(\neg x\vee y)\wedge x=(\neg x\wedge x)\vee (y\wedge x)=y\wedge x\leq y,$

co daje $\neg x\vee y\in A$. Po drugie: jeśli $z\in A$, to $z\wedge x\leq y$, co implikuje $\neg x\vee (z\wedge x)\leq \neg x\vee y$. A zatem: z\leq \neg x\vee z = (\neg x\vee z)\wedge(\neg x\vee x) = \neg x\vee (z\wedge x)\leq \neg x\vee y. Pokazaliśmy zatem, że $\neg x\vee y$ jest ograniczeniem górnym zbioru $A$. Ten element należy do $A$, więc jest supremum $A$.

==Zadanie 4.8==

Udowodnij Fakt 4.12.

Rozwiązanie:

Pokażemy, że w dowolnej algebrze Heytinga $L$, jeśli dla $x\in L$ istnieje $\neg x$, to musi być $\neg x=x\Rightarrow \mathbf {0}$. Załóżmy zatem, że $x$ ma element przeciwny. Skoro $\neg x\wedge x=\mathbf {0} \leq \mathbf {0}$, to z definicji implikacji, $\neg x\leq x\Rightarrow \mathbf {0}$. Aby udowodnić nierówność w przeciwną stronę, co skończy dowód, zauważmy najpierw, że $(x\Rightarrow \mathbf {0} )\wedge x=\mathbf {0}$. A zatem:

$x\Rightarrow \mathbf {0} =(x\Rightarrow \mathbf {0} )\wedge (x\vee \neg x)=((x\Rightarrow \mathbf {0} )\wedge x)\vee ((x\Rightarrow \mathbf {0} )\wedge \neg x)=\mathbf {0} \vee ((x\Rightarrow \mathbf {0} )\wedge \neg x)=(x\Rightarrow \mathbf {0} )\wedge \neg x,$

co oznacza przecież, że $x\Rightarrow \mathbf {0} \leq \neg x$.

==Zadanie 4.9==

Udowodnij Fakt 4.13.

Rozwiązanie:

Pierwsze dwa stwierdzenia są trywialne. Równości: trzecia: $(x\Rightarrow \mathbf {1} )=\mathbf {1}$, czwarta: $(\mathbf {1} \Rightarrow x)=x$, piąta: $(y\wedge z)\Rightarrow x=(z\Rightarrow (y\Rightarrow x))$, szósta: $(x\Rightarrow (y\wedge z))=(x\Rightarrow y)\wedge (x\Rightarrow z)$, zostały dowiedzione dla dowolnej kategorii kartezjańsko zamkniętej w Zadaniu 4.3. Siódma nierówność $\mathbf {1} \leq x\Rightarrow x$ jest trywialna, ósma: $\mathbf {1} \leq (x\Rightarrow (y\Rightarrow x))$ też, pozostaje do wykazania:

$\mathbf {1} \leq (x\Rightarrow (y\Rightarrow z))\Rightarrow ((x\Rightarrow y)\Rightarrow (x\Rightarrow z)),$

które to zdanie dowodzimy następująco: skoro $(y\Rightarrow z)\wedge y\leq z$, to $x\Rightarrow ((y\Rightarrow z)\wedge y)\leq x\Rightarrow z$, bo podnoszenie do potęgi jest funktorem - patrz Zadanie 4.1. Zadanie 4.3, część (8) daje zatem:

$(x\Rightarrow (y\Rightarrow z))\wedge (x\Rightarrow y)\leq x\Rightarrow z,$

co jest równoważne:

$(x\Rightarrow (y\Rightarrow z))\leq (x\Rightarrow y)\Rightarrow (x\Rightarrow z)$

i w końcu:

$\mathbf {1} \wedge (x\Rightarrow (y\Rightarrow z))\leq (x\Rightarrow y)\Rightarrow (x\Rightarrow z)$

oraz:

$\mathbf {1} \leq (x\Rightarrow (y\Rightarrow z))\Rightarrow ((x\Rightarrow y)\Rightarrow (x\Rightarrow z)).$

==Zadanie 4.10==

Udowodnij, że jeśli kartezjańsko zamknięta kategoria $\mathbf {C}$ ma koprodukty, to jest dystrybutywna, tzn. istnieje naturalny izomorfizm:

$A\times (B+C)\cong (A\times B)+(A\times C).$

Wskazówka:

Niezwykle użyteczny jest dualny wniosek do wniosku z lematu Yonedy, który to znajdziemy w Zadaniu 7.2.

Rozwiązanie:

Znamy już metodę rozwiązania. Wystarczy nam zatem następujący ciąg izomorfizmów prawdziwy dla dowolnego $Z\in \mathbf {C} _{0}$:

$\mathrm {Hom} _{\mathbf {C} }(A\times (B+C),Z)\cong \mathrm {Hom} _{\mathbf {C} }((B+C)\times A,Z)\cong \mathrm {Hom} _{\mathbf {C} }((B+C),[A,Z])\cong \mathrm {Hom} _{\mathbf {C} }(B,[A,Z])+\mathrm {Hom} _{\mathbf {C} }(C,[A,Z])\cong \mathrm {Hom} _{\mathbf {C} }(B\times A,Z)+\mathrm {Hom} _{\mathbf {C} }(C\times A,Z)\cong \mathrm {Hom} _{\mathbf {C} }(A\times B,Z)+\mathrm {Hom} _{\mathbf {C} }(A\times C,Z)\cong \mathrm {Hom} _{\mathbf {C} }((A\times B)+(A\times C),Z).$

Zwróćmy uwagę, że wykorzystaliśmy tu w kluczowych momentach twierdzenie dualne do Zadania 3.5, czyli fakt, że hom-funktor $\mathrm {Hom} _{\mathbf {C} }(-,Z)$ zachowuje koprodukty.