\documentclass{article}
\input{packages}
\input{def}

\homework{Transformations}

\begin{document}
\maketitle

\begin{exercise}
Prove that for any category $\cat{C}$ and any object $\ob{C} : \cat{C}$, the category $\cat{Sub}(\ob{C})$ is thin, meaning there is at most one morphism between any two objects.
\end{exercise}

\begin{proof}
Let $\mo{m}_1 : \ob{S}_1 \mono \ob{C}$ and $\mo{m}_2 : \ob{S}_2 \mono \ob{C}$ be objects of $\cat{Sub}(\ob{C})$, and let $\mo{f}_1$ and $\mo{f}_2$ be morphisms from $\langle \ob{S}_1, \mo{m}_1 \rangle$ to $\langle \ob{S}_2, \mo{m}_2 \rangle$. By definition, the means $\mo{f}_1 \cocomp \mo{m}_2$ equals $\mo{m}_1$ and $\mo{f}_2 \cocomp \mo{m}_2$ equals $\mo{m}_1$. Thus, $\mo{f}_1 \cocomp \mo{m}_2$ equals $\mo{f}_2 \cocomp \mo{m}_2$. In order to be object of $\cat{Sub}(\ob{C})$, $\mo{m}_2$ must be a monomorphism. By the definition of monomorphism, the equality $\mo{f}_1 \cocomp \mo{m}_2 = \mo{f}_2 \cocomp \mo{m}_2$ implies $\mo{f}_1$ equals $\mo{f}_2$, thereby guaranteeing thinness.
\end{proof}

\begin{exercise}
Prove that $\cat{Prost}$ is a reflective subcategory of $\cat{Rel}(2)$ (the category whose objects are sets with a binary relation and whose morphisms are relation-preserving functions).
\end{exercise}

\begin{proof}
Given a set $X$ with a binary relation $R : X \times X \to \Prop$, define $\leq_R$ to be the reflexive-transitive closure of $R$.
The identity function $X$ is a relation-preserving function from $\langle X, R \rangle$ to $\langle X, \leq_R \rangle$ by the definition of closure.
Suppose $f$ is a relation-preserving function from $\langle X, R \rangle$ to $\langle Y, \sqsubseteq \rangle$, and $\sqsubseteq$ is a reflexive, transitive relation.
Then $f(x) \sqsubseteq f(x)$ due to reflexivity, and given a chain $x_1 \mathrel{R} \dots \mathrel{R} x_n$ we know $f(x_1) \sqsubseteq \dots \sqsubseteq f(x_n)$ and so $f(x_1) \sqsubseteq f(x_n)$ by transitivity.
Therefore, $f$ is also a relation-preserving function from $\langle X, \leq_R \rangle$ to $\langle Y, \sqsubseteq \rangle$ by the definition of reflexive-transitive closure.
\end{proof}

\begin{exercise}
Suppose a subcategory $\cat{S} \xmono{I} \cat{C}$ has a mapping from each object $\ob{C} : \cat{C}$ to a reflection arrow $\ob{C} \xmto{\mo{r}_\ob{C}} I(R(\ob{C}))$.
Prove that there is a unique way to extend the function $R$ to a functor from $\cat{C}$ to $\cat{S}$ such that the reflection arrows form a natural transformation $\mo{r} : \cat{C} \nto R \cocomp I$.
\end{exercise}

