exercises.tex

% Notes and exercises on Category Theory
\documentclass[letterpaper,12pt]{article}
\usepackage{amsmath,amssymb,amsthm,enumitem,fourier,diagrams,tikz-cd}
\usepackage[hidelinks]{hyperref}

\newcommand{\N}{\mathbb{N}}
\newcommand{\R}{\mathbb{R}}

\newcommand{\true}{\top}
\newcommand{\false}{\bot}
\newcommand{\vertex}{\bullet}

\newcommand{\iso}{\cong}
\newcommand{\eq}{\sim}
\newcommand{\eqv}{\simeq}
\newcommand{\xto}{\xrightarrow}
\newcommand{\parto}{\rightharpoondown}
\newcommand{\mono}{\rightarrowtail}
\newcommand{\epi}{\twoheadrightarrow}
\newcommand{\adj}{\dashv}
\newcommand{\radj}{\vdash}
\newcommand{\adjrule}{\frac}
\newcommand{\limplies}{\Rightarrow}
\newcommand{\ex}{\Rightarrow}
\newcommand{\edge}{\rightarrow}

\newcommand{\sect}{\cap}
\newcommand{\bigunion}{\bigcup}
\newcommand{\meet}{\wedge}
\newcommand{\bigmeet}{\bigwedge}
\newcommand{\join}{\vee}
\newcommand{\bigjoin}{\bigvee}
\newcommand{\compl}{\lnot}
\newcommand{\obj}{{\cdot}}
\newcommand{\after}{\circ}
\newcommand{\limit}{\varprojlim}
\newcommand{\colimit}{\varinjlim}
\newcommand{\eval}{\epsilon}
\newcommand{\term}{{!}}
\newcommand{\mult}{\cdot}
\newcommand{\mprod}{\otimes}
\newcommand{\tprod}{\otimes}

\DeclareMathOperator{\dom}{dom}
\DeclareMathOperator{\cod}{cod}
\DeclareMathOperator{\im}{im}
\DeclareMathOperator{\fdom}{\mathbf{dom}}
\DeclareMathOperator{\fst}{fst}
\DeclareMathOperator{\snd}{snd}
\DeclareMathOperator{\Hom}{Hom}
\DeclareMathOperator{\Sub}{Sub}
\DeclareMathOperator{\Diagrams}{\mathbf{Diagrams}}
\DeclareMathOperator{\Cone}{\mathbf{Cone}}
\DeclareMathOperator{\pow}{\mathcal{P}}
\DeclareMathOperator{\ult}{Ult}
\DeclareMathOperator{\up}{\uparrow}
\DeclareMathOperator{\down}{\downarrow}
\DeclareMathOperator{\ev}{ev}
\DeclareMathOperator{\id}{id}

