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

\homework{Categories}

\begin{document}
\maketitle

\begin{exercise}
Give, for any category~$\cat{C}$ and any object~$\ob{C} : \cat{C}$, a monoidal structure on the set~$\ob{C} \mto \ob{C}$.
\end{exercise}

\begin{proof}
The operator is~$\cocomp$, which is a total function because the domain and codomain of all elements of $\ob{C} \mto \ob{C}$ are the same.
It is associative because composition is associative in categories.
The identity is $\id_\ob{C}$, which is a (left and right) identity of the monoid due to its categorical requirements because each morphism is both from $\ob{C}$ and to $\ob{C}$.
\end{proof}

\begin{exercise}
Prove that for any monoid~$\alg{M}$ there is a category with one object~$\star$ such that $\star \mto \star$ equals~$M$.
\end{exercise}

\begin{proof}
The only triple of objects is $\langle \star, \star, \star \rangle$, so composition need only be a function from $\star \mto \star \times \star \mto \star \to \star \mto \star$. This is simply, $M \times M \to M$, so we can use $*_\alg{M}$.
Composition is associative because multiplication in monoids is associative.
Define $\id_\star$ (and therefore all identities) to be $e_\alg{M}$, which is both a left and right identity with respect to composition because $e_\alg{M}$ is an identity with respect to multiplication.
\end{proof}

\begin{exercise}
Show that the above extends to a functor from~$\cat{Mon}_b$ to~$\cat{Cat}$.
\end{exercise}

\begin{proof}
This requires showing that a monoid homomorphism $\langle f, \noprf \rangle$ from $\langle M, *, \noprf, 1, \noprf \rangle$ to $\langle N, +, \noprf, 0, \noprf \rangle$ gives a functor from $\langle \{\star\}, \lambda \langle \star, \star \rangle.\; M, \lambda \star, \star, \star \rangle,\; *, \noprf, \lambda \star.\; 1, \noprf \rangle$ to $\langle \{\star\}, \lambda \langle \star, \star \rangle.\; N, \lambda \star, \star, \star \rangle,\; +, \noprf, \lambda \star.\; 0, \noprf \rangle$:
\begin{description}
\item[Mapping of Objects] The object $\star$ is mapped to $\star$.
\item[Mapping of Morphisms] For the domain $\star$ and codomain $\star$, the morphism $m : M$ is mapped to the morphism $f(m) : N$ from $f(\star) = \star$ to $f(\star) = \star$.
\item[Preservation of Composition] Given morphisms $\star \xmto{m_1} \star \xmto{m_2} \star$, $$f(m_1 \cocomp m_2) = f(m_1 * m_2) = f(m_1) + f(m_2) = f(m_1) \cocomp f(m_2)$$
\item[Preservation of Identity] Given an object $\star$, $$f(\id_\star) = f(1) = 0 = \id_\star = \id_{f(\star)}$$
\end{description}
\end{proof}

\begin{exercise}
Show that there is a functor~$F : \cat{Set} \mto \cat{Mon}$ and a functor~$U : \cat{Mon} \mto \cat{Set}$ such that $F \cocomp U$ equals $\List$. Hint: $U$~maps a monoid to its underlying set.
\end{exercise}

\begin{proof}
Define the functor $U$ to map each monoid to its underlying set and each monoid homomorphism to its underlying function. Composition and identity are preserved because composition and identity of monoid homomorphisms are defined as composition and identity of functions.

Define the functor $F$ to map each set $S$ to the monoid $(\List S)_{\append}$ and to map each function $f$ to the monoid homomorphism $\texttt{map}_f$.
$\texttt{map}_f$ is a monoid homomorphism since it maps the empty list (the identity of $\append$) to the empty list and it maps the composition of two lists to the composition of what those two lists map to.
$F$ preserves composition and identity for the same reason $\List$ does because composition and identity in $\cat{Mon}_b$ are inherited from $\cat{Set}$.
That is, $F$ produces monoid homomorphisms functorially because $\texttt{map}_f$ operates componentwise and preserves the structure of a list.
\end{proof}

