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

From Studia Informatyczne

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

Grafika:tk-4.3.png

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

Grafika:tk-4.4.png


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:
Grafika:tk-4.5.png

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):
Grafika:tk-4.7.png

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:
Grafika:tk-4.8.png

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

Grafika:tk-4.9.png

daje natychmiast:

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.