\begin{proof}
Given a $\cat{C}$-morphism $\mo{f} : \ob{C}_1 \mto \ob{C}_2$, define $R(\mo{f})$ to be the unique morphism $(\mo{f} \cocomp \mo{r}_{\ob{C}_2})^\rtol$ with the property that $\mo{r}_{\ob{C}_1} \cocomp I((\mo{f} \cocomp \mo{r}_{\ob{C}_2})^\rtol) = \mo{f} \cocomp \mo{r}_{\ob{C}_2}$ guaranteed to exist because $\mo{r}_{\ob{C}_1}$ is a reflection arrow. By construction, this makes $\mo{r}$ a natural transformation from $\cat{C}$ to $R \cocomp I$. Simililary, uniqueness of $(\mo{f} \cocomp \mo{r}_{\ob{C}_2})^\rtol$ guarantees uniqueness of $R$. All that is left to prove is that $R$ is a functor. By definition, $R(\mo{f} \cocomp \mo{g})$ is the unique morphism with the property that $\mo{r}_{\ob{C}_1} \cocomp I(R(\mo{f} \cocomp \mo{g}))$ equals $(\mo{f} \cocomp \mo{g}) \cocomp \mo{r}_{\ob{C}_3}$. The chain of equalities $\mo{r}_{\ob{C}_1} \cocomp I(R(\mo{f}) \cocomp R(\mo{g})) = \mo{r}_{\ob{C}_1} \cocomp I(R(\mo{f})) \cocomp I(R(\mo{g})) = \mo{f} \cocomp \mo{r}_{\ob{C}_2} \cocomp I(R(\mo{g})) = \mo{f} \cocomp \mo{g} \cocomp \mo{r}_{\ob{C}_3}$ shows that $R(\mo{f}) \cocomp R(\mo{g})$ also enjoys this property and so must equal $R(\mo{f} \cocomp \mo{g})$. Similarly, the chain of equalities $\mo{r}_{\ob{C}} \cocomp I(\id_{R(\ob{C})}) = \mo{r}_{\ob{C}} \cocomp \id_{I(R(\ob{C}))} = \mo{r}_{\ob{C}} = \id_{\ob{C}} \cocomp \mo{r}_{\ob{C}}$ implies that $\id_{R(\ob{C})}$ equals $R(\id_\ob{C})$.
\end{proof}

\begin{exercise}
Prove that the category $\cat{Cat}$ can be enriched in the multicategory $\cat{CAT}$.
\end{exercise}

\begin{proof}
We present the biased enrichment:
\begin{framed}
\begin{description}
\item[Objects:] The class of small categories
\item[Morphisms:] Given small categories $\cat{C}$ and $\cat{D}$, the corresponding object of morphisms is the category of functors and natural transformations $\cat{C} \expto \cat{D}$
\item[Compositions $\mo{c}$:] Define composition to be the binary functor from $[\cat{C} \expto \cat{D}, \cat{D} \expto \cat{E}]$ to $\cat{C} \expto \cat{E}$ that maps $\langle F : \cat{C} \mto \cat{D}, G : \cat{D} \mto \cat{E} \rangle$ to $F \cocomp G : \cat{C} \mto \cat{E}$ and $\langle \alpha : F_1 \nto F_2, \beta : G_1 \nto G_2 \rangle$ to $\alpha \cdot \beta : F_1 \cocomp G_1 \nto F_2 \cocomp G_2$ where $(\alpha \cdot \beta)_\ob{C}$ is any path in the diagram below, which commutes due to naturality of $\beta$:
\begin{center}
\begin{tikzpicture}
\node(f1g1) at (-1.5,1) {$G_1(F_1(\ob{C}))$};
\node(f2g1) at (1.5,1) {$G_1(F_2(\ob{C}))$};
\node(f1g2) at (-1.5,-1) {$G_2(F_1(\ob{C}))$};
\node(f2g2) at (1.5,-1) {$G_2(F_2(\ob{C}))$};
\draw[->] (f1g1) -- node[above] {$G_1(\alpha_\ob{C})$} (f2g1);
\draw[->] (f1g1) -- node[left] {$\beta_{F_1(\ob{C})}$} (f1g2);
\draw[->] (f2g1) -- node[right] {$\beta_{F_2(\ob{C})}$} (f2g2);
\draw[->] (f1g2) -- node[below] {$G_2(\alpha_\ob{C})$} (f2g2);
\draw[->] (f1g1) -- node[sloped,above] {$(\alpha \cdot \beta)_\ob{C}$} (f2g2);
\end{tikzpicture}
\end{center}
$\alpha \cdot \beta$ is a natural transformation since $G_1(F_1(\mo{c})) \cocomp (\alpha \cdot \beta)_{\ob{C}_2} = G_1(F_1(\mo{c})) \cocomp \beta_{F_1(\ob{C}_2)} \cocomp G_2(\alpha_\ob{C}_2) = \beta_{F_1(\ob{C}_1)} \cocomp G_2(F_1(\mo{c})) \cocomp G_2(\alpha_\ob{C}_2) = \beta_{F_1(\ob{C}_1)} \cocomp G_2(F_1(\mo{c}) \cocomp \alpha_\ob{C}_2) = \beta_{F_1(\ob{C}_1)} \cocomp G_2(\alpha_{\ob{C}_1} \cocomp F_2(\mo{c})) = \beta_{F_1(\ob{C}_1)} \cocomp G_2(\alpha_{\ob{C}_1}) \cocomp G_2(F_2(\mo{c})) = (\alpha \cdot \beta)_{\ob{C}_1} \cocomp G_2(F_2(\mo{c}))$ holds for any $\mo{c} : \ob{C}_1 \mto \ob{C}_2$.