\begin{exercise}
Prove that any category that has exactly one functor to it from each other category must be isomorphic to the category~$\cat{1}$.
\end{exercise}

\begin{proof}
$\cat{1}$ has only one object and only one morphism.
Let $I$ be the unique functor from $\cat{1}$ to the other category, and let $J$ be the functor from that category to $\cat{1}$ mapping everything to the unique object or morphism.
By definition of $J$, the endofunctor $I \cocomp J$ on $\cat{1}$ maps the unique object and morphism to the unique object and morphism, making it equal to the identity functor on $\cat{1}$.
$J \cocomp I$ is a functor from the other category to itself, and so is the identity functor, so by the assumed uniqueness property of the other category, these two functors must be equal.
Thus, $I$ and $J$ are inverses of each other, making the other category isomorphic to $\cat{1}$.
\end{proof}

\begin{exercise}
Prove that any category that has exactly one functor from it to each other category must be isomorphic to the category~$\cat{0}$.
\end{exercise}

\begin{proof}
$\cat{0}$ has no objects and no morphisms.
Let $I$ be the unique functor from the other category to $\cat{0}$, and let $J$ be the functor from $\cat{0}$ to that category mapping nothing.
By definition of $J$, the endofunctor $J \cocomp I$ on $\cat{0}$ maps nothing, making it equal to the identity functor on $\cat{0}$.
$I \cocomp J$ is a functor from the other category to itself, and so is the identity functor, so by the assumed uniqueness property of the other category, these two functors must be equal.
Thus, $I$ and $J$ are inverses of each other, making the other category isomorphic to $\cat{0}$.
\end{proof}

\begin{exercise}
Given categories $\cat{A}$ and~$\cat{B}$, define a category~$\cat{A} \times \cat{B}$ with ``projection'' functors $\pi_A$ and~$\pi_B$ from it to $\cat{A}$ and~$\cat{B}$ respectively.
\end{exercise}

\begin{proof}
Each object of $\cat{A} \times \cat{B}$ is a pair $\langle A, B \rangle$ where $A$ is an object of $\cat{A}$ and $B$ is an object of $\cat{B}$.
A morphism from $\langle A_1, B_1 \rangle$ to $\langle A_2, B_2 \rangle$ is a pair $\langle f, g \rangle$ where $f$ is a morphism of $\cat{A}$ from $A_1$ to $A_2$ and $g$ is a morphism from $\cat{B}$ from $B_1$ to $B_2$.
Given morphisms $\langle A_1, B_1 \rangle \xmto{\langle f_1, g_1 \rangle} \langle A_2, B_2 \rangle \xmto{\langle f_2, g_2 \rangle} \langle A_3, B_3 \rangle$, define their composition to be $\langle f_1 \cocomp f_2, g_1 \cocomp g_2 \rangle$.
This is associative because composition in $\cat{A}$ and $\cat{B}$ is associative.
Given an object $\langle A, B \rangle$, define its identity to be $\langle \id_A, \id_B \rangle$.
This is an identity because $\id_A$ and $\id_B$ are identities in $\cat{A}$ and $\cat{B}$.

Define the projection functor $\pi_A$ to map $\langle A, B \rangle$ to $A$ and $\langle f, g \rangle$ to $f$. $\pi_A(\langle f_1, g_1 \rangle \cocomp \langle f_2, g_2 \rangle) = \pi_A(\langle f_1 \cocomp f_2, g_1 \cocomp g_2 \rangle) = f_1 \cocomp f_2$ and $\pi_A(\langle \id_A, \id_B \rangle) = \id_A$, so $\pi_A$ is a functor.

Define the projection functor $\pi_B$ to map $\langle A, B \rangle$ to $B$ and $\langle f, g \rangle$ to $g$. $\pi_B(\langle f_1, g_1 \rangle \cocomp \langle f_2, g_2 \rangle) = \pi_A(\langle f_1 \cocomp f_2, g_1 \cocomp g_2 \rangle) = g_1 \cocomp g_2$ and $\pi_B(\langle \id_A, \id_B \rangle) = \id_B$, so $\pi_B$ is a functor.
\end{proof}

\end{document}