\newcommand{\pair}[2]{\langle{#1},{#2}\rangle}
\newcommand{\pairing}[1]{\langle#1\rangle}
\newcommand{\copair}[2]{[{#1},{#2}]}
\newcommand{\copairing}[1]{[#1]}
\newcommand{\comp}[1]{\overline{#1}}
\newcommand{\inv}[1]{#1^{-1}}
\renewcommand{\star}[1]{#1^{*}}
\newcommand{\cat}[1]{\mathbf{#1}}
\newcommand{\dual}[1]{#1^{\mathrm{op}}}
\newcommand{\arr}[1]{#1^{\rightarrow}}
\newcommand{\under}[1]{|{#1}|}
\newcommand{\gen}[1]{\langle{#1}\rangle}
\newcommand{\curry}[1]{\lambda{#1}}
\newcommand{\uncurry}[1]{\overline{#1}}
\newcommand{\pull}[1]{#1^{*}}
\newcommand{\fin}[1]{#1_{\mathrm{fin}}}
\newcommand{\comma}[2]{(#1|#2)}
\newcommand{\tr}[1]{\overline{#1}}
\newcommand{\sprod}[2]{\langle#1,#2\rangle}

\newcommand{\2}{\cat{2}}
\newcommand{\A}{\cat{A}}
\newcommand{\B}{\cat{B}}
\newcommand{\C}{\cat{C}}
\newcommand{\Cop}{\dual{\C}}
\newcommand{\D}{\cat{D}}
\newcommand{\Dop}{\dual{\D}}
\newcommand{\E}{\cat{E}}
\newcommand{\Ee}{\mathcal{E}}
\newcommand{\J}{\cat{J}}
\renewcommand{\P}{\cat{P}}
\newcommand{\V}{\cat{V}}
\newcommand{\Vop}{\dual{\V}}
\newcommand{\X}{\cat{X}}
\newcommand{\Rel}{\cat{Rel}}
\newcommand{\Relop}{\dual{\Rel}}
\newcommand{\Sets}{\cat{Sets}}
\newcommand{\Setsop}{\dual{\Sets}}
\newcommand{\Setsp}{\Sets_*}
\newcommand{\Setsf}{\fin{\Sets}}
\newcommand{\Setsfop}{\dual{\Setsf}}
\newcommand{\SetsCop}{\Sets^{\Cop}}
\newcommand{\Par}{\cat{Par}}
\newcommand{\Mon}{\cat{Mon}}
\newcommand{\Grp}{\cat{Groups}}
\newcommand{\Pre}{\cat{Pre}}
\newcommand{\Pos}{\cat{Pos}}
\newcommand{\Posop}{\dual{\Pos}}
\newcommand{\Types}{\C(\lambda)}
\newcommand{\Cat}{\cat{Cat}}
\newcommand{\BA}{\cat{BA}}
\newcommand{\BAop}{\dual{\BA}}
\newcommand{\BAf}{\fin{\BA}}
\newcommand{\Ord}{\cat{Ord}}
\newcommand{\Ordf}{\fin{\Ord}}
\newcommand{\Grph}{\cat{Graphs}}
\newcommand{\Vect}{\cat{Vect}}
\newcommand{\Vectop}{\dual{\Vect}}

\newcommand{\powBA}{\pow^{\BA}}
\newcommand{\powBAop}{\dual{(\powBA)}}
\newcommand{\powU}{\pow^{\up}}

% Arrows
\newarrow{Mono} >--->
\newarrow{Epi} ----{>>}

% Theorems
\theoremstyle{definition}
\newtheorem*{exer}{Exercise}

\theoremstyle{remark}
\newtheorem*{rmk}{Remark}

\newtheoremstyle{direction}{0.5em}{0.5em}{}{}{}{}{0.5em}{}
\theoremstyle{direction}
\newtheorem*{fwd}{\(\implies\)}
\newtheorem*{bwd}{\(\impliedby\)}

% Meta
\title{\textit{Category Theory}\\Notes and Exercises}
\author{John Peloquin}
\date{}

\begin{document}
\maketitle

\section*{Introduction}
This document contains notes and exercises from~\cite{awodey}.

\newpage
\section*{Chapter 1}
\begin{rmk}
If \(\C\)~is a category and \(C\in\C\), then the identity arrow \(C\to C\) is terminal in~\(\C/C\);\footnote{The concept of a terminal object is defined in Chapter~2.} moreover if \(C\)~is terminal in~\(\C\), then \(\C/C\iso\C\). In this sense, \emph{taking a slice at an object amounts to making that object terminal}.
\end{rmk}

\begin{rmk}
If \(\C\)~is a category and \(X\to C\) is an arrow in~\(\C\), then
\[(\C/C)/(X/C)\iso\C/X\]
In other words, \emph{a slice of a slice is a slice}.
\end{rmk}

\begin{exer}[1]
In~\(\Rel\), let the objects be sets and the arrows be relations between sets,\footnote{An arrow \(A\to B\) between sets \(A\)~and~\(B\) is understood as a triple \((R,A,B)\) with \(R\subseteq A\times B\).} with identities and composites defined as usual for relations.
\begin{enumerate}[itemsep=0pt]
\item[(a)] \(\Rel\)~is a category.
\item[(b)] Let \(G:\Sets\to\Rel\) map sets to themselves and functions to their graphs, so \(G(A)=A\) and
\[G(f:A\to B)=\{\,\pair{x}{f(x)}\mid x\in A\,\}\subseteq A\times B\]
Then \(G\)~is a functor.
\item[(c)] Let \(C:\Relop\to\Rel\) map sets to themselves and relations to their inverses, so \(C(A)=A\) and
\[C(R\subseteq A\times B)=\inv{R}=\{\,\pair{y}{x}\mid\pair{x}{y}\in R\,\}\subseteq B\times A\]
Then \(C\)~is a functor.
\end{enumerate}
\begin{proof}\
\begin{enumerate}[itemsep=0pt]
\item[(a)] We must verify that composition of relations is associative and unital. Suppose \(R\subseteq A\times B\), \(S\subseteq B\times C\), and \(T\subseteq C\times D\). For \(\pair{w}{z}\in A\times D\), by the definition of composition we have
\begin{align*}
\pair{w}{z}\in(T\after S)\after R&\iff\exists x\in B[\pair{w}{x}\in R\land\pair{x}{z}\in T\after S]\\
								&\iff\exists x\in B,y\in C[\pair{w}{x}\in R\land\pair{x}{y}\in S\land\pair{y}{z}\in T]\\
								&\iff\exists y\in C[\pair{w}{y}\in S\after R\land\pair{y}{z}\in T]\\
								&\iff\pair{w}{z}\in T\after(S\after R)
\end{align*}
So \((T\after S)\after R=T\after(S\after R)\). It is immediate that \(R\after 1_A=R=1_B\after R\), where \(1_X\)~denotes the identity relation on~\(X\).
\item[(b)] By construction, \(G\)~maps objects to objects and arrows to arrows, and \(G(f:A\to B)\)~is an arrow from \(G(A)=A\) to \(G(B)=B\). Clearly \(G(1_A)=1_A=1_{G(A)}\). If \(f:A\to B\) and \(g:B\to C\), then \((g\after f)(x)=z\) if and only if \(f(x)=y\) and \(g(y)=z\), so \(G(g\after f)=G(g)\after G(f)\).
\item[(c)] Recall for a relation \(R\subseteq A\times B\), \(R\)~is represented as an arrow in~\(\Rel\) by the triple~\((R,A,B)\), and in~\(\Relop\) by the triple~\((R,B,A)\), where it is denoted by~\(\star{R}\).\footnote{Importantly, \(R\)~is \emph{not} represented in~\(\Relop\) by~\((\inv{R},B,A)\). The arrow is reversed by swapping the domain and codomain, but the underlying relation (set of ordered pairs) is unchanged.} So in~\(\Rel\), \(\dom R=A\) and \(\cod R=B\), whereas in~\(\Relop\), \(\dom\star{R}=B=\star{B}\) and \(\cod\star{R}=A=\star{A}\), where \(R\)~and~\(\star{R}\) are here treated as arrows.

By construction, \(C\)~maps objects to objects and arrows to arrows. Now \(C((R,B,A))=(\inv{R},B,A)\), so \(C\)~preserves domains and codomains. Also
\[C(1_{\star{A}})=C(\star{1_A})=\inv{1_A}=1_A=1_{C(\star{A})}\]
For \(S\subseteq B\times C\),
\[C(\star{R}\after\star{S})=C(\star{(S\after R)})=\inv{(S\after R)}=\inv{R}\after\inv{S}=C(\star{R})\after C(\star{S})\qedhere\]
\end{enumerate}
\end{proof}
\end{exer}

\begin{exer}[2]\
\begin{enumerate}[itemsep=0pt]
\item[(a)] \(\Rel\iso\Relop\)
\item[(b)] \(\Sets\not\iso\Setsop\)
\item[(c)] For any set~\(X\) with powerset~\(P(X)\), \(P(X)\iso\dual{P(X)}\) as poset categories.
\end{enumerate}
\begin{proof}\
\begin{enumerate}[itemsep=0pt]
\item[(a)] The functor in Exercise~1(c) is its own inverse, hence is an isomorphism.
\item[(b)] The empty function is the only function into the empty set, but there is no set with exactly one function out of it.
\item[(c)] Recall in~\(P(X)\) there exists a unique arrow \(A\to B\) if and only if \(A\subseteq B\), hence in~\(\dual{P(X)}\) there exists a unique arrow \(A\to B\) if and only if \(A\supseteq B\).

For \(A\subseteq X\), write \(\comp{A}=X-A=\{\,x\in X\mid x\not\in A\,\}\). Define \(C:\dual{P(X)}\to P(X)\) by \(C(A)=\comp{A}\) and
\[C(A\to B)=\comp{A}\to\comp{B}=C(A)\to C(B)\]
which is well defined since \(A\supseteq B\) if and only if \(\comp{A}\subseteq\comp{B}\). Clearly \(C\)~maps objects to objects and arrows to arrows, and also preserves domains and codomains. Substituting \(A\)~for~\(B\) above shows that \(C\)~preserves identities. For \(X\supseteq A\supseteq B\supseteq D\),
\[C(A\to B\to D)=\comp{A}\to\comp{B}\to\comp{D}=C(A)\to C(B)\to C(D)\]
so \(C\)~preserves composites. Therefore \(C\)~is a functor. Since \(C\)~is clearly its own inverse, \(C\)~is an isomorphism.\qedhere
\end{enumerate}
\end{proof}
\end{exer}

\begin{exer}[3]\
\begin{enumerate}[itemsep=0pt]
\item[(a)] In~\(\Sets\), the isomorphisms are precisely the bijections.
\item[(b)] In~\(\Mon\), the isomorphisms are precisely the bijective homomorphisms.
\item[(c)] In~\(\Pos\), the isomorphisms are \emph{not} the bijective homomorphisms.
\end{enumerate}
\begin{proof}\
\begin{enumerate}[itemsep=0pt]
\item[(a)] A function \(f:A\to B\) has a (two-sided) inverse if and only if it is bijective. Indeed, suppose \(g:B\to A\) is an inverse of~\(f\). If \(a,a'\in A\) and \(f(a)=f(a')\), then
\[a=1_A(a)=(g\after f)(a)=g(f(a))=g(f(a'))=(g\after f)(a')=1_A(a')=a'\]
If \(b\in B\), then \(b=1_B(b)=(f\after g)(b)=f(g(b))\). Conversely, if \(f\)~is bijective, then for each \(b\in B\) we can let~\(g(b)\) be the unique \(a\in A\) with \(f(a)=b\). Then \(g:B\to A\) is clearly an inverse of~\(f\).
\item[(b)] A monoid homomorphism is, in particular, a function, hence an isomorphism is a bijective homomorphism by~(a). Conversely, if \(f:A\to B\) is a bijective homomorphism, then \(f\)~has an inverse \emph{function} \(g:B\to A\) by~(a). If \(b,b'\in B\), then
\[bb'=1_B(b)1_B(b')=(f\after g)(b)(f\after g)(b')=f(g(b))f(g(b'))=f(g(b)g(b'))\]
so
\[g(bb')=g(f(g(b)g(b')))=(g\after f)(g(b)g(b'))=1_A(g(b)g(b'))=g(b)g(b')\]
Therefore \(g\)~is a homomorphism and hence \(f\)~is an isomorphism.
\item[(c)] As in~(b), a poset homomorphism is, in particular, a function, hence an isomorphism is a bijective homomorphism by~(a). However, unlike in~(b), the inverse of a bijective homomorphism need not be a homomorphism. For example, consider a poset consisting of two copies of \(\N=(N,\le)\) with no relations between the copies. Map this poset into~\(\N\) by ``zipping'' the two copies together, sending one to the evens in order, and the other to the odds in order. This mapping is clearly a bijective homomorphism, but its inverse is not since, for example, \(0\le 1\) in the image, but the preimage of~\(0\) is not related to the preimage of~\(1\).\qedhere
\end{enumerate}
\end{proof}
\end{exer}

\begin{exer}[5]
Let \(\C\)~be a category and \(C\in\C\). Let \(U:\C/C\to\C\) ``forget about the base object~\(C\)'' by mapping each object \(f:A\to C\) to its domain~\(A\) and each arrow \(a:A\to B\) to ``itself.''\footnote{An arrow in~\(\C/C\) is understood as a triple \((a,f,f')\) where \(a:A\to B\), \(f:A\to C\), and \(f':B\to C\) are arrows in~\(\C\) with \(f=f'\after a\). So \(U((a,f,f'))=a\).} Then \(U\)~is a functor.

Let \(F:\C/C\to\arr{\C}\) map objects to themselves and each arrow \(a:A\to B\) to the pair~\((a,1_C)\), where \(1_C\)~is the identity arrow for~\(C\) in~\(\C\). Then \(F\)~is a functor, and \(\fdom\after F=U\), where \(\fdom:\arr{\C}\to\C\) is the functor mapping each object \(f:A\to B\) to its domain~\(A\) and each arrow \((g_1,g_2)\) to~\(g_1\).
\end{exer}
\begin{proof}
\(U\)~maps objects to objects and arrows to arrows, and preserves domains and codomains of arrows. Since \(\C/C\) inherits identities and composites from~\(\C\), \(U\)~also preserves identities and composites. Therefore \(U\)~is a functor.

\(F\)~maps objects to objects and arrows to arrows, and preserves domains and codomains of arrows, since if \(a:A\to B\) maps \(f:A\to C\) to \(f':B\to C\) in~\(\C/C\), then \(1_C\after f=f=f'\after a\), hence \((a,1_C)\)~maps~\(f\) to~\(f'\) in~\(\arr{\C}\). Since \(\arr{\C}\)~also inherits identities and composites from~\(\C\), \(F\)~also preserves identities and composites. Therefore \(F\)~is a functor. Clearly \(\fdom\after F=U\).
\end{proof}

\begin{exer}[8]
For a (small) category~\(\C\), let \(P(\C)\) consist of the objects from~\(\C\) ordered as follows:
\begin{center}
\(A\le B\) if and only if there exists an arrow \(A\to B\) in~\(\C\)
\end{center}
Then \(P(\C)\)~is a preorder, and \(P:\Cat\to\Pre\) determines a functor with \(P\after C=1_{\Pre}\), where \(C:\Pre\to\Cat\) is the evident inclusion functor.
\end{exer}
\begin{proof}
Reflexivity and transitivity of the order in~\(P(\C)\) follow from the existence of identities and composites in~\(\C\). So \(P\)~maps categories to preorders. For a functor \(F:\C\to\D\), let \(P(F)\)~be the restriction of~\(F\) to objects. If \(A\le B\) in~\(P(\C)\), there exists an arrow \(f:A\to B\) in~\(\C\). But then \(F(f):F(A)\to F(B)\) is an arrow in~\(\D\), so \(F(A)\le F(B)\) in~\(P(\D)\). Therefore \(P(F)\)~is monotone, and hence \(P\)~maps functors to preorder homomorphisms. Since \(P\)~just restricts functors to objects, it preserves domains and codomains, identities, and composites, hence it is a functor. It is obvious that \(P\after C=1_{\Pre}\).
\end{proof}
\begin{rmk}
In general \(C\after P\ne 1_{\Cat}\) because \(P\)~loses information about the arrow structure of categories. Specifically, multiple arrows from one object to another will be represented by a single relation between those objects under~\(P\).
\end{rmk}

\begin{exer}[11]
There exists a functor \(M:\Sets\to\Mon\) mapping each set~\(A\) to the free monoid on~\(A\).
\end{exer}
\begin{proof}
We prove this in two ways.
\begin{enumerate}[itemsep=0pt]
\item[(a)] Let \(M(A)=\star{A}\) and for \(f:A\to B\) define \(M(f):\star{A}\to\star{B}\) by
\[M(f)(a_1\cdots a_k)=f(a_1)\cdots f(a_k)\quad a_1,\ldots,a_k\in A\]
\(M(f)\)~is well defined on~\(\star{A}\) since every element in~\(\star{A}\) can be expressed uniquely as a product of elements of~\(A\), and by construction \(M(f)\)~is a monoid homomorphism extending~\(f\). So \(M\)~maps objects to objects and arrows to arrows. Clearly \(M\)~preserves domains and codomains of arrows and \(M(1_A)=1_{\star{A}}\). If \(g:B\to C\), then
\begin{align*}
M(g\after f)(a_1\cdots a_k)&=(g\after f)(a_1)\cdots(g\after f)(a_k)\\
	&=g(f(a_1))\cdots g(f(a_k))\\
	&=M(g)(f(a_1)\cdots f(a_k))\\
	&=M(g)(M(f)(a_1\cdots a_k))\\
	&=(M(g)\after M(f))(a_1\cdots a_k)
\end{align*}
So \(M(g\after f)=M(g)\after M(f)\) and \(M\)~preserves composites. Therefore \(M\)~is a functor.
\item[(b)] Let \(M(A)\)~be ``the'' free monoid on~\(A\) satisfying the universal mapping property (Propositions 1.9~and~1.10). For \(f:A\to B\to\under{M(B)}\), let \(M(f)\)~be the unique monoid homomorphism from~\(M(A)\) to~\(M(B)\) extending~\(f\). Clearly \(M\)~maps objects to objects and arrows to arrows, and preserves domains and codomains of arrows. Now \(1_{M(A)}\)~extends~\(1_A\), hence we must have \(M(1_A)=1_{M(A)}\). Similarly if \(g:B\to C\to\under{M(C)}\), then \(M(g)\after M(f)\) extends~\(g\after f\), hence we must have \(M(g\after f)=M(g)\after M(f)\). Therefore \(M\)~is a functor.\qedhere
\end{enumerate}
\end{proof}
\begin{rmk}
A homomorphism \(h:M(A)\to B\) is uniquely determined by its action on~\(A\), where this action is \(\under{h}\after i:A\to\under{M(A)}\to\under{B}\). This is trivially true by the universal mapping property since \(h\)~extends~\(\under{h}\after i\) to~\(M(A)\), that is, \(\under{h}\after i=\under{h}\after i\). This is a familiar concept in mathematics (for example, a linear transformation of a vector space is uniquely determined by its action on a basis, etc.).
\end{rmk}

\newpage
\section*{Chapter~2}
\begin{rmk}
Recall that a monoid homomorphism \(h:M(A)\to B\) is uniquely determined by its action on~\(A\). For inclusion \(i:A\to\under{M(A)}\) and homomorphisms \(j,k:M(A)\to B\), this implies that if \(\under{j}\after i=\under{k}\after i\) then \(j=k\). So while \(i\)~is not an epi in~\(\Sets\) (it is not a surjection) and is not even an arrow in~\(\Mon\) (it is not a homomorphism), it is like an epi \emph{if} we blur the line between \(\Sets\)~and~\(\Mon\). It is ``structurally surjective'' in the sense that once a homomorphic structure is determined on~\(A\), it is determined on~\(M(A)\).\footnote{Compare with Example~2.5.}
\end{rmk}

\begin{exer}[1]
In~\(\Sets\), the epis are precisely the surjections. Therefore the isos are precisely the epi-monos.
\end{exer}
\begin{proof}
If \(f:A\to B\) is a surjection, then \(f\)~has a right inverse (AC), hence \(f\)~is a split epi. Conversely, if \(f\)~is not a surjection, there exists \(b\in B\) with \(b\not\in f[A]\). Define \(g:B\to 2\) by
\[g(x)=\begin{cases}
1&\text{if }x=b\\
0&\text{otherwise}
\end{cases}\]
Then \(g\ne0\), but \(g\after f=0\after f\), so \(f\)~is not an epi. Therefore the epis are precisely the surjections.

Now by this result and Proposition~2.2, the epi-monos are precisely the bijections. By Exercise~1.3, the bijections are precisely the isos. Therefore the epi-monos are precisely the isos.
\end{proof}

\begin{exer}[2]
In a poset category, every arrow is an epi-mono since there is at most one arrow between any two objects.
\end{exer}

\begin{exer}[3]
Inverses are unique.
\end{exer}
\begin{proof}
If \(f:A\to B\) and \(g,g':B\to A\) are inverses of~\(f\), then
\[g=g\after 1_B=g\after(f\after g')=(g\after f)\after g'=1_A\after g'=g'\qedhere\]
\end{proof}

\begin{exer}[4]
Let \(f:A\to B\), \(g:B\to C\), and \(h:A\to C\) form a commutative triangle (\(h=g\after f\)):
\begin{diagram}[nohug]
A	&\rTo^f	&B\\
	&\rdTo_h&\dTo>g\\
	&		&C
\end{diagram}
\begin{enumerate}[itemsep=0pt]
\item[(a)] If \(f\)~and~\(g\) are monic [epic, iso], so is~\(h\).
\item[(b)] If \(h\)~is monic, so is~\(f\).
\item[(c)] If \(h\)~is epic, so is~\(g\).
\item[(d)] If \(h\)~is monic, \(g\)~need not be.
\item[(e)] If \(h\)~is epic, \(f\)~need not be.
\end{enumerate}
\begin{proof}\
\begin{enumerate}[itemsep=0pt]
\item[(a)] Suppose \(f\)~and~\(g\) are monic. If \(x,y:D\to A\) and \(h\after x=h\after y\), then
\[g\after(f\after x)=(g\after f)\after x=h\after x=h\after y=(g\after f)\after y=g\after(f\after y)\]
so \(f\after x=f\after y\) since \(g\)~is monic, and \(x=y\) since \(f\)~is monic. Therefore \(h\)~is monic.

Suppose \(f\)~and~\(g\) are epic. If \(i,j:C\to D\) and \(i\after h=j\after h\), then
\[(i\after g)\after f=i\after (g\after f)=i\after h=j\after h=j\after(g\after f)=(j\after g)\after f\]
so \(i\after g=j\after g\) since \(f\)~is epic, and \(i=j\) since \(g\)~is epic. Therefore \(h\)~is epic.\footnote{This also follows from the previous result by duality. If \(f\)~and~\(g\) are epic in~\(\C\), then \(\star{f}\)~and~\(\star{g}\) are monic in~\(\Cop\), so \(\star{h}\)~is monic in~\(\Cop\), so \(h\)~is epic in~\(\C\).}

If \(f\)~and~\(g\) are isos, then \(\inv{h}=\inv{f}\after\inv{g}\), so \(h\)~is an iso.
\item[(b)] If \(f\)~is not monic, choose \(x\ne y\) such that \(f\after x=f\after y\). Then
\[h\after x=(g\after f)\after x=g\after(f\after x)=g\after(f\after y)=(g\after f)\after y=h\after y\]
So \(h\)~is not monic.
\item[(c)] If \(g\)~is not epic, choose \(i\ne j\) such that \(i\after g=j\after g\). Then
\[i\after h=i\after(g\after f)=(i\after g)\after f=(j\after g)\after f=j\after(g\after f)=j\after h\]
So \(h\)~is not epic.\footnote{This also follows from the previous result by duality. If \(h\)~is epic in~\(\C\), then \(\star{h}=\star{f}\after\star{g}\)~is monic in~\(\Cop\), so \(\star{g}\)~is monic in~\(\Cop\), so \(g\)~is epic in~\(\C\).}
\item[(d),(e)] In~\(\Sets\), let \(A=C=1\) and \(B=2\) and let \(f=0_{A\to B}\) and \(g=0_{B\to C}\). Then \(h=0_{A\to C}\) is both monic and epic, but \(g\)~is not monic and \(f\)~is not epic.\qedhere
\end{enumerate}
\end{proof}
\end{exer}

\begin{exer}[5]
For \(f:A\to B\), the following are equivalent:
\begin{enumerate}[itemsep=0pt]
\item[(a)] \(f\)~is an iso.
\item[(b)] \(f\)~is a mono and a split epi.
\item[(c)] \(f\)~is a split mono and an epi.
\item[(d)] \(f\)~is a split mono and a split epi.
\end{enumerate}
\begin{proof}
It is immediate that (a)~\(\implies\)~(d)~\(\implies\)~(b),(c).

For (b)~\(\implies\)~(a), suppose that \(f\)~is monic and \(g:B\to A\) satisfies \(f\after g=1_B\). We claim \(g\)~also satisfies \(g\after f=1_A\), so \(f\)~is an iso. But this follows from
\[f\after(g\after f)=(f\after g)\after f=1_B\after f=f=f\after 1_A\]
since \(f\)~is monic.

For (c)~\(\implies\)~(a), suppose that \(f\)~is epic and \(g:B\to A\) satisfies \(g\after f=1_A\). We claim \(g\)~also satisfies \(f\after g=1_B\), so \(f\)~is an iso. But this follows from
\[(f\after g)\after f=f\after(g\after f)=f\after 1_A=f=1_B\after f\]
since \(f\)~is epic.\footnote{This also follows from the previous result by duality. If \(f\)~is epic and \(g\)~is a left inverse of~\(f\) in~\(\C\), then \(\star{f}\)~is monic and \(\star{g}\)~is a right inverse of~\(\star{f}\) in~\(\Cop\). Therefore \(\star{f}\)~is an iso in~\(\Cop\), so \(f\)~is an iso in~\(\C\).} 
\end{proof}
\end{exer}

\begin{exer}[7]
A retract of a projective object is projective.
\end{exer}
\begin{proof}
Let \(P\)~be projective and \(R\)~be a retract of~\(P\) where \(s:R\to P\), \(r:P\to R\), and \(r\after s=1_R\). Suppose \(f:R\to Y\) and \(e:X\epi Y\). Note \(f\after r:P\to Y\), so by projectivity of~\(P\) there exists \(p:P\to X\) such that \(e\after p=f\after r\):
\begin{diagram}[nohug]
	&						&	&				&X\\
	&						&	&\ruTo(4,2)^p	&\dEpi>e\\
P	&\pile{\rTo^r\\\lTo_s}	&R	&\rTo_f			&Y
\end{diagram}
Now \(p\after s:R\to X\) and
\[e\after(p\after s)=(e\after p)\after s=(f\after r)\after s=f\after(r\after s)=f\after 1_R=f\]
Therefore \(R\)~is projective.
\end{proof}

\begin{exer}[8]
In~\(\Sets\), every set is projective.
\end{exer}
\begin{proof}
If \(f:P\to Y\) and \(g:X\epi Y\), then since \(g\)~is surjective (Exercise~1), \(g\)~has a right inverse \(h:Y\to X\) with \(g\after h=1_Y\). Set \(p=h\after f:P\to X\):
\begin{diagram}[nohug]
	&					&X\\
	&\ruTo^{p=h\after f}&\dEpi<g\uTo>h\\
P	&\rTo_f				&Y
\end{diagram}
Then
\[g\after p=g\after(h\after f)=(g\after h)\after f=1_Y\after f=f\]
Therefore \(P\)~is projective. 
\end{proof}
\begin{rmk}
Projectivity is more interesting in categories of structured sets, where it implies ``freeness'' of structure allowing factoring of outgoing morphisms.
\end{rmk}

\begin{exer}[11]
For a set~\(A\), let \(A\text{-}\Mon\) be the category of \(A\)-monoids \((M,m)\), where \(M\)~is a monoid and \(m:A\to U(M)\), with arrows \(h:(M,m)\to(N,n)\), where \(h:M\to N\) is a monoid homomorphism and \(n=U(h)\after m\).

An initial object in \(A\text{-}\Mon\) is just a free monoid on~\(A\) in~\(\Mon\).
\end{exer}
\begin{proof}
The \(A\)-monoid~\((M,m)\) is initial if and only if for all \(A\)-monoids~\((N,n)\), there is a unique \(A\)-monoid homomorphism \(h:(M,m)\to(N,n)\). This is just to say that \(m:A\to U(M)\) and for all monoids~\(N\) with \(n:A\to U(N)\) there is a unique monoid homomorphism \(h:M\to N\) with \(n=U(h)\after m\). But this is just the universal mapping property for the free monoid on~\(A\) in~\(\Mon\).
\end{proof}

\begin{exer}[12]
For a Boolean algebra~\(B\), Boolean homomorphisms \(p:B\to\2\) correspond exactly to ultrafilters in~\(B\).
\end{exer}
\begin{proof}
If \(p:B\to\2\) is a homomorphism, then \(U_p=\inv{p}(1)\) is an ultrafilter in~\(B\). Indeed, \(U_p\ne\emptyset\) since \(p(1)=1\), and \(U_p\ne B\) since \(p(0)=0\ne 1\). If \(a\in U_p\) and \(a\le b\), then \(1=p(a)\le p(b)\), so \(p(b)=1\) and \(b\in U_p\). If \(a\in U_p\) and \(b\in U_p\), then
\[p(a\meet b)=p(a)\meet p(b)=1\meet 1=1\]
so \(a\meet b\in U_p\). Finally, if \(a\not\in U_p\) then \(p(a)=0\), so \(p(\compl a)=\compl p(a)=1\) and \(\compl a\in U_p\). On the other hand, \(p(a)\meet p(\compl a)=0\), so we cannot have \(a\in U_p\) and \(\compl a\in U_p\).

Conversely, if \(U\)~is an ultrafilter in~\(B\) and \(p_U:B\to\2\) is defined by
\[
p_U(x)=\begin{cases}
1&\text{if }x\in U\\
0&\text{otherwise}
\end{cases}
\]
then \(p\)~is a homomorphism, by reasoning similar to that above. Clearly the maps \(p\mapsto U_p\) and \(U\mapsto p_U\) are mutually inverse.
\end{proof}

\begin{exer}[13]
In any category with binary products,
\[(A\times B)\times C\iso A\times (B\times C)\]
\end{exer}
\begin{proof}
Instead of using the universal property of a ternary product, we use only the universal properties of the binary products. Define
\[f=\pair{p_A\after p_{A\times B}}{\pair{p_B\after p_{A\times B}}{p_C}}:(A\times B)\times C\to A\times(B\times C)\]
where the \(p\)'s are the obvious projections, and
\[g=\pair{\pair{q_A}{q_B\after q_{B\times C}}}{q_C\after q_{B\times C}}:A\times(B\times C)\to(A\times B)\times C\]
where the \(q\)'s are the obvious projections. Then \(f\) and~\(g\) are inverses, so they are isomorphisms. For example,
\begin{align*}
f\after g&=\pair{p_A\after p_{A\times B}}{\pair{p_B\after p_{A\times B}}{p_C}}\after g\\
	&=\pair{p_A\after p_{A\times B}\after g}{\pair{p_B\after p_{A\times B}\after g}{p_C\after g}}\\
	&=\pair{p_A\after \pair{q_A}{q_B\after q_{B\times C}}}{\pair{p_B\after \pair{q_A}{q_B\after q_{B\times C}}}{q_C\after q_{B\times C}}}\\
	&=\pair{q_A}{\pair{q_B\after q_{B\times C}}{q_C\after q_{B\times C}}}\\
	&=\pair{q_A}{q_{B\times C}}\\
	&=1_{A\times(B\times C)}\qedhere
\end{align*}
\end{proof}

\begin{exer}[15]
For a category~\(\C\) and objects \(A,B\in\C\), let \(\C_{A,B}\)~be the category with objects \((X,x_1,x_2)\), where \(x_1:X\to A\) and \(x_2:X\to B\) in~\(\C\), and with arrows \(f:(X,x_1,x_2)\to(Y,y_1,y_2)\), where \(f:X\to Y\) and \(x_i=y_i\after f\) in~\(\C\).

A terminal object in~\(\C_{A,B}\) is just a product of \(A\)~and~\(B\) in~\(\C\).
\end{exer}
\begin{proof}
Object \((P,p_1,p_2)\) in~\(\C_{A,B}\) is terminal if and only if for all objects \((X,x_1,x_2)\) there is a unique \(p:(X,x_1,x_2)\to(P,p_1,p_2)\). This is just to say that \(p_1:P\to A\), \(p_2:P\to B\), and for all objects \(X\in\C\) with arrows \(x_1:X\to A\) and \(x_2:X\to B\) there is a unique \(p:X\to P\) with \(x_i=p_i\after p\). But this is just the universal mapping property for the product~\(A\times B\) in~\(\C\).
\end{proof}
\begin{rmk}
The objects in~\(\C_{A,B}\) are just pairs of ``generalized elements'' of \(A\)~and~\(B\) in~\(\C\). A terminal object in~\(\C_{A,B}\) has a unique ``generalized element'' for every such pair, hence it is just the product~\(A\times B\).
\end{rmk}

\begin{exer}[16]
Let \(\Types\)~be the category of types in the \(\lambda\)-calculus. Then the product functor \(\times:\Types\times\Types\to\Types\) maps objects \(A\)~and~\(B\) to~\(A\times B\) and arrows \(f:A\to B\) and \(g:A'\to B'\) to \(f\times g:A\times A'\to B\times B'\) where
\[f\times g=\lambda c.\pair{f(\fst(c))}{g(\snd(c))}\]
For any fixed type~\(A\), there is a functor~\(A\to(-)\) on~\(\Types\) taking each type~\(X\) to the type~\(A\to X\).
\end{exer}
\begin{proof}
We know \(\Types\)~has products, so the product functor is defined on~\(\Types\). For \(f:A\to B\) and \(g:A'\to B'\), if
\[A\lTo^{p_1}A\times A'\rTo^{p_2}A'\]
where \(p_1=\lambda z.\fst(z)\) and \(p_2=\lambda z.\snd(z)\), then
\begin{align*}
f\times g&=\pair{f\after p_1}{g\after p_2}\\
	&=\lambda c.\pair{f(p_1c)}{g(p_2c)}\\
	&=\lambda c.\pair{f(\fst(c))}{g(\snd(c))}
\end{align*}
Fix a type~\(A\). Let \(A\to(-)\)~map each type~\(X\) to the type~\(A\to X\) and map each function \(f:X\to Y\) to the function \(\overline{f}:(A\to X)\to(A\to Y)\) given by \(\overline{f}=\lambda g.f\after g\), where \(f\after g=\lambda x.f(gx)\). We claim this mapping is a functor.

Indeed, this mapping clearly maps objects to objects and arrows to arrows and it preserves domains and codomains of arrows. It also clearly preserves identities. If \(g:Y\to Z\), then
\begin{align*}
\overline{g\after f}&=\lambda h.(g\after f)\after h\\
	&=\lambda h.g\after(f\after h)\\
	&=\lambda h.\overline{g}(\overline{f}h)\\
	&=\overline{g}\after\overline{f}
\end{align*}
So the mapping also preserves composites.\footnote{Note preservation of identities and composites relies on \(\beta\eta\)-equivalence for \emph{equality} of the functions involved.} Therefore it is a functor.
\end{proof}
\begin{rmk}
This result shows that in functional programming languages such as Haskell, functions of a fixed input type are ``functorial'' types. This implies that functions on arbitrary types can be lifted to operate on such functions through composition.
\end{rmk}

\begin{exer}[17]
In any category~\(\C\) with products, define the \emph{graph} of an arrow \(f:A\to B\) by
\[\Gamma(f)=\pair{1_A}{f}:A\mono A\times B\]
Then \(\Gamma(f)\)~is a mono for every arrow~\(f\).

In~\(\Sets\), \(\Gamma\)~determines a functor \(G:\Sets\to\Rel\) mapping sets to themselves and functions to their graphs.
\end{exer}
\begin{proof}
To see that \(\Gamma(f)\)~is a mono, suppose \(x,y:X\to A\) and \(\Gamma(f)\after x=\Gamma(f)\after y\). By the universal mapping property of~\(A\times B\),
\[\Gamma(f)\after x=\pair{1_A}{f}\after x=\pair{1_A\after x}{f\after x}=\pair{x}{f\after x}\]
Similarly \(\Gamma(f)\after y=\pair{y}{f\after y}\). Therefore \(\pair{x}{f\after x}=\pair{y}{f\after y}\), so \(x=y\).

Define \(G:\Sets\to\Rel\) by \(G(A)=A\) and \(G(f:A\to B)=\Gamma(f)[A]\subseteq A\times B\). Then clearly \(G\)~is just the map from Exercise~1.1(b), which is a functor.
\end{proof}

\newpage
\section*{Chapter~3}
\begin{exer}[1]
Let \(\C\)~be a (locally small) category. Then
\[A\rTo^{c_1}C\lTo^{c_2}B\]
is a coproduct if and only if for all objects~\(Z\) the function
\begin{align*}
\Hom(C,Z)&\to\Hom(A,Z)\times\Hom(B,Z)\\
f&\mapsto\pair{f\after c_1}{f\after c_2}
\end{align*}
is an iso.
\end{exer}
\begin{proof}
By duality, the given diagram is a coproduct in~\(\C\) if and only if
\[\star{A}\lTo^{\star{c_1}}\star{C}\rTo^{\star{c_2}}\star{B}\]
is a product in~\(\Cop\). We know this diagram is a product in~\(\Cop\) if and only if for all objects~\(\star{Z}\), the function
\begin{align*}
\Hom_{\Cop}(\star{Z},\star{C})&\to\Hom_{\Cop}(\star{Z},\star{A})\times\Hom_{\Cop}(\star{Z},\star{B})\\
\star{f}&\mapsto\pair{\star{c_1}\after\star{f}}{\star{c_2}\after\star{f}}
\end{align*}
is an iso (Proposition~2.20). But by definition of~\(\Cop\),
\[\Hom_{\Cop}(\star{Z},\star{X})=\Hom_{\C}(X,Z)\]
for all objects \(X\in\C\) and \(\star{c_i}\after\star{f}=\star{(f\after c_i)}\) for all arrows \(f\in\C\), so the functions are the same.
\end{proof}

\begin{exer}[2]
The free monoid functor preserves coproducts, that is,
\[M(A+B)\iso M(A)+M(B)\]
\end{exer}
\begin{proof}
By the universal property of~\(M(A)\), let \(i_1:M(A)\to M(A+B)\) extend the inclusion \(A\to A+B\to\under{M(A+B)}\).\footnote{The inclusion \(A\to A+B\) is from the coproduct construction, and the inclusion \(A+B\to\under{M(A+B)}\) is from the free monoid construction. Observe \(A\to A+B\) is lifted to~\(i_1\) by the free monoid functor.} Similarly let \(i_2:M(B)\to M(A+B)\) extend the inclusion \(B\to A+B\to\under{M(A+B)}\). We claim
\[M(A)\rTo^{i_1}M(A+B)\lTo^{i_2}M(B)\]
is a coproduct of \(M(A)\)~and~\(M(B)\), from which the desired result follows by uniqueness of the coproduct (Proposition~3.12).

Given \(x:M(A)\to N\) and \(y:M(B)\to N\), let \(\under{x}_A:A\to\under{N}\) be the composite of the inclusion \(A\to\under{M(A)}\) with \(\under{x}:\under{M(A)}\to\under{N}\), and similarly let \(\under{y}_B:B\to\under{N}\) be the composite of the inclusion \(B\to\under{M(B)}\) with \(\under{y}:\under{M(B)}\to\under{N}\). By the universal property of~\(A+B\), there is a unique copairing~\(\copair{\under{x}_A}{\under{y}_B}:A+B\to\under{N}\), and by the universal property of~\(M(A+B)\) this copairing extends uniquely to a homomorphism \(z:M(A+B)\to N\).

It follows from the copairing and the universal property of~\(M(A)\) that \(z\after i_1=x\) since both \(z\after i_1\)~and~\(x\) extend~\(\under{x}_A\) to~\(M(A)\), and similarly \(z\after i_2=y\). Moreover it follows from uniqueness of the copairing and the extension that \(z\)~uniquely satisfies these equations. Therefore \(z\)~is a copairing~\(\copair{x}{y}\), and \(M(A+B)\)~is a coproduct of \(M(A)\)~and~\(M(B)\) as claimed.
\end{proof}

\begin{exer}[4]
If \(\powBA:\Setsop\to\BA\) denotes the (contravariant) powerset Boolean algebra functor, then
\[\powBA(A+B)\iso\powBA(A)\times\powBA(B)\]
\end{exer}
\begin{proof}
We have \(\powBA\iso\Hom_{\Sets}(-,2)\),\footnote{See Chapter~7.} and the contravariant representable functors map coproducts to products by the dual of Corollary~2.22.
\end{proof}

\begin{exer}[5]
Let \(\C\)~be the category of proofs in a natural deduction system with disjunction introduction rules
\[\begin{array}{c}
\varphi\\
\hline
\varphi\lor\psi
\end{array}
\qquad
\begin{array}{c}
\psi\\
\hline
\varphi\lor\psi
\end{array}\]
and disjunction elimination rule
\[\begin{array}{ccc}
&[\varphi]&[\psi]\\
&\vdots&\vdots\\
\varphi\lor\psi&\vartheta&\vartheta\\
\hline
&\vartheta&
\end{array}\]
Note the introduction rules give proofs \(i_1:\varphi\to\varphi\lor\psi\) and \(i_2:\psi\to\varphi\lor\psi\), and the elimination rule gives a proof \(\copair{p}{q}:\varphi\lor\psi\to\vartheta\) from proofs \(p:\varphi\to\vartheta\) and \(q:\psi\to\vartheta\).

For any proofs \(p:\varphi\to\vartheta\), \(q:\psi\to\vartheta\), and \(r:\varphi\lor\psi\to\vartheta\), identify proofs under the equations
\[\copair{p}{q}\after i_1=p\qquad \copair{p}{q}\after i_2=q\qquad [r\after i_1,r\after i_2]=r\]
to disregard unnecessary introduction and elimination of disjunction.

Then \(\C\)~has coproducts, and in fact \(\varphi+\psi=\varphi\lor\psi\).
\end{exer}
\begin{proof}
To see that
\[\varphi\rTo^{i_1}\varphi\lor\psi\lTo^{i_2}\psi\]
is a coproduct, suppose \(p:\varphi\to\vartheta\) and \(q:\psi\to\vartheta\) are proofs. Let \(r:\varphi\lor\psi\to\vartheta\) be the proof given by application of the elimination rule to \(p\)~and~\(q\). Then by the first two identification rules, \(r\after i_1=p\) and \(r\after i_2=q\). If \(s:\varphi\lor\psi\to\vartheta\) also satisfies these properties, then by the second identification rule
\[s=[s\after i_1,s\after i_2]=[p,q]=[r\after i_1,r\after i_2]=r\]
Therefore \(r\)~is unique, and so \(\varphi\lor\psi\)~is a coproduct.
\end{proof}
\begin{rmk}
Dually, it can be shown that the category of proofs in a system with conjunction elimination rules
\[\begin{array}{c}
\varphi\land\psi\\
\hline
\varphi
\end{array}
\qquad
\begin{array}{c}
\varphi\land\psi\\
\hline
\psi
\end{array}\]
determining proofs \(p_1:\varphi\land\psi\to\varphi\) and \(p_2:\varphi\land\psi\to\psi\), together with conjunction introduction rule
\[\begin{array}{ccc}
&[\vartheta]&[\vartheta]\\
&\vdots&\vdots\\
\vartheta&\varphi&\psi\\
\hline
&\varphi\land\psi&
\end{array}\]
determining a proof \(\pair{p}{q}:\vartheta\to\varphi\land\psi\) from proofs \(p:\vartheta\to\varphi\) and \(q:\vartheta\to\psi\), all under identification rules
\[p_1\after\pair{p}{q}=p\qquad p_2\after\pair{p}{q}=q\qquad\pair{p_1\after r}{p_2\after r}=r\]
for arbitrary proofs \(p:\vartheta\to\varphi\), \(q:\vartheta\to\psi\), and \(r:\vartheta\to\varphi\land\psi\), has products, and in fact \(\varphi\times\psi=\varphi\land\psi\).
\end{rmk}

\begin{exer}[6]
The category~\(\Mon\) has all equalizers.
\end{exer}
\begin{proof}
Given any monoid homomorphisms \(f,g:A\to B\), define the set
\[E=\{\,x\in A\mid f(x)=g(x)\,\}\]
We claim \(E\)~is a submonoid of~\(A\). Indeed, \(u_A\in E\) since \(f(u_A)=u_B=g(u_A)\), and if \(x,y\in E\) then \(xy\in E\) since
\[f(xy)=f(x)f(y)=g(x)g(y)=g(xy)\]
Let \(i:E\to A\) be the inclusion homomorphism. It follows that \(i\)~is an equalizer of \(f\)~and~\(g\), by the same argument used in~\(\Sets\).
\end{proof}

\begin{exer}[7]
Let \(\C\)~be a category with coproducts. If \(P\)~and~\(Q\) are projective, then \(P+Q\)~is projective.
\end{exer}
\begin{proof}
Suppose
\[P\rTo^{i_1}P+Q\lTo^{i_2}Q\]
is a coproduct diagram. If \(f:P+Q\to X\) and \(e:E\epi X\), then by projectivity of \(P\)~and~\(Q\) there exist arrows \(\overline{f\after i_1}:P\to E\) and \(\overline{f\after i_2}:Q\to E\) satisfying equations \(e\after\overline{f\after i_k}=f\after i_k\). Define \(\overline{f}=\copair{\overline{f\after i_1}}{\overline{f\after i_2}}\). Then
\[e\after\overline{f}
=e\after\copair{\overline{f\after i_1}}{\overline{f\after i_2}}
=\copair{e\after\overline{f\after i_1}}{e\after\overline{f\after i_2}}
=\copair{f\after i_1}{f\after i_2}
=f\]
Therefore \(P+Q\)~is projective.
\end{proof}

\begin{exer}[8]
An object~\(Q\) is \emph{injective} in a category~\(\C\) if \(\star{Q}\)~is projective in~\(\Cop\), that is, if for all arrows \(f:X\to Q\) and monos \(m:X\mono A\), there exists \(\overline{f}:A\to Q\) such that \(\overline{f}\after m=f\):
\begin{diagram}[nohug]
X		&\rTo^f					&Q\\
\dMono<m&\ruTo_{\overline{f}}	&\\
A		&						&
\end{diagram}

In~\(\Pos\), the empty poset is not injective, but the singleton poset is injective.
\end{exer}
\begin{proof}
For the empty poset, consider any nonempty~\(A\).
\end{proof}

\begin{exer}[11]
The category~\(\Sets\) has all coequalizers.
\end{exer}
\begin{proof}
Given any functions \(f,g:A\to B\), let \(\eq\)~be the equivalence relation on~\(B\) generated by pairs \(f(x)\eq g(x)\) for all \(x\in A\).\footnote{This is defined as the intersection of all equivalence relations on~\(B\) containing all such pairs, which is the smallest equivalence relation containing all such pairs. Note this intersection is well defined since \(B\times B\) is an equivalence relation on~\(B\) containing all such pairs.} Let \(C\)~be the quotient~\(B/\eq\). We claim the projection \(\pi:B\to C\) given by \(y\mapsto[y]\) is a coequalizer of \(f\)~and~\(g\).

Clearly \(\pi\after f=\pi\after g\) since for \(x\in A\), \(f(x)\eq g(x)\), hence
\[\pi(f(x))=[f(x)]=[g(x)]=\pi(g(x))\]
Suppose \(h:B\to D\) satisfies \(h\after f=h\after g\). Let \(\eq_h\)~be the equivalence relation on~\(B\) defined by
\[y\eq_h z\iff h(y)=h(z)\]
Note \(f(x)\eq_h g(x)\) for all \(x\in A\) since \(h\after f=h\after g\). This implies \({\eq}\subseteq{\eq_h}\), so if \(y\eq z\) then \(h(y)=h(z)\). In other words, \(h\)~respects~\(\eq\). Define \(\overline{h}:C\to D\) by \([y]\mapsto h(y)\). Then \(\overline{h}\)~is well defined since \(h\)~respects~\(\eq\), and \(\overline{h}\after\pi=h\). Moreover, \(\overline{h}\)~is unique since \(\pi\)~is epic (surjective).

Therefore \(\pi\)~is a coequalizer of \(f\)~and~\(g\).
\end{proof}

\begin{exer}[14]
In the category~\(\Sets\):
\begin{enumerate}[itemsep=0pt]
\item[(a)] If \(f:A\to B\) and
\[A\lTo^{p_1}A\times A\rTo^{p_2}A\]
then the equalizer of \(f\after p_1\)~and~\(f\after p_2\) is an equivalence relation on~\(A\), called the \emph{kernel} of~\(f\).
\item[(b)] If \(R\)~is an equivalence relation on~\(A\) and \(\pi:A\to A/R\) is the projection \(x\mapsto[x]\), then \(\ker\pi=R\).
\item[(c)] If \(R\)~is a binary relation on~\(A\) and \(\gen{R}\)~is the equivalence relation on~\(A\) generated by~\(R\), then the projection \(\pi:A\to A/\gen{R}\) is a coequalizer of the projections \(p_1,p_2:R\to A\).
\item[(d)] If \(R\)~is a binary relation on~\(A\), then \(\gen{R}\)~is just the kernel of the coequalizer of the projections \(p_1,p_2:R\to A\).
\end{enumerate}
\end{exer}
\begin{proof}\
\begin{enumerate}[itemsep=0pt]
\item[(a)] We know (Example~3.15) that the equalizer is just (the inclusion of)
\begin{align*}
E&=\{\,(x,y)\mid f\after p_1(x,y)=f\after p_2(x,y)\,\}\\
	&=\{\,(x,y)\mid f(x)=f(y)\,\}\subseteq A\times A
\end{align*}
It is immediate that \(E\)~is an equivalence relation on~\(A\).
\item[(b)] We have
\begin{align*}
(x,y)\in\ker\pi&\iff\pi(x)=\pi(y)\\
	&\iff[x]=[y]\\
	&\iff(x,y)\in R
\end{align*}
\item[(c)] By the proof of Exercise~11 with \(f=p_1\) and \(g=p_2\).
\item[(d)] By part~(b) we know \(\gen{R}=\ker\pi\) where \(\pi:A\to A/\gen{R}\) is the projection \(x\mapsto[x]\), and by part~(c) we know \(\pi\)~is a coequalizer of the projections \(p_1,p_2:R\to A\).\qedhere
\end{enumerate}
\end{proof}
\begin{rmk}
The kernel of a function is just the set of pairs of elements identified or equated by the function. For projecton under an equivalence relation, this is obviously just the relation itself. If we want to identify elements under an \emph{arbitrary} relation (using a quotient construction), then we must also identify elements under the equivalence relation generated by that relation.
\end{rmk}

\newpage
\section*{Chapter~4}
\begin{rmk}
For a group in a category, the characterizing ``equations''
\begin{gather*}
m(m(x,y),z)=m(x,m(y,z))\\
m(x,u)=x=m(u,x)\\
m(x,ix)=u=m(ix,x)
\end{gather*}
must be understood to \emph{mean} that the following diagrams commute:
\begin{diagram}
(Z\times Z)\times Z					&		&\rTo^{\iso}	&		&Z\times(Z\times Z)\\
\dTo<{(m\after(x\times y))\times z}	&		&				&		&\dTo>{x\times(m\after(y\times z))}\\
G\times G							&\rTo_m	&G				&\lTo_m	&G\times G
\end{diagram}
\begin{diagram}
Z\times 1		&\lTo^{\pair{1_Z}{!}}_{\iso}&Z		&\rTo^{\pair{!}{1_Z}}_{\iso}	&1\times Z\\
\dTo<{x\times u}&							&\dTo<x	&								&\dTo>{u\times x}\\
G\times G		&\rTo_m						&G		&\lTo_m							&G\times G
\end{diagram}
\begin{diagram}
Z\times Z			&\lTo^{\Delta}	&Z			&\rTo^{\Delta}	&Z\times Z\\
\dTo<{x\times ix}	&				&\dTo<{u!}	&				&\dTo>{ix\times x}\\
G\times G			&\rTo_m			&G			&\lTo_m			&G\times G
\end{diagram}
Note that a ``pair'' like \((x,y)\) in an ``equation'' is interpreted as a product arrow \(x\times y\) in the corresponding diagram.

The defining diagrams for~\(G\) commute if and only if the above diagrams commute for all \(x,y,z:Z\to G\). Indeed, for the forward direction, the above diagrams can be factored through the diagrams for~\(G\); for the reverse direction, taking \(x=y=z=1_G\) in the above diagrams yields the diagrams for~\(G\).
\end{rmk}

\begin{rmk}
We can also consider the concept of a \emph{group (or monoid) in a monoidal category}, which has the monoidal product~\(\mprod\) instead of~\(\times\) in its definition. For example, a \emph{monad} on a category~\(\C\) is a monoid in the monoidal category~\(\C^{\C}\) of endofunctors of~\(\C\) under composition.\footnote{See Chapters 7 and~10.}
\end{rmk}

\begin{rmk}
The homomorphism theorem for groups (Theorem~4.10) shows that for a group homomorphism \(h:G\to H\), \(\ker h\)~is universal among the normal subgroups of~\(G\) factorization through which preserves~\(h\). Equivalently, \(G/\ker h\) is universal among quotients through which \(h\)~is preserved.

In detail, \(K=\ker h\) is a normal subgroup of~\(G\) making the following diagram commute:
\begin{diagram}[nohug]
G			&\rTo^h					&H\\
\dTo<{\pi_K}&\ruTo>{\overline{h_K}}	&\\
G/K			&						&
\end{diagram}
Given any normal subgroup \(N\)~of~\(G\) making the following diagram commute:
\begin{diagram}[nohug]
G			&\rTo^h					&H\\
\dTo<{\pi_N}&\ruTo>{\overline{h_N}}	&\\
G/N			&						&
\end{diagram}
there exists a unique homomorphism \(\pi_{K/N}:G/N\to G/K\) making the following diagram commute:
\begin{diagram}[nohug]
G/N				&\rTo^{\overline{h_N}}	&H\\
\dTo<{\pi_{K/N}}&\ruTo>{\overline{h_K}}	&\\
G/K				&						&
\end{diagram}
Indeed, \(\pi_{K/N}([x]_N)=[x]_K\) is a well defined homomorphism since \(N\subseteq K\), and
\[(\overline{h_K}\after\pi_{K/N})([x]_N)=\overline{h_K}(\pi_{K/N}([x]_N))=\overline{h_K}([x]_K)=h(x)=\overline{h_N}([x]_N)\]
Also \(\pi_{K/N}\)~is unique since \(\overline{h_K}\)~is injective. In other words, \(\overline{h_N}\)~factors uniquely through~\(\overline{h_K}\).

Intuitively, as \(N\)~ranges from \(1\)~to~\(K\), \(G/N\)~``collapses'' more and more of the structure of~\(G\) while still preserving~\(h\). Since \(G/K\)~is the ``smallest'' with this property, it is always possible to collapse from~\(G/N\) to \(G/K\) and still preserve~\(h\).

Observe \(\pi_{K/N}\)~is surjective and \(\ker\pi_{K/N}=K/N\), from which it follows that
\[(G/N)/(K/N)\iso G/K\]
This is just the third isomorphism theorem for groups.
\end{rmk}

\begin{exer}[1]
Let \(G\)~be a group. A categorical congruence~\(\eq\) on~\(G\) (viewed as a category\footnote{Recall a group is a category with only one object in which every arrow is an iso.}) is the same thing as an equivalence relation on~\(G\) determined by a normal subgroup \(N\subseteq G\). Moreover, \(G/{\eq}=G/N\).
\end{exer}
\begin{proof}
If \(\eq\)~is a categorical congruence on~\(G\), then \(\eq\)~determines an equivalence relation on the arrows of~\(G\), which are just the elements of~\(G\). Let \(N=[1]\) be the equivalence class of the identity \(1\in G\). For \(x,y\in G\), observe
\begin{align*}
x\eq y&\iff xy^{-1}\eq yy^{-1}=1&&\text{by closure of~\(\eq\)}\\
	&\iff xy^{-1}\in [1]=N
\end{align*}
Now \(1\in N\), and if \(x,y\in N\) then \(x\eq y\), so \(xy^{-1}\in N\). Hence \(N\)~is a subgroup of~\(G\). Moreover, if \(x\in N\) and \(y\in G\), then again by closure
\[yxy^{-1}\eq y1y^{-1}=yy^{-1}=1\]
so \(yxy^{-1}\in N\). Hence \(N\)~is normal. The above biconditional shows that \(\eq\)~is just the equivalence relation determined by~\(N\).

Conversely, if \(N\)~is a normal subgroup of~\(G\), then the equivalence relation defined by
\[x\eq y\iff xy^{-1}\in N\]
is a categorical congruence. Indeed, if \(x\eq y\) then \(x\)~is trivially parallel to~\(y\) since all arrows are parallel (there being only one object). If \(x\eq y\), then \(xy^{-1}\in N\), so for \(w,z\in G\),
\[wxz(wyz)^{-1}=wxzz^{-1}y^{-1}w^{-1}=w(xy^{-1})w^{-1}\in N\]
since \(N\)~is normal, so \(wxz\eq wyz\). Hence \(\eq\)~is closed under composition.

Now for congruence~\(\eq\), \(G/{\eq}\)~consists of one object and arrows which are the equivalence classes of the arrows in~\(G\) under~\(\eq\), composed by \([x][y]=[xy]\). This arrow structure matches the element structure of~\(G/N\), where \(N\)~is the normal subgroup of~\(G\) corresponding to~\(\eq\). Therefore \(G/{\eq}=G/N\).
\end{proof}
\begin{rmk}
This exercise shows that the homomorphism theorem for categories (Theorem~4.13) is in fact a generalization of the homomorphism theorem for groups (Theorem~4.10).
\end{rmk}

\begin{exer}[3]
If \(G\)~is an abelian group, then \(G\)~is a group in the category of groups.
\end{exer}
\begin{proof}
Since \(G\)~is a group, \(G\)~is an object in the category. Define \(m:G\times G\to G\) by \(m(x,y)=xy\). Then for \((x,y),(x',y')\in G\times G\),
\begin{align*}
m((x,y)(x',y'))&=m(xx',yy')&&\text{since }(x,y)(x',y')=(xx',yy')\\
	&=xx'yy'&&\\
	&=xyx'y'&&\text{since \(G\)~is abelian}\\
	&=m(x,y)m(x',y')&&
\end{align*}
So \(m\)~is a homomorphism, that is, an arrow in the category. Define \(u:1\to G\) by \(u(u)=u\) and \(i:G\to G\) by \(i(x)=x^{-1}\). Clearly \(u\)~is a homomorphism. If \(x,y\in G\), then
\[i(xy)=(xy)^{-1}=y^{-1}x^{-1}=x^{-1}y^{-1}=i(x)i(y)\]
since \(G\)~is abelian. So \(i\)~is a homomorphism.

Now for \(x,y,z\in G\), we have
\[m(m(x,y),z)=m(xy,z)=(xy)z=x(yz)=m(x,yz)=m(x,m(y,z))\]
and
\[m(x,u)=xu=x=ux=m(u,x)\]
and
\[m(x,i(x))=m(x,x^{-1})=xx^{-1}=u=x^{-1}x=m(x^{-1},x)=m(i(x),x)\]
So \(m\)~is associative, \(u\)~is a unit for~\(m\), and \(i\)~is an inverse for~\(m\), for elements of~\(G\). It follows that this is also true for generalized elements of~\(G\), by definition of the homomorphism composition and pairing operations in the category. Therefore \(G\)~is a group in the category.
\end{proof}

\begin{exer}[7]
Let \(\eq\)~be a congruence in~\(\C\). If \(f,f':A\to B\), \(g,g':B\to C\), \(f\eq f'\), and \(g\eq g'\), then \(gf\eq g'f'\).
\end{exer}
\begin{proof}
By two applications of closure, we have
\[gf\eq gf'\eq g'f'\qedhere\]
\end{proof}
\begin{rmk}
Together with the fact that congruent arrows are parallel, this exercise shows that composition in the congruence category~\(\C^{\eq}\) is well defined.
\end{rmk}

\begin{exer}[8]
Let \(F,G:\C\to\D\) be functors such that \(F(X)=G(X)\) for all objects \(X\in\C\). Define a relation~\(\eq\) on the arrows of~\(\D\) as follows:
\begin{quote}
\(f\eq g\) \(\iff\) \(f\)~and~\(g\) are parallel and for all functors \(H:\D\to\E\) with \(HF=HG\), \(H(f)=H(g)\).
\end{quote}
Then \(\eq\)~is a congruence on~\(\D\), and \(\D/{\eq}\)~is a coequalizer of \(F\)~and~\(G\).
\end{exer}
\begin{proof}
It is immediate that \(\eq\)~is an equivalence relation on parallel arrows. If \(f,g:A\to B\), \(a:X\to A\), \(b:B\to Y\), and \(f\eq g\), we claim \(bfa\eq bga\). Indeed, \(bfa\)~and~\(bga\) are parallel since \(f\)~and~\(g\) are parallel, and if \(H:\D\to\E\) is a functor with \(HF=HG\), then
\[H(bfa)=H(b)H(f)H(a)=H(b)H(g)H(a)=H(bga)\]
So \(\eq\)~is closed under composition, and hence is a congruence.

Now if \(f\in\C\), then \(F(f)\)~and~\(G(f)\) are parallel since \(F\)~and~\(G\) agree on objects, and if \(H:\D\to\E\) with \(HF=HG\), then
\[H(F(f))=HF(f)=HG(f)=H(G(f))\]
Therefore \(F(f)\eq G(f)\) for all \(f\in\C\).\footnote{In fact, \(\eq\)~is the congruence generated by pairs \(F(f)\eq G(f)\) for all arrows \(f\in\C\). Compare with Exercise~3.13.}

Let \(P:\D\to\D/{\eq}\) be the projection functor \(f\mapsto[f]\). Then \(PF\)~and~\(PG\) agree on objects since \(F\)~and~\(G\) do, and \(PF\)~and~\(PG\) agree on arrows since \(F(f)\eq G(f)\) for all \(f\in\C\). Therefore \(PF=PG\). If \(H:\D\to\E\) is any functor with \(HF=HG\), then \(H\)~respects the congruence by definition of the congruence, so the functor \(\overline{H}:\D/{\eq}\to\E\) given by \([f]\mapsto H(f)\) is well defined with \(\overline{H}P=H\). Moreover, \(\overline{H}\)~is unique in this regard since \(P\)~is epic.
\end{proof}

\newpage
\section*{Chapter~5}
\begin{rmk}
The pullback functor \(\Cop\to\Cat\) (Proposition 5.10) is closely related to the slice functor \(\C/(-):\C\to\Cat\) (Section 1.6). They both map an object~\(C\) to the slice category~\(\C/C\). The former maps an arrow to a functor taking the ``inverse image'' (pullback) under that arrow, while the latter maps an arrow to a functor taking the image (composite) under that arrow.
\end{rmk}

\begin{rmk}
If \(\J\)~is an index category with initial object \(i\in\J\), then for any diagram \(D:\J\to\C\),
\[\limit_{j\in\J}D_j=D_i\]
Dually if \(i\in\J\) is a terminal object, then
\[\colimit_{j\in\J}D_j=D_i\]
\end{rmk}

\begin{rmk}
If \(F:\C\to\D\) creates limits of type~\(\J\), and \(\D\)~has all limits of type~\(\J\), then \(F\)~also preserves limits of type~\(\J\). In other words, \emph{creating limits is a stronger condition than preserving limits}, provided the target category has limits.
\end{rmk}
\begin{proof}
If \(C:\J\to\C\) is a diagram of type~\(\J\) in~\(\C\) with limit \(p_j:L\to C_j\) in~\(\C\), then \(Fp_j:FL\to FC_j\) is a cone to~\(FC\) in~\(\D\). Let \(q_j:\limit_j FC_j\to FC_j\) denote the limit of~\(FC\) in~\(\D\). Since \(F\)~creates limits, there is a limit \(p_j':L'\to C_j\) to~\(C\) in~\(\C\) with \(FL'=\limit_j FC_j\) and \(Fp_j'=q_j\). By uniqueness of limits in~\(\C\), there is \(u:L\iso L'\) with \(p_j'\after u=p_j\), so \(Fu:FL\iso FL'=\limit_j FC_j\) with
\[q_j\after Fu=Fp_j'\after Fu=F(p_j'\after u)=Fp_j\]
That is, the cone \(Fp_j:FL\to FC_j\) is isomorphic to the cone \(q_j:\limit_j FC_j\to FC_j\) in~\(\D\), so \(Fp_j:FL\to FC_j\) is a limit to~\(FC\) in~\(\D\).
\end{proof}

\begin{exer}[1]
Let \(\C\)~be a category and \(X\in\C\). A pullback in~\(\C\) over~\(X\) is just a product in~\(\C/X\).
\end{exer}
\begin{proof}
This follows directly from the universal mapping properties. Alternately, we know (Example~5.20) that a pullback is a limit of a diagram of this type:
\begin{diagram}
	&		&\obj\\
	&		&\dTo\\
\obj&\rTo	&\obj
\end{diagram}
Similarly (Example~5.17), a product is a limit of a diagram of this type:
\[\obj\qquad\obj\]
A diagram of the former type in~\(\C\) over~\(X\) is just a diagram of the latter type in~\(\C/X\), so the limits coincide.
\end{proof}

\begin{exer}[3]
A pullback of a mono is a mono.
\end{exer}
\begin{proof}
Suppose \(m:M\mono A\) is a mono and \(m':M'\to A'\) is a pullback of~\(m\) along \(f:A'\to A\). Further suppose \(x,y:X\to M'\) with \(m'x=m'y\):
\begin{diagram}
X	&\pile{\rTo^x\\\rTo_y}	&M'			&\rTo^{f'}	&M\\
	&\rdTo					&\dTo<{m'}	&			&\dMono>m\\
	&						&A'			&\rTo_f		&A
\end{diagram}
Then
\[m(f'x)=(mf')x=(fm')x=f(m'x)=f(m'y)=(fm')y=(mf')y=m(f'y)\]
It follows that \(f'x=f'y\) since \(m\)~is monic. Set \(g=m'x=m'y\) and \(h=f'x=f'y\). Since \(M'\)~is a pullback, there is a unique \(z:X\to M'\) with \(m'z=g\) and \(f'z=h\), and since \(x\)~and~\(y\) both satisfy these equations, it follows that \(x=y\). Therefore \(m'\)~is monic as desired.
\end{proof}

\begin{exer}[4]
Let \(\C\)~be a category, \(A\in\C\), and \(M,N\in\Sub_{\C}(A)\). Then
\[M\subseteq N\iff\forall z:Z\to A\ (z\in_A M\implies z\in_A N)\]
\end{exer}
\begin{proof}
If \(M\subseteq N\), let \(i:M\to N\) satisfy \(m=ni\). For \(z:Z\to A\) with \(z\in_A M\), let \(\overline{z}:Z\to M\) satisfy \(z=m\overline{z}\):
\begin{diagram}[nohug]
Z	&\rTo^{\overline{z}}&M			&\rTo^i		&N\\
	&\rdTo_z			&\dMono>m	&\ldMono>n	&\\
	&					&A			&			&
\end{diagram}
Then
\[z=m\overline{z}=(ni)\overline{z}=n(i\overline{z})\]
So \(i\overline{z}:Z\to N\) witnesses \(z\in_A N\).

Conversely, if \(z\in_A M\) implies \(z\in_A N\), then since \(m\in_A M\) trivially (\(m=m1_A\)), we have \(m\in_A N\). This means there is \(i:M\to N\) with \(m=ni\), so \(M\subseteq N\).
\end{proof}

\begin{exer}[5]
Let \(\C\)~be a category, \(A\in\C\), and \(M,N\in\Sub_{\C}(A)\). Then
\[M\equiv N\iff\forall z:Z\to A\ (z\in_A M\iff z\in_A N)\]
\end{exer}
\begin{proof}
Immediate from Exercise~4.
\end{proof}

\begin{rmk}
The previous two results justify the abuse of subset notation for subobjects through the abuse of set membership notation for generalized elements. 
\end{rmk}

\begin{exer}[6]
Let \(\C\)~be a category with products and pullbacks. Then \(\C\)~has equalizers.
\end{exer}
\begin{proof}
Given \(f,g:A\to B\), construct this pullback:
\begin{diagram}
E		&\rTo^h				&B\\
\dTo<e	&					&\dTo>{\pair{1_B}{1_B}}\\
A		&\rTo_{\pair{f}{g}}	&B\times B
\end{diagram}
We claim that \(e:E\to A\) is an equalizer of \(f\)~and~\(g\). Indeed, since the diagram commutes,
\[\pair{fe}{ge}=\pair{f}{g}e=\pair{1_B}{1_B}h=\pair{h}{h}\]
Therefore \(fe=ge\). And if \(z:Z\to A\) with \(fz=gz\), then this square commutes:
\begin{diagram}
Z		&\rTo^{fz=gz}		&B\\
\dTo<z	&					&\dTo>{\pair{1_B}{1_B}}\\
A		&\rTo_{\pair{f}{g}}	&B\times B
\end{diagram}
Since \(E\)~is a pullback, there exists a unique \(u:Z\to E\) with \(z=eu\).
\end{proof}

\begin{exer}[7]
Let \(\C\)~be a locally small category with all small limits and \(C\in\C\). Then the representable functor
\[\Hom_{\C}(C,-):\C\to\Sets\]
is continuous.
\end{exer}
\begin{proof}
We prove this directly from the definition of limit, not using products and equalizers.\footnote{Compare the proof of Proposition~5.25.}

Write \(H=\Hom_{\C}(C,-)\). Let \(D:\J\to\C\) be a diagram of type~\(\J\) in~\(\C\), and let \(p_j:\limit_j D_j\to D_j\) be a limit for~\(D\) in~\(\C\). We claim \(H(p_j):H(\limit_j D_j)\to H(D_j)\) is a limit for~\(HD\) in~\(\Sets\). Indeed, clearly it is a cone to~\(HD\) in~\(\Sets\) since \(H\)~is a functor. Suppose \((X,x_j)\)~is a cone to~\(HD\) in~\(\Sets\), so the arrows \(x_j:X\to H(D_j)\) form commutative triangles of the following form for \(\alpha:i\to j\) in~\(\J\):
\begin{diagram}[nohug]
		&			&X						&			&\\
		&\ldTo<{x_i}&						&\rdTo>{x_j}&\\
H(D_i)	&			&\rTo_{H(D_{\alpha})}	&			&H(D_j)
\end{diagram}
We must show there is a unique \(u:X\to H(\limit_j D_j)\) in~\(\Sets\) with \(x_j=H(p_j)u\). To this end, observe that for \(x\in X\), \((C,x_j(x))\)~is a cone to~\(D\) in~\(\C\). Indeed, from the above diagram it follows that for \(j\in\J\), \(x_j(x):C\to D_j\) in~\(\C\) and for \(\alpha:i\to j\in\J\), this diagram commutes:
\begin{diagram}[nohug]
		&				&C					&				&\\
		&\ldTo<{x_i(x)}	&					&\rdTo>{x_j(x)}	&\\
D_i		&				&\rTo_{D_{\alpha}}	&				&D_j
\end{diagram}
Let \(u(x)\)~be the unique \(C\to\lim_j D_j\) in~\(\C\) with \(x_j(x)=p_ju(x)\). Then for \(x\in X\),
\[(H(p_j)u)(x)=H(p_j)(u(x))=p_ju(x)=x_j(x)\]
So \(H(p_j)u=x_j\). Moreover, if \(u':X\to H(\limit_j D_j)\) in~\(\Sets\) satisfies \(x_j=H(p_j)u'\), then for \(x\in X\), \(u'(x):C\to\limit_j D_j\) in~\(\C\) with \(x_j(x)=H(p_j)u'(x)\), so \(u'(x)=u(x)\) by uniqueness of~\(u(x)\). Therefore \(u'=u\), so \(u\)~is unique as needed.
\end{proof}

\begin{exer}[9]
Let \(\C\)~be a category with limits of type~\(\J\). There exists a category \(\Diagrams(\J,\C)\) of diagrams of type~\(\J\) in~\(\C\), and a limit functor
\[\limit_{\J}:\Diagrams(\J,\C)\to\C\]
In particular, there exists a product functor
\[\prod_{i\in I}:\Sets^{I}\to\Sets\]
for \(I\)-indexed families of sets.
\end{exer}
\begin{proof}
The objects in \(\Diagrams(\J,\C)\) are functors \(F:\J\to\C\), and the arrows are natural transformations between those functors.\footnote{In other words, \(\Diagrams(\J,\C)\) is just the functor category~\(\C^{\J}\). See Chapter~7.} More specifically, an arrow \(\theta:F\to G\) between \(F:\J\to\C\) and \(G:\J\to\C\) is a family of arrows \(\theta_j:Fj\to Gj\) for each \(j\in\J\) such that for \(\alpha:i\to j\in\J\), this square commutes:
\begin{diagram}
Fi				&\rTo^{\theta_i}	&Gi\\
\dTo<{F\alpha}	&					&\dTo>{G\alpha}\\
Fj				&\rTo_{\theta_j}	&Gj
\end{diagram}
The identity~\(1_F\) consists of the identity arrows~\(1_{Fj}\) for \(j\in\J\). If \(\theta:F\to G\) and \(\lambda:G\to H\), then \(\lambda\theta:F\to H\) consists of the composite arrows~\(\lambda_j\theta_j\) for \(j\in\J\). Indeed, the diagrams involved obviously commute, and associativity and unity of composition are inherited from~\(\C\).

For \(F:\J\to\C\), let \(\limit F\)~be the vertex of the limit of~\(F\) in~\(\C\). For \(\theta:F\to G\), let \(f_j:\limit F\to Fj\) and \(g_j:\limit G\to Gj\) in~\(\C\) and observe that \(\theta_jf_j:\limit F\to Gj\) is a cone to~\(G\) in~\(\C\). Let \(\limit \theta\)~be the unique \(u_{\theta}:\limit F\to\limit G\) in~\(\C\) such that \(\theta_jf_j=g_ju_{\theta}\). We claim \(\limit\)~is a functor. Indeed, it clearly maps objects to objects and arrows to arrows and preserves domains and codomains of arrows. It is also clear that \(\limit 1_F=1_{\limit F}\). If \(\theta:F\to G\) and \(\lambda:G\to H\), then \(\limit\lambda\theta\) is the unique \(u_{\lambda\theta}:\limit F\to\limit H\) such that \(\lambda_j\theta_j f_j=h_ju_{\lambda\theta}\). Now \(u_{\lambda}u_{\theta}:\limit F\to\limit H\) and it follows from \(\theta_jf_j=g_ju_{\theta}\) and \(\lambda_jg_j=h_ju_{\lambda}\) that \(\lambda_j\theta_jf_j=h_ju_{\lambda}u_{\theta}\). Therefore \(u_{\lambda\theta}=u_{\lambda}u_{\theta}\) by uniqueness of~\(u_{\lambda\theta}\), that is, \(\limit\lambda\theta=(\limit\lambda)(\limit\theta)\), as desired.

Now viewing the set~\(I\) as a discrete category, an \(I\)-indexed family of sets is just a diagram of type~\(I\) in~\(\Sets\), and in this case the limit is just the product. Hence \(\prod\)~is a functor by the above.
\end{proof}
\begin{rmk}
It follows that if \(F,G:\J\to\C\) and \(F\iso G\), then \(\limit F\iso\limit G\).
\end{rmk}

\begin{rmk}
If \(F:\J\to\C\), and \(f_j:L\to Fj\) and \(f_j':L'\to Fj\) are both limits of~\(F\) in~\(\C\), then \(f=(f_j)\)~is a natural transformation from the constant functor \(\Delta(L):\J\to\C\) to~\(F\), and \(\limit f:L\to L'\) is the isomorphism with \(f_j=f_j'\after\limit f\).
\end{rmk}

\begin{exer}[12]
In~\(\Pos\), let \([n]=\{0\le\cdots\le n\}\), let \([n]\to[n+1]\) be inclusion, and let the sequence \(S:\omega\to\Pos\) be given by
\[[0]\to[1]\to\cdots[n]\to[n+1]\to\cdots\]
Then \(\limit S=[0]\) and \(\colimit S=\omega\).
\end{exer}
\begin{proof}
Immediate from definitions.
\end{proof}

\newpage
\section*{Chapter~6}
\begin{rmk}
An exponential \emph{object} \(B^A\) ``captures'' the \emph{arrows} \(A\to B\) in a category. The sense in which the arrows are captured depends on the category.
\end{rmk}

\begin{rmk}
Let \(\C\)~be a (locally small) category with binary products and \(B,C\in\C\). An object \(C^B\in\C\) is an exponential for \(B\) and~\(C\) if and only if
\[\Hom_{\C}(A\times B,C)\iso\Hom_{\C}(A,C^B)\tag{1}\]
for all \(A\in\C\) and the isomorphism is natural in~\(A\).\footnote{The concept of naturality is defined in Chapter~7.}
\end{rmk}
\begin{proof}
If \(C^B\)~is an exponential, let \(\eval:C^B\times B\to C\) be the evaluation arrow. We know that transposition relative to~\(\eval\) induces the isomorphism~(1). Moreover, if \(f:A\times B\to C\) and \(g:A'\to A\), then this diagram commutes:
\begin{diagram}[nohug]
C^B\times B					&								&\\
\uTo<{\curry{f}\times 1_B}	&\rdTo^{\eval}					&\\
A\times B					&\rTo_f							&C\\
\uTo<{g\times 1_B}			&\ruTo>{f\after(g\times 1_B)}	&\\
A'\times B					&								&
\end{diagram}
Since
\[(\curry{f}\times 1_B)\after(g\times 1_B)=(\curry{f}\after g)\times 1_B\]
it follows that
\[\curry{(f\after(g\times 1_B))}=\curry{f}\after g\]
so this diagram commutes:
\begin{diagram}
\Hom(A\times B,C)			&\rTo^{\iso}&\Hom(A,C^B)\\
\dTo<{\Hom(g\times 1_B,C)}	&			&\dTo>{\Hom(g,C^B)}\\
\Hom(A'\times B,C)			&\rTo_{\iso}&\Hom(A',C^B)
\end{diagram}
This establishes naturality of~(1) in~\(A\).

Conversely, if (1)~holds naturally in~\(A\), first take \(A=C^B\) and let \(\eval:C^B\times B\to C\) be the arrow corresponding to~\(1_{C^B}\). If \(f:A\times B\to C\) for some~\(A\), let \(\curry{f}:A\to C^B\) be the arrow corresponding to~\(f\) in~(1). Then commutativity of
\begin{diagram}
\Hom(C^B\times B,C)					&\rTo^{\iso}&\Hom(C^B,C^B)\\
\dTo<{\Hom(\curry{f}\times 1_B,C)}	&			&\dTo>{\Hom(\curry{f},C^B)}\\
\Hom(A\times B,C)					&\rTo_{\iso}&\Hom(A,C^B)
\end{diagram}
implies
\[\eval\after(\curry{f}\times 1_B)=f\]
Moreover, \(\curry{f}\)~is unique with this property. So \(C^B\) (with~\(\eval\)) is an exponential.
\end{proof}

\begin{rmk}
Let \(\C\)~be a (locally small) category with binary products and \(B\in\C\). If \(E:\C\to\C\) is a functor, then \(E\iso(-)^B\) if and only if
\[\Hom_{\C}(A\times B,C)\iso\Hom_{\C}(A,EC)\]
for all \(A,C\in\C\) and the isomorphism is natural in both \(A\) and~\(C\).
\end{rmk}
\begin{proof}
By extension of the previous argument, or by the fact that the product functor \((-)\times B\) is left adjoint to the exponential functor \((-)^B\).\footnote{See Chapter~9.}
\end{proof}

\begin{rmk}
Let \(\C\)~be a cartesian closed category and \(\eta=\curry{1_{A\times B}}:A\to(A\times B)^B\). For \(f:A\times B\to C\), to see that the diagram
\begin{diagram}[nohug]
(A\times B)^B	&\rTo^{f^B}			&C^B\\
\uTo<{\eta}		&\ruTo>{\curry{f}}	&\\
A				&					&
\end{diagram}
commutes, observe that the diagram
\begin{diagram}[nohug]
C^B\times B				&\rTo^{\eval}			&C\\
\uTo<{f^B\times 1_B}	&						&\uTo>f\\
(A\times B)^B\times B	&\rTo_{\eval}			&A\times B\\
\uTo<{\eta\times 1_B}	&\ruTo>{1_{A\times B}}	&\\
A\times B				&						&
\end{diagram}
commutes and
\[(f^B\times 1_B)\after(\eta\times 1_B)=(f^B\after\eta)\times 1_B\]
This result shows that the transpose of~\(f\) can be obtained by applying~\(f\) after the transposed pairing operation~\(\eta\). The transpose~\(\eta\) is ``universal'' because every transpose can be obtained from it in this way. Note \(\eta\)~is just the unit of the adjunction \((-)\times B\adj(-)^B\) at~\(A\), while \(\eval\)~is the counit.\footnote{See Chapter~9.}
\end{rmk}

\begin{rmk}
If \(p:A\to I\) is a function and \(A_i=\inv{p}(i)\), then the following diagram is a pullback:
\begin{diagram}
\prod_{i\in I}A_i	&\rTo	&A^I\\
\dTo				&		&\dTo>{p^I}\\
1					&\rTo	&I^I
\end{diagram}
In other words, \emph{multiplication over~\(I\) is a pullback of exponentiation by~\(I\)}. This idea allows us to define products in categories with pullbacks and exponentials.
\end{rmk}

\begin{rmk}
If \(\C\)~and~\(\D\) are cartesian closed categories, then so is~\(\C\times\D\). Moreover, the terminal object, products, and exponentials (including the evaluation and transpose maps for exponentials) are all computed componentwise.
\end{rmk}
\begin{proof}
Let \(1_{\C}\)~be terminal in~\(\C\) and \(1_{\D}\)~be terminal in~\(\D\). Then for \((C,D)\in\C\times\D\), \((\term_C,\term_D):(C,D)\to(1_{\C},1_{\D})\) is unique, so \(1_{\C\times\D}=(1_{\C},1_{\D})\)~is terminal in~\(\C\times\D\).

Suppose \((A,B),(C,D)\in\C\times\D\). Then \((A\times C,B\times D)\in\C\times\D\) and
\[(A,B)\lTo^{(p_1,p_1)}(A\times C,B\times D)\rTo^{(p_2,p_2)}(C,D)\]
For \(f:(X,Y)\to(A,B)\) and \(g:(X,Y)\to(C,D)\), define
\[\pair{f}{g}=\bigl(\pair{f_1}{g_1},\pair{f_2}{g_2}\bigr):(X,Y)\to(A\times C,B\times D)\]
Then
\[(p_1,p_1)\after\pair{f}{g}=(f_1,f_2)=f\quad\text{and}\quad(p_2,p_2)\after\pair{f}{g}=(g_1,g_2)=g\]
Conversely, for any \(h:(X,Y)\to(A\times C,B\times D)\),
\begin{align*}
\pair{(p_1,p_1)\after h}{(p_2,p_2)\after h}&=\pair{(p_1\after h_1,p_1\after h_2)}{(p_2\after h_1,p_2\after h_2)}\\
	&=\bigl(\pair{p_1\after h_1}{p_2\after h_1},\pair{p_1\after h_2}{p_2\after h_2}\bigr)\\
	&=(h_1,h_2)\\
	&=h
\end{align*}
Therefore \((A,B)\times(C,D)=(A\times C,B\times D)\) is a product in~\(\C\times\D\).

We claim \((C^A,D^B)\)~is an exponential for \((A,B)\)~and~\((C,D)\) in~\(\C\times\D\). Indeed, let \(\eval_{C^A}:C^A\times A\to C\) and \(\eval_{D^B}:D^B\times B\to D\) be evaluation arrows in \(\C\)~and~\(\D\) respectively and define
\[\eval=(\eval_{C^A},\eval_{D^B}):(C^A,D^B)\times(A,B)\to(C,D)\]
For \(f:(X,Y)\times(A,B)\to(C,D)\), \(f_1:X\times A\to C\) and \(f_2:Y\times B\to D\), so \(\curry{f_1}:X\to C^A\) and \(\curry{f_2}:Y\to D^B\). Define
\[\curry{f}=(\curry{f_1},\curry{f_2}):(X,Y)\to(C^A,D^B)\]
Then
\begin{align*}
\eval\after(\curry{f}\times 1_{(A,B)})&=(\eval_{C^A},\eval_{D^B})\after((\curry{f_1},\curry{f_2})\times(1_A,1_B))\\
	&=(\eval_{C^A},\eval_{D^B})\after(\curry{f_1}\times1_A,\curry{f_2}\times1_B)\\
	&=(f_1,f_2)\\
	&=f
\end{align*}
Conversely, for \(h:(X,Y)\to(C^A,D^B)\),
\[\uncurry{h}=\eval\after(h\times1_{(A,B)})=(\eval_{C^A},\eval_{D^B})\after(h_1\times1_A,h_2\times1_B)=(\uncurry{h_1},\uncurry{h_2})\]
So
\[\curry{\uncurry{h}}=\curry{(\uncurry{h_1},\uncurry{h_2})}=(\curry{\uncurry{h_1}},\curry{\uncurry{h_2}})=(h_1,h_2)=h\]
Therefore \((C,D)^{(A,B)}=(C^A,D^B)\) is an exponential in~\(\C\times\D\) as claimed.
\end{proof}

\begin{rmk}
Let \(\2=\{\,\false\le\true\,\}\) be the initial Boolean algebra. Let \(\2^{(-)}:\Posop\to\Pos\) denote the functor sending a poset~\(I\) to the exponential poset~\(\2^I\) of monotone maps \(I\to\2\) ordered pointwise, and sending a monotone map \(f:J\to I\) to the monotone map \(\2^f:\2^I\to\2^J\) defined by \(\varphi\mapsto\varphi\after f\).\footnote{See Exercise~12.} Note
\[\2^{(-)}=\Hom_{\Pos}(-,\2)\]
with induced poset structure.

Let \(\powU:\Posop\to\Pos\) denote the functor sending a poset~\(I\) to the poset of upward closed subsets of~\(I\) ordered by inclusion, and sending a monotone map \(f:J\to I\) to the monotone map defined by \(S\mapsto\inv{f}(S)\). Then there is a natural isomorphism
\[\2^I\iso\powU(I)\]
In particular, \(\powU\)~is representable.\footnote{Compare to Example~7.4.} Dually, \(\2^{\dual{I}}\)~is naturally isomorphic to the poset of downward closed subsets of~\(I\) under inclusion.
\end{rmk}
\begin{proof}
The isomorphism sends \(\varphi\in\2^I\) to the extension \(S_{\varphi}=\inv{\varphi}(\true)\) and sends \(S\in\powU(I)\) to the characteristic map \(\varphi_S:I\to\2\) defined by
\[\varphi_S(x)=\begin{cases}
\true&\text{if }x\in S\\
\false&\text{otherwise}
\end{cases}\]
For \(f:J\to I\) monotone, the naturality square
\begin{diagram}
\2^I		&\rTo^{\iso}&\powU(I)\\
\dTo<{\2^f}	&			&\dTo>{\powU(f)}\\
\2^J		&\rTo_{\iso}&\powU(J)
\end{diagram}
obviously commutes.
\end{proof}

\begin{rmk}
Let \(I\)~be a poset. It is instructive to see how exponentials in~\(\Sets^I\) fall out of the general construction of exponentials in categories of sheaves using the Yoneda lemma.\footnote{See Chapter~8.} To this end, let \(y:\dual{I}\to\Sets^I\) be the (contravariant) Yoneda embedding. Then
\[y(i)_j=\Hom_I(i,j)\iso\begin{cases}
1&\text{if }i\le j\\
0&\text{otherwise}
\end{cases}\]
and \(y(i)_{jk}:y(i)_j\to y(i)_k\) is the obvious function. Also \(y(i\le j):y(j)\to y(i)\) is the obvious family of functions.

For \(A,B\in\Sets^I\) we must have
\begin{align*}
(B^A)_i&\iso\Hom(y(i),B^A)\\
	&\iso\Hom(y(i)\times A,B)\\
	&\iso\Hom(A|_i,B|_i)
\end{align*}
since
\[(y(i)\times A)_j=y(i)_j\times A_j\iso\begin{cases}
A_j&\text{if }i\le j\\
0&\text{otherwise}
\end{cases}\]
Finally
\[(B^A)_{ij}\iso\Hom(y(i\le j)\times 1_A,B)\]
which obviously sends \(f:A|_i\to B|_i\) to \(f|_j:A|_j\to B|_j\).
\end{rmk}

\begin{rmk}
The category \(\Vect\) of vector spaces and linear maps (over \(\R\), say) is \emph{not} cartesian closed because it does not have exponentials,\footnote{See Exercise~9.} although for any vector spaces \(V\) and~\(W\) there \emph{is} the vector space \(L(V,W)\) of linear maps from \(V\) to~\(W\). Instead, there is a natural isomorphism
\[\Hom(U\tprod V,W)\iso\Hom(U,L(V,W))\]
where \(U\tprod V\) is the tensor product of \(U\) and~\(V\). For this reason, \(\Vect\)~is called \emph{monoidal closed}.
\end{rmk}

\begin{exer}[2]
Let \(\C\)~be a cartesian closed category and \(A,B,C\in\C\).
\begin{enumerate}[itemsep=0pt]
\item[(a)] \((A\times B)^C\iso A^C\times B^C\)
\item[(b)] \((A^B)^C\iso A^{B\times C}\)
\end{enumerate}
\end{exer}
\begin{proof}\
\begin{enumerate}[itemsep=0pt]
\item[(a)] We prove that \(A^C\times B^C\)~is an exponential for \(A\times B\)~and~\(C\), from which the isomorphism follows by uniqueness of exponentials under the universal mapping property.

Let \(\eval_A:A^C\times C\to A\) and \(\eval_B:B^C\times C\to B\) be evaluation arrows, and let
\begin{align*}
\alpha:(A^C\times B^C)\times(C\times C)&\iso(A^C\times C)\times(B^C\times C)\\
	\pair{\pair{w}{x}}{\pair{y}{z}}&\mapsto\pair{\pair{w}{y}}{\pair{x}{z}}
\end{align*}
for generalized elements \(w,x,y,z\). Observe
\[\alpha:\pair{w}{x}\times\pair{y}{z}\mapsto\pair{w\times y}{x\times z}\]
Define \(\eval:(A^C\times B^C)\times C\to A\times B\) by
\[\eval=(\eval_A\times\eval_B)\after\alpha\after(1_{A^C\times B^C}\times\pair{1_C}{1_C})\]
We claim \((A^C\times B^C,\eval)\)~is an exponential for \(A\times B\)~and~\(C\); that is, for all \(f:Z\times C\to A\times B\), there is a unique \(\curry{f}:Z\to A^C\times B^C\) such that \(\eval\after(\curry{f}\times1_C)=f\):
\begin{diagram}[nohug]
A^C\times B^C		&&(A^C\times B^C)\times C		&\rTo^{\eval}	&A\times B\\
\uTo<{\curry{f}}	&&\uTo<{\curry{f}\times1_C}		&\ruTo>f		&\\
Z					&&Z\times C						&				&
\end{diagram}
Indeed, suppose \(f:Z\times C\to A\times B\). Let \(f_1=p_1\after f\) and \(f_2=p_2\after f\):
\begin{diagram}[nohug]
	&			&Z\times C	&				&\\
	&\ldTo<{f_1}&\dTo>f		&\rdTo>{f_2}	&\\
A	&\lTo^{p_1}	&A\times B	&\rTo^{p_2}		&B
\end{diagram}
Then there exist unique \(\curry{f_1}:Z\to A^C\) and \(\curry{f_2}:Z\to B^C\) with \(\eval_A\after(\curry{f_1}\times1_C)=f_1\) and \(\eval_B\after(\curry{f_2}\times1_C)=f_2\). Define \(\curry{f}=\pair{\curry{f_1}}{\curry{f_2}}:Z\to A^C\times B^C\). Then
\begin{align*}
\eval\after(\curry{f}\times1_C)&=(\eval_A\times\eval_B)\after\alpha\after(1_{A^C\times B^C}\times\pair{1_C}{1_C})\after(\pair{\curry{f_1}}{\curry{f_2}}\times1_C)\\
	&=(\eval_A\times\eval_B)\after\alpha\after(\pair{\curry{f_1}}{\curry{f_2}}\times\pair{1_C}{1_C})\\
	&=(\eval_A\times\eval_B)\after\pair{\curry{f_1}\times1_C}{\curry{f_2}\times1_C}\\
	&=\pair{\eval_A\after(\curry{f_1}\times1_C)}{\eval_B\after(\curry{f_2}\times1_C)}\\
	&=\pair{f_1}{f_2}\\
	&=f
\end{align*}
Finally, \(\curry{f}\)~is unique in satisfying this property since \(\curry{f_1}\)~and~\(\curry{f_2}\) are unique. This establishes the claim.
\item[(b)] We exhibit isomorphisms between \((A^B)^C\)~and~\(A^{B\times C}\) directly. Define \(g:(A^B)^C\to A^{B\times C}\) and \(h:A^{B\times C}\to(A^B)^C\) by
\[g=\curry{(\uncurry{\eval}\after\alpha)}\qquad h=\curry{\curry{(\eval\after\inv{\alpha})}}\]
where \(\alpha:Z\times(B\times C)\iso(Z\times C)\times B\).\footnote{We do not distinguish notationally between the different evaluation, transpose, inverse transpose, and isomorphism arrows involved. However, the context makes clear which ones are intended.} We claim that \(g\)~and~\(h\) are mutually inverse, from which it follows that they are isomorphisms.

By the universal mapping property for exponentials applied twice,
\[h\after g=1_{(A^B)^C}\iff\eval\after((\eval\after((h\after g)\times 1_C))\times 1_B)=\eval\after(\eval\times 1_B)\]
Observe
\begin{align*}
\eval\after((\eval\after((h\after g)\times 1_C))\times 1_B)&=\eval\after((\eval\after(h\times1_C)\after(g\times1_C))\times 1_B)\\
	&=\eval\after((\uncurry{h}\after(g\times1_C))\times 1_B)\\
	&=\eval\after(\uncurry{h}\times1_B)\after((g\times1_C)\times1_B)\\
	&=\uncurry{\uncurry{h}}\after((g\times1_C)\times1_B)\\
	&=\eval\after\inv{\alpha}\after((g\times1_C)\times1_B)\\
	&=\eval\after\inv{\alpha}\after\alpha(g\times(1_B\times1_C))\after\inv{\alpha}\\
	&=\eval\after(g\times1_{B\times C})\after\inv{\alpha}\\
	&=\uncurry{g}\after\inv{\alpha}\\
	&=\uncurry{\eval}\after\alpha\after\inv{\alpha}\\
	&=\uncurry{\eval}\\
	&=\eval\after(\eval\times1_B)
\end{align*}
Therefore \(h\after g=1_{(A^B)^C}\). Similarly \(g\after h=1_{A^{B\times C}}\). So \(g\)~and~\(h\) are mutually inverse as claimed.\qedhere
\end{enumerate}
\end{proof}
\begin{rmk}
In~\(\Sets\), this exercise (circuitously) justifies the familiar exponent laws \((ab)^c=a^cb^c\) and \((a^b)^c=a^{bc}\) for \(a,b,c\in\N\).
\end{rmk}

\begin{exer}[4]
\(\Mon\)~is not cartesian closed.
\end{exer}
\begin{proof}
Suppose \(\Mon\)~is cartesian closed. Let \(M\)~and~\(N\) be any monoids with distinct homomorphisms \(f,g:M\to N\) (for example, take \(M=N=(\N,+)\), \(f=0\), and \(g=1\)). Define
\begin{align*}
f':1\times M&\to N&g':1\times M&\to N\\
(0,m)&\mapsto f(m)&(0,m)&\mapsto g(m)
\end{align*}
Then clearly \(f'\)~and~\(g'\) are also distinct homomorphisms. By assumption there is an exponential~\(N^M\) and transpose homomorphisms
\[\curry{f'}:1\to N^M\qquad\text{and}\qquad\curry{g'}:1\to N^M\]
However since \(N^M\)~is a monoid, there is only one homomorphism \(1\to N^M\) (the identity element must be mapped to the identity element), so we must have \(\curry{f'}=\curry{g'}\). Therefore
\[f'=\uncurry{\curry{f'}}=\uncurry{\curry{g'}}=g'\]
---contradicting that \(f'\ne g'\).\footnote{See also Exercise~9.}
\end{proof}

\begin{exer}[5]
For graphs \(G\) and~\(H\), define \(H^G\) to be the graph whose vertices are arbitrary functions \(\varphi:G_v\to H_v\) and whose edges \(\theta:\varphi\to\psi\) are functions \(\theta:G_e\to H_e\) making these diagram commute:\footnote{The edge is the whole triple \((\theta,\varphi,\psi)\)---otherwise the source and target are not uniquely determined!}
\begin{diagram}[eqno=(1)]
G_v				&\lTo^s	&G_e			&\rTo^t	&G_v\\
\dTo<{\varphi}	&		&\dTo>{\theta}	&		&\dTo>{\psi}\\
H_v				&\lTo_s	&H_e			&\rTo_t	&H_v
\end{diagram}
The map \(\eval:H^G\times G\to H\) defined on vertices by \((\varphi,v)\mapsto\varphi(v)\) and on edges by \((\theta,e)\mapsto\theta_e\) is a graph homomorphism. Moreover, for any graph homomorphism \(f:F\times G\to H\) there is a graph homomorphism \(\curry{f}:F\to H^G\) defined on vertices by \(v\mapsto f(v,-)\) and on edges by \(e\mapsto f(e,-)\) unique with \(\eval\after(\curry{f}\times 1_G)=f\). In other words, \(H^G\) (with \(\eval\)) is an exponential for \(G\) and~\(H\).
\end{exer}
\begin{proof}
That \(\eval\)~is a homomorphism follows immediately from~(1). That \(\curry{f}\)~is a homomorphism follows from commutativity of this diagram:
\begin{diagram}
G_v				&\lTo^s	&G_e			&\rTo^t	&G_v\\
\dTo<{f(s(e),-)}&		&\dTo>{f(e,-)}	&		&\dTo>{f(t(e),-)}\\
H_v				&\lTo_s	&H_e			&\rTo_t	&H_v
\end{diagram}
It is obvious that \(\curry{f}\)~is unique with \(\eval\after(\curry{f}\times 1_G)=f\).
\end{proof}

\begin{rmk}
It is instructive to see how this falls out of the general construction of exponentials in categories of sheaves using the Yoneda lemma.\footnote{See Chapter~8.} To this end, let \(\Gamma\)~be the category
\begin{diagram}
e&\pile{\rTo^s\\\rTo_t}&v
\end{diagram}
so the category of graphs is \(\Grph=\Sets^{\Gamma}\), and let \(y:\dual{\Gamma}\to\Grph$ be the (contravariant) Yoneda embedding. Then it is easy to verify:
\begin{itemize}
\item \(y(v)\)~is the ``vertex graph'' \(\vertex\) consisting of a single vertex with no edges.
\item \(y(e)\)~is the ``edge graph'' \(\vertex\edge\vertex\) consisting of two vertices with one edge between them.
\item \(y(s):y(v)\to y(e)\) is the ``source vertex homomorphism'' which picks out the source vertex of the edge graph.
\item \(y(t):y(v)\to y(e)\) is the ``target vertex homomorphism'' which picks out the target vertex of the edge graph.
\item The graph \(\vertex\times G\) is the graph of ``vertices of~\(G\)'' consisting of the vertices of~\(G\) with no edges between them.
\item The graph \((\vertex\edge\vertex)\times G\) is the graph of ``edges of~\(G\)'' consisting of (i) two copies \(v_s\) and~\(v_t\) of each vertex~\(v\) of~\(G\), where \(v_s\) represents ``\(v\)~as a possible source vertex'' and \(v_t\) represents ``\(v\)~as a possible target vertex'', and (ii) an edge \(s(e)_s\to t(e)_t\) for each edge~\(e\) of~\(G\).
\item \(y(s)\times 1_G\) sends each vertex of~\(G\) to that vertex considered as a possible source vertex.
\item \(y(t)\times 1_G\) sends each vertex of~\(G\) to that vertex considered as a possible target vertex.
\end{itemize}
Now if \(H^G\)~is an exponential graph we must have
\begin{align*}
(H^G)_v&\iso\Hom_{\Grph}(y(v),H^G)\\
	&\iso\Hom_{\Grph}(\vertex\, ,H^G)\\
	&\iso\Hom_{\Grph}(\vertex\times G,H)\\
	&\iso\Hom_{\Sets}(G_v,H_v)
\end{align*}
which checks out, and
\begin{align*}
(H^G)_e&\iso\Hom_{\Grph}(y(e),H^G)\\
	&\iso\Hom_{\Grph}(\vertex\edge\vertex,H^G)\\
	&\iso\Hom_{\Grph}((\vertex\edge\vertex)\times G,H)
\end{align*}
with
\[(H^G)_s\iso\Hom_{\Grph}(y(s)\times 1_G,H)\]
and
\[(H^G)_t\iso\Hom_{\Grph}(y(t)\times 1_G,H)\]
This also checks out, since graph homomorphisms from the graph of ``edges of~\(G\)'' to~\(H\) correspond to edge mappings \(\theta:\varphi\to\psi\) satisfying~(1), where \(\varphi\)~is the induced mapping of ``vertices as possible source vertices'' and \(\psi\)~is the induced mapping of ``vertices as possible target vertices''.
\end{rmk}

\begin{exer}[9]
Let \(\C\)~be a cartesian closed category and \(A,B\in\C\). Then there is a bijective correspondence between arrows \(A\to B\) and arrows \(1\to B^A\).
\end{exer}
\begin{proof}
This follows from
\[\Hom_{\C}(A,B)\iso\Hom_{\C}(1\times A,B)\iso\Hom_{\C}(1,B^A)\]
The second isomorphism follows from the definition of the exponential. For the first isomorphism, let
\[1\lTo^{\term_{1\times A}}1\times A\rTo^p A\]
be projections, and let \(q=\pair{\term_A}{1_A}:A\to1\times A\). Then \(p\after q=1_A\), and conversely
\[q\after p=\pair{\term_A}{1_A}\after p=\pair{\term_A\after p}{p}=\pair{\term_{1\times A}}{p}=1_{1\times A}\]
so \(A\iso 1\times A\), and the functor \(\Hom_{\C}(-,B)\) preserves this isomorphism.
\end{proof}

\begin{exer}[12]
Let \(\C\)~be a cartesian closed category and \(C\in\C\). Exponentiation with base object~\(C\) gives a contravariant functor \(C^{(-)}:\Cop\to\C\).
\end{exer}
\begin{proof}
For objects \(A\in\C\), define \(C^{(-)}(A)=C^A\). For arrows \(f:A\to B\) in~\(\C\), define
\[C^{(-)}(f)=C^f=\curry{(\eval_{C^B}\after(1_{C^B}\times f))}:C^B\to C^A\]
where \(\eval_{C^B}:C^B\times B\to C\) is evaluation, so the following diagram commutes:
\begin{diagram}
C^B\times B				&\rTo^{\eval_{C^B}}		&C\\
\uTo<{1_{C^B}\times f}	&						&\uTo>{\eval_{C^A}}\\
C^B\times A				&\rTo_{C^f\times 1_A}	&C^A\times A
\end{diagram}
Then \(C^{(-)}\)~maps objects to objects and arrows to arrows and preserves domains and codomains of arrows in~\(\Cop\). Also
\[C^{1_A}=\curry{(\eval_{C^A}\after(1_{C^A}\times1_A))}=\curry{(\eval_{C^A}\after1_{C^A\times A})}=\curry{\eval_{C^A}}=1_{C^A}\]
so \(C^{(-)}\)~preserves identities. If \(f:X\to Y\) and \(g:Y\to Z\), then the following diagram commutes (the upper left and lower right inner squares are just the squares above for \(g\)~and~\(f\), respectively, and the other two inner squares are trivial):
\begin{diagram}
C^Z\times Z				&\rTo^{\eval_{C^Z}}	&C						&\rTo^{1_C}			&C\\
\uTo<{1_{C^Z}\times g}	&					&\uTo>{\eval_{C^Y}}		&					&\uTo>{1_C}\\
C^Z\times Y				&\rTo_{C^g\times1_Y}&C^Y\times Y			&\rTo_{\eval_{C^Y}}	&C\\
\uTo<{1_{C^Z}\times f}	&					&\uTo>{1_{C^Y}\times f}	&					&\uTo>{\eval_{C^X}}\\
C^Z\times X				&\rTo_{C^g\times1_X}&C^Y\times X			&\rTo_{C^f\times1_X}&C^X\times X
\end{diagram}
On the left we have
\[(1_{C^Z}\times g)\after(1_{C^Z}\times f)=1_{C^Z}\times(g\after f)\]
On the bottom we have
\[(C^f\times1_X)\after(C^g\times1_X)=(C^f\after C^g)\times1_X\]
Commutativity of the diagram therefore implies
\[\uncurry{C^{g\after f}}=\eval_{C^Z}\after(1_{C^Z}\times(g\after f))=\eval_{C^X}\after((C^f\after C^g)\times1_X)=\uncurry{C^f\after C^g}\]
It follows that \(C^{g\after f}=C^f\after C^g\) and hence \(C^{(-)}\)~preserves composites in~\(\Cop\). This completes the proof that \(C^{(-)}\)~is a contravariant functor.
\end{proof}

\begin{exer}[13]
Let \(\C\)~be a cartesian closed category with coproducts and \(A,B,C\in\C\). Then
\[(A+B)\times C\iso(A\times C)+(B\times C)\]
\end{exer}
\begin{proof}
We prove that \((A+B)\times C\)~is a coproduct of \(A\times C\)~and~\(B\times C\), from which the isomorphism follows by uniqueness of coproducts under the universal mapping property.

Observe the injections
\[A\times C\rTo^{i_1\times1_C}(A+B)\times C\lTo^{i_2\times1_C}B\times C\]
If \(f:A\times C\to Z\) and \(g:B\times C\to Z\), then \(\curry{f}:A\to Z^C\) and \(\curry{g}:B\to Z^C\), so \(\copair{\curry{f}}{\curry{g}}:A+B\to Z^C\). Define
\[p=\uncurry{\copair{\curry{f}}{\curry{g}}}:(A+B)\times C\to Z\]
Then
\begin{align*}
p\after(i_1\times1_C)&=\uncurry{\copair{\curry{f}}{\curry{g}}}\after(i_1\times1_C)\\
	&=\eval\after(\copair{\curry{f}}{\curry{g}}\times1_C)\after(i_1\times1_C)\\
	&=\eval\after((\copair{\curry{f}}{\curry{g}}\after i_1)\times1_C)\\
	&=\eval\after(\curry{f}\times1_C)\\
	&=f
\end{align*}
Similarly \(p\after(i_2\times1_C)=g\). Moreover, if \(q:(A+B)\times C\to Z\) is arbitrary, then \(\curry{q}:A+B\to Z^C\), so
\begin{align*}
\curry{q}&=\copair{\curry{q}\after i_1}{\curry{q}\after i_2}\\
	&=\copair{\curry{(q\after(i_1\times1_C))}}{\curry{(q\after(i_2\times1_C))}}
\end{align*}
because
\[\eval\after((\curry{q}\after i_k)\times1_C)=\eval\after(\curry{q}\times1_C)\after(i_k\times1_C)=q\after(i_k\times1_C)\]
It follows that
\[q=\uncurry{\copair{\curry{(q\after(i_1\times1_C))}}{\curry{(q\after(i_2\times1_C))}}}\]
from which it is immediate that \(p\)~is unique in satisfying the equations above. Therefore \((A+B)\times C\)~is indeed a coproduct as desired. 
\end{proof}
\begin{rmk}
In~\(\Sets\), this exercise (circuitously) justifies the familiar distributive law \((a+b)c=ac+bc\) for \(a,b,c\in\N\).
\end{rmk}

\begin{exer}[15]
Let \(\2=\{\,\false\le\true\,\}\) be the initial Boolean algebra.
\begin{enumerate}[itemsep=0pt]
\item[(a)] For any poset~\(I\), the exponential poset~\(\2^I\) is a Heyting algebra.
\item[(b)] For any cartesian closed poset~\(\A\), where \(\2^{\dual{\A}}\) is thought of as the poset of downward closed subsets of~\(\A\) under inclusion,\footnote{See the remark above about \(\2^{\dual{I}}\) for posets~\(I\).} the map \(y:\A\to\2^{\dual{\A}}\) defined by
\[y(a)=\down(a)=\{\,x\mid x\le a\,\}\]
is monotone, injective, and preserves cartesian closed structure.
\end{enumerate}
\end{exer}
\begin{proof}
For~(a), the limits and colimits are computed pointwise. For example if \(\varphi,\psi\in\2^I\), then
\[(\varphi\meet\psi)(x)=\varphi(x)\meet\psi(x)\]
Indeed, \(\varphi\meet\psi:I\to\2\) and if \(x\le y\) then
\[\varphi(x)\meet\psi(x)\le\varphi(x)\meet\psi(y)\le\varphi(y)\meet\psi(y)\]
so \(\varphi\meet\psi\) is monotone. If \(\lambda\in\2^I\), then \(\lambda\le\varphi\meet\psi\) if and only if \(\lambda\le\varphi\) and \(\lambda\le\psi\), so \(\varphi\meet\psi\) is the product of \(\varphi\) and~\(\psi\).

The exponential of \(\varphi\) and~\(\psi\) is defined by
\[(\varphi\ex\psi)(x)=\begin{cases}
\true&\text{if }\varphi(z)\le\psi(z)\text{ for all }z\ge x\\
\false&\text{otherwise}
\end{cases}\]
Then \((\varphi\ex\psi):I\to\2\). If \(x\le y\) and \((\varphi\ex\psi)(x)=\true\), then in particular \(\varphi(z)\le\psi(z)\) for all \(z\ge y\), so \((\varphi\ex\psi)(y)=\true\) and therefore \((\varphi\ex\psi)\)~is monotone. If \(\lambda\in\2^I\), we claim
\[\lambda\meet\varphi\le\psi\quad\text{if and only if}\quad\lambda\le(\varphi\ex\psi)\]
Indeed, for the forward direction, if \(\lambda(x)=\true\) then \(\lambda(z)=\true\) for all \(z\ge x\), so
\[\varphi(z)=\true\meet\varphi(z)=\lambda(z)\meet\varphi(z)\le\psi(z)\]
for all \(z\ge x\), so \((\varphi\ex\psi)(x)=\true\) and therefore \(\lambda\le(\varphi\ex\psi)\). For the reverse direction, if \(\lambda(x)\meet\varphi(x)=\true\) then \(\lambda(x)=\true\) and \(\varphi(x)=\true\), so \((\varphi\ex\psi)(x)=\true\) and in particular we must have \(\psi(x)=\true\) and therefore \(\lambda\meet\varphi\le\psi\).

For~(b), \(a\le b\) if and only if \(\down(a)\subseteq\down(b)\), so it is immediate that \(y\)~is monotone and injective. Moreover \(\down(1)=\A\) and
\[\down(a\meet b)=\down(a)\sect\down(b)\]
so \(y\)~preserves all finite products. Note the exponential of \(S\) and~\(T\) in~\(\2^{\dual{\A}}\) is
\[T^S=\{\,x\mid\down(x)\sect S\subseteq T\,\}\]
so
\[\down(a\ex b)=\down(b)^{\down(a)}\]
which means \(y\)~preserves exponentials.
\end{proof}
\begin{rmk}
For a poset~\(I\), the Yoneda embedding \(y:I\to\Sets^{\dual{I}}\) is given by\footnote{See Chapter~8.}
\[y(a)(x)=\Hom_I(x,a)=\begin{cases}
\{x\le a\}&\text{if }x\le a\\
\emptyset&\text{otherwise}
\end{cases}\]
But we might as well take \(\{x\le a\}=\true\) and \(\emptyset=\false\), yielding \(y:I\to\2^{\dual{I}}\) above.
\end{rmk}

\newpage
\section*{Chapter~7}
\begin{rmk}
A natural transformation \(\theta:F\to G\) between two functors \(F:\C\to\D\) and \(G:\C\to\D\) looks like this:
\begin{center}
\begin{tikzcd}[sep=huge] % not doing tab alignment on this one
A \ar[r, "f"] \ar[rd, "g\after f"' name=gf] & B \ar[d, "g" name=g] & & \\
 & C & & \\
 & & GA \ar[r, "Gf" name=Gf] \ar[rd, "G(g\after f)"'] & GB \ar[d, "Gg"] \\
 & & & GC \\
FA \ar[r, "Ff" name=Ff] \ar[rd, "F(g\after f)"'] \ar[rruu, dashed, bend left, "\theta_A"] & FB \ar[d, "Fg"] \ar[rruu, dashed, bend left, end anchor=south west, crossing over, "\theta_B"] & & \\
 & FC \ar[rruu, dashed, bend left, start anchor=north east, "\theta_C"] & &
 \ar[from=gf, to=Ff, Rightarrow, shorten <=2em, shorten >=5em, bend right=20, "F"{', inner sep=1.25em, yshift=3em}]
 \ar[from=g, to=Gf, Rightarrow, shorten=3em, bend left=10, "G" inner sep=0.75em]
\end{tikzcd}
\end{center}
\end{rmk}

\begin{rmk}
For functors
\begin{diagram}
\B&\rTo^R&\C&\pile{\rTo^F\\\rTo_G}&\D&\rTo^S&\E
\end{diagram}
if \(\varphi:F\to G\) is a natural transformation, then \(S\varphi_R:SFR\to SGR\) is a natural transformation. In other words, \emph{composing natural transformations with functors produces natural transformations}.
\end{rmk}
\begin{proof}
The transformation \(\psi=S\varphi_R:SFR\to SGR\) is defined by
\[\psi_B=S(\varphi_{RB}):SFRB\to SGRB\]
If \(f:B\to B'\in\B\), then applying~\(S\) to the commutative diagram
\begin{diagram}
FRB			&\rTo^{\varphi_{RB}}	&GRB\\
\dTo<{FRf}	&						&\dTo>{GRf}\\
FRB'		&\rTo_{\varphi_{RB'}}	&GRB'
\end{diagram}
yields the commutative diagram
\begin{diagram}
SFRB		&\rTo^{\psi_B}		&SGRB\\
\dTo<{SFRf}	&					&\dTo>{SGRf}\\
SFRB'		&\rTo_{\psi_{B'}}	&SGRB'
\end{diagram}
so \(\psi\)~is a natural transformation.
\end{proof}

\begin{rmk}
If \(F_1\iso G_1\) and \(F_2\iso G_2\), then \(F_1F_2\iso G_1G_2\). In other words, \emph{composites of isomorphic functors are isomorphic}.
\end{rmk}
\begin{proof}
By the previous remark and Lemma~7.11.
\end{proof}

\begin{rmk}
The previous remark is useful in establishing natural isomorphisms. For example, in a locally small category with products, it follows from
\[A\times(B\times C)\iso(A\times B)\times C\]
being natural in \(A,B,C\) that
\[\Hom(A\times(B\times C),X)\iso\Hom((A\times B)\times C,X)\]
is also natural in \(A,B,C\).
\end{rmk}

\begin{rmk}
Many universal properties can be characterized in terms of natural isomorphisms between representable functors. For example, in a locally small category, an object~\(P\) is a product of objects \(A\) and~\(B\) if and only if there is a natural isomorphism
\[\Hom(-,P)\iso\Hom(-,A)\times\Hom(-,B)\]
Such characterizations are useful when applying the Yoneda principle.\footnote{See Chapter~8.}
\end{rmk}

\begin{rmk}
The functor \((-)^*:\Vectop\to\Vect\) is self-adjoint.\footnote{See Chapter~9.} More precisely, for the functors
\begin{diagram}
\Vect&\pile{\rTo^{\dual{{(-)^*}}}\\\lTo_{(-)^*}}&\Vectop
\end{diagram}
there is an adjunction
\[\dual{{(-)^*}}\adj(-)^*\]
\end{rmk}
\begin{proof}
Let \((-)^{**}=(-)^*\after\dual{{(-)^*}}\). For a vector space~\(V\), the linear transformation \(\eta_V:V\to V^{**}\) given by \(x\mapsto\ev_x\), where \(\ev_x\)~is ``evaluation at~\(x\)'', is the component at~\(V\) of a natural transformation \(\eta:1_{\Vect}\to(-)^{**}\).\footnote{See Example~7.12.} For a vector space~\(W\) and linear transformation \(f:V\to W^*\), if there is a linear transformation \(g:W\to V^*\) making the diagram
\begin{diagram}[nohug]
V^{**}			&\rTo^{g^*}	&W^*\\
\uTo<{\eta_V}	&\ruTo>f	&\\
V				&			&
\end{diagram}
commute, then for any \(x\in V\) and \(w\in W\),
\begin{align*}
f(x)(w)&=(g^*\after\eta_V)(x)(w)\\
	&=g^*(\ev_x)(w)\\
	&=(\ev_x\after g)(w)\\
	&=g(w)(x)
\end{align*}
It is easy to verify that the definition
\[g(w)(x)=f(x)(w)\]
makes \(g:W\to V^*\) a linear transformation, so \(\eta\)~is the unit of the indicated adjunction (and essentially the counit, since the adjunction is self-dual).
\end{proof}
\begin{rmk}
This proof can be shortened using the natural isomorphisms
\[L(V,W^*)\iso(V\tprod W)^*\iso(W\tprod V)^*\iso L(W,V^*)\]
In the finite-dimensional case, this result shows that the natural isomorphism \(V\iso V^{**}\) arises directly from the dual operation itself.
\end{rmk}

\begin{rmk}
In the finite-dimensional case, how do we actually know that there is no natural way to choose an isomorphism \(V\iso V^*\)? What would it even mean for there to be a natural way? Arguably, for such an isomorphism to be natural it should at least respect change of basis in~\(V\).

Let \(\V\)~be the subcategory of~\(\Vect\) consisting of the finite-dimensional spaces (over some fixed field of characteristic zero) and the automorphisms of these spaces. Let \(\inv{(-)}:\Vop\to\V\) denote the inversion functor and \((-)^*:\Vop\to\V\) the dual functor. An isomorphism \(V\iso V^*\) respecting change of basis would be a natural isomorphism \(\zeta:\inv{(-)}\iso(-)^*\)---for any automorphism \(f:V\to V\), the following diagram would commute:
\begin{diagram}
V				&\rTo^{\zeta_V}_{\iso}	&V^*\\
\dTo<{\inv{f}}	&						&\dTo>{f^*}\\
V				&\rTo_{\zeta_V}^{\iso}	&V^*
\end{diagram}
In bracket notation, this is equivalent to
\[\sprod{x}{\zeta_V(y)}=\sprod{f(x)}{\zeta_V(f(y))}\tag{1}\]
for all \(x,y\in V\). However, it can be proved that there is no such~\(\zeta\) satisfying~(1) for all~\(V\) in~\(\V\).\footnote{See for example Exercise~9.8 in~\cite{blyth}.} Therefore there is no natural isomorphism \(V\iso V^*\).
\end{rmk}

\begin{rmk}
The bifunctor lemma (Lemma~7.14) just says that a map \(F:\A\times\B\to\C\) is a functor if and only if it is functorial in each argument and the functors in each argument induce natural transformations between the functors in the other argument (this is the ``interchange law'').

More specifically, \(F\)~is a functor if and only if for each fixed \(A\in\A\) and \(B\in\B\), \(F(A,-)\) and~\(F(-,B)\) are functors and for any \(\alpha:A\to A'\) and \(\beta:B\to B'\), \(F(-,\beta)\)~is a natural transformation from~\(F(-,B)\) to~\(F(-,B')\) and \(F(\alpha,-)\)~is a natural transformation from~\(F(A,-)\) to~\(F(A',-)\):
\begin{diagram}
F(A,B)				&\rTo^{F(A,\beta)}	&F(A,B')\\
\dTo<{F(\alpha,B)}	&					&\dTo>{F(\alpha,B')}\\
F(A',B)				&\rTo_{F(A',\beta)}	&F(A',B')
\end{diagram}
This just means that the two paths these functors induce between the objects \(F(A,B)\) and~\(F(A',B')\) agree.
\end{rmk}

\begin{rmk}
In Example~7.18, we see that for a functor \(F:\D\to\C\), \(\Cone(F)\) is just the subcategory of \(\C^{\D}/F\) consisting of constant-valued functors and constant natural transformations between them over~\(F\).
\end{rmk}

\begin{rmk}
In the monoidal category \(\C^{\C}\) under composition, the product of two natural transformations \(\alpha:G\to G'\) and \(\beta:F\to F'\) is given by
\[\alpha\mprod\beta=\alpha_{F'}\after G\beta=G'\beta\after\alpha_F:GF\to G'F'\]
In particular, \(1_G\mprod\beta=G\beta\) and \(\alpha\mprod 1_F=\alpha_F\).

A monoid in this category is (by definition) a triple \((T,\mu,\eta)\) where \(T:\C\to\C\) is an endofunctor and \(\mu:T^2\to T\) and \(\eta:1\to T\) are natural transformations making these ``associativity'' and ``unit'' diagrams commute:
\begin{diagram}[nohug]
T^3					&\rTo^{1_T\mprod\mu}&T^2		&&T	&\rTo^{\eta\mprod1_T}	&T^2		&\lTo^{1_T\mprod\eta}	&T\\
\dTo<{\mu\mprod1_T}	&					&\dTo>{\mu}	&&	&\rdTo<{1_T}			&\dTo>{\mu}	&\ldTo>{1_T}			&\\
T^2					&\rTo_{\mu}			&T			&&	&						&T			&						&
\end{diagram}
This is precisely a monad on~\(\C\).\footnote{See Chapter~10.}

A monoid homomorphism \(h:(S,\mu^S,\eta^S)\to(T,\mu^T,\eta^T)\) in this category is a natural transformation \(h:S\to T\) which respects multiplication and units by making these diagrams commute:
\begin{diagram}[nohug]
S^2			&\rTo^{h\mprod h}	&T^2			&&S				&\rTo^h			&T\\
\dTo<{\mu^S}&					&\dTo>{\mu^T}	&&\uTo<{\eta^S}	&\ruTo>{\eta^T}	&\\
S			&\rTo_h				&T				&&1				&				&
\end{diagram}
This is a monad homomorphism on~\(\C\).
\end{rmk}

\begin{rmk}
The fact that \(\Par\eqv\Setsp\) can be used to explain the use of sentinel values in computer programming. The points introduced by the equivalence functor \(F:\Par\to\Setsp\) are just sentinel values used to signal where partial functions are undefined.
\end{rmk}

\begin{rmk}
For the pseudo-inverse functors
\begin{diagram}
\Par&\pile{\rTo^F\\\lTo_G}&\Setsp
\end{diagram}
there is an ``ambidextrous'' adjunction\footnote{See Chapter~9.}
\[\cdots\adj F\adj G\adj F\adj\cdots\]
making the equivalence \(\Par\eqv\Setsp\) an adjoint equivalence.\footnote{This phenomenon actually occurs for \emph{any} adjoint equivalence.}
\end{rmk}
\begin{proof}
For a set~\(A\), pointed set~\((B,b)\), and partial function \(f:A\parto B-\{b\}\), there is a pointed function \(g:A_*\to(B,b)\) unique with \(Gg=f\) given by
\[g(x)=\begin{cases}
f(x)&\text{if }x\in U_f\\
b&\text{otherwise}
\end{cases}\]
This means that the identity natural isomorphism \(1_{1_{\Par}}:1_{\Par}\to 1_{\Par}=GF\) is the unit of the adjunction \(F\adj G\). The other isomorphism yields the counit.

A similar argument shows that \(G\adj F\) with the unit and counit swapped and inverted.
\end{proof}

\begin{rmk}
For the functors
\begin{diagram}
\Sets&\pile{\rTo^{\powBAop}\\\lTo_{\ult}}&\BAop
\end{diagram}
there is an adjunction\footnote{See Chapter~9.}
\[\powBAop\adj\ult\]
In particular, the induced equivalence \(\BAf\eqv\Setsfop\) is an adjoint equivalence.
\end{rmk}
\begin{proof}
Let \(\mathcal{U}=\ult\after\powBAop\). For a set~\(X\), the function \(\eta_X:X\to\mathcal{U}(X)\) sending an element \(x\in X\) to the principal ultrafilter
\[\eta_X(x)=\{\,S\subseteq X\mid x\in S\,\}\]
is the component at~\(X\) of a natural transformation \(\eta:1_{\Sets}\to\mathcal{U}\).\footnote{See Section~7.3.} For a Boolean algebra~\(B\) and function \(f:X\to\ult(B)\), if there is a Boolean homomorphism \(h:B\to\powBA(X)\) making the diagram
\begin{diagram}[nohug]
\mathcal{U}(X)	&\rTo^{\ult(h)}	&\ult(B)\\
\uTo<{\eta_X}	&\ruTo>f		&\\
X				&				&
\end{diagram}
commute, then for any \(x\in X\),
\[\inv{h}(\eta_X(x))=f(x)\]
which means for any \(b\in B\),
\[h(b)=\{\,x\in X\mid b\in f(x)\,\}=\inv{f}(\{\,V\in\ult(B)\mid b\in V\,\})\]
It is easy to verify that this definition makes~\(h\) a Boolean homomorphism, so \(\eta\)~is the unit of the indicated adjunction.
\end{proof}
\begin{rmk}
Dually, there is an adjunction
\[\dual{\ult}\adj\powBA\]
whose unit is the Stone representation
\[\phi_B(b)=\{\,V\in\ult(B)\mid b\in V\,\}\]
\end{rmk}

\begin{rmk}
If \(B\)~is a finite Boolean algebra and \(b\in B\) with \(b\ne 0\), then there is an atom \(a\in A(B)\) with \(a\le b\).
\end{rmk}
\begin{proof}
By induction on the number of elements less than~\(b\).
\end{proof}

\begin{rmk}[Lemma~7.33]
If \(B\)~is a finite Boolean algebra, then
\begin{enumerate}[itemsep=0pt]
\item[(i)] \(b=\bigjoin\{\,a\in A(B)\mid a\le b\,\}\)
\item[(ii)] If \(a\in A(B)\) and \(a\le b\join b'\), then \(a\le b\) or \(a\le b'\).
\end{enumerate}
\end{rmk}
\begin{proof}
For~(i), let \(c=\bigjoin\{\,a\in A(B)\mid a\le b\,\}\). Clearly \(c\le b\). If \(b\not\le c\), then \(b\meet\compl c\ne 0\), so by the previous remark there is \(a\in A(B)\) with \(a\le b\meet\compl c\). Now \(a\le b\) so \(a\le c\), and also \(a\le\compl c\), so \(a\le c\meet\compl c=0\), contradicting that \(a\ne 0\).

For~(ii), if \(a\not\le b\) and \(a\not\le b'\), then \(a\le\compl b\) and \(a\le\compl b'\) (Lemma~7.32), so
\[a\le\compl b\meet\compl b'=\compl(b\join b')\]
and hence \(a\not\le b\join b'\).
\end{proof}

\begin{exer}[1]
Let \(\mathcal{F}=\powBA\after\dual{\ult}:\BA\to\Setsop\to\BA\). For a Boolean algebra~\(B\), define \(\phi_B:B\to\mathcal{F}(B)\) by
\[\phi_B(b)=\{\,V\in\ult(B)\mid b\in V\,\}\]
Then \(\phi_B\)~is a Boolean homomorphism, and for any Boolean homomorphism \(h:A\to B\), the following diagram commutes:
\begin{diagram}
A		&\rTo^{\phi_A}	&\mathcal{F}(A)\\
\dTo<h	&				&\dTo>{\mathcal{F}(h)}\\
B		&\rTo_{\phi_B	}&\mathcal{F}(B)
\end{diagram}
\end{exer}
\begin{proof}
It is immediate from ultrafilter properties that \(\phi_B\)~is a homomorphism. For \(a\in A\), we have
\begin{align*}
(\phi_B\after h)(a)&=\phi_B(h(a))\\
	&=\{\,V\in\ult(B)\mid h(a)\in V\,\}\\
	&=\{\,V\in\ult(B)\mid a\in\inv{h}(V)\in\ult(A)\,\}\\
	&=\inv{\dual{\ult}(h)}\{\,U\in\ult(A)\mid a\in U\,\}\\
	&=(\powBA(\dual{\ult}(h)))(\phi_A(a))\\
	&=\mathcal{F}(h)(\phi_A(a))\\
	&=(\mathcal{F}(h)\after\phi_A)(a)\qedhere
\end{align*}
\end{proof}

\begin{exer}[2]
The homomorphism~\(\phi_B\) from the previous exercise is injective.
\end{exer}
\begin{proof}
If \(a,b\in B\) and \(a\ne b\), then we may assume \(a\not\le b\), so \(a\meet\compl b\ne 0\). Now \(\up(a\meet\compl b)\)~is a proper filter, which is contained in an ultrafilter~\(V\) by the ultrafilter theorem. It follows that \(a\in V\) but \(b\not\in V\), so \(\phi_B(a)\ne\phi_B(b)\).
\end{proof}

\begin{exer}[3]
The homomorphism~\(\phi_B\) from the previous exercise is bijective if \(B\)~is finite.
\end{exer}
\begin{proof}
By Lemmas 7.32 and~7.33, the mapping \(\psi_B:\mathcal{F}(B)\to B\) defined by
\[\psi_B(S)=\bigjoin\{\,\bigmeet_{b\in V}b\mid V\in S\,\}\]
is left inverse to~\(\phi_B\).
\end{proof}

\begin{exer}[4]
The forgetful functors
\[\Grp\rTo^{U}\Mon\rTo^{V}\Sets\]
have the following properties:
\begin{center}
\begin{tabular}{|r|c|c|}
\hline
						&\(U\)	&\(V\)\\
\hline
Injective on objects	&Yes	&No\\
Injective on arrows		&Yes	&Yes\\
Surjective on objects	&No		&No\\
Surjective on arrows	&No		&No\\
Faithful				&Yes	&Yes\\
Full					&Yes	&No\\
\hline
\end{tabular}
\end{center}
\end{exer}

\begin{exer}[7]
A natural transformation is an isomorphism if and only if each of its components is an isomorphism.
\end{exer}
\begin{proof}
Let \(F,G:\C\to\D\) be functors and \(\vartheta:F\to G\) a natural transformation with components \(\vartheta_C:FC\to GC\) for all \(C\in\C\). We claim \(\vartheta\)~is an iso in~\(\D^{\C}\) if and only if \(\vartheta_C\)~is an iso in~\(\D\) for all \(C\in\C\).

Suppose \(\vartheta\)~is an iso with inverse \(\psi:G\to F\), so \(\psi\after\vartheta=1_F\) and \(\vartheta\after\psi=1_G\). Since composites and identities in~\(\D^{\C}\) are defined componentwise, it is immediate that \(\psi_C\)~is an inverse of~\(\vartheta_C\), so \(\vartheta_C\)~is an iso, for all \(C\in\C\).

Suppose conversely that for all \(C\in\C\), \(\vartheta_C:FC\to GC\)~is an iso, so there is an inverse \(\psi_C:GC\to FC\) with \(\psi_C\after\vartheta_C=1_{FC}\) and \(\vartheta_C\after\psi_C=1_{GC}\). We claim the family~\(\psi\) is a natural transformation from~\(G\) to~\(F\). Indeed, for \(\alpha:B\to C\) in~\(\C\), we know \(\vartheta_C\after F\alpha=G\alpha\after\vartheta_B\):
\begin{diagram}
FB				&\rTo^{\vartheta_B}		&GB\\
\dTo<{F\alpha}	&						&\dTo>{G\alpha}\\
FC				&\rTo_{\vartheta_C}		&GC
\end{diagram}
Applying \(\psi_C\)~on the left and \(\psi_B\)~on the right, we obtain \(\psi_C\after G\alpha=F\alpha\after\psi_B\):
\begin{diagram}
GB				&\rTo^{\psi_B}		&FB\\
\dTo<{G\alpha}	&					&\dTo>{F\alpha}\\
GC				&\rTo_{\psi_C}		&FC
\end{diagram}
So \(\psi\in\D^{\C}\). It is immediate that \(\psi\after\vartheta=1_F\) and \(\vartheta\after\psi=1_G\), so \(\vartheta\)~is an iso.
\end{proof}
\begin{rmk}
If a natural transformation consists of monos, it is a mono, but the converse is not true.
\end{rmk}

\begin{exer}[9]
The function
\begin{align*}
\eta_A:A&\to\pow\pow(A)\\
a&\mapsto\{\,X\subseteq A\mid a\in X\,\}
\end{align*}
is a natural transformation from~\(1_{\Sets}\) to~\(\pow\pow\), where \(\pow\)~is the contravariant powerset functor.
\end{exer}
\begin{proof}
If \(f:A\to B\) is a function, we claim the following diagram commutes:
\begin{diagram}
A		&\rTo^{\eta_A}	&\pow\pow(A)\\
\dTo<f	&				&\dTo>{\pow\pow(f)}\\
B		&\rTo_{\eta_B}	&\pow\pow(B)
\end{diagram}
By definition,
\begin{align*}
\pow(f):\pow(B)&\to\pow(A)\\
Y&\mapsto\inv{f}(Y)=\{\,x\in A\mid f(x)\in Y\,\}
\end{align*}
so
\begin{align*}
\pow\pow(f):\pow\pow(A)&\to\pow\pow(B)\\
\mathcal{C}&\mapsto\inv{(\inv{f})}(\mathcal{C})=\{\,Y\subseteq B\mid\inv{f}(Y)\in\mathcal{C}\,\}
\end{align*}
Therefore for \(x\in A\),
\begin{align*}
(\eta_B\after f)(x)&=\eta_B(f(x))\\
	&=\{\,Y\subseteq B\mid f(x)\in Y\,\}\\
	&=\{\,Y\subseteq B\mid x\in\inv{f}(Y)\,\}\\
	&=\{\,Y\subseteq B\mid \inv{f}(Y)\in\eta_A(x)\,\}\\
	&=\pow\pow(f)(\eta_A(x))\\
	&=(\pow\pow(f)\after\eta_A)(x)\qedhere
\end{align*}
\end{proof}
\begin{rmk}
The function~\(\eta_A\) is actually a natural embedding since if \(x\ne y\), then \(\{x\}\in\eta_A(x)-\eta_A(y)\), so \(\eta_A(x)\ne\eta_A(y)\).
\end{rmk}

\begin{exer}[10]
Let \(\C\)~be a locally small category. There exists a functor
\[\Hom:\Cop\times\C\to\Sets\]
inducing the familiar representable functors
\[\Hom(C,-):\C\to\Sets\qquad\Hom(-,C):\Cop\to\Sets\]
\end{exer}
\begin{proof}
By the bifunctor lemma (Lemma~7.14), it is sufficient to prove that the representable functors satisfy the ``interchange law'', that is, for all \(\alpha:A'\to A\) and \(\beta:B\to B'\), the following diagram commutes:
\begin{diagram}
\Hom(A,B)				&\rTo^{\Hom(\alpha,B)}	&\Hom(A',B)\\
\dTo<{\Hom(A,\beta)}	&						&\dTo>{\Hom(A',\beta)}\\
\Hom(A,B')				&\rTo_{\Hom(\alpha,B')}	&\Hom(A',B')
\end{diagram}
Indeed, for \(f:A\to B\),
\begin{align*}
(\,\Hom(\alpha,B')\after\Hom(A,\beta)\,)(f)&=\Hom(\alpha,B')(\,\Hom(A,\beta)(f)\,)\\
	&=\Hom(\alpha,B')(\beta\after f)\\
	&=\beta\after f\after\alpha\\
	&=\Hom(A',\beta)(f\after\alpha)\\
	&=\Hom(A',\beta)(\,\Hom(\alpha,B)(f)\,)\\
	&=(\,\Hom(A',\beta)\after\Hom(\alpha,B)\,)(f)\qedhere
\end{align*}
\end{proof}

\begin{exer}[12]
If \(\C\eqv\D\) and \(\C\)~has binary products, so does~\(\D\).
\end{exer}
\begin{proof}
By the characterization of equivalence (Proposition~7.26), there exists a functor \(F:\C\to\D\) which is fully faithful and essentially surjective on objects.

If \(X,Y\in\D\), fix \(A,B\in\C\) with \(\vartheta_X:F(A)\iso X\) and \(\vartheta_Y:F(B)\iso Y\). In~\(\C\), there is a product diagram
\[A\lTo^{p_1}A\times B\rTo^{p_2}B\]
Applying~\(F\) to this diagram, we obtain
\[X\lTo^{\vartheta_X}F(A)\lTo^{F(p_1)}F(A\times B)\rTo^{F(p_2)}F(B)\rTo^{\vartheta_Y}Y\]
We claim this is a product diagram of \(X\)~and~\(Y\) in~\(\D\).

Indeed, for \(Z\in\D\) with \(x:Z\to X\) and \(y:Z\to Y\), fix \(C\in\C\) with \(\vartheta_Z:F(C)\iso Z\). Also fix \(a:C\to A\) and \(b:C\to B\) with \(F(a)=\inv{\vartheta_X}\after x\after\vartheta_Z\) and \(F(b)=\inv{\vartheta_Y}\after y\after\vartheta_Z\). In~\(\C\), there is a unique pair \(p=\pair{a}{b}:C\to A\times B\) with \(p_1\after p=a\) and \(p_2\after p=b\):
\begin{diagram}[nohug]
	&			&C			&			&\\
	&\ldTo<a	&\dTo<p		&\rdTo>b	&\\
A	&\lTo_{p_1}	&A\times B	&\rTo_{p_2}	&B
\end{diagram}
Applying \(F\)~to this diagram, we obtain
\begin{diagram}[nohug,size=3.5em,tight]
	&					&Z		&					&				&					&Z		&					&\\
	&\ldTo<x			&		&\luTo>{\vartheta_Z}&				&\ruTo^{\vartheta_Z}&		&\rdTo>y			&\\
X	&					&		&					&F(C)			&					&		&					&Y\\
	&\luTo<{\vartheta_X}&		&\ldTo<{F(a)}		&\dTo<{F(p)}	&\rdTo>{F(b)}		&		&\ruTo>{\vartheta_Y}&\\
	&					&F(A)	&\lTo_{F(p_1)}		&F(A\times B)	&\rTo_{F(p_2)}		&F(B)	&					&
\end{diagram}
It is immediate from this diagram that \(\pair{x}{y}=F(p)\after\inv{\vartheta_Z}\), which is unique since \(p\)~is unique and \(F\)~is fully faithful.
\end{proof}

\begin{exer}[13]
The ``size'' of a category is respected by isomorphism but not by equivalence. For example, we know \(\Ordf\eqv\Setsf\), but \(\Ordf\)~is countably infinite while \(\Setsf\)~is not even small.\footnote{Here \(\Setsf\)~is understood as the category of \emph{all} finite sets and functions between them.}
\end{exer}

\begin{exer}[17]
Let \(I\)~be a set. Then
\[\Sets^I\eqv\Sets/I\]
and this equivalence is ``natural'' in the sense that for any function \(f:J\to I\), the following diagram commutes up to natural isomorphism, where \(\Sets^f\) is the reindexing functor, and \(\pull{f}\)~is the pullback functor:
\begin{diagram}
\Sets^I			&\rTo	&\Sets/I\\
\dTo<{\Sets^f}	&		&\dTo>{\pull{f}}\\
\Sets^J			&\rTo	&\Sets/J
\end{diagram}
\end{exer}
\begin{proof}
Define \(\Phi_I:\Sets^I\to\Sets/I\) as follows:
\begin{itemize}
\item Objects: for an indexed family of sets \((A_i)_{i\in I}\), let \(p_i:A_i\to I\) be constant with \(p_i(x)=i\) for all \(x\in A_i\), and define the ``indexing projection''
\[\Phi_I((A_i)_{i\in I})=\pi_I=[p_i]:\coprod_{i\in I}A_i\to I\]
where we take \(\coprod_{i\in I}A_i=\bigunion_{i\in I}(A_i\times\{i\})\).
\item Arrows: for an indexed family of functions \((f_i:A_i\to B_i)_{i\in I}\), define
\[\Phi_I((f_i:A_i\to B_i)_{i\in I})=\coprod_{i\in I}f_i:\coprod_{i\in I}A_i\to\coprod_{i\in I}B_i\]
\end{itemize}
It is immediate that \(\Phi_I\)~is a functor. Define \(\Psi_I:\Sets/I\to\Sets^I\) as follows:
\begin{itemize}
\item Objects: for a function \(\alpha:X\to I\), define
\[\Psi_I(\alpha)=(\inv{\alpha}(i))_{i\in I}\]
\item Arrows: for functions \(\alpha:X\to I\), \(\beta:Y\to I\), and \(\gamma:X\to Y\) with \(\alpha=\beta\after\gamma\), define
\[\Psi_I(\gamma)=\bigl(\,\gamma|_{\inv{\alpha}(i)}:\inv{\alpha}(i)\to\inv{\beta}(i)\,\bigr)_{i\in I}\]
\end{itemize}
It is also immediate that \(\Psi_I\)~is a functor, \(\Psi_I\after\Phi_I\iso1_{\Sets^I}\), and \(\Phi_I\after\Psi_I\iso 1_{\Sets/I}\). Therefore \(\Sets^I\eqv\Sets/I\).

Now suppose \(f:J\to I\) is a function. Define
\begin{align*}
\Sets^f:\Sets^I&\to\Sets^J\\
(A_i)_{i\in I}&\mapsto(A_{f(j)})_{j\in J}\\
(f_i:A_i\to B_i)_{i\in I}&\mapsto(f_{f(j)}:A_{f(j)}\to B_{f(j)})_{j\in J}
\end{align*}
It is immediate that \(\Sets^f\)~is a functor (the ``reindexing functor''). We already know that pullback \(\pull{f}:\Sets/I\to\Sets/J\) is a functor (Proposition~5.10). We claim that \(\Phi_J\after\Sets^f\iso\pull{f}\after\Phi_I\), which is equivalent to \(\Sets^f\iso\Psi_J\after\pull{f}\after\Phi_I\). The latter follows from the pullback diagram
\begin{diagram}
\coprod_{j\in J}A_{f(j)}	&\rTo	&\coprod_{i\in I}A_i\\
\dTo<{\pi_J}				&		&\dTo>{\pi_I}\\
J							&\rTo_f	&I
\end{diagram}
where the upper arrow is the reindexing function \((x,j)\mapsto(x,f(j))\).
\end{proof}
\begin{rmk}
We already know that \(\Sets^I\iso\prod_{i\in I}\Sets\) (Example~7.15), so this result shows that \(\Sets/I\eqv\prod_{i\in I}\Sets\). In particular, \(\Sets/2\eqv\Sets\times\Sets\). Since \(\Sets\times\Sets\)~is cartesian closed (by the remark in Chapter~6 above), this implies \(\Sets/2\)~is cartesian closed (by Exercise~12, and similar arguments).
\end{rmk}

\begin{rmk}
We have a functor \(\Sets^{(-)}:\Setsop\to\Cat\),\footnote{Here we ignore size issues.} which maps a set~\(I\) to the category~\(\Sets^I\) and maps a function \(f:J\to I\) to the functor \(\Sets^f:\Sets^I\to\Sets^J\). Indeed, note for \(g:K\to J\) that
\[\Sets^{fg}=\Sets^g\after\Sets^f\]
since
\begin{align*}
\Sets^{fg}((A_i)_{i\in I})&=(A_{(fg)(k)})_{k\in K}\\
	&=(A_{f(gk)})_{k\in K}\\
	&=\Sets^g((A_{f(j)})_{j\in J})\\
	&=\Sets^g(\Sets^f((A_i)_{i\in I}))\\
	&=(\Sets^g\after\Sets^f)((A_i)_{i\in I})
\end{align*}
\end{rmk}

\begin{rmk}
For a category~\(\C\) and functors \(F,G:\C\to\Cat\), say that \(\Phi:F\to G\) is a \emph{natural equivalence of categories}\footnote{A better concept for describing this phenomenon is that of \emph{pseudonatural equivalence} in 2-categories. See \url{https://math.stackexchange.com/q/3713074}.} if it is a family of equivalences of categories
\[(\Phi_C:FC\eqv GC)_{C\in\C}\tag{1}\]
such that for all \(f:C\to C'\), there is a natural isomorphism
\[\Phi_{C'}\after Ff\iso Gf\after\Phi_C\tag{2}\]
---that is, the following diagram commutes up to natural isomorphism:
\begin{diagram}
FC			&\rTo^{\Phi_C}		&GC\\
\dTo<{Ff}	&					&\dTo>{Gf}\\
FC'			&\rTo_{\Phi_{C'}}	&GC'
\end{diagram}
Note this definition generalizes that of natural isomorphism for category-valued functors by allowing equivalence instead of isomorphism in~(1) and allowing natural isomorphism instead of equality in~(2).

The previous exercise shows that there is a natural equivalence of this sort between the reindexing functor \(\Sets^{(-)}:\Setsop\to\Cat\) and the pullback functor \((-)^*:\Setsop\to\Cat\).\footnote{See the remark at the beginning of Chapter~5 above.}
\end{rmk}

\newpage
\section*{Chapter~8}
\begin{rmk}
For a set~\(I\), the Yoneda embedding \(y:I\to\Sets^I\) is given by
\[y(i)=(\delta_{ij})_{j\in I}\]
where \(\delta_{ii}=1\) and \(\delta_{ij}=0\) for \(i\ne j\).
\end{rmk}

\begin{rmk}
In the proof of Proposition~8.7, the functors
\[\Hom(yC,F_{(-)})=\Hom(yC,-)\after F:J\to\SetsCop\to\Sets\]
and
\[F_{(-)}C=\ev_C\after F:J\to\SetsCop\to\Sets\]
are isomorphic since \(\Hom(yC,-)\iso\ev_C\) (Yoneda) and composition preserves isomorphism.\footnote{See the remark at the beginning of Chapter~7 above.} It follows that
\[\limit_{j\in J}\Hom(yC,F_j)\iso\limit_{j\in J}F_jC\]
since the limit operation is functorial.\footnote{See Exercise~9 in Chapter~5 above.}

In the rest of this remark, we use the notation \(U(-)\) to denote the arrow into a limit uniquely determined by a cone. To define the action of~\(\limit F_j\) on arrows in~\(\C\), first observe that for \(\alpha:j\to j'\) in~\(J\) and \(f:D\to C\) in~\(\C\), the following diagram commutes by definition of the limit and naturality of~\(F_{\alpha}\):
\begin{diagram}[nohug,eqno=(1)]
			&				&\limit F_jC		&					&\\
			&\ldTo<{p_{j,C}}&					&\rdTo>{p_{j',C}}	&\\
F_jC		&				&\rTo^{F_{\alpha}C}	&					&F_{j'}C\\
\dTo<{F_jf}	&				&					&					&\dTo>{F_{j'}f}\\
F_jD		&				&\rTo_{F_{\alpha}D}	&					&F_{j'}D
\end{diagram}
It follows that the functions \(F_jf\after p_{j,C}:\limit F_jC\to F_jD\) form a cone to~\(F_{(-)}D\), so the following diagram commutes:
\begin{diagram}[eqno=(2)]
\limit F_jC		&\rDashto^{U(F_jf\after p_{j,C})}	&\limit F_jD\\
\dTo<{p_{j,C}}	&									&\dTo>{p_{j,D}}\\
F_jC			&\rTo_{F_jf}						&F_jD
\end{diagram}
We therefore define
\[(\limit F_j)(f)=U(F_jf\after p_{j,C})\]
It follows that
\[(\limit F_j)(1_C)=1_{\limit F_jC}\]
and for \(g:E\to D\) in~\(\C\),
\begin{align*}
(\limit F_j)(f\after g)&=U(F_j(f\after g)\after p_{j,C})\\
	&=U(F_jg\after F_jf\after p_{j,C})\\
	&=U(F_jg\after p_{j,D})\after U(F_jf\after p_{j,C})\\
	&=(\limit F_j)(g)\after(\limit F_j)(f)
\end{align*}
so \(\limit F_j\)~is a (contravariant) functor.

To see that \(\limit F_j\)~is indeed the limit of the~\(F_j\), first observe that the functions \(p_{j,C}:\limit F_jC\to F_jC\) form natural transformations \(p_j:\limit F_j\to F_j\) by~(2), and these~\(p_j\) form a cone to~\(F\) by~(1). If \(q_j:G\to F_j\) is also a cone to~\(F\), then the following diagram commutes:
\begin{diagram}[nohug,eqno=(3)]
GC				&\rTo^{Gf}	&GD				&					&\\
\dTo<{q_{j,C}}	&			&\dTo>{q_{j,D}}	&\rdTo>{q_{j',D}}	&\\
F_jC			&\rTo_{F_jf}&F_jD			&\rTo_{F_{\alpha}D}	&F_{j'}D
\end{diagram}
In particular for each object~\(C\) the~\(q_{j,C}\) form a cone from~\(GC\) to~\(F_{(-)}C\), and for \(\theta_C=U(q_{j,C})\) the following diagram commutes:
\begin{diagram}[nohug,eqno=(4)]
GC				&\rTo^{Gf}				&GD					&				&\\
\dTo<{\theta_C}	&						&\dTo>{\theta_D}	&\rdTo>{q_{j,D}}&\\
\limit F_jC		&\rTo_{(\limit F_j)(f)}	&\limit F_jD		&\rTo_{p_{j,D}}	&F_jD
\end{diagram}
This implies \(\theta:G\to\limit F_j\) is natural and \(p_j\after\theta=q_j\), so \(\limit F_j\)~is universal.
\end{rmk}

\begin{rmk}
In the proof of Proposition~8.10, note that for an arrow \(h:C'\to C\) in~\(\C\) and a functor \(F:\Cop\to\Sets\), the diagram
\begin{diagram}[nohug,eqno=(1)]
yC'	&			&\rTo^{yh}	&			&yC\\
	&\rdTo<{x'}	&			&\ldTo>{x}	&\\
	&			&F			&			&
\end{diagram}
commutes if and only if \(F(h)(x)=x'\)---that is, if and only if \(h:(x',C')\to(x,C)\) is an arrow in~\(\int_{\C}F\)---by commutativity of
\begin{diagram}
\Hom(yC,F)			&\rTo^{\iso}&FC\\
\dTo<{\Hom(yh,F)}	&			&\dTo>{Fh}\\
\Hom(yC',F)			&\rTo_{\iso}&FC'
\end{diagram}
Taking \(F=P\) in~(1) shows that \(P\)~is a cocone.

For \(\vartheta:P\to Q\), to see that the naturality diagram
\begin{diagram}
PC			&\rTo^{\vartheta_C}		&QC\\
\dTo<{Ph}	&						&\dTo>{Qh}\\
PC'			&\rTo_{\vartheta_{C'}}	&QC'
\end{diagram}
commutes, observe that for \(x\in PC\) and \(x'=P(h)(x)\),
\[(Qh\after\vartheta_C)(x)=Q(h)(\vartheta_{(x,C)})=\vartheta_{(x',C')}=\vartheta_{C'}(x')=(\vartheta_{C'}\after Ph)(x)\]
where the second equality follows by taking \(F=Q\) in~(1).

Now for any \(\eta:P\to Q\), we have commutativity of
\begin{diagram}[eqno=(2)]
\Hom(yC,P)			&\rTo^{\iso}&PC\\
\dTo<{\Hom(yC,\eta)}&			&\dTo>{\eta_C}\\
\Hom(yC,Q)			&\rTo_{\iso}&QC
\end{diagram}
Taking \(\eta=\vartheta\) in~(2) shows that \(\vartheta\after x=\vartheta_{(x,C)}\). If \(\varphi:P\to Q\) satisfies \(\varphi\after x=\vartheta_{(x,C)}\), then taking \(\eta=\varphi\) in~(2) shows that \(\varphi=\vartheta\).
\end{rmk}

\begin{rmk}
For a set~\(I\) and an \(I\)-indexed family \(A=(A_i)_{i\in I}\) of sets,
\[\int_I A=\{\,(x,i)\mid x\in A_i\,\}=\coprod_{i\in I}A_i\]
and the canonical projection \(\pi:\int_I A\to I\) with \(\pi(x,i)=i\) is just the indexing projection of the family. By Proposition~8.10 and a prior remark above,
\[A\iso\colimit_{x\in A_i}(\delta_{ij})_{j\in I}\]
Intuitively, if you take a copy of the ``singleton family'' \((\delta_{ij})_{j\in I}\) for each \(x\in A_i\), and put all the copies together, you get a family that looks just like~\(A\).
\end{rmk}

\begin{rmk}
If \(P,Q\in\SetsCop\) and \(\vartheta:P\to Q\), then there is a functor
\[I(\vartheta):\int_{\C}P\to\int_{\C}Q\]
defined by \(I(\vartheta)(x,C)=(\vartheta_Cx,C)\). Indeed, if \(h:(x',C')\to(x,C)\) is an arrow in~\(\int_{\C}P\), then commutativity of
\begin{diagram}
PC			&\rTo^{\vartheta_C}		&QC\\
\dTo<{Ph}	&						&\dTo>{Qh}\\
PC'			&\rTo_{\vartheta_{C'}}	&QC'
\end{diagram}
implies
\[Q(h)(\vartheta_C x)=\vartheta_{C'}(P(h)(x))=\vartheta_{C'}x'\]
so \(I(\vartheta)(h)=h:(\vartheta_{C'}x',C')\to(\vartheta_C x,C)\) is an arrow in~\(\int_{\C}Q\). Clearly \(I(\vartheta)\)~preserves identities and composites, so it is a functor. Note it preserves the underlying objects and arrows in~\(\C\).

Moreover, if \(\C\)~is small then \(I:\SetsCop\to\Cat\) is a functor, where \(I(P)=\int_{\C}P\). In other words, \emph{integrating over a (small) category is functorial}.
\end{rmk}

\begin{rmk}
In the proof of Proposition~8.11, to define the action of~\(F_!\) on an arrow \(\vartheta:P\to Q\) we use the previous remark. Write \(P\iso\colimit_{j\in J}A_j\) and \(Q\iso\colimit_{k\in K}B_k\) where \(J=\int_{\C}P\) and \(K=\int_{\C}Q\) and \(A:J\to\C\) and \(B:K\to\C\) are the projections. Since \(I(\vartheta):J\to K\) preserves the underlying objects and arrows in~\(\C\), it follows that \(\colimit_{k\in K}FB_k\) is a cocone to~\(FA_{(-)}\) in~\(\Ee\), and so there is a unique arrow
\[F_!\,\vartheta:\colimit_{j\in J}FA_j\to\colimit_{k\in K}FB_k\]
induced by the universal property of~\(\colimit_{j\in J}FA_j\). Clearly \(F_!\)~preserves identities and composites, so it is a functor.
\end{rmk}

\begin{rmk}
For \(C\in\C\), the category of elements \(\int_{\C}yC\) has the terminal object \((1_C,C)\). Indeed, for any object~\((x',C')\), we have \(x':C'\to C\) and \(yC(x')(1_C)=x'\), so \(x':(x',C')\to(1_C,C)\) and \(x'\)~is the only arrow with this property.
\end{rmk}

\begin{exer}[1]
If \(F:\C\to\D\) is fully faithful, then \(C\iso C'\) iff \(FC\iso FC'\).
\end{exer}
\begin{proof}
The forward direction holds since functors preserve isos. For the reverse direction, if \(x:FC\to FC'\) and \(y:FC'\to FC\) are inverses, then since \(F\)~is full there are \(f:C\to C'\) and \(g:C'\to C\) with \(Ff=x\) and \(Fg=y\). Now
\[F(g\after f)=F(g)\after F(f)=y\after x=1_{FC}=F(1_C)\]
so \(g\after f=1_C\) since \(F\)~is faithful. Similarly \(f\after g=1_{C'}\), so \(f\) and~\(g\) are inverses.
\end{proof}

\begin{exer}[2]
The representable functors generate~\(\SetsCop\).
\end{exer}
\begin{proof}
If \(P,Q\in\SetsCop\) and \(\varphi,\psi:P\to Q\) satisfy \(\varphi\after\vartheta=\psi\after\vartheta\) for all \(\vartheta:yC\to P\), then
\[\Hom(yC,\varphi)=\Hom(yC,\psi)\]
so we have a commutative diagram by the Yoneda lemma:
\begin{diagram}
\Hom(yC,P)	&\rTo^{\iso}&PC\\
\dTo		&			&\dTo<{\varphi_C}\dTo>{\psi_C}\\
\Hom(yC,Q)	&\rTo_{\iso}&QC
\end{diagram}
It follows that \(\varphi_C=\psi_C\) for all~\(C\), so \(\varphi=\psi\).
\end{proof}

\begin{exer}[3]
If \(\C\)~is a locally small cartesian closed category, then
\[(A\times B)^C\iso A^C\times B^C\tag{1}\]
and if \(\C\)~also has binary coproducts, then
\[A^{(B+C)}\iso A^B\times A^C\tag{2}\]
\end{exer}
\begin{proof}
By the Yoneda principle. For~(1), we have
\begin{align*}
\Hom(X,(A\times B)^C)&\iso\Hom(X\times C,A\times B)\\
	&\iso\Hom(X\times C,A)\times\Hom(X\times C,B)\\
	&\iso\Hom(X,A^C)\times\Hom(X,B^C)\\
	&\iso\Hom(X,A^C\times B^C)
\end{align*}
For~(2), we have
\begin{align*}
\Hom(X,A^{(B+C)})&\iso\Hom(X\times(B+C),A)\\
	&\iso\Hom(X\times B+X\times C,A)\\
	&\iso\Hom(X\times B,A)\times\Hom(X\times C,A)\\
	&\iso\Hom(X,A^B)\times\Hom(X,A^C)\\
	&\iso\Hom(X,A^B\times A^C)
\end{align*}
All isos are natural in~\(X\).
\end{proof}

\begin{exer}[7]
The Yoneda embedding \(y:\C\to\SetsCop\) preserves binary products and exponentials.
\end{exer}
\begin{proof}
For products, we have
\begin{align*}
y(A\times B)(C)&=\Hom(C,A\times B)\\
	&\iso\Hom(C,A)\times\Hom(C,B)\\
	&=yA(C)\times yB(C)\\
	&=(yA\times yB)(C)
\end{align*}
and the iso is natural in~\(C\). For exponentials, we have
\begin{align*}
y(B^A)(C)&=\Hom(C,B^A)\\
	&\iso\Hom(C\times A,B)\\
	&=yB(C\times A)\\
	&\iso\Hom(y(C\times A),yB)\\
	&\iso\Hom(yC\times yA,yB)\\
	&=yB^{\,yA}(C)
\end{align*}
and the isos are natural in~\(C\).
\end{proof}

\begin{exer}[10]
The \(\lambda\)-calculus is complete with respect to diagram categories.
\end{exer}
\begin{proof}
Anything provable in the \(\lambda\)-calculus is true in every cartesian closed model, hence in every diagram model since they are cartesian closed. On the other hand, if something is not provable it is not true in some cartesian closed model, hence not true in some containing diagram model.
\end{proof}

\begin{exer}[11]
The slice category~\(\Sets/X\) is cartesian closed.
\end{exer}
\begin{proof}
\(\Sets/X\eqv\Sets^X\) and \(\Sets^X\) is cartesian closed.
\end{proof}

\newpage
\section*{Chapter~9}
\begin{rmk}
For functors
\begin{diagram}
\C&\pile{\rTo^F\\\lTo_U}&\D&\pile{\rTo^G\\\lTo_V}&\E
\end{diagram}
if \(F\adj U\) and \(G\adj V\), then \(GF\adj UV\). In other words, \emph{composites of adjoints are adjoints}.
\end{rmk}
\begin{proof}
For \(C\in\C\) and \(E\in\E\), we have natural isomorphisms
\[\Hom(GFC,E)\iso\Hom(FC,VE)\iso\Hom(C,UVE)\qedhere\]
\end{proof}

\begin{rmk}
For functors
\begin{diagram}
F,G:\C&\pile{\rTo\\\lTo}&\D:U
\end{diagram}
if \(G\iso F\adj U\), then \(G\adj U\). In other words, \emph{a functor isomorphic to an adjoint is an adjoint}.
\end{rmk}
\begin{proof}
For \(C\in\C\) and \(D\in\D\), we have natural isomorphisms
\[\Hom(GC,D)\iso\Hom(FC,D)\iso\Hom(C,UD)\qedhere\]
\end{proof}

\begin{rmk}
For functors
\begin{diagram}[p=0.5\PileSpacing]
\A					&\pile{\rTo^{F_1}\\\lTo_{U_1}}	&\B\\
\uTo<{U_3}\dTo>{F_3}&								&\uTo<{U_2}\dTo>{F_2}\\
\C					&\pile{\rTo{F_4}\\\lTo_{U_4}}	&\D
\end{diagram}
if \(F_i\adj U_i\) for all~\(i\), then \(F_4F_3\iso F_2F_1\) if and only if \(U_3U_4\iso U_1U_2\). In other words, \emph{a square of left adjoints commutes up to iso if and only if the corresponding square of right adjoints does so}.
\end{rmk}
\begin{proof}
For the forward direction, we have
\[U_3U_4\radj F_4F_3\iso F_2F_1\adj U_1U_2\]
so \(U_3U_4\iso U_1U_2\) by uniqueness of adjoints. The reverse direction follows by duality.
\end{proof}

\begin{rmk}
To see that a pseudo-inverse \(U:\D\eqv\C\) is an adjoint, recall that \(U\)~is fully faithful and essentially surjective on objects.\footnote{See Proposition~7.26.} For each object \(C\in\C\) we can choose an object \(FC\in\D\) and an isomorphism \(\eta_C:C\iso UFC\). For an arrow \(f:C\to C'\) in~\(\C\), let \(Ff:FC\to FC'\) be the unique arrow in~\(\D\) making this diagram commute:
\begin{diagram}
C					&\rTo^f		&C'\\
\dTo<{\eta_C}>{\iso}&			&\dTo>{\eta_{C'}}<{\iso}\\
UFC					&\rTo_{UFf}	&UFC'
\end{diagram}
Then \(F:\C\to\D\) is a functor and \(\eta:1_{\C}\iso UF\) is a natural isomorphism. For \(D\in\D\) and \(C'=UD\), \(g=\inv{U}(\inv{\eta_{C'}}\after UFf)\) is unique with \(f=Ug\after\eta_C\), so \(\eta\)~is the unit of an adjunction \(F\adj U\).
\end{rmk}

\begin{rmk}
If \(E:\C\to\D\) and \(F:\D\to\C\) exhibit an equivalence \(\C\eqv\D\), it is not true in general that the natural isomorphisms \(1_{\C}\iso FE\) and \(EF\iso 1_{\D}\) are the unit and counit of an adjunction. However, the previous remark shows that we can tweak \(E\) or~\(F\) to make this true.
\end{rmk}

\begin{rmk}
Equivalence of categories preserves adjoints. If \(F\adj U\) in the following diagram, then \(F'\adj U'\):
\begin{diagram}
\C			&\pile{\rTo^F\\\lTo_U}				&\D\\
\dTo>{\eqv}	&									&\dTo<{\eqv}\\
\C'			&\pile{\rDashto^{F'}\\\lDashto_{U'}}&\D'
\end{diagram}
In particular, isomorphism of categories preserves adjoints.
\end{rmk}
\begin{proof}
By the previous remark, we may assume without loss of generality that the equivalences are \emph{adjoint} equivalences. The result then follows from the prior remark about composites of adjoints.
\end{proof}

\begin{rmk}
In the proof of Corollary~9.5, view \(F:\Cop\to\Dop\) and \(U:\Dop\to\Cop\), so
\[\psi=\inv{\phi}:\Hom_{\Cop}(UD,C)\iso\Hom_{\Dop}(D,FC)\]
is natural in \(C\) and~\(D\). Apply Proposition~9.4 to obtain the unit \(\epsilon:1_{\Dop}\to FU\) for~\(\Dop\), which is just the desired counit \(\epsilon:FU\to 1_{\D}\) for~\(\D\). This argument shows that taking opposites reverses an adjunction.
\end{rmk}

\begin{rmk}
In the proof of Proposition~9.9, to see that \(\varphi_D:UD\iso VD\) is natural in~\(D\), let \(h:D\to D'\) and observe that this diagram commutes:
\begin{diagram}
\Hom(C,UD)		&\rTo^{(\varphi_D)_*}_{\iso}	&\Hom(C,VD)\\
\dTo<{(Uh)_*}	&								&\dTo>{(Vh)_*}\\
\Hom(C,UD')		&\rTo_{(\varphi_{D'})_*}^{\iso}	&\Hom(C,VD')
\end{diagram}
Taking \(C=UD\) and chasing \(1_{UD}\) around the diagram, we see that
\[Vh\after\varphi_D=\varphi_{D'}\after Uh\]
so \(\varphi\)~is natural in~\(D\), and \(U\iso V\).

Alternately, note that the diagram just represents commutativity at~\(C\) of the image of the naturality square for~\(\varphi\) under the (faithful) Yoneda embedding.
\end{rmk}

\begin{rmk}
Let \(\alpha:J\to I\) be a function between sets and \(\alpha^*:\Sets^I\to\Sets^J\) the induced reindexing functor. To see that
\[\textstyle\sum_{\alpha}\adj\alpha^*\adj\prod_{\alpha}\]
first observe that there is a bijective correspondence between families
\[\adjrule{\varphi_i:\sum_{\alpha j=i}B_j\to X_i}{\psi_j:B_j\to X_{\alpha j}}\]
given in the downward direction by \(\psi_j=\varphi_{\alpha j}\after i_j\), where \(i_j:B_j\to\sum_{\alpha k=\alpha j}B_k\) is the canonical injection, and in the upward direction by \(\varphi_i=\copairing{\,\psi_j\mid j\in\inv{\alpha}(i)\,}\).

Dually, there is a bijective correspondence between families
\[\adjrule{\psi_j:X_{\alpha j}\to B_j}{\varphi_i:X_i\to\prod_{\alpha j=i}B_j}\]
given in the downward direction by \(\varphi_i=\pairing{\,\psi_j\mid j\in\inv{\alpha}(i)\,}\) and in the upward direction by \(\psi_j=p_j\after\varphi_{\alpha j}\) where \(p_j\)~is the canonical projection.
\end{rmk}

\begin{rmk}
In the first half of the proof of Proposition~9.20, let \(f=B:B\to 1\) and identify \(\Ee/1\) and~\(\Ee\). Then we have
\begin{diagram}
B	&&\Ee/B\\
\dTo&&\dTo>{\sum_B}\ \uTo>{B^*}\ \dTo>{\prod_B}\\
1	&&\Ee
\end{diagram}
Since \(\sum_B\adj B^*\), it follows that \(B^*\)~is pullback over the terminal object, which is multiplication by~\(B\) (over~\(B\)):
\[B^*A=(\pi:A\times B\to B)\]
Therefore \(\sum_BB^*A=A\times B\). Now since \(B^*\adj\prod_B\), there are natural isomorphisms
\begin{align*}
\Hom(C,\textstyle\prod_BB^*A)&\iso\Hom(B^*C,B^*A)\\
	&\iso\Hom(\textstyle\sum_BB^*C,A)\\
	&\iso\Hom(C\times B,A)
\end{align*}
It follows that \(\prod_BB^*A=A^B\) (contrary to what the book says).

In the second half of the proof, we use the idea that multiplication over~\(F\) is the pullback of exponentiation by~\(F\).\footnote{See the remark in Chapter~6 above.} Observe that
\begin{diagram}[nohug]
Y\times F	&\rTo^f		&X\\
			&\rdTo<{\pi}&\dTo>p\\
			&			&F
\end{diagram}
commutes if and only if
\begin{diagram}
Y	&\rTo^{\curry f}	&X^F\\
\dTo&					&\dTo>{p^F}\\
1	&\rTo_{\curry 1_F}	&F^F
\end{diagram}
commutes, by considering this diagram:
\begin{diagram}[nohug]
F^F\times F			&							&\rTo^{\eval_F}	&			&F\\
\uTo<{p^F\times 1_F}&							&				&			&\uTo>{1_F}\\
X^F\times F			&\rTo^{\eval_X}				&X				&\rTo^p		&F\\
					&\luTo<{\curry{f}\times 1_F}&\uTo>f			&\ruTo>{\pi}&\\
					&							&Y\times F		&			&
\end{diagram}
It follows that there is a natural isomorphism
\[\Hom(F^*Y,p)\iso\Hom(Y,\textstyle\prod_F(p))\]
\end{rmk}

\begin{rmk}
For a set~\(I\) and an \(I\)-indexed family \(A=(A_i)_{i\in I}\) of sets with \(J=\int_I A=\coprod_{i\in I}A_i\),\footnote{See the remark in Chapter~8 above.} there is clearly an equivalence
\[\Sets^I/A\eqv\Sets^J\]
which in one direction takes an \(I\)-indexed family \((f_i:B_i\to A_i)_{i\in I}\) of functions to the \(J\)-indexed family of sets whose \((x,i)\)-th set is \(\inv{f_i}(x)\), and in the other direction takes a \(J\)-indexed family \((S_{(x,i)})_{x\in A_i}\) of sets to the \(I\)-indexed family
\[\bigl(\,\pi_i:\coprod_{x\in A_i}S_{(x,i)}\to A_i\,\bigr)_{i\in I}\]
of indexing projections. This is just a special case of Lemma~9.23.
\end{rmk}

\begin{rmk}
The proof of Freyd's adjoint functor theorem (9.29) uses the idea that a free object can be constructed as a subobject of a big enough product of ``representative'' objects. For example, the free group on a set~\(X\) can be constructed as a subgroup of a big direct product of groups~\(G\) for which there are functions \(X\to U(G)\); the only difficulty lies in showing that the representative groups form a set, as opposed to a proper class.\footnote{See \cite{bergman} and~\cite{lang}.} This is just the ``solution set'' in the adjoint functor theorem.

In the proof of the theorem, to see that the existence of an initial object
\[(FX,\eta_X:FX\to UFX)\]
in the comma category \(\comma{X}{U}\) for each object \(X\in\X\) implies the existence of a left adjoint \(F\adj U\), first define \(F:\X\to\C\) on an arrow \(f:X\to Y\) to be the unique arrow \(Ff:FX\to FY\) with \(\eta_Y\after f=UFf\after\eta_X\):
\begin{diagram}
X		&\rTo^{\eta_X}	&UFX		&&FX\\
\dTo<f	&				&\dTo>{UFf}	&&\dDashto>{Ff}\\
Y		&\rTo_{\eta_Y}	&UFY		&&FY
\end{diagram}
It is then immediate that \(F\)~is a functor, \(\eta:1_{\X}\to UF\) is a natural transformation, and \(\eta\)~is the unit of the adjunction \(F\adj U\).
\end{rmk}

\begin{exer}[1]
For functors \(F:\C\to\D\) and \(U:\D\to\C\), given an isomorphism
\[\phi:\Hom_{\D}(FC,D)\iso\Hom_{\C}(C,UD)\]
natural in \(C\) and~\(D\), the family \(\eta_C:C\to UFC\) defined by \(\eta_C=\phi(1_{FC})\) is a natural transformation \(\eta:1_{\C}\to UF\).
\end{exer}
\begin{proof}
For \(h:C'\to C\), the following diagram commutes by naturality:
\begin{diagram}
\Hom(FC,FC)		&\rTo^{\phi}_{\iso}	&\Hom(C,UFC)\\
\dTo<{(Fh)^*}	&					&\dTo>{h^*}\\
\Hom(FC',FC)	&\rTo_{\phi}^{\iso}	&\Hom(C',UFC)\\
\uTo<{(Fh)_*}	&					&\uTo>{(UFh)_*}\\
\Hom(FC',FC')	&\rTo_{\phi}^{\iso}	&\Hom(C',UFC')
\end{diagram}
Chasing \(1_{FC}\) and~\(1_{FC'}\) around the diagram, we see that
\[\eta_C\after h=UFh\after\eta_{C'}\]
so \(\eta\)~is natural.
\end{proof}

\begin{exer}[2]
If \(M\)~is a monoid, then the counit \(\epsilon:FUM\to M\) is surjective.
\end{exer}
\begin{proof}
For any element \(a\in M\), consider the point \(a:1\to UM\). By the universal property of the unit \(\eta:1\to UF1\), there is \(\tr{a}:F1\to M\) with \(a=U(\tr{a})\after\eta\), and by the universal property of the counit~\(\epsilon\) there is \(\tr{\tr{a}}:1\to UM\) with \(\tr{a}=\epsilon\after F(\tr{\tr{a}})\):
\begin{diagram}[nohug]
UF1			&\rTo^{U(\tr{a})}	&UM	&&F1&\rTo^{F(\tr{\tr{a}})}	&FUM\\
\uTo<{\eta}	&\ruTo>a			&	&&	&\rdTo<{\tr{a}}			&\dTo>{\epsilon}\\
1			&					&	&&	&						&M
\end{diagram}
Now
\[a=\tr{a}(*)=\epsilon(F(\tr{\tr{a}})(*))\]
Since \(a\)~was arbitrary, it follows that \(\epsilon\)~is surjective.
\end{proof}

\begin{exer}[3]
The unit of the adjunction \((-)\times A\adj(-)^A\) is just the transposed pairing operation~\(\eta\) discussed in Chapter~6 above.
\end{exer}

\begin{exer}[6]
If \(P:\Cat\to\Pre\) is the preorder functor and \(C:\Pre\to\Cat\) the inclusion functor,\footnote{See Exercise~8 in Chapter~1 above.} then \(P\adj C\).
\end{exer}
\begin{proof}
The identity \(1_{\Pre}=PC\) gives the counit \(1_Q:PC(Q)\to Q\). Indeed, for any monotone map \(f:P(\C)\to Q\), there is obviously a unique functor \(\tr{f}:\C\to C(Q)\) making the following diagram commute:
\begin{diagram}[nohug]
P(\C)	&\rTo^{P(\tr{f})}	&PC(Q)\\
		&\rdTo<f			&\dTo>{1_Q}\\
		&					&Q
\end{diagram}
Therefore \(P\adj C\).
\end{proof}

\begin{exer}[9]
The contravariant powerset functor \(\pow:\Setsop\to\Sets\) is adjoint to itself---more precisely, right adjoint to \(\dual{\pow}:\Sets\to\Setsop\).
\end{exer}
\begin{proof}
Since \(\pow\iso2^{(-)}\), we have
\begin{align*}
\Hom_{\Setsop}(\dual{\pow}(X),Y)&\iso\Hom_{\Sets}(Y,\pow(X))\\
	&\iso\Hom_{\Sets}(Y,2^X)\\
	&\iso\Hom_{\Sets}(X\times Y,2)\\
	&\iso\Hom_{\Sets}(X,2^Y)\\
	&\iso\Hom_{\Sets}(X,\pow(Y))\qedhere
\end{align*}
\end{proof}
\begin{rmk}
The ordinal \(1=\{0\}\) is terminal in~\(\Sets\) and hence initial in~\(\Setsop\), but \(\pow(1)=\{0,1\}=2\) is not initial in~\(\Sets\) (there is no function \(2\to0\)), so \(\pow\)~is not a left adjoint (and for the same reason \(\dual{\pow}\)~is not a right adjoint).
\end{rmk}

\begin{exer}[12]
Let \(\P\)~be the category of propositions under entailment and \(p\in\P\). There is an adjunction
\[(-)\land p\adj p\limplies(-)\tag{1}\]
The counit of this adjunction is \emph{modus ponens}:
\[(p\limplies a)\land p\to a\]
Moreover, \((-)\land p\) has a left adjoint if and only if \(p\)~is a tautology, in which case
\[1_{\P}\adj(-)\land p\tag{2}\]
\end{exer}
\begin{proof}
For~(1), the operations are obviously functorial and \(a\land p\to b\) if and only if \(a\to(p\limplies b)\). For~(2), if \((-)\land p\) is a right adjoint then we must have
\[\true\to\true\land p\to p\to\true\]
so \(p\)~is a tautology, and in that case (2)~is obvious.
\end{proof}
\begin{rmk}
In general if \(\C\)~is a category with all finite products, then \(1_{\C}\adj(-)\times 1\).
\end{rmk}

\begin{exer}[13]
For a set~\(I\), the Yoneda embedding \(y:I\to\Sets^I\) is given by\footnote{See the remark in Chapter~8 above.}
\[y(i)=(\delta_{ij})_{j\in I}\]
If \(f:J\to I\) is a function, then the following diagram commutes up to natural isomorphism:
\begin{diagram}
\Sets^J		&\rTo^{\sum_f}	&\Sets^I\\
\uTo<{y_J}	&				&\uTo>{y_I}\\
J			&\rTo_f			&I
\end{diagram}
Indeed, for \(i\in I\) and \(j\in J\),
\[\textstyle y_I(f(j))_i=\delta_{i f(j)}=\sum_{f(k)=i}\delta_{jk}=(\,\sum_f((\delta_{jk})_{k\in J}))_i=(\,\sum_f(y_J(j)))_i\]
The composite
\[I\xto{y}\Sets^I\eqv\Sets/I\]
sends \(i\in I\) to the point \(i:1\to I\). The above diagram becomes
\begin{diagram}
\Sets/J	&\rTo^{f_L}	&\Sets/I\\
\uTo	&			&\uTo\\
J		&\rTo_f		&I
\end{diagram}
Now let \(i:\pow(I)\to\Sets/I\) map \(U\subseteq I\) to the inclusion \(i(U):U\to I\) and map a subset relation \(U\subseteq V\subseteq I\) to the inclusion \(i(U\subseteq V):U\to V\) over~\(I\). Clearly \(i\)~is a functor. Let \(\sigma:\Sets/I\to\pow(I)\) map a function \(f:X\to I\) to its image~\(\im f\) and map a commutative triangle
\begin{diagram}[nohug]
X&\rTo&Y\\
&\rdTo<f&\dTo>g\\
&&I
\end{diagram}
to the subset relation \(\im f\subseteq\im g\). Then \(\sigma\)~is clearly a functor, and \(\sigma\adj i\) since for \(f:X\to I\) and \(U\subseteq I\), we have \(\im f\subseteq U\) if and only if \(f\)~factors through the inclusion~\(i(U)\).
\end{exer}

\begin{exer}[17]
If \(\C\)~is a cartesian closed category and \(1\xto{0}N\xto{s}N\) is a natural numbers object in~\(\C\), then we can define an addition operation \(+:N\times N\to N\). We use the idea that \((-)+m\) is given by~\(s^m\). Let \(\id:1\to N^N\) be the transpose of the projection \(1\times N\iso N\). Then there is \(f:N\to N^N\) unique making this diagram commute:
\begin{diagram}[nohug]
1	&\rTo^0			&N			&\rTo^s		&N\\
	&\rdTo_{\id}	&\dDashto>f	&			&\dDashto>f\\
	&				&N^N		&\rTo_{s^N}	&N^N
\end{diagram}
Transposing yields this commutative diagram:
\begin{diagram}
1\times N	&\rTo^{0\times 1_N}	&N\times N			&\rTo^{s\times 1_N}	&N\times N\\
\dTo<{\iso}	&					&\dTo>{\uncurry{f}}	&					&\dTo>{\uncurry{f}}\\
N			&\rTo_{1_N}			&N					&\rTo_s				&N
\end{diagram}
This yields the equations
\begin{align*}
\uncurry{f}(0,n)&=n\\
\uncurry{f}(sm,n)&=s\uncurry{f}(m,n)
\end{align*}
Writing \(s=(-)+1\) and \(\uncurry{f}=+\), these are just the equations of addition:
\begin{align*}
0+n&=n\\
(m+1)+n&=(m+n)+1
\end{align*}
Therefore \(\uncurry{f}:N\times N\to N\) is the desired addition operation.

In a similar way, we can define a multiplication operation \(\mult:N\times N\to N\). Let \(t=\curry{(+\after\pair{\eval}{\pi})}\) where \(\eval:N^N\times N\to N\) is evaluation and \(\pi:N^N\times N\to N\) is projection. Let \(z:1\to N^N\) be the transpose of the composite \(1\times N\xto{!}1\xto{0}N\). Then there is \(g:N\to N^N\) unique making this diagram commute:
\begin{diagram}[nohug]
1	&\rTo^0		&N			&\rTo^s	&N\\
	&\rdTo_z	&\dDashto>g	&		&\dDashto>g\\
	&			&N^N		&\rTo_t	&N^N
\end{diagram}
Transposing yields these commutative diagrams:
\begin{diagram}[nohug]
1\times N	&\rTo^{0\times 1_N}	&N\times N			&&N\times N	&\rTo^{s\times 1_N}			&N\times N\\
\dTo<!		&					&\dTo>{\uncurry{g}}	&&			&\rdTo<{\uncurry{g}+\pi_2}	&\dTo>{\uncurry{g}}\\
1			&\rTo_0				&N					&&			&							&N
\end{diagram}
Writing \(\uncurry{g}=\mult\)\ , these yield the equations of multiplication:
\begin{align*}
0\mult n&=0\\
(m+1)\mult n&=m\mult n+n
\end{align*}
Therefore \(\uncurry{g}:N\times N\to N\) is the desired multiplication operation.

Continuing this way, we can define an exponentiation operation \(N\times N\to N\). Let \(e=\curry{(\mult\after\pair{\eval}{\pi})}\), let \(u:1\to N^N\) be the transpose of the composite
\[1\times N\xto{!}1\xto{0}N\xto{s}N\]
and let \(h:N\to N^N\) be the unique arrow making this diagram commute:
\begin{diagram}[nohug]
1	&\rTo^0		&N			&\rTo^s	&N\\
	&\rdTo_u	&\dDashto>h	&		&\dDashto>h\\
	&			&N^N		&\rTo_e	&N^N
\end{diagram}
Writing \(\uncurry{h}(m,n)=n^m\), it follows that
\begin{align*}
n^0&=1\\
n^{m+1}&=n^m\mult n
\end{align*}
so \(\uncurry{h}:N\times N\to N\) is the desired exponentiation operation.

Finally, we can define a factorial operation \(N\to N\) by letting \(p:N\to N\times N\) be the unique arrow making this diagram commute:
\begin{diagram}[nohug]
1	&\rTo^0				&N			&\rTo^s						&N\\
	&\rdTo_{\pair{1}{1}}&\dDashto>p	&							&\dDashto>p\\
	&					&N\times N	&\rTo_{\pair{\mult}{s\pi_2}}&N\times N
\end{diagram}
This yields the equations
\begin{align*}
p(0)&=(0!\,,1)\\
p(n+1)&=((n+1)!\,,n+2)
\end{align*}
so \(\pi_1p:N\to N\) is the desired factorial operation.
\end{exer}

\begin{exer}[18]
In~\(\Sets\), a structure \(1\xto{0}N\xto{s}N\) is a natural numbers object if and only if
\begin{diagram}[eqno=(1)]
1&\rTo^0&N&\lTo^s&N
\end{diagram}
is a coproduct diagram (so \(N\iso1+N\)) and
\begin{diagram}[eqno=(2)]
N&\pile{\rTo^s\\\rTo_{1_N}}&N&\rTo^!&1
\end{diagram}
is a coequalizer diagram.
\end{exer}
\begin{proof}
For the forward direction, we may assume without loss of generality that \(N=\N\), \(0\)~is zero and \(s(n)=n+1\) is the successor function. For any \(x\in X\) and \(f:\N\to X\), define \(h:\N\to X\) by
\[h(n)=\begin{cases}
x&\text{if }n=0\\
f(n-1)&\text{if }n\ne0
\end{cases}\]
Then clearly \(h\)~is unique making this diagram commute:
\begin{diagram}[nohug]
1&\rTo^0&\N&\lTo^s&\N\\
&\rdTo<x&\dDashto>h&\ldTo>f\\
&&X&&
\end{diagram}
Therefore (1)~is a coproduct diagram. If \(fs=f=f\,1_{\N}\), then \(f(n+1)=f(n)\) for all \(n\in\N\), so \(f(n)=f(0)\) for all \(n\in\N\) by induction on~\(\N\). It follows that \(f(0)\)~is unique making this diagram commute:
\begin{diagram}[nohug]
\N	&\pile{\rTo^s\\\rTo_{1_{\N}}}	&\N	&\rTo^!		&1\\
	&								&	&\rdTo<f	&\dDashto>{f(0)}\\
	&								&	&			&X
\end{diagram}
Therefore (2)~is a coequalizer diagram.

Conversely, if (1)~is a coproduct diagram then it follows that \(s:N\to N\setminus\{0\}\) is a bijection. Define
\[S=\{\,x\in N\mid x=s^n(0)\text{ for some }n\in\N\,\}\]
and let \(\chi:N\to2\) be the characteristic function of~\(S\) in~\(N\). Then \(\chi(0)=1\) since \(0=s^0(0)\), and \(\chi s=\chi=\chi 1_N\), so if (2)~is a coequalizer diagram then \(\chi(x)=1\) for all \(x\in N\) and \(S=N\). It follows that \(n\mapsto s^n(0)\) is an iso \(\N\iso N\) and \(N\)~is a natural numbers object.
\end{proof}
\begin{rmk}
The coproduct diagram~(1) expresses that \(N\)~is a Hilbert Hotel (it can always accommodate a new guest), and the coequalizer diagram~(2) expresses that \(N\)~supports induction.
\end{rmk}

\begin{exer}[19]
The underlying graph functor\footnote{See Exercise~1 in Chapter~1 above.} \(\Gamma:\Sets\to\Rel\) has a right adjoint \(\Phi:\Rel\to\Sets\).
\end{exer}
\begin{proof}
We use the idea that a relation \(R\subseteq A\times B\) is fully encoded in the function \(f_R:A\to\pow(B)\) with \(f(a)=\{\,b\in B\mid a\mathrel{R}b\,\}\).

Define \(\Phi(A)=\pow(A)\) and \(\Phi(R\subseteq A\times B):\pow(A)\to\pow(B)\) by
\[X\mapsto\{\,b\in B\mid x\mathrel{R}b\text{ for some }x\in X\,\}\]
Then \(\Phi\)~is clearly a functor. Let \({\ni_A}\subseteq\pow(A)\times A\) denote the (reverse) membership relation on~\(A\). Then \(\ni\)~is a natural transformation \(\Gamma\Phi\to 1_{\Rel}\) since the following diagram commutes:
\begin{diagram}
\pow(A)				&\rTo^{\ni_A}	&A\\
\dTo<{\Gamma\Phi(R)}&				&\dTo>R\\
\pow(B)				&\rTo_{\ni_B}	&B
\end{diagram}
Moreover, \(f_R\)~is unique making the following diagram commute:
\begin{diagram}[nohug]
A	&\rTo^{\Gamma f_R}	&\pow(B)\\
	&\rdTo<R			&\dTo>{\ni_B}\\
	&					&B
\end{diagram}
Therefore \(\ni\)~is the counit of an adjunction \(\Gamma\adj\Phi\). The unit \(\eta_A:A\mapsto\pow(A)\) is just the singleton map \(a\mapsto\{a\}\).
\end{proof}
\begin{rmk}
\(\Gamma\)~is not a right adjoint since \(1=\Gamma 1\) is terminal in~\(\Sets\) but not in~\(\Rel\), and \(\Phi\)~is not a left adjoint since \(0\)~is initial in~\(\Rel\) but \(\pow(0)=1\) is not initial in~\(\Sets\).
\end{rmk}

\newpage
\section*{Chapter~10}
\begin{rmk}
Let \(S:\Sets\to\Sets\) be the monad sending a set~\(X\) to the strings over~\(X\), and \(P:\Sets\to\Sets\) the covariant powerset monad sending \(X\) to the subsets of~\(X\).\footnote{See Examples 10.5 and~10.7.} Define \(h_X:SX\to PX\) by sending a string to the elements in the string:
\[h_X[x_1,\ldots,x_n]=\{x_1,\ldots,x_n\}\]
Then \(h_X\)~is natural in~\(X\) since for any \(f:X\to Y\), this diagram commutes:
\begin{diagram}
X		&\rTo^{[-]_X}	&SX			&\rTo^{h_X}	&PX\\
\dTo<f	&				&\dTo<{Sf}	&			&\dTo>{Pf}\\
Y		&\rTo_{[-]_Y}	&SY			&\rTo_{h_Y}	&PY
\end{diagram}
It is also easy to see that \(h:S\to P\) respects multiplication and units by making these diagrams commute:
\begin{diagram}[nohug]
S^2			&\rTo^{h\mprod h}	&P^2				&&S			&\rTo^h			&P\\
\dTo<{\sum}	&					&\dTo>{\bigunion}	&&\uTo<{[-]}&\ruTo>{\{-\}}	&\\
S			&\rTo_h				&P					&&1			&				&
\end{diagram}
Therefore \(h\)~is a monad homomorphism.\footnote{See the remark in Chapter~7 above.} This reflects the intuition that (some) structure is preserved when we switch from concatenating strings to taking unions of the sets of elements in those strings.
\end{rmk}

\begin{rmk}
In the proof of Proposition~10.6, when viewing \(T\)~as an endofunctor of~\(\C^T\), we take \(T(A,\alpha)=(TA,\mu_A)\)---completely disregarding~\(\alpha\)! For an arrow \(h:(A,\alpha)\to(B,\beta)\) in~\(\C^T\) with underlying arrow \(h:A\to B\) in~\(\C\), we see that the arrow \(Th:TA\to TB\) in~\(\C\) yields an arrow \(Th:(TA,\mu_A)\to(TB,\mu_B)\) in~\(\C^T\). This is functorial since the identities and composites in~\(\C^T\) are just inherited from those in~\(\C\), and \(T\)~is an endofunctor of~\(\C\).
\end{rmk}

\begin{rmk}
In the proof of Proposition~10.12, let \(i_n:P^n0\to I\) be the colimit and \(\varphi=\colimit_n i_n:PI\to I\) the isomorphism with \(\varphi\after Pi_n=i_{n+1}\).\footnote{See Exercise~9 in Chapter~5 above.} If \(\alpha:PX\to X\) is a \(P\)-algebra and \(h:I\to X\) makes the diagram
\begin{diagram}
PI				&\rTo^{Ph}		&PX\\
\dTo<{\varphi}	&				&\dTo>{\alpha}\\
I				&\rTo_h			&X
\end{diagram}
commute, then \(h\)~is uniquely determined by the arrows \(h\after i_n\). But \(h\after i_0:0\to X\) and
\begin{align*}
h\after i_{n+1}&=h\after\varphi\after Pi_n\\
	&=\alpha\after Ph\after Pi_n\\
	&=\alpha\after P(h\after i_n)
\end{align*}
so these arrows are uniquely determined by induction on~\(n\).

To construct~\(h\), let \(h_0:0\to X\) and \(h_{n+1}=\alpha\after Ph_n\). It follows by induction on~\(n\) that \(h_n:P^n0\to X\) is a cocone, so we have \(h=\colimit_n h_n:I\to X\). Then
\begin{align*}
h\after\varphi\after Pi_n&=h\after i_{n+1}\\
	&=h_{n+1}\\
	&=\alpha\after Ph_n\\
	&=\alpha\after P(h\after i_n)\\
	&=\alpha\after Ph\after Pi_n
\end{align*}
so \(h\after\varphi=\alpha\after Ph\), since this arrow is uniquely determined by its composites with the arrows~\(Pi_n\). This shows that \(\varphi:PI\to I\) is an initial \(P\)-algebra.
\end{rmk}

\begin{exer}[1]
The natural numbers \((\N,0,s)\), where \(s:\N\to\N\) is the successor function \(s(n)=n+1\), form an initial algebra for the ``successor endofunctor'' \(S:\Sets\to\Sets\) with \(S(X)=X+1\).
\end{exer}
\begin{proof}
We know that \((\N,0,s)\) is a natural numbers object in~\(\Sets\),\footnote{See Chapter~9.} which is the same thing as an initial \(S\)-algebra.
\end{proof}
\begin{rmk}
This result is reminiscent of the fact that \(\omega\)~is the least fixed point of the operation \(1+(-)\) on the ordinals.
\end{rmk}

\begin{exer}[3]
If \(T:\C\to\C\) is an endofunctor and \(i:TI\to I\) is an initial \(T\)-algebra, then \(i\)~is an isomorphism.
\end{exer}
\begin{proof}
Consider \(Ti:T(TI)\to TI\). Since \(i\)~is initial, there is \(h:I\to TI\) making this diagram commute:
\begin{diagram}
TI		&\rTo^{Th}	&T^2I		&\rTo^{Ti}	&TI\\
\dTo<i	&			&\dTo>{Ti}	&			&\dTo>i\\
I		&\rTo_h		&TI			&\rTo_i		&I
\end{diagram}
Again since \(i\)~is initial, we must have \(ih=1_I\), which also implies
\[hi=Ti\after Th=T(ih)=T(1_I)=1_{TI}\]
so \(i\)~is an isomorphism.
\end{proof}

\begin{exer}[5]
For adjoint functors \(F:\C\to\D\) and \(U:\D\to\C\) with unit \(\eta:1_{\C}\to UF\) and counit \(\epsilon:FU\to 1_{\D}\), let \(T=UF\) be the associated monad with unit~\(\eta\) and multiplication \(\mu=U\epsilon_F\). There is a comparison functor \(\Phi:\D\to\C^T\) which maps an object \(D\) to the \(T\)-algebra \(U\epsilon_D:T(UD)\to UD\) and maps an arrow \(f:D\to E\) to the arrow \(Uf:UD\to UE\). Moreover, \(\Phi\)~commutes with the forgetful functors \(U\) and \(U^T:\C^T\to\C\):
\begin{diagram}[nohug]
\D	&\rTo^{\Phi}&\C^T\\
	&\rdTo<U	&\dTo>{U^T}\\
	&			&\C
\end{diagram}
\end{exer}
\begin{proof}
To see that \(U\epsilon_D\)~is a \(T\)-algebra, recall that
\begin{diagram}[nohug]
UD	&\rTo^{\eta_{UD}}	&UFUD\\
	&\rdTo<{1_{UD}}		&\dTo>{U\epsilon_D}\\
	&					&UD
\end{diagram}
commutes by the triangle identity (10.1), and apply~\(U\) to the diagram
\begin{diagram}
FUFUD					&\rTo^{FU\epsilon_D}&FUD\\
\dTo<{\epsilon_{FUD}}	&					&\dTo>{\epsilon_D}\\
FUD						&\rTo_{\epsilon_D}	&D
\end{diagram}
which commutes since \(\epsilon\)~is natural.

To see that \(Uf:U\epsilon_D\to U\epsilon_E\), apply~\(U\) to the diagram
\begin{diagram}
FUD					&\rTo^{FUf}	&FUE\\
\dTo<{\epsilon_D}	&			&\dTo>{\epsilon_E}\\
D					&\rTo_f		&E
\end{diagram}
which also commutes since \(\epsilon\)~is natural. It is then immediate that \(\Phi\)~is a functor which commutes with the forgetful functors.
\end{proof}

\begin{exer}[6]
The triple \((\pow,\{-\},\bigunion)\) is a monad on~\(\Sets\), where \(\pow:\Sets\to\Sets\) is the covariant powerset functor, \(\{-\}_X:X\mapsto\pow(X)\) is the singleton function \(x\mapsto\{x\}\), and \(\bigunion_X:\pow(\pow(X))\to\pow(X)\) is the union function \(\alpha\mapsto\bigunion\alpha\).
\end{exer}
\begin{proof}
We know that \(\pow\)~is a functor. If \(f:X\to Y\) is a function, then the square
\begin{diagram}
X		&\rTo^{\{-\}_X}	&\pow(X)\\
\dTo<f	&				&\dTo>{\pow(f)}\\
Y		&\rTo_{\{-\}_Y}	&\pow(Y)
\end{diagram}
commutes since it just computes \(x\mapsto\{f(x)\}\). Therefore \(\{-\}:1\to\pow\) is a natural transformation. Similarly the square
\begin{diagram}
\pow^2(X)		&\rTo^{\bigunion_X}	&\pow(X)\\
\dTo<{\pow^2(f)}&					&\dTo>{\pow(f)}\\
\pow^2(Y)		&\rTo_{\bigunion_Y}	&\pow(Y)
\end{diagram}
commutes since it just computes \(\alpha\mapsto\bigunion_{A\in\alpha}f(A)\).\footnote{Here \(\bigunion_{A\in\alpha}f(A)\) means \(\bigunion\{\,f(A)\mid A\in\alpha\,\}\).} Therefore \(\bigunion:\pow^2\to\pow\) is also a natural transformation. The associativity diagram
\begin{diagram}
\pow^3(X)					&\rTo^{\pow(\bigunion_X)}	&\pow^2(X)\\
\dTo<{\bigunion_{\pow(X)}}	&							&\dTo>{\bigunion_X}\\
\pow^2(X)					&\rTo_{\bigunion_X}			&\pow(X)
\end{diagram}
commutes since for \(\beta\in\pow^3(X)\),
\[\bigunion\bigunion\beta=\bigunion_{\alpha\in\beta}\bigunion\alpha\]
Finally, the unit diagram
\begin{diagram}[nohug]
\pow(X)	&\rTo^{\pow(\{-\}_X)}	&\pow^2(X)			&\lTo^{\{-\}_{\pow(X)}}	&\pow(X)\\
		&\rdTo<1				&\dTo>{\bigunion_X}	&\ldTo>1				&\\
		&						&\pow(X)			&						&
\end{diagram}
commutes since for \(\alpha\in\pow(X)\),
\[\bigunion_{A\in\alpha}\{A\}=\alpha=\bigunion\{\alpha\}\]
Therefore we have a monad.
\end{proof}

\begin{exer}[8]
Let \(F\adj U\) be the free forgetful adjunction between \(F:\Sets\to\Mon\) and \(U:\Mon\to\Sets\), and let \(T=UF\) be the associated monad. Every \(T\)-algebra \(\alpha:TA\to A\) arises from a unique monoid structure on~\(A\).
\end{exer}
\begin{proof}
We use the notation of Example~10.7. The monoid structure must be defined by the unit \(1=\alpha[]\) and multiplication \(x\mult y=\alpha[x,y]\). This multiplication is associative since
\begin{align*}
(x\mult y)\mult z&=\alpha[\alpha[x,y],z]\\
	&=\alpha[\alpha[x,y],\alpha[z]]\\
	&=\alpha(\mu[[x,y],[z]])\\
	&=\alpha[x,y,z]\\
	&=\alpha(\mu[[x],[y,z]])\\
	&=\alpha[\alpha[x],\alpha[y,z]]\\
	&=\alpha[x,\alpha[y,z]]\\
	&=x\mult(y\mult z)
\end{align*}
and is unital by a similar computation. It follows by induction that
\[x_1\mult\cdots\mult x_n=\alpha[x_1,\ldots,x_n]\]
so the algebra arises from the monoid structure as desired.
\end{proof}

\begin{exer}[11]
For a monad \((T,\eta,\mu)\) on a category~\(\C\), the Kleisli category~\(\C_T\) is indeed a category.
\end{exer}
\begin{proof}
For arrows \(f_T:A_T\to B_T\), \(g_T:B_T\to C_T\), and \(h_T:C_T\to D_T\) in~\(\C_T\),
\begin{align*}
(h_T\after g_T)\after f_T&=\mu_D\after T(\mu_D\after Th\after g)\after f\\
	&=\mu_D\after T\mu_D\after T^2h\after Tg\after f\\
	&=\mu_D\after\mu_{TD}\after T^2h\after Tg\after f\\
	&=\mu_D\after Th\after\mu_C\after Tg\after f\\
	&=h_T\after(g_T\after f_T)
\end{align*}
where the third equality follows from associativity of~\(\mu\) (10.5), and the fourth equality follows from naturality of~\(\mu\):
\begin{diagram}
T^2C		&\rTo^{\mu_C}	&TC\\
\dTo<{T^2h}	&				&\dTo>{Th}\\
T^3D		&\rTo_{\mu_{TD}}&T^2D
\end{diagram}
Therefore composition in~\(\C_T\) is associative. Also
\[f_T\after 1_{A_T}=\mu_B\after Tf\after\eta_A=\mu_B\after\eta_{TB}\after f=1_{TB}\after f=f_T\]
by naturality and unity of~\(\eta\) (10.6):
\begin{diagram}[nohug]
A		&\rTo^{\eta_A}		&TA\\
\dTo<f	&					&\dTo>{Tf}\\
TB		&\rTo^{\eta_{TB}}	&T^2B\\
		&\rdTo<{1_{TB}}		&\dTo>{\mu_B}\\
		&					&TB
\end{diagram}
Finally
\[1_{B_T}\after f_T=\mu_B\after T\eta_B\after f=1_{TB}\after f=f_T\]
again by unity of~\(\eta\). Therefore composition in~\(\C_T\) is unital.
\end{proof}

% References
\newpage
\begin{thebibliography}{0}
\bibitem{awodey} Awodey, S. \textit{Category Theory}, 2nd~ed. Oxford, 2010.
\bibitem{bergman} Bergman, G. \textit{An Invitation to General Algebra and Universal Constructions}, 2nd~ed. Springer, 2015.
\bibitem{blyth} Blyth, T. \textit{Module Theory: An Approach to Linear Algebra.} Oxford, 1977.
\bibitem{lang} Lang, S. \textit{Algebra}, 3rd~ed. Springer, 2002.
\end{thebibliography}
\end{document}