\documentclass{article}
\usepackage[a4paper]{geometry}
\usepackage{amsmath,amssymb,amsthm,tikz}
\usetikzlibrary{matrix,arrows,calc,positioning}
\newenvironment{tikzeqn}{\equation\notag\begin{tikzpicture}}{\end{tikzpicture}\endequation}
\newtheorem{theorem}{Theorem}
\newtheorem{proposition}[theorem]{Proposition}
\theoremstyle{definition}
\newtheorem{definition}{Definition}
\newcommand{\blank}{\rule[0.5ex]{0.6em}{.4pt}}
\newcommand{\op}{\ensuremath{\sp\mathrm{op}}}
\newcommand{\C}{\ensuremath{\mathbb{C}}}
\newcommand{\Set}{\ensuremath{\mathbf{Set}}}
\newcommand{\funcat}[2]{\ensuremath{\left[#1,#2\right]}}
\newcommand{\y}{\ensuremath{\operatorname{\text{\textit{\textbf{y}}}}}}
\newcommand{\To}{\ensuremath{\Longrightarrow}}
\newcommand{\id}[1]{\ensuremath{\operatorname{id}_{#1}}}
\newcommand{\K}{\ensuremath{\kappa}}
\newcommand{\expo}[2]{\ensuremath{\left({#1}\Rightarrow{#2}\right)}}
\newcommand{\comma}[2]{\ensuremath{\left({#1}\downarrow{#2}\right)}}
\newcommand{\slice}[2]{\ensuremath{\left({#1}/{#2}\right)}}
\newcommand{\colim}{\ensuremath{\operatornamewithlimits{colim}}}
\newcommand{\ob}{\ensuremath{\operatorname{ob}}}
\newcommand{\mor}{\ensuremath{\operatorname{mor}}}
\newcommand{\dom}{\ensuremath{\operatorname{dom}}}
\newcommand{\cod}{\ensuremath{\operatorname{cod}}}
\title{Presheaves}
\author{Ramana Kumar (rk436)}
\begin{document}
\maketitle
\section{Introduction}
A $\mathbf{V}$-valued presheaf, $P$, on a category $C$ is a functor $P:C\op\to\mathbf{V}$.
The functor category $\funcat{C\op}{\mathbf{V}}$ is also known as a presheaf category.
Presheaf categories inherit much structure from $\mathbf{V}$, and this can sometimes be useful in reasoning about the source category $C$.
In particular, if homs in $C$ are objects in $\mathbf{V}$, then $C$ embeds fully and faithfully in its presheaf category via the Yoneda embedding.
And when $\mathbf{V}$ has small (co)limits, then so does the presheaf category.
The Yoneda embedding preserves cartesian closed structure, but not necessarily all colimits; however, in the case we consider, it does.
We take $\mathbf{V}=\Set$ and $C=\C$ to be a locally small category, and therefore only consider set-valued presheaves where the Yoneda embedding applies.
The presheaf category on $\C$ is denoted $\widehat\C$.
In this setting, we define the embedding and prove Yoneda's lemma, then use the embedding in the course of demonstrating the structure available in $\widehat\C$.
In particular, we show that $\widehat\C$ is cartesian closed, complete, and cocomplete (because $\Set$ is).
We then show that every presheaf $P$ can be recovered as a colimit of representable presheaves, where being representable means coming via the embedding.
Finally, we show that if $\C$ is small, then $\widehat\C$ is equivalent to the free cocompletion of $\C$, that is, the ``best'' category that has all colimits and in which $\C$ embeds.
\section{The Yoneda Embedding}
An embedding is a functor that is full and faithful.
Both of these notions relate to homs, that is, collections of morphisms of the same type.
A functor $F$ is full if it is surjective on homs, which means every morphism $k:FX\to FY$ in the target category is the image of some morphism $g:X\to Y$ in the source, that is, $k=Fg$.
A functor is faithful if it is injective on homs, which means if $Ff=Fg$ for morphisms $f,g:X\to Y$ in the source, then in fact $f=g$.
We want to embed the category $\C$ in the presheaf category $\widehat\C$.
The functor that does this, $\y:\C\to\widehat\C$, therefore assigns a functor to every object in $\C$, and a natural transformation to every morphism in $\C$.
The trick is to assign objects to hom functors; a hom functor for $x$ sends an object $y$ to the hom of morphisms from $y$ to $x$, thereby capturing the substantial information about $x$ available from the collections of $x$-valued morphisms.
By assuming $\C$ is locally small, we ensure that these homs are sets, and thus that hom functors are suitable as outputs of $\y$.
\begin{definition}
The \emph{contravariant hom functor} for an object $x\in\C$, written $\C(\blank,x):\C\op\to\Set$ is given by $\C(y,x)$ on objects $y\in\C$ and $\C(f,x)=(\blank\circ f):\C(v,x)\to\C(u,x)$ on morphisms $f:u\to v$ in $\C$.
(This is a functor because $(\blank\circ g)\circ(\blank\circ f)=(\blank\circ(f\circ g))$.)
The \emph{covariant hom functor} for $x$, written $\C(x,\blank):\C\to\Set$, is defined dually: $\C(x,y)$ on objects $y$ and $\C(x,f)=f\circ\blank$ on morphisms $f$.
\end{definition}
\begin{samepage}
\begin{proposition}
For each morphism $f:x\to y$ in $\C$, the collection $\{\C(z,f)\}_{z\in\C}$ is a natural transformation from $\C(\blank,x)$ to $\C(\blank,y)$.
\end{proposition}
\begin{proof}
The naturality condition for a morphism $g:u\to v$ in $\C$ is:
\begin{tikzeqn}
\matrix [matrix of math nodes, row sep=2em, column sep=2em]
{ |(vx)| \C(v,x) & |(ux)| \C(u,x) \\
|(vy)| \C(v,y) & |(uy)| \C(u,y) \\ };
\path[->]
(vx) edge node[above] {$\C(g,x)$} (ux)
(vx) edge node[left] {$\C(v,f)$} (vy)
(ux) edge node[right] {$\C(u,f)$} (uy)
(vy) edge node[below] {$\C(g,y)$} (uy);
\end{tikzeqn}
\[\C(g,y)\circ\C(v,f)=(\blank\circ g)\circ(f\circ\blank)=f\circ\blank\circ g=(f\circ\blank)\circ(\blank\circ g)=\C(u,f)\circ\C(g,x)\]
\end{proof}
\begin{definition}
The \emph{Yoneda functor} $\y:\C\to\widehat\C$ is given by $\C(\blank,x)$ on objects $x\in\C$ and $\{\C(z,f)\}_{z\in\C}$ on morphisms $f\in\C$.
(This is a functor because composition in a functor category is component-wise: $\{\C(z,f)\}_{z\in\C}\circ\{\C(z,g)\}_{z\in\C}=\{f\circ\blank\}_{z\in\C}\circ\{g\circ\blank\}_{z\in\C}=\{f\circ g\circ\blank\}_{z\in\C}=\{\C(z,f\circ g)\}_{z\in\C}$.)
\end{definition}
\end{samepage}
We will see (Theorem~\ref{Yoneda embedding}) that the Yoneda functor is straightforwardly faithful.
To show that it is full, we make use of a famous fact: the Yoneda lemma.
It says that the map sending a natural transformation $\eta:\y x\To (F:\C\op\to\Set)$ to the element $\eta_x(\id{x})\in Fx$ has an inverse, which establishes a bijection between the sets $\widehat\C(\y x,F)\cong Fx$.
(In fact, the bijections as $x$ ranges over $\C$ behave like a natural isomorphism, but we do not prove this.)
%But $\widehat\C(\blank,F)$ is not necessarily a set-valued hom functor, because $\widehat\C$ is not necessarily locally small, although when the argument is $\y x$ for some $x$, the lemma says the hom is in bijection with a set.)
\begin{theorem}[Yoneda]\label{Yoneda}
For all presheaves $F\in\widehat\C$ and objects $x\in\C$, the map $\eta\mapsto\eta_x(\id{x})$ is a bijection between $\widehat\C(\y x,F)$ and $Fx$.
\end{theorem}
\begin{proof}
Let $\eta:\y x\To F$, so $\eta_x:\C(x,x)\to Fx$ and hence $\eta_x(\id{x})\in Fx$.
To show that this map has an inverse is to show that every element $a\in Fx$ determines a unique natural transformation $\mu^a$ that satisfies $\mu^a_x(\id{x})=a$.
Let $a\in Fx$.
Take $\mu^a=\{\lambda{f}.\,Ff(a)\}_{z\in\C}$.
Observe that this has the right type: the argument to $\mu^a_z$ is a morphism $f\in\y x=\C(z,x)$, so $Ff:Fx\to Fz$, which means $Ff(a)\in Fz$ and thus $\mu^a:\y x\longrightarrow F$.
Also $\mu^a_x(\id{x})=(F\id{x})(a)=\id{Fx}(a)=a$.
Now we show that $\mu^a$ is natural.
For a morphism $g:u\to v$ in $\C\op$, the naturality condition is
\begin{tikzeqn}
\matrix [matrix of math nodes, row sep=2em, column sep=2em]
{ |(ux)| \C(u,x) & |(vx)| \C(v,x) \\
|(Fu)| Fu & |(Fv)| Fv \\ };
\path[->]
(ux) edge node[above] {$\C(g,x)$} (vx)
(ux) edge node[left] {$\mu^a_u$} (Fu)
(vx) edge node[right] {$\mu^a_v$} (Fv)
(Fu) edge node[below] {$Fg$} (Fv);
\end{tikzeqn}
Let $f\in\C(u,x)$, then
$Fg(\mu^a_u(f))=Fg(Ff(a))=F(f\circ g)(a)=\mu^a_v(f\circ g)=\mu^a_v(\C(g,x)(f))$.
Thus $\mu^a:\y x\To F$.
Finally we show that $\mu^a$ is unique.
Suppose $\mu':\y x\To F$ and $\mu'_x(\id{x})=a$.
Then for any $z\in\C$ and $f\in\C(z,x)$, we have $\mu'_z(\C(f,x)(\id{x}))=Ff(\mu'_x(\id{x}))$ by naturality for $f$ at $\id{x}\in\C(x,x)$.\footnote{We are taking $g=f$, $u=x$, $v=z$, and $f=\id{x}$ in the diagram used to show that $\mu^a$ is natural, to see it as a naturality condition for $\mu'$.
This change, where the $f$ that was considered as an object has become the $g$ and is considered as a morphism, is the key to the lemma, and the reason to use homs.}
But $\mu'_z(f)=\mu'_z(\id{x}\circ f)=\mu'_z(\C(f,x)(\id{x}))=Ff(\mu'_x(\id{x}))=Ff(a)=\mu^a_z(f)$, therefore $\mu'=\mu^a$.
\end{proof}
\begin{definition}
Given a presheaf $F:\C\op\to\Set$ an object $x\in\C$, and an object $a\in Fx$, let $\widetilde{a}$ be the unique natural transformation $\y x\To F$ such that $\widetilde{a}_x(\id{x})=a$.
That is, $\widetilde{a}=\{\lambda{f}.\,Ff(a)\}_{z\in\C}$.
\end{definition}
\begin{samepage}
\begin{theorem}\label{Yoneda embedding}
$\y$ is an embedding
\end{theorem}
\begin{proof}
First, we show it is faithful.
Suppose $\y f=\y g$ for morphisms $f,g:x\to y$ in $\C$.
Since $(\y f)_x(\id{x})=\C(x,f)(\id{x})=f\circ\id{x}=f$, and similarly $(\y g)_x(\id{x})=g$, it follows that $f=g$.
Second, we show it is full.
Let $k:\y x\to\y y$ be a morphism in $\widehat\C$, that is $k:\C(\blank,x)\To\C(\blank,y)$ for some $x,y\in\C$.
Then $k_x(\id{x})\in\C(x,y)$ is a morphism $x\to y$ in $\C$ so we may consider the natural transformation $\y(k_x(\id{x}))$.
As above, we have $(\y(k_x(\id{x})))_x(\id{x})=k_x(\id{x})$, but Theorem~\ref{Yoneda} says $k$ is the only natural transformation with this property, so $k=\y(k_x(\id{x}))$.
\end{proof}
\end{samepage}
\section{Complete, Cocomplete, Closed}
A category is complete if it has all small limits, cocomplete if it has all small colimits, and cartesian closed if has finite products and function spaces.
Products are a kind of limit, so a complete category is closed if it has function spaces.
A limit of a diagram (functor) $D:J\to C$ of shape $J$ in a category $C$ is an object $L\in C$ and a natural transformation $\psi:\K_L\To D$, that is universal.
($\K_L$ is the constant $J\to C$ functor given by $\K_L(x)=L$, $K_L(f)=\id{L}$.)
The data $(L,\psi)$ is called a cone of $D$, with vertex $L$, and it is a limit if it is terminal in the category of cones of $D$, which means every other cone $(L',\phi')$ of $D$ factors through $(L,\phi)$ via a unique morphism $L'\to L$ in $C$.
A limit is small if the shape of the diagram is a small category, that is, if the the collection of morphisms of $J$ is a set (it follows that the collection of objects is also a set, since every object has an identity morphism).
Colimits are dual: the natural transformation goes from $D\To\K_L$, and a cocone is a colimit if it is initial in the category of cocones.
A function space (or exponential object) between two objects $x,y$ in a category $C$ with binary products is an object $\expo{x}{y}$ and a morphism $e:\expo{x}{y}\times x\to y$ in $C$ such that for every morphism $e':z\times x\to y$ there exist a unique morphism $\widetilde{e'}:z\to\expo{x}{y}$ such that $e\circ(\widetilde{e'}\times\id{x})=e'$.
This is a universal property, but not one that can be expressed as a limit.
Two examples of limits are singled out for their importance: small products, and equalisers.
A category with just these limits is in fact complete.
A small product is a limit whose shape is a discrete category, that is, a category where all morphisms are identities.
We write $\prod_{x\in J} Dx$ for the vertex of a product of the objects $Dx$, and reuse the letter $\pi$ for the natural transformation, calling the components $\pi_x$ projections.
Given a collection $\{f_x\}_{x\in J}$ of morphisms from $P$ to the objects $Dx$, we write $\langle f\rangle:P\to\prod_x Dx$ for the unique map given by the universal property.
Dually, we write $\coprod_{x\in J}Dx$ for the vertex of a coproduct, $\iota_x$ for the components, called injections, of the natural transformation, and $[f]$ for the unique map out of a coproduct.
An equaliser is a limit of shape \begin{tikzpicture}[baseline=-0.5ex]\useasboundingbox (-3ex,0) rectangle (3ex,0);\matrix (m) [matrix of math nodes, column sep = 2ex] { \bullet & \bullet \\ }; \path[->]($(m-1-1)+(1ex,0.5ex)$) edge ($(m-1-2)+(-1ex,0.5ex)$) ($(m-1-1)-(-1ex,0.5ex)$) edge ($(m-1-2)-(1ex,0.5ex)$); \end{tikzpicture} (two objects, two morphisms plus identities).
A cone of such a diagram can be represented by a single component, an incoming morphism on the left whose composites with the two parallel arrows are equal, because then the composite (either one) serves as the second required component.
\begin{theorem}\label{products equalisers complete}
A category with small products and equalisers is complete.
Dually, a category with small coproducts and coequalisers is cocomplete.
\end{theorem}
\begin{proof}
Let $C$ be a category with small products and equalisers.
Let $D:J\to C$ be a diagram, where $J$ is small.
Then $S_1=\{j\mid j\in\ob{J}\}$ and $S_2=\{f\mid f \in\mor{J}\}$ are both sets, and therefore can be viewed as small discrete categories by adding (inconsequential) identity morphisms.
Thus we may consider $P_1=\prod_{j\in S_1}Dj$ and $P_2=\prod_{f\in S_2}D(\cod{f})$ because $C$ has small products (and because $\cod:S_2\to S_1$ and therefore $D\circ\cod$ is a functor).
Using the universal property of $P_2$, we can construct two parallel morphisms $\langle\{\pi_{\cod{f}}\}_{f\in S_2}\rangle$ and $\langle\{Df\circ\pi_{\dom{f}}\}_{f\in S_2}\rangle$ in $C$, and then take their equaliser $E$.
This is illustrated for the case when $J$ has three objects and two non-identities in the following diagram in $C$.
\begin{tikzeqn}
\matrix [matrix of math nodes, row sep = 4em, column sep = 3em] {
|(Da)| Da && |(Db)| Db && |(Dc)| Dc\\
|(E)| E & |(P1)| P_1 && |(P2)| P_2 &\\
};
\path [->]
(Da) edge node[above]{$Df$} (Db)
(Dc) edge node[above]{$Dg$} (Db)
($(P1)!3ex!(Da)$) edge node[left]{$\pi_a$} (Da)
($(P1.north)!2ex!(Db)$) edge node[left]{$\pi_b$} (Db)
($(P1.north)!2ex!(Dc)$) edge node[below right]{$\pi_c$} (Dc)
($(P2.west)!3ex!(Db)$) edge[bend left] node[above left=1ex and 2ex]{$\pi_f$} (Db)
($(P2.east)!4ex!(Db)$) edge[bend right] node[above right=0ex and -1ex]{$\pi_g$} (Db)
($(P1.east)+(0,1ex)$) edge node[above] {$\langle\pi_b,\pi_b\rangle$} ($(P2.west)+(0,1ex)$)
($(P1.east)-(0,1ex)$) edge node[below] {$\langle Df\circ\pi_a,Dg\circ\pi_c\rangle$} ($(P2.west)-(0,1ex)$)
(E) edge node[above] {$e$} (P1)
;
\end{tikzeqn}
Here we have $\pi_f\circ\langle\pi_b,\pi_b\circ\rangle=\pi_b=\pi_g\circ\langle\pi_b,\pi_b\rangle$, and $\pi_f\circ\langle Df\circ\pi_a,Dg\circ\pi_c\rangle=Df\circ\pi_a$ and $\pi_g\circ\langle Df\circ\pi_a,Dg\circ\pi_c\rangle=Dg\circ\pi_c$ since the products are cones, and $\langle\pi_b,\pi_b\rangle\circ e =\langle Df\circ\pi_a,Dg\circ\pi_c\rangle\circ e$ since the equaliser is a cone.
Therefore, $Df\circ\pi_a\circ e=\pi_g\circ\langle Df\circ\pi_a,Dg\circ\pi_c\rangle\circ e=\pi_g\circ\langle\pi_b,\pi_b\rangle\circ e=\pi_b\circ e$, for example, which means $\pi_a\circ e$ and $\pi_b\circ e$ as components satisfy the naturality condition for $f$.
In general, the limit of $D$ is given by $(E,\{\pi_j\circ e\}_{j\in J})$, and it is universal because $E$ is universal, and forming a cone is equivalent to equalising the arrows between $P_1$ and $P_2$.
\end{proof}
We note briefly that $\Set$ has (co)products and (co)equalisers: Cartesian products give small products, restriction to a particular subset gives an equaliser, disjoint unions give small coproducts, and quotient by a particular equivalence relation gives a coequaliser.
%more detail?
%\begin{definition}
%For small $\C$, we define two diagrams $\widehat\C\to\Set$ whose limits will be used to define limits in $\widehat\C$.
%Define $D_{\pi}$ by $D_{\pi}(P)=\prod_{c\in\C}P(c)$ on objects\footnote{treating $\ob\C$ as a discrete category} and $D_{\pi}(\eta)=\langle\{\eta_c\circ\pi_c\}_{c\in\C}\rangle$ on morphisms.
%Define $D_{\iota}$ by $D_{\iota}(P)=\coprod_{c\in\C}P(c)$ on objects and $D_{\iota}(\eta)=[\{\iota_c\circ\eta_c\}_{c\in\C}]$ on morphisms.
%That these are functors follows from the universal properties of products and coproducts (in $\Set$).
%\end{definition}
\newcommand{\prpr}[1]{\ensuremath{\Pi_{#1}}}
\newcommand{\coprpr}[1]{\ensuremath{\amalg_{#1}}}
\begin{definition}
Let $D=\{P_j\}_{j\in J}$ be a family of presheaves indexed by a set $J$.
The \emph{product presheaf} $\prpr{D}$ is given by $\prpr{D}(c)=\prod_{j\in J}P_j(c)$ and $\prpr{D}(f)=\langle\{P_j(f)\circ\pi_j\}_{j\in J}\rangle$.
The requirements of this as a functor, namely $\langle\{\pi_j\}_{j\in J}\rangle=\id{\prpr{D}(c)}$ and $\langle\{P_j(f)\circ P_j(g)\circ\pi_j\}_{j\in J}\rangle=\langle\{P_j(f)\circ\pi_j\}_{j\in J}\rangle\circ\langle\{P_j(g)\circ\pi_j\}_{j\in J}\rangle$, are instances of properties of products in general.
Similarly, the \emph{coproduct presheaf} $\coprpr{D}$ is given by $\coprpr{D}(c)=\coprod_{j\in J}P_j(c)$ and $\coprpr{D}(f)=[\iota_j\circ P_j(f)\}_{j\in J}]$.
\end{definition}
\begin{theorem}\label{presheaf bicomplete}
If $\C$ is small, then $\widehat\C$ is complete and cocomplete.
\end{theorem}
\begin{proof}
In light of Theorem~\ref{products equalisers complete}, it suffices to show that $\widehat\C$ has small products, equalisers, small coproducts, and coequalisers.
Let $D:J\to\widehat\C$ be a diagram where $J$ is small and discrete, so we can view $D$ as a set-indexed family of presheaves.
Then $(\prpr{D},\{\{\pi_j\}_{c\in\C}\}_{j\in J})$ is a limit of $D$.
Similarly $(\coprpr{D},\{\{\iota_j\}_{c\in\C}\}_{j\in J})$ is a colimit of $D$.
Now consider two parallel morphisms, $\eta_1,\eta_2:P\To Q$, in $\widehat\C$.
\end{proof}
\begin{theorem}
$\widehat\C$ is closed.
\end{theorem}
\begin{proof}
\end{proof}
\begin{theorem}\label{Yoneda bicontinuous}
$\y$ preserves limits, function spaces, and colimits.
\end{theorem}
\begin{proof}
\end{proof}
\section{Presheaves are Colimits of Representables}
A functor in $\widehat\C$ is representable if it is isomorphic to some hom functor $\y c$.
Therefore a diagram $D:J\to\widehat\C$ is a diagram of representable presheaves (representables) if for all $x\in J$, we have $Dx\cong\y c$ for some $c\in C$.
We will show in this section that every presheaf arises as the colimit of some diagram of representables, which means the representables in some sense ``generate'' the category $\widehat\C$.
In fact, in the next section, we use this idea to show that $\widehat\C$ is the free cocompletion of $\C$.
What is the diagram of which a given presheaf $P$ is a colimit?
It is the Yoneda embedding restricted to the subcategory of objects whose hom functors have morphisms into $P$.
We define the machinery to construct this subcategory below.
\begin{definition}
Given functors $T:X\to C$ and $S:Y\to C$, the \emph{comma category}, denoted $\comma{T}{S}$, is given by:
\begin{itemize}
\item
Objects are triples $(x,y,\eta)$ with two objects $x\in X$ and $y\in Y$ and a morphism $\eta:Ta\to Sb$.
\item
Morphisms are pairs $(g,h):(x,y,\eta)\to(x',y',\eta')$ of morphisms $g:x\to x'$ and $h:y\to y'$ such that $\eta'\circ Tg=Sh\circ\eta$.
\end{itemize}
The identity on $(x,y,\eta)$ is $(\id{x},\id{y})$, and composition is given by $(g,h)\circ(g',h')=(g\circ g',h\circ h')$.
(This is a category because $\eta\circ T(\id{x})=\eta=S(\id{y})\circ\eta$, and $((g,h)\circ(g',h'))\circ(g'',h'')=(g\circ g'\circ g'',h\circ h'\circ h'')=(g,h)\circ((g',h')\circ(g'',h''))$.)
As a special case, when $Y=\bullet$, we obtain a generalized \emph{slice category}, denoted $\slice{T}{P}$ where $P=S(\bullet)$ is the chosen object in $C$.
Since there is only one object in $Y$, we may simplify objects in $\slice{T}{P}$ as pairs $(x,\eta)$, and morphisms $g:(x,\eta)\to(x',\eta')$ as morphisms $g:x\to x'$ such that
\begin{tikzeqn}
\matrix[matrix of math nodes,row sep=1.5em,column sep=1em]{
|(Ta)| Tx && |(Ta')| Tx'\\
& |(x)| P &\\};
\path[->] (Ta) edge node[left]{$\eta$} (x) (Ta') edge node[right]{$\eta'$} (x) (Ta) edge node[above]{$Tg$} (Ta');
\end{tikzeqn}
\end{definition}
\begin{definition}
Given a presheaf $P\in\widehat\C$, the \emph{representability diagram}, denoted $\Delta_P:\slice{\y}{P}\to\widehat\C$, is given by $\Delta_P(x,\eta)=\y x$ on objects and $\Delta_P(g)=\y g$.
This is a functor because $\y$ is, and because slice category identities and composites are pointwise.
\end{definition}
\begin{theorem}
For all presheaves $P\in\widehat\C$, there exists a diagram $D:J\to\widehat\C$ of representables such that $P$ is a (vertex of a) colimit of $D$.
\end{theorem}
\begin{proof}
Let $P\in\widehat{C}$.
Take $D=\Delta_P$, which is a diagram of representables by definition.
To give a cocone with vertex $P$ is to give a natural transformation $\psi:\Delta_P\To\K_P$.
Take $\psi=\{\eta\}_{(x,\eta)\in\slice{\y}{P}}$.
Then the naturality conditions for $\psi$ match the conditions on morphisms in the slice category, so $\psi$ is natural.
It remains to show that this cocone is initial.
Let $(Q,\varphi)$ be a cone of $\Delta_P$.
We must find a unique factorisation $h:(P,\psi)\to(Q,\varphi)$; in other words, the following diagram, showing a sketch of $\Delta_P$ and the two cones, must commute (in $\widehat\C$) for a unique $h$:
\begin{tikzeqn}
\matrix [matrix of math nodes,row sep=3em,column sep=3em] {
|(y0)| \y x & |(y1)| \y x'& |(y2)| \y x'' & |(d)| \dots & |(y3)| \y x''' \\
&&|(P)| P&&\\
&&|(Q)| Q&&\\
};
\path[->]
(y0) edge node[left=1em]{$\eta$} (P)
(y1) edge node[left]{$\eta'$} (P)
(y2) edge node[right]{$\eta''$} (P)
(d) edge (P)
(y3) edge node[right=1em]{$\eta'''$} (P)
(y0) edge[bend right] node[left]{$\varphi_{(x,\eta)}$} (Q)
(y1) edge[bend right] node[left]{$\varphi_{(x',\eta')}$} (Q)
(d) edge[bend left] (Q)
(y3) edge[bend left] node[right]{$\varphi_{(x''',\eta''')}$} (Q)
(P) edge[dashed] node[right]{$h$} (Q)
(y0) edge node[above]{$\y g$}(y1)
($(y1.east)+(0,0.5ex)$) edge node[above]{$\y g'$} ($(y2.west)+(0,0.5ex)$)
($(y2.west)-(0,0.5ex)$) edge ($(y1.east)-(0,0.5ex)$)
(d) edge node[above] {$\y g'''$} (y2)
($(d.east)+(0,0.5ex)$) edge node[above] {$\y g''''$} ($(y3.west)+(0,0.5ex)$)
($(d.east)-(0,0.5ex)$) edge ($(y3.west)-(0,0.5ex)$)
;
\end{tikzeqn}
Take $h=\{\lambda{a}.\,(\varphi_{(x,\widetilde{a})})_x(\id{x})\}_{x\in\C}$.
To check this is a morphism of cones from $(P,\psi)$ to $(Q,\varphi)$ is to check that it is a natural transformation $P\To Q$, and that it makes all triangles above involving $h$ commute (the other triangles commute because the components of both cones are morphisms in $\widehat\C$ and therefore natural).
First, observe that if $a\in Px$, then $\widetilde{a}:\y x\To P$ by definition, so $(x,\widetilde{a})$ is an object in the slice category.
Therefore $\varphi_{(x,\widetilde{a})}:\y x\To Q$, so $h_x(a)\in Qx$, thus $h:P\longrightarrow Q$.
Naturality of $h$ follows from naturality of $\varphi_{(x,\widetilde{a})}$.
%For naturality of $h$, observe that if $f:y\to x$ in $\C\op$ then we have $Qf((\varphi_{(x,\widetilde{a})})_x(\id{x})=(\varphi_{(x,\widetilde{a})})_y((\y x)(f)(\id{x}))$
Now look at $(h\circ\eta)_x(\id{x})$ for some $(x,\eta)\in\slice{\y}{P}$.
We have $(h\circ\eta)_x(\id{x})=h_x(\eta_x(\id{x}))=\varphi_{(x,\widetilde{\eta_x(\id{x})})}(\id{x})=\varphi_{(x,\eta)}(\id{x})$, since $\eta=\widetilde{\eta_x(\id{x})}$ by definition, therefore, by Theorem~\ref{Yoneda}, $h\circ\eta=\varphi_{(x,\eta)}$.
Thus the triangles above commute.
Finally, $h$ is unique because for each $(x,\eta)\in\slice{\y}{P}$, both $\eta$ and $\varphi_{(x,\eta)}$ are determined by their action at component $x$ on $\id{x}$.
If a natural transformation $P\To Q$ is to make the diagram commute, its component at $x$ must send $\eta_x(\id{x})$ to the same place $\varphi_{(x,\eta)}$ sends $\id{x}$.
That is what $h$ does.
\end{proof}
\section{The Presheaf Category is the Free Cocomplete Category}
A free construction gives an object some additional structure without making any unnecessary commitments.
We can state this precisely in category theory by saying that any other object with the additional structure must factor through the free construction.
Let us look at free cocompletions, where the additional structure is the existence of small colimits.
A free cocompletition of $C$, is a cocomplete category $\overline{C}$ and a cocontinuous embedding $C\overset{Y}\hookrightarrow\overline{C}$, such that for any cocomplete category and cocontinuous embedding $C\overset{F}\hookrightarrow D$ there is a unique-up-to-isomorphism cocontinuous functor $\overline{F}:\overline{C}\to D$ such that $F=\overline{F}\circ Y$.
\begin{theorem}
If $\C$ is small, then $\C\overset\y\hookrightarrow\widehat\C$ is a free cocompletion.
\end{theorem}
\begin{proof}
By Theorems \ref{presheaf bicomplete} and \ref{Yoneda bicontinuous}, we know that $\widehat\C$ is cocomplete and that $\y$ is cocontinuous (since small categories are also locally small).
It remains to show that this embedding is universal.
Let $\C\overset{F}\hookrightarrow D$ be a cocontinuous embedding into a cocomplete category.
For each $P\in\widehat\C$, we have a diagram $\slice{\y}{P}\overset{U_P}\to\C\overset{F}\hookrightarrow{D}$, where $U_P$ is the forgetful functor: $(x,\eta)\mapsto x$, $g\mapsto g$.
The collection of objects of $\slice{\y}{P}$ is $\{(x,\eta)\mid\eta:\y x\To P\}$; Theorem~\ref{Yoneda} says this is $\bigcup_{x\in\C}\{(x,\widetilde{a})\mid{a\in Px}\}$.
Since $\C$ is small, the union is over a set, so $\slice{\y}{P}$ is small.
Since $D$ is cocomplete, $F\circ U_P$ has a colimit.
Let $(L_P,\psi_P)=\colim(F\circ U_P)$ for each $P\in\widehat\C$.
For each $\mu:P\To Q$ in $\widehat\C$, there is a cocone of $F\circ U_P$ given by $(L_Q,\{(\psi_Q)_{(x,\mu\circ\eta)}\}_{(x,\eta)\in\slice{\y}{P}})$.
To see that this is a cocone, observe that $(x,\mu\circ\eta)\in\slice{\y}{Q}$, because $\y x\overset\eta\To P\overset\mu\To Q$, and $\psi_Q:(F\circ U_Q)\To(\K_{L_Q}:\slice{\y}{Q}\to D)$, so $(\psi_Q)_{(x,\mu\circ\eta)}:Fx\to L_Q$, and the collection is natural because $\psi_Q$ is natural.
%for each morphism $g:(x,\eta)\to(x',\eta')$ in $\slice{\y}{P}$, we have $(\psi_Q)_{(x',\mu\circ\eta')}\circ Fg=?$
Since $L_P$ is the vertex of a colimit, there is a unique map $\dot\mu:L_P\to L_Q$ in $D$ factorising $(L_Q,\psi_Q)$.
Take $\overline{F}$ to be the functor defined by $\overline{F}(P)=L_P$ and $\overline{F}(\mu)=\dot\mu$.
This is a functor because post-composition always factorises a cocone, so if $P\overset\mu\To Q\overset{\mu'}\To R$, then $\dot\mu'\circ\dot\mu$ factorises $(L_R,\psi_R)$ through $(L_P,\psi_P)$, but $\dot{(\mu'\circ\mu)}$ is the unique map that does so, so they must be equal.
It remains to show that $\overline{F}$ factorises $F$ through $\y$, is cocontinuous, and is unique up to isomorphism.
To see that $\overline{F}\circ\y=F$, it suffices to show that for each $x\in\C$ the diagram $U_{\y x}$ has a colimit in $\C$ with vertex $x$, because $\overline{F}\circ\y$ is defined using colimits of the form $\slice{\y}{\y x}\overset{U_{\y x}}\to\C\overset{F}\hookrightarrow D$ but $F$ preserves colimits in $\C$ .
\end{proof}
\end{document}