To be a functor this process needs to distribute over composition of natural transformations in $\cat{C} \expto \cat{D}$ (and preserve identities, which I show later). So, we need to show $(\alpha \cocomp \alpha') \cdot (\beta \cocomp \beta')$ equals $(\alpha \cdot \beta) \cocomp (\alpha' \cdot \beta')$. Consider the following two diagrams:
\begin{center}
\begin{tikzpicture}
\node(f1g1) at (-3,2) {$G_1(F_1(\ob{C}))$};
\node(f2g1) at (0,2) {$G_1(F_2(\ob{C}))$};
\node(f3g1) at (3,2) {$G_1(F_3(\ob{C}))$};
\node(f1g2) at (-3,0) {$G_2(F_1(\ob{C}))$};
\node(f2g2) at (0,0) {$G_2(F_2(\ob{C}))$};
\node(f3g2) at (3,0) {$G_2(F_3(\ob{C}))$};
\node(f1g3) at (-3,-2) {$G_3(F_1(\ob{C}))$};
\node(f2g3) at (0,-2) {$G_3(F_2(\ob{C}))$};
\node(f3g3) at (3,-2) {$G_3(F_3(\ob{C}))$};
\draw[->] (f1g1) -- node[above] {$G_1(\alpha_\ob{C})$} (f2g1);
\draw[->] (f2g1) -- node[above] {$G_1(\alpha'_\ob{C})$} (f3g1);
\draw[->] (f1g1) -- node[left] {$\beta_{F_1(\ob{C})}$} (f1g2);
\draw[->] (f2g1) -- node[right] {$\beta_{F_2(\ob{C})}$} (f2g2);
\draw[->] (f3g1) -- node[right] {$\beta_{F_3(\ob{C})}$} (f3g2);
\draw[->] (f1g2) -- node[below] {$G_2(\alpha_\ob{C})$} (f2g2);
\draw[->] (f2g2) -- node[above] {$G_2(\alpha'_\ob{C})$} (f3g2);
\draw[->] (f1g2) -- node[left] {$\beta'_{F_1(\ob{C})}$} (f1g3);
\draw[->] (f2g2) -- node[right] {$\beta'_{F_2(\ob{C})}$} (f2g3);
\draw[->] (f3g2) -- node[right] {$\beta'_{F_3(\ob{C})}$} (f3g3);
\draw[->] (f1g3) -- node[below] {$G_3(\alpha_\ob{C})$} (f2g3);
\draw[->] (f2g3) -- node[below] {$G_3(\alpha'_\ob{C})$} (f3g3);
\draw[->] (f1g1) -- node[sloped,above] {$(\alpha \cdot \beta)_\ob{C}$} (f2g2);
\draw[->] (f2g2) -- node[sloped,above] {$(\alpha' \cdot \beta')_\ob{C}$} (f3g3);
\end{tikzpicture}
\begin{tikzpicture}
\node(f1g1) at (-3,2) {$G_1(F_1(\ob{C}))$};
\node(f3g1) at (3,2) {$G_1(F_3(\ob{C}))$};
\node(f1g3) at (-3,-2) {$G_3(F_1(\ob{C}))$};
\node(f3g3) at (3,-2) {$G_3(F_3(\ob{C}))$};
\draw[->] (f1g1) -- node[above] {$G_1((\alpha \cocomp \alpha')_\ob{C})$} (f3g1);
\draw[->] (f1g1) -- node[right] {$(\beta \cocomp \beta')_{F_1(\ob{C})}$} (f1g3);
\draw[->] (f3g1) -- node[left] {$(\beta \cocomp \beta')_{F_3(\ob{C})}$} (f3g3);
\draw[->] (f1g3) -- node[below] {$G_3((\alpha \cocomp \alpha')_\ob{C})$} (f3g3);
\draw[->] (f1g1) -- node[sloped,above] {$((\alpha \cocomp \beta) \cdot (\alpha' \cocomp \beta'))_\ob{C}$} (f3g3);
\end{tikzpicture}
\end{center}
Both diagrams commute due to naturality and the definition of $\cdot$. Notice that the left wall of both diagrams are equal due to the definition of $\cocomp$ on natural transformations and the distributivity of $G_1$. Similarly for the other three walls. Thus the two diagonals must be equal. Since the left diagrams's diagonal is $((\alpha \cdot \beta) \cocomp (\alpha' \cdot \beta'))_\ob{C}$ by definition of $\cocomp$, this proves $(\alpha \cocomp \alpha') \cdot (\beta \cocomp \beta')$ equals $(\alpha \cdot \beta) \cocomp (\alpha' \cdot \beta')$.

Lastly, this process preserves identities: $$(\id_F \cdot \id_G)_\ob{C} = G(\id_{F(\ob{C})}) \cocomp \id_{G(F(\ob{C}))} = \id_{G(F(\ob{C}))} \cocomp \id_{G(F(\ob{C}))} = \id_{G(F(\ob{C}))} = (\id_{F \cocomp G})_\ob{C}$$
\item[Associativity $\prf{a}$:] We need to show that $(F \cocomp G) \cocomp H$ equals $F \cocomp (G \cocomp H)$, which is already known since $\cat{Cat}$ is a category and so composition is associative, and that $(\alpha \cdot \beta) \cdot \gamma$ equals $\alpha \cdot (\beta \cdot \gamma)$. Consider the following cubes:
\begin{center}
\hspace{-.5in}
$(\prf{a})$
\begin{tikzpicture}[scale=1.25,baseline=5mm]
\node(111) at (0,3) {$H_1(G_1(F_1(\ob{C})))$};
\node(211) at (4,3) {$H_1(G_1(F_2(\ob{C})))$};
\node(121) at (0,0) {$H_1(G_2(F_1(\ob{C})))$};
\node(221) at (4,0) {$H_1(G_2(F_2(\ob{C})))$};
\node(112) at (1,1) {$H_2(G_1(F_1(\ob{C})))$};
\node(212) at (5,1) {$H_2(G_1(F_2(\ob{C})))$};
\node(122) at (1,-2) {$H_2(G_2(F_1(\ob{C})))$};
\node(222) at (5,-2) {$H_2(G_2(F_2(\ob{C})))$};
\draw[->] (111) -- node[above] {$H_1(G_1(\alpha_\ob{C}))$} (211);
\draw[->] (112) -- node[below] {$H_2(G_1(\alpha_\ob{C}))$} (212);
\draw[->] (121) -- node[above] {$H_1(G_2(\alpha_\ob{C}))$} (221);
\draw[->] (122) -- node[below] {$H_2(G_2(\alpha_\ob{C}))$} (222);
\draw[->] (111) -- node[left] {$H_1(\beta_{F_1(\ob{C})})$} (121);
\draw[->] (211) -- node[left] {$H_1(\beta_{F_2(\ob{C})})$} (221);
\draw[->] (112) -- node[right] {$H_2(\beta_{F_1(\ob{C})})$} (122);
\draw[->] (212) -- node[right] {$H_2(\beta_{F_2(\ob{C})})$} (222);
\draw[->] (111) -- node[sloped,above] {$\gamma_{G_1(F_1(C))}$} (112);
\draw[->] (211) -- node[sloped,above] {$\gamma_{G_1(F_2(C))}$} (212);
\draw[->] (121) -- node[sloped,below] {$\gamma_{G_2(F_1(C))}$} (122);
\draw[->] (221) -- node[sloped,below] {$\gamma_{G_2(F_2(C))}$} (222);
\end{tikzpicture}
\begin{tabular}{@{}c@{}}%
\begin{tikzpicture}[scale=.85]
\node at (-.5,1) {$(\prf{b})$};
\node(111) at (0,3) {};
\node(211) at (5,3) {};
\node(121) at (0,0) {};
\node(221) at (5,0) {};
\node(112) at (1.5,1.5) {};
\node(212) at (6.5,1.5) {};
\node(122) at (1.5,-1.5) {};
\node(222) at (6.5,-1.5) {};
\draw[->] (111) -- (211);
\draw[->] (112) -- (212);
\draw[->] (121) -- (221);
\draw[->] (122) -- (222);
\draw[->] (111) -- (121);
\draw[->] (211) -- (221);
\draw[->] (112) -- (122);
\draw[->] (212) -- (222);
\draw[->] (111) -- node[sloped,below] {~~~~\small $\gamma_{G_1(F_1(C))}$} (112);
\draw[->] (211) -- (212);
\draw[->] (121) -- (122);
\draw[->] (221) -- node[sloped,above] {\small $\gamma_{G_2(F_2(C))}$~~~~} (222);
\draw[->] (111) -- node[sloped,above] {\small $H_1((\alpha \cdot \beta)_\ob{C})$} (221);
\draw[->] (112) -- node[sloped,below] {\small $H_2((\alpha \cdot \beta)_\ob{C})$} (222);
\end{tikzpicture}%
\\%
\begin{tikzpicture}[scale=.85]
\node at (-.5,1) {$(\prf{c})$};
\node(111) at (0,3) {};
\node(211) at (5,3) {};
\node(121) at (0,0) {};
\node(221) at (5,0) {};
\node(112) at (1.5,1.5) {};
\node(212) at (6.5,1.5) {};
\node(122) at (1.5,-1.5) {};
\node(222) at (6.5,-1.5) {};
\draw[->] (111) -- node[above] {\small $H_1(G_1(\alpha_\ob{C}))$} (211);
\draw[->] (112) -- (212);
\draw[->] (121) -- (221);
\draw[->] (122) -- node[below] {\small $H_1(G_1(\alpha_\ob{C}))$} (222);
\draw[->] (111) -- (121);
\draw[->] (211) -- (221);
\draw[->] (112) -- (122);
\draw[->] (212) -- (222);
\draw[->] (111) -- (112);
\draw[->] (211) -- (212);
\draw[->] (121) -- (122);
\draw[->] (221) -- (222);
\draw[->] (111) -- node[sloped,above] {$\small (\beta \cdot \gamma)_{F_1(\ob{C})}$~~} (122);
\draw[->] (211) -- node[sloped,below] {~~~~$\small (\beta \cdot \gamma)_{F_2(\ob{C})}$} (222);
\end{tikzpicture}%
\end{tabular}
\end{center}
Cube~$(\prf{a})$ commutes due to naturality and functoriality. It indicates the missing labels for cubes $(\prf{b})$ and~$(\prf{c})$, which also commute by the definition of $\cdot$. $((\alpha \cdot \beta) \cdot \gamma)_\ob{C}$ is defined to be the diagonal of cube~$(\prf{b})$, and $(\alpha \cdot (\beta \cdot \gamma))_\ob{C}$ is defined to be the diagonal of cube~$(\prf{c})$.
Both of those are the diagonals of cube~$(\prf{a})$ and so must be equal, proving associativity.
\item[Identities $\mo{i}$:] For each small category~$\cat{C}$, we need to select an object of $\cat{C} \expto \cat{C}$. We select the identity functor.
\item[Identity $\prf{i}$:] We need to show that $\mathit{Id}_\cat{C} \cocomp F = F = F \cocomp \mathit{Id}_\cat{D}$, which is true since $\cat{Cat}$ is a category and we are using its identities, and that $\mathit{Id}_\cat{C} \cdot \alpha = \alpha = \alpha \cdot \mathit{Id}_\cat{D}$: $$(\id_{\mathit{Id}_\cat{C}} \cdot \alpha)_\ob{C} = F_1(\id_{\ob{C}}) \cocomp \alpha_{\mathit{Id}_\cat{C}(\ob{C})} = \id_{F_1(\ob{C})} \cocomp \alpha_\ob{C} = \alpha_\ob{C} = \alpha_\ob{C} \cocomp \id_{F_2(\ob{C})} = \mathit{Id}_\cat{D}(\alpha_\ob{C}) \cocomp \id_{\mathit{Id}_\cat{D}(F_2(\ob{C}))} = (\alpha \cdot \id_{\mathit{Id}_\cat{D}})_\ob{C}$$
\end{description}
\end{framed}
\end{proof}

\end